Can a parallel computer simulate a quantum computer? Is BQP inside NP?

Question

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.

Comments

@Yrogirg: Oh, I see--- that isn't true, because you need to initialize the processor state, to tell each of the processors what to do. You can simulate arbitrarily many processors on a single one, at a cost of memory and slowdown. If these processors don't share memory, and if they all the processes are branched by a fork instruction as in unix, you get a "nondeterministic" machine, and it is an open problem if it is even faster than a regular single processor machine asymptotically (although it is obviously true). This is P!=NP.

---

@RonMaimon: would you consider infinite energy to be unphysical? If not, why not the energy required for infinite parallelism? What if we took all of that energy and put it into a single processor to make it compute infinitely quickly (as in a 'Zeno' processor), to actually obtain answers to the halting problem? To me, these questions of infinity (or exponentials) are not identical, but they are certainly equivalent in that they are resources which we could never hope use to obtain locally an answer to a difficult computational problem. So they are all unphysical as far as I'm concerned.

This post imported from StackExchange Physics at 2014-07-24 15:39 (UCT), posted by SE-user Niel de Beaudrap

---

@NieldeBeaudrap: Ok, ok, we agree on this, it's just a question of "potential infinity" and how you explain things. I don't like explaining things that are simple so that they sound mysterious--- this is obscurantism--- and if a student asks you "what is a nondeterministic machine?" You can say "A machine with so many processors that UNIX's 'fork' instruction is cost free, no matter how many times you use it."

By the way, this does lead to a simple thing I don't see anywhere in the literature--- if you allow the machines to keep a label identifying the other processes, and trade their results with other machines, compare notes as they are running, I think you get a bigger class intermediate between NP and PSPACE. Let me call this hypothetical class "SHM-P" (for unix shm--- shared memory). This is the natural polynomial thing that strictly includes BQP and that isn't PSPACE (at least not obviously).

---

@RonMaimon: we're converging on an approximate agreement; though your characterization of a nondeterministic machine would be like me describing an electron as a tiny hard ball of electrical charge which spins on its axis, but which is so sensitive to magnetized measurement devices that it jitters and swings to align with or against any large magnetic field it encounters -- it's a coarse description which misses much. As for labelled processes: the problem is to define how the "processors" would exchange results in a way which agrees with tensor product structure / accounts for entanglement.

This post imported from StackExchange Physics at 2014-07-24 15:39 (UCT), posted by SE-user Niel de Beaudrap

---

@NieldeBeaudrap: We are not converging on anything! I have not changed my mind in any way in this discussion--- you are wrong to say my characterization is false stop it, it is not a coarse description, it's the friggin definition! It's a fine characterization of what a "nondeterministic machine" is. NP is a trivial, obvious concept. You are wrong about entanglement--- you can simulate exact BQP in SHM-P, it is easy to do iterated matrix multiplication on this machine. You asked for something which surpasses the state of the art, SHM-P is it.

---

@NieldeBeaudrap: Parallel machines do exist, calling them "imaginary" is silly. You can do a non-slowing-down fork instruction on a machine with multiple processors, people do it all the time now, and you can imagine a machine with a large number of independent processors. This is what a nondeterministic machine is, and the tripe about it being "unphysical" or "mysterious" is annoying. I didn't say the people working in this field are incompetent, I said they are obscurantists. There's a huge difference. Logicians are competent obscurantists for example.

---

@Ron: there do not exist any computers which can potentially double the number of processors working on a problem at any point in time. If you're satisfied with solving problems like SAT on 30 bits, then yes, a server farm of a just over a billion networked simple processors suffices, and initialising them won't take too long with a network topology in 3+1D. But it simply doesn't scale; the structure of spacetime itself works against getting the needed resources. If you make do with a fixed # of processors, you then can no longer complete in poly-time, unless e.g. P = NP.

This post imported from StackExchange Physics at 2014-07-24 15:39 (UCT), posted by SE-user Niel de Beaudrap

Answer 1

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.

