18
$\begingroup$

If you have an infinite memory infinite processor number classical computer, and you can fork arbitrarily many threads to solve a problem, you have what is called a "nondeterministic" machine. This name is misleading, since it isn't probabilistic or quantum, but rather parallel, but it is unfortunately standard in complexity theory circles. I prefer to call it "parallel", which is more standard usage.

Anyway, can a parallel computer simulate a quantum computer? I thought the answer is yes, since you can fork out as many processes as you need to simulate the different branches, but this is not a proof, because you might recohere the branches to solve a PSPACE problem that is not parallel solvable.

Is there a problem strictly in PSPACE, not in NP, which is in BQP? Can a quantum computer solve a problem which cannot be solved by a parallel machine?

Jargon gloss

  1. BQP: (Bounded error Quantum Polynomial-time) the class of problems solvable by a quantum computer in a number of steps polynomial in the input length.
  2. NP: (Nondeterministic Polynomial-time) the class of problems solvable by a potentially infinitely parallel ("nondeterministic") machine in polynomial time
  3. P: (Polynomial-time) the class of problems solvable by a single processor computer in polynomial time
  4. PSPACE: The class of problems which can be solved using a polynomial amount of memory, but unlimited running time.
Improve this question
$\endgroup$
29
  • 2
    $\begingroup$ @Yrogirg: Ron Maimon's statement that a quantum computer is probably couldn't not simulate an infinite memory, ininite processor computer is not only correct, it is an enormous understatement. Though Ron disagrees with me on this point, it is generally accepted in the domain of quantum information theory that quantum states don't contain even exponentially more information than classical-states. $\endgroup$
    – Niel de Beaudrap
    Commented Aug 21, 2012 at 0:22
  • 1
    $\begingroup$ For others: Niel is misleading and wrong about the quantum state not "having" exponential information. What he notices is that you can't encode and extract more than the classical amount of information in a quantum state, but that's not saying anything--- the representation of a quantum state at intermediate times is not by the amount of information you can get out of it through some measurement. This is the terminology difference, and it is essential: he means "what can you get out", and I mean "what do you need to say to simulate it". $\endgroup$
    – Ron Maimon
    Commented Aug 21, 2012 at 2:33
  • 2
    $\begingroup$ @RonMaimon: This is comical. You're basically playing the role of Richard Feynman, inasmuch that he apparently couldn't be convinced that P vs NP was an open problem; only with you it's P vs BQP. I'm only saying that it hasn't been proven either way yet. That isn't to say that I believe that we can factorize with coin flips; quite the opposite, I do think that superpolynomial time is probably necessary to simulate quantum computers. But much of what is exponential in quantum states is also exponential in probability distributions, and we have no solid proofs. Does this bother you? $\endgroup$
    – Niel de Beaudrap
    Commented Aug 21, 2012 at 12:25
  • 1
    $\begingroup$ @RonMaimon: I edited it because it's polemical. There is nothing misleading in calling it "nondeterministic": a computation with unboundedly many processors is only one way to describe the model, and is no more physical than one making guesses nondeterministically. You are deliberately discouraging people from acquiring the tools people would require to assess complexity literature on their own by reverting my edit which provided explanations and links to the existing concepts. If you think complexity is in the dark ages, whatever is motivating you to care about NP, anyway? $\endgroup$
    – Niel de Beaudrap
    Commented Aug 23, 2012 at 9:48
  • 4
    $\begingroup$ @RonMaimon: A "nondeterministic" machine in the CS sense is one in which there is one processor, but no specification of which of the permitted transitions it may explore, not even probabilistically; it is simply not determined, hence the name. It's non-physical, but then that concept was defined by logicians who didn't put a priority on realism of physical evolution. If you prefer a different idiom, that's fine. But that doesn't make the standard terminology "non-standard". As for our competence or obfuscation: once you've managed to surpass the state of the art, do please let us know. $\endgroup$
    – Niel de Beaudrap
    Commented Sep 11, 2012 at 18:00

3 Answers 3

Reset to default
22
$\begingroup$

This has been a major open problem in quantum complexity theory for 20 years. Here's what we know:

(1) Suppose you insist on talking about decision problems only ("total" ones, which have to be defined for every input), as people traditionally do when defining complexity classes like P, NP, and BQP. Then we have proven separations between BQP and NP in the "black-box model" (i.e., the model where both the BQP machine and the NP machine get access to an oracle), as mmc alluded to. On the other hand, while it's very plausible that those would extend to oracle separations between BQP and PH (the entire polynomial hierarchy), right now, we don't even know how to prove an oracle separation between BQP and AM (a probabilistic generalization of NP slightly higher than MA). Roughly the best we can do is to separate BQP from MA.

And to reiterate, all of these separations are in the black-box model only. It remains completely unclear, even at a conjectural level, whether or not these translate into separations in the "real" world (i.e., the world without oracles). We don't have any clear examples analogous to factoring, of real decision problems in BQP that are plausibly not in NP. After years thinking about the problem, I still don't have a strong intuition either that BQP should be contained in NP in the "real" world or that it shouldn't be.

(Note added: If you allow "promise problems," computer scientists' term for problems whose answers can be undefined for some inputs, then I'd guess that there probably is indeed a separation between PromiseBQP and PromiseNP. But my example that I'd guess witnesses the separation is just the tautological one! I.e., "given as input a quantum circuit, does this circuit output YES with at least 90% probability or with at most 10% probability, promised that one of those is the case?")

For more, check out my paper BQP and the Polynomial Hierarchy.

(2) On the other hand, if you're willing to generalize your notion of a "computational problem" beyond just decision problems -- for example, to problems of sampling from a specified probability distribution -- then the situation becomes much clearer. First, as Niel de Beaudrap said, Alex Arkhipov and I (and independently, Bremner, Jozsa, and Shepherd) showed there are sampling problems in BQP (OK, technically, "SampBQP") that can't be in NP, or indeed anywhere in the polynomial hierarchy, without the hierarchy collapsing. Second, in my BQP vs. PH paper linked to above, I proved unconditionally that relative to a random oracle, there are sampling and search problems in BQP that aren't anywhere in PH, let alone in NP. And unlike the "weird, special" oracles needed for the separations in point (1), random oracles can be "physically instantiated" -- for example, using any old cryptographic pseudorandom function -- in which case these separations would very plausibly carry over to the "real," non-oracle world.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "We don't have any clear examples analogous to factoring, of real decision problems in BQP that are plausibly not in NP", I accepted mmc's answer because I thought "recursive Fourier sampling" is an example of this. Regarding oracles and the real world, NP oracles are not uncomputable, they are just slow to compute, so you can realize them in real world. $\endgroup$
    – Ron Maimon
    Commented Aug 21, 2012 at 15:53
  • 2
    $\begingroup$ Recursive Fourier Sampling is an oracle problem; we don't know how to realize it in the non-oracle setting. (Also, it only gives an n vs. n^(log n) separation; if you want an n vs. exp(n) oracle separation check out my BQP vs. PH paper.) And yes, most of the oracles we talk about are computable, but if they're exponentially slow, then simulating them might negate the complexity separation that was our original goal. $\endgroup$
    – Scott Aaronson
    Commented Aug 21, 2012 at 15:59
14
$\begingroup$

There is no definitive answer due to the fact that no problem is known to be inside PSPACE and outside P. But recursive Fourier sampling is conjectured to be outside MA (the probabilistic generalization of NP) and has an efficient quantum algorithm. Check page 3 of this survey by Vazirani for more details.

Improve this answer
$\endgroup$
13
$\begingroup$

To add to mmc's response, it is currently generally suspected that NP and BQP are incomparable: that is, that neither is contained in the other. As usual for complexity theory, the evidence is circumstantial; and the suspicion here is orders of magnitude less intense (if we pretend that strength of suspicion is measurable) than the general hypothesis that P ≠ NP.

Specifically: as Aaronson and Archipov showed somewhat recently, there are problems in BQP which, if they were contained in NP, would imply that the polynomial hierarchy collaspes to the third level. Restricting myself to conveying the significance of this complexity theorist jargon, any time they talk about the "polynomial hierarchy collapsing" to any level, they mean something which they would regard as (a) quite implausible, and consequently (b) disasterous to their understanding of complexity on the level of the transition from Newtonian mechanics to quantum mechanics, i.e. a revolution of comprehension to be informally anticipated perhaps no more frequently than once every century or so. (The ultimate crisis, a total "collapse" of this "hierarchy", to the zeroeth level, would be precisely the result P = NP.)

Improve this answer
$\endgroup$
28
  • $\begingroup$ +1: The paper you link is great, thanks. BTW: saying how implausible people find something isn't evidence without an argument: one should just make up a simple nonrigorous argument to explain why stuff is hard. It's easy for NP and factoring, but for the higher levels of the polynomial hierarchy, I never tried. $\endgroup$
    – Ron Maimon
    Commented Aug 21, 2012 at 2:30
  • 2
    $\begingroup$ Ron, if you do try, I predict you'll be able to find a "simple nonrigorous argument" by which to convince yourself that the polynomial hierarchy should indeed be infinite! (To calibrate, I'm much more confident of that than I am that factoring is classically hard.) Just take whatever intuition you've already used to convince yourself that P!=NP, and try extending it to convince yourself that NP!=coNP. Then try convincing yourself that P^NP != NP^NP. Then conclude, by "physicist induction", that ALL these classes should be distinct! :-) $\endgroup$
    – Scott Aaronson
    Commented Aug 21, 2012 at 8:46
  • $\begingroup$ @RonMaimon: I agree with you on the implausibility front. I prefer actual proofs, personally. Of course, the proofs (if they exist) are nevertheless expected to be difficult to find, because no-one's succeeded yet. I'm really just representing the sociopolitical import of those claims. $\endgroup$
    – Niel de Beaudrap
    Commented Aug 21, 2012 at 12:30
  • 1
    $\begingroup$ Ron, I don't quite understand your argument for why factoring should be hard, but it seems like it can't possibly work. For how does your argument deal with the existence of algorithms like the Number Field Sieve, which classically factors an n-bit integer using ~exp(n^{1/3}) steps, still exponential but much much faster than a "full search"? Note that, like any algorithm, the Number Field Sieve can be implemented reversibly with only a constant-factor slowdown. $\endgroup$
    – Scott Aaronson
    Commented Aug 21, 2012 at 17:35
  • 2
    $\begingroup$ This sounds either way too good to be true -- like your "method of counting waste bits" will revolutionize theoretical computer science, by giving us at least heuristic answers to all the great unsolved problems -- or else like you simply have some way to map the best known conventional algorithms into this framework. So yes, details please! (Since it's a bit off-topic, go ahead and post them somewhere else, or email me and Niel.) $\endgroup$
    – Scott Aaronson
    Commented Aug 21, 2012 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.