34
$\begingroup$

The standard popular-news account of quantum computing is that a quantum computer (QC) would work by splitting into exponentially many noninteracting parallel copies of itself in different universes and having each one attempt to verify a different certificate, then at the end of the calculation, the single copy that found a valid certificate "announces" its solution and the other branches magically vanish.

People who know anything about theoretical quantum computation know that this story is absolute nonsense, and that the rough idea described above more closely corresponds to a nondeterministic Turing machine (NTM) than to a quantum computer. Moreover, the compexity class of problems efficiently solvable by NTMs is NP and by QCs is BQP, and these classes are not believed to be equal.

People trying to correct the popular presentation rightfully point out that the simplistic "many-worlds" narrative greatly overstates the power of QCs, which are not believed to be able to solve (say) NP-complete problems. They focus on the misrepresentation of the measurement process: in quantum mechanics, which outcome you measure is determined by the Born rule, and in most situations the probability of measuring an incorrect answer completely swamps the probability of measuring the right one. (And in some cases, such as black-box search, we can prove that no clever quantum circuit can beat the Born rule and deliver an exponential speedup.) If we could magically "decide what to measure", then we would be able to efficiently solve all problems in the complexity class PostBQP, which is believed to be much large than BQP.

But I've never seen anyone explicitly point out that there is another way in which the popular characterization is wrong, which goes in the other direction. BQP is believed to be not a strict subset of NP, but instead incomparable to it. There exist problems like Fourier checking which are believed to not only lie outside of NP, but in fact outside of the entire polynomial hierarchy PH. So with respect to problems like these, the popular narrative actually understates rather than overstates the power of QCs.

My naive intuition is that if we could "choose what to measure", then the popular narrative would be more or less correct, which would imply that these super-quantum-computers would be able to efficiently solve exactly the class NP. But we believe that this is wrong; in fact PostBQP=PP, which we believe to be a strict superset of NP.

Is there any intuition for what's going on behind the scenes that allows a quantum computer to be (in some respects) more powerful than a nondeterministic Turing machine? Presumably this "inherently quantum" power, when combined with postselection (which in a sense NTMs already have) is what makes a super-QC so much more powerful than a NTM. (Note that I'm looking for some intuition that directly contrasts NTMs and QCs with postselection, without "passing through" the classical complexity class PP.)

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
19
$\begingroup$

From a pseudo-foundational standpoint, the reason why BQP is a differently powerful (to coin a phrase) class than NP, is that quantum computers can be considered as making use of destructive interference.

Many different complexity classes can be described in terms of (more or less complicated properties of) the number of accepting branches of an NTM. Given an NTM in 'normal form', meaning that the set of computational branches are a complete binary tree (or something similar to it) of some polynomial depth, we may consider classes of languages defined by making the following distinctions:

  • Is the number of accepting branches zero, or non-zero? (A characterisation of NP.)
  • Is the number of accepting branches less than the maximum, or exactly equal to the maximum? (A characterisation of coNP.)
  • Is the number of accepting branches at most one-third, or at least two-thirds, of the total? (A characterisation of BPP.)
  • Is the number of accepting branches less than one-half, or at least one-half, of the total? (A characterisation of PP.)
  • Is the number of accepting branches different from exactly half, or equal to exactly half, of the total? (A characterisation of a class called C=P.)

These are called counting classes, because in effect they are defined in terms of the count of accepting branches.

Interpreting the branches of an NTM as randomly generated, they are questions about the probability of acceptance (even if these properties are not efficiently testable with any statistical confidence). A different approach to describing complexity classes is to consider instead the gap between the number of accepting branches and the number of rejecting branches of an NTM. If counting the cumulation of NTM computational branches corresponds to probabilities, one could suggest that canceling accepting branches against rejecting branches models the cancellation of computational 'paths' (as in sum-over-paths) in quantum computation — that is, as modeling destructive interference.

The best known upper bounds for BQP, namely AWPP and PP, are readily definable in terms of 'acceptance gaps' in this way. The class NP, however, does not have such an obvious characterisation. Furthermore, many of the classes which one obtains from definitions in terms of acceptance gaps appear to be more powerful than NP. One could take this to indicate that 'nondeterministic destructive interference' is a potentially more powerful computational resource than mere nondeterminism; so that even if quantum computers do not take full advantage of this computational resource, it may nevertheless resist easy containment in classes such as NP.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Are P and PSPACE counting classes? Naively it seems that yes for P, as it could be defined as the set of problems such that every path accepts, but I'm not sure about PSPACE. $\endgroup$
    – tparker
    Mar 30, 2018 at 19:25
  • 1
    $\begingroup$ PSPACE is not a counting class, no. You're on the right track with P --- you must require that either every path accepts or every pah rejects (or a similarly strong requirement), or else you might end up with coNP , coRP , or some other class not known to equal P . $\endgroup$
    – Niel de Beaudrap
    Mar 30, 2018 at 19:30
  • $\begingroup$ Presumably PH isn't a counting class either, since it's naturally formulated in terms of an alternating rather than nondeterministic Turing machine? $\endgroup$
    – tparker
    Jun 5, 2018 at 20:45
  • $\begingroup$ If BPP requires two-thirds of the branches to accept, PP requires half to accept, and NP only requires one to accept, wouldn't that imply that $\mathbf{BPP} \subset \mathbf{PP} \subset \mathbf{NP}$? But in fact $\mathbf{BPP} \subset \mathbf{NP} \subset \mathbf{PP}$, and both inclusions are believed to be strict. $\endgroup$
    – tparker
    Jun 11, 2018 at 16:18
  • 1
    $\begingroup$ @tparker: You are missing some details, for instance the behaviour of NO instances in the definition of BPP (see the post). In short, these thresholds do not map in a linear manner to broadness of instances taken to be YES instances. (And to the best of my knowledge, no such relation as $\mathsf {BPP \subseteq NP} $ is known --- at best we know $\mathsf {BPP \subseteq NP^{NP} \cap coNP^{NP}}$.) $\endgroup$
    – Niel de Beaudrap
    Jun 11, 2018 at 21:19
-1
$\begingroup$

This answer was 'migrated' from when this question was asked on Computer Science (Author remains the same)

Well, one main reason is that there aren't any quantum algorithms that solve NP-hard problems in polynomial time.

Another is that adiabetic quantum annealing (as in the Dwave) can only barely beat the classical quantum annealing.

Also, most researchers think P$\neq$NP. A lot believe P$=$BQP. However, P$\neq$PostBQP. Is PostBQP$\neq$NP now contradictionay? No. We only know that P$=$NP is a weaker statement than (not nessecarily implying more!) PostBQP$=$P! So, why all the fuss about a question harder than P vs. NP!

As for why to believe P$=$BQP, some believe any improvement will not be asymptotic or merely a constant, as in differing implementation.

So, there are some reasons to believe PostBQP$\neq$NP. But this is all speculation and likely remains speculation for a while. You can believe whatever you want, for now, at least.

There exist problems like Fourier checking which are believed to not only lie outside of NP, but in fact outside of the entire polynomial hierarchy. So with respect to problems like these, the popular narrative actually understates rather than overstates the power of QCs.

As for this, I haven't seen a result that states a quantum computer can solve this efficiently! Also, that the machine can solve weird problems fast (simulating itself in $O(n)$, for example) isn't more surprising that a waterfall simulating itself in $O(n)$ (n being the number of simulation steps)

Improve this answer
$\endgroup$
0

Your Answer

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

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