What’s taking so long, Mr. Babbage? | Hacker News Reader

What’s taking so long, Mr. Babbage?

scottaaronson.com

41 pointsbdr12 comments

"Quantum computers are not known to be able to solve NP-complete problems in polynomial time."

I don't get the blog's subtitle. Why would anyone suppose that quantum computers could solve NPC problems in polynomial time if non-quantum computers can't? The P and NP complexity classes don't have anything to do with the hardware used to perform computation. Quantum computing isn't some new model of computation, i.e. it's equivalent to Turing machines or the lambda calculus.

If you work in quantum computing -- which I did, full time for 13 years, and part time for a few years prior to that -- it's VERY common to run into people outside the field who believe that quantum computers can solve NP-complete problems in polynomial time. Dozens of wrong papers have been written claiming just that, and the claim also appears frequently (often implicitly) in popular journalism. The blog's subtitle is just acknowledgment of that fact.

Incidentally, P and NP certainly do have to do with the hardware. There are nonlinear variants on quantum mechanics in which all the problems in NP can be solved in polynomial time. See http://arxiv.org/abs/quant-ph/9801041 These variants are, however, unlikely to describe the way the world works.

There is a myth that quantum computers are known to be able to solve NP-complete problems in polynomial time by trying all possibilities at once using quantum superposition. For example, by simultaneously trying all possible variable assignments in a SAT problem.

In general, you're confusing decidability and running-time. Just because two models of computing are Turing equivalent (are capable of deciding the same problems) does not mean that they have the same running time on those problems.

I didn't intend to imply decidability at all. I just meant that since a quantum computer is equivalent to a Turing machine, and complexity classes are often (and I think were originally) formally described and proven in terms of Turing machines.

Maybe decidability was the wrong word to use.

There are two separate questions: 1) Can model of computation X recognize language Y? 2) How fast can it do so?

When someone says quantum computers are "equivalent" to Turing machines, that's referring only to question 1. In other words, any given language can be recognized by a quantum computer if and only if it can be recognized by a Turing machine.

Just because they are equivalent in this sense doesn't imply anything about question 2. For a concrete example, see http://en.wikipedia.org/wiki/Shors_algorithm -- if factorization takes polynomial time on a quantum computer but exponential time on a Turing machine, it must be reasonable to ask whether quantum computers can be that much faster for a whole class of problems.

Edit: also note that a complexity class is just a set of languages. We can talk about those languages in different contexts, even if they are specified in terms of a particular model of computation.

I think the article is trying to equate quantum computers with non-deterministic Turing Machines - which still looks like a matter for debate.

As for P & NP - aren't they defined in terms of decision problems that can be solved in polynomial time by deterministic and non-deterministic TMs respectively? Which is a distinction that is about as close to "the hardware used to perform computations" as it is possible to get while working with abstractions.

You're right. P and NP are formally defined specifically to Turing machines, but the Church-Turing thesis says that all models of general computation are equivalent. If quantum computers can solve any (which means all) NPC problems in polynomial time, then they're something entirely separate from all the models of general computation we currently know of. I can't even fathom what that even means. Wikipedia mentions some "non-Turing models" of computing, but most seem to be either jokes or highly theoretical: http://en.wikipedia.org/wiki/Zeno_machine http://en.wikipedia.org/wiki/Hypercomputation

When talking about complexity you usually have to drop the "turing machine as a metaphor for everything" idea very fast. In complexity theory you're interested in how fast will some different variations of computing machines (that might not be turing-complete or might by more than turing complete) be at solving some problems. Conversely, if you assume a model of computing (for example, AC0 is the model you get if your computing machine is restricted to be a circuit of constant depth plus a polynomial number of AND and OR gates; the L^HALTING model is what you get if you augment a finite-state automaton with an oracle that can tell it whether or not a given program halts). The model P is the set of problems that you can solve with a traditional turing machine with only a polynomial number of steps. It is also the set of problems that you can specify with first-order-logic formulas plus a least-fixed-point operator. NP is the set of problems solvable by a nondeterministic turing machine in polynomial time, but it also is the set of problems that a deterministic turing machine can verify a solution of in polynomial time, the class of problems for which there exists a probabilistic proof checker that can verify a solution to it with as high a probability as you want by checking only a constant number of bits from a properly-formatted proof. I could go on.

But what I'm getting at is that quantum computing today is basically trying to solve the question of where would you place the BQP (bounded-error quantum probabilistic algorithms) complexity class in the complexity zoo. If it is found equivalent to NP (that is, if a quantum computer can solve any NP problem with as high a probability as you want in polynomial time) that's what it means. There is nothing known so far that makes this a priori impossible. What there is is an exponential speedup for some problems (ie, problems that are not known to be in BPP, which is the deterministic equivalent of BQP for turing machines, are known to be in BQP), no NP-complete problem is in BQP and it does not seem possible for a quantum cmputer to solve an NP-complete problem. On the other hand, if you can prove that BQP is better than BPP but worse than NP you've just proven that P is not NP.

>Quantum computing isn't some new model of computation, i.e. it's equivalent to Turing machines or the lambda calculus.

This isn't immediately obvious to someone who hears about quantum computing but doesn't actually get a proper explanation. The intuition that n qubits in superposition can evaluate a number of possibilities exponential in n simultaneously is understandable, even if it's not really correct.

But some problems, such as factorization, are known to be solvable on quantum computer in polynomial time, and there is no known program that solves that on det. Turing machine.

I agree that there is no reason to believe that quantum computers will solve NPC problems.

[edit] On det. Turing machine, in polynomial time...

I'm not familiar with this quantum algorithm for factorization, or the "standard" factorization algorithm. Are we talking about integer factorization? It doesn't seem obvious to me how factorization would even be phrased as a decision problem. I know that primality testing is known to be in P.

I don't know if any of this comment even makes since, considering I believe the complexity classes P and NP are formally defined in terms of Turing machines anyway. Any NPC problem along with some polynomial computation can be used to solve any other NPC problem. I don't think quantum computers aren't going to reveal a polynomial-time algorithm for a known NPC problem.

If someone refers to the "standard" algorithm for factoring on quantum computers, they're talking about Shor's algorithm.

http://en.wikipedia.org/wiki/Shors_algorithm

(Also, remember that factoring is not (known to be) NP-complete.)

Reply on news.ycombinator.com