On the surface, quantum algorithms have little to do with classical computing and P vs NP in particular: Solving problems from NP with quantum computers tells us nothing about the relations of these classical complexity classes1.

On the other hand, the 'alternative description' of the classical complexity class PP as the class PostBQP presented in this paper is, as far as I'm aware, considered as an important result for 'classical complexity', by 'quantum complexity'.

In fact, Scott Aaronson, the author of the paper, writes at the end of the abstract:

This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.

Hence, my question is: are there results from the field of quantum complexity that 'simplify' the P vs NP problem, similar to the quantum description of PP? If there are no such results, is there a good reason to not expect these results, despite the 'success' for PP?

1: Take the answer to this question, for example: Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?

  • $\begingroup$ Nice question, I'm also very interested in this topic in particular. Thanks! $\endgroup$ – SalvaCardona Apr 27 '18 at 10:01

I don't think there are clear reasons for a 'yes' or a 'no' answer. However, I can provide a reason why PP was much more likely to admit such a characterisation than NP was, and to give some intuitions for why NP might never have a simple characterisation in terms of modification of the quantum computational model.

Counting complexity

The classes NP and PP can both be characterised in terms of the number of accepting branches of a non-deterministic Turing machine, which we can describe in a more down-to-earth way in terms of the possible outcomes of a randomised computation which uses uniformly random bits. We can then describe these two classes as:

  • L ∈ NP if there is a polynomial-time randomised algorithm which outputs a single bit α ∈ {0,1}, such that x ∈ L if and only if Prα = 1 | x ] is non-zero (though this probability may be tiny), as opposed to zero.

  • L ∈ PP if there is a polynomial-time randomised algorithm which outputs a single bit α ∈ {0,1}, such that x ∈ L if and only if Prα = 1 | x ] is greater than 0.5 (though possibly only by the tiniest amount), as opposed to being equal to or less than 0.5 (e.g. by a tiny amount).

One way of seeing why these classes can't be practically solved using this probabilistic description, is that it may take exponentially many repeats to be confident of a probability estimate for Prα = 1 | x ] because of the tininess of the differences in the probabilities involved.

Gap complexity and quantum complexity

Let us describe the outcomes '0' and '1' in the above computation as 'reject' and 'accept'; and let us call a randomised branch which gives a reject/accept result, a rejecting or accepting branch. Because every branch of the randomised computation which is not accepting is therefore rejecting, PP can also be defined in terms of the difference between the number of accepting and rejecting computational paths — a quantity which we may call the acceptance gap: specifically, whether the acceptance gap is positive, or less than or equal to zero. With a little more work, we can obtain an equivalent characterisation for PP, in terms of whether the acceptance gap is greater than some threshold, or less than some threshold, which may be zero or any other efficiently computable function of the input x.

This in turn can be used to characterise languages in PP in terms of quantum computation. From the description of PP in terms of randomised computations having acceptance probabilities (possibly slightly) greater than 0.5, or at most 0.5, all problems in PP admit a polynomial-time quantum algorithm which has the same distinction in acceptance probabilities; and by modelling quantum computations as a sum over computational paths, and simulating these paths using rejecting branches for paths of negative weight and accepting branches of paths of positive weight, we can also show that such a quantum algorithm making a (statistically weak) distinction describes a problem in PP.

It is not obvious that we can do the same thing for NP. There is no natural way to describe NP in terms of acceptance gaps, and the obvious guess for how you might try to fit it into the quantum computational model — by asking whether the probability of measuring an outcome '1' is zero, or non-zero — instead gives you a class called coC=P, which is not known to equal NP, and very roughly could be described as being about as powerful as PP rather than close to NP in power.

Of course, someday one might somehow find a characterisation of NP in terms of acceptance gaps, or one might find new ways of relating quantum computation to counting complexity, but I'm not sure anyone has any convincing ideas of how this might come about.


The prospects for getting insights into the P versus NP problem itself, via quantum computation, are not promising — though it isn't impossible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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