This post imported from StackExchange Physics at 2014-07-24 15:40 (UCT), posted by SE-user Scott Aaronson

Comments

"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.

---

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.

This post imported from StackExchange Physics at 2014-07-24 15:40 (UCT), posted by SE-user Scott Aaronson

Answer 2

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.

This post imported from StackExchange Physics at 2014-07-24 15:39 (UCT), posted by SE-user mmc

Answer 3

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.)

This post imported from StackExchange Physics at 2014-07-24 15:39 (UCT), posted by SE-user Niel de Beaudrap

Comments

(In a similar vein, I find HEP papers full of mind-numbing brain-destroying jargon and impenetrable handwaving! Must not be too much worth understanding there...)

This post imported from StackExchange Physics at 2014-07-24 15:39 (UCT), posted by SE-user Scott Aaronson

---

@ScottAaronson: I don't know these, thank you for pointing them out! I am happy to learn, and I hope that the ideas are good. The analogy with HEP is not really right, the physicists generally bend over backwards to eliminate unnecessary jargon, and speak as much as possible in homey metaphors. There is a political cabal in physics that will smack you if you don't say things as clearly as you possibly can, it's very nice, and I wish other fields had it.

---

Let me see if I understand your idea: first you fix a "universal" reversible circuit C? (Otherwise, how do you know which reversible computation to run backwards, once you've guessed the final values of the waste bits?) Then given (say) a composite integer N and its prime factors p,q, you search for a final value b of the waste bits, such that C^{-1}(p,q,b)=(N,a) for some other string a (which you can think of as the "instructions" to C)? Of course, even after you've found such an a, there's no guarantee it will work for some other composite integer N'.

This post imported from StackExchange Physics at 2014-07-24 15:39 (UCT), posted by SE-user Scott Aaronson

---

It's amazing how strongly people's perception of "jargon-ness" can just reflect their background. I'd heard about how important AdS/CFT was, so I went through the papers on it, hoping to learn the new conceptual insights about spacetime in quantum gravity ... and instead found technical constructions involving stacks of D3-branes. Which CS theory papers are you reading? Whichever they are, I can probably point you to better ones. In the proceedings of the major CS theory conferences (STOC, FOCS, CCC, ...), the first few pages of every paper are just history, motivation, high-level ideas...

This post imported from StackExchange Physics at 2014-07-24 15:39 (UCT), posted by SE-user Scott Aaronson

---

@ScottAaronson: Not exactly--- you start with a reversible computer, and input (I,p,q,0) where 0 is a string of zeroed out bits, I are the instructions for multiply (which you don't touch) and p and q are the inputs. Then you runs it forward, and you get (I,pq,J) where J is junk. You now ignore J and you get the output of the regular machine: (I,pq). If you just add bits to the answer, you reverse the computation to get (I,p',q',J'). If you guessed right J' is 0, as you initialized the machine originally. If you make the least wasteful algorithm (perhaps on copies) I felt you need to search J.

Regarding jargon and physics, the jargon-free holography insights are better found in 'tHooft's papers in Nuclear Physics B in the period 1985-1990, but they contain a few inaccuracies. The Susskind papers from '90-96 also contain these insights. The Maldacena paper builds somewhat on previous string and supergravity papers, and is less accessible.

---

First: I'm not addressing your idea because I don't understand it. Why should we expect that bounding the number of waste bits in a reversible computation (rather than some other quantity, like number of gates, or number of memory bits in an irreversible computation) would give any particular insight? Write up something more detailed, and I'll be happy to read it and form an opinion.

This post imported from StackExchange Physics at 2014-07-24 15:39 (UCT), posted by SE-user Scott Aaronson

---

@ScottAaronson: Because you can reverse the computation starting with any waste bits by running the computer backwards, and only if you guessed the right final value of the waste-bits, you end up zeroing them all out when you are done reversing. If you try to use as few waste bits as possible, I felt you should be maximally compressing them as you compute, then they end up effectively random (otherwise you could compress them further), so the remaining waste-bit number is the minimal hard-to-guess part of the forward computation.