Is there a general statement about what kinds of problems can be solved more efficiently using quantum computers (quantum gate model only)? Do the problems for which an algorithm is known today have a common property?

As far as i understand quantum computing helps with the hidden subgroup problem (Shor); Grover's algorithm helps speedup search problems. I have read that quantum algorithms can provide speed-up if you look for a 'global property' of a function (Grover/Deutsch).

  1. Is there a more concise and correct statement about where quantum computing can help?
  2. Is it possible to give an explanation why quantum physics can help there (preferably something deeper that 'interference can be exploited')? And why it possibly will not help for other problems (e.g. for NP-complete problems)?

Are there relevant papers that discuss just that?

I had asked this question before over on cstheory.stackexchange.com but it may be more suitable here.


On computational helpfulness in general

Without perhaps realising it, you are asking a version of one of the most difficult questions you can possibly ask about theoretical computer science. You can ask the same question about classical computers, only instead of asking whether adding 'quantumness' is helpful, you can ask:

  • Is there a concise statement about where randomised algorithms can help?

    It's possible to say something very vague here — if you think that solutions are plentiful (or that the number of solutions to some sub-problem are plentiful) but that it might be difficult to systematically construct one, then it's helpful to be able to make choices at random in order to get past the problem of systematic construction. But beware, sometimes the reason why you know that there are plentiful solutions to a sub-problem is because there is a proof using the probabilistic method. When this is the case, you know that the number of solutions is plentiful by reduction to what is in effect a helpful randomised algorithm!

    Unless you have another way of justifying the fact that the number of solutions is plentiful for those cases, there is no simple description of when a randomised algorithm can help. And if you have high enough demands of 'helpfulness' (a super-polynomial advantage), then what you are asking is whether $\mathsf P \ne \mathsf{BPP}$, which is an unsolved problem in complexity theory.

  • Is there a concise statement about where parallelised algorithms can help?

    Here things may be slightly better. If a problem looks as though it can be broken down into many independent sub-problems, then it can be parallelised — though this is a vague, "you'll know it when you see it" sort of criterion. The main question is, will you know it when you see it? Would you have guessed that testing feasibility of systems of linear equations over the rationals is not only parallelisable, but could be solved using $O(\log^2 n)$-depth circuits [c.f. Comput. Complex. 8 (pp. 99--126), 1999]?

    One way in which people try to paint a big-picture intuition for this is to approach the question from the opposite direction, and say when it is known that a parallelised algorithm won't help. Specifically, it won't help if the problem has an inherently sequential aspect to it. But this is circular, because 'sequential' just means that the structure that you can see for the problem is one which is not parallelised.

    Again, there is no simple, comprehensive description of when a parallelised algorithm can help. And if you have high enough demands of 'helpfulness' (a poly-logarithmic upper bound on the amount of time, assuming polynomial parallelisation), then what you are asking is whether $\mathsf P \ne \mathsf{NC}$, which is again an unsolved problem in complexity theory.

The prospects for "concise and correct descriptions of when [X] is helpful" are not looking too great by this point. Though you might protest that we're being too strict here: on the grounds of demanding more than a polynomial advantage, we couldn't even claim that non-deterministic Turing machines were 'helpful' (which is clearly absurd). We shouldn't demand such a high bar — in the absence of techniques to efficiently solve satisfiability, we should at least accept that if we somehow could obtain a non-deterministic Turing machine, we would indeed find it very very helpful. But this is different from being able to characterise precisely which problems we would find it helpful for.

On the helpfulness of quantum computers

Taking a step back, is there anything we can say about where quantum computers are helpful?

We can say this: a quantum computer can only do something interesting if it is taking advantage of the structure of a problem, which is unavailable to a classical computer. (This is hinted at by the remarks about a "global property" of a problem, as you mention). But we can say more than this: problems solved by quantum computers in the unitary circuit model will instantiate some features of that problem as unitary operators. The features of the problem which are unavailable to classical computers will be all those which do not have a (provably) statistically significant relationship to the standard basis.

  • In the case of Shor's algorithm, this property is the eigenvalues of a permutation operator which is defined in terms of multiplication over a ring.
  • In the case of Grover's algorithm, this property is whether the reflection about the set of marked states, commutes with the reflection about the uniform superposition — this determines whether the Grover iterator has any eigenvalues which are not $\pm 1$.

It is not especially surprising to see that in both cases, the information relates to eigenvalues and eigenvectors. This is an excellent example of a property of an operator which need not have any meaningful relationship to the standard basis. But there is no particular reason why the information has to be an eigenvalue. All that is needed is to be able to describe a unitary operator, encoding some relevant feature of the problem which is not obvious from inspection of the standard basis, but is accessible in some other easily described way.

In the end, all this says is that a quantum computer is useful when you can find a quantum algorithm to solve a problem. But at least it's a broad outline of a strategy for finding quantum algorithms, which is no worse than the broad outlines of strategies I've described above for randomised or parallelised algorithms.

Remarks on when a quantum computer is 'helpful'

As other people have noted here, "where quantum computing can help" depends on what you mean by 'help'.

  • Shor's algorithm is often trotted out in such discussions, and once in a while people will point out that we don't know that factorisation isn't solvable in polynomial-time. So do we actually know that "quantum computing would be helpful for factorising numbers"?

    Aside from the difficulty in realising quantum computers, I think here the reasonable answer is 'yes'; not because we know that you can't factorise efficiently using conventional computers, but because we don't know how you would do it using conventional computers. If quantum computers help you to do something that you have no better approach to doing, it seems to me that this is 'helping'.

  • You mention Grover's algorithm, which yields a well-known square-root speedup over brute-force search. This is only a polynomial speedup, and a speedup over a naive classical algorithm — we have better classical algorithms than brute-force search, even for NP-compelete problems. For instance, in the case of 3-SAT instances with a single satisfying assignment, the PPSZ algorithm has a runtime of $O(2^{0.386\,n})$, which outperforms Grover's original algorithm. So is Grover's algorithm 'helpful'?

    Perhaps Grover's algorithm as such is not especially helpful. However, it may be helpful if you use it to elaborate more clever classical strategies beyond brute-force search: using amplitude amplification, the natural generalisation of Grover's algorithm to more general settings, we can improve on the performance of many non-trivial algorithms for SAT (see e.g. [ACM SIGACT News 36 (pp.103--108), 2005 — free PDF link]; hat tip to Martin Schwarz who pointed me to this reference in the comments).

    As with Grover's algorithm, amplitude amplification only yields polynomial speed-ups: but speaking practically, even a polynomial speedup may be interesting if it isn't washed out by the overhead associated with protecting quantum information from noise.

  • $\begingroup$ Hi Niel! There is actually a quantum version of PPSZ with Grover speed-up: digitalcommons.utep.edu/cgi/… $\endgroup$ – Martin Schwarz Apr 5 '18 at 7:50
  • $\begingroup$ @MartinSchwarz: Thanks, that's an excellent reference! :-) I've added it to the final remarks on 'helpfulness', which feels quite apt. $\endgroup$ – Niel de Beaudrap Apr 5 '18 at 8:47
  • $\begingroup$ Niel, admittedly, my math skills are a bit under par for understanding this answer, but am I correct in interpreting what you said to mean that when there's an underlying relationship between the data that is difficult to impose on classical algorithms, that is when quantum computers shine? So to test with an example, should quantum computers be fantastic for finding primes? $\endgroup$ – TheEnvironmentalist Apr 6 '18 at 6:36
  • 1
    $\begingroup$ @TheEnvironmentalist: that could be considered a necessary condition for a quantum advantage, but it isn't sufficient. One also has to be able to see precisely how the structure might be accessible by other means. ('Accessible' here is relative: the HHL algorithm shows aspects of linear algebra which are efficency solvable classically, but even more accessible to quantum algorithms; and Grover's algorithm shows how quantum algorithms seem to obtain a little bit more access to information about unstructured problems than classical algorithms can, but 'shine' is a strong word to use there.) $\endgroup$ – Niel de Beaudrap Apr 6 '18 at 7:45
  • $\begingroup$ Very interesting answer. What is exactly meant by "features that do not have a (provably) statistically significant relationship to the standard basis." ? $\endgroup$ – JanVdA Jun 19 '18 at 12:22

TL;DR: No, we do not have any precise "general" statement about exactly which type of problems quantum computers can solve, in complexity theory terms. However, we do have a rough idea.

According to Wikipedia's sub-article on Relation to to computational complexity theory




The capacity of a quantum computer to accelerate classical algorithms has rigid limits—upper bounds of quantum computation's complexity. The overwhelming part of classical calculations cannot be accelerated on a quantum computer. A similar fact takes place for particular computational tasks, like the search problem, for which Grover's algorithm is optimal.

Bohmian Mechanics is a non-local hidden variable interpretation of quantum mechanics. It has been shown that a non-local hidden variable quantum computer could implement a search of an N-item database at most in ${\displaystyle O({\sqrt[{3}]{N}})}$ steps. This is slightly faster than the $\displaystyle O({\sqrt {N}})$ steps taken by Grover's algorithm. Neither search method will allow quantum computers to solve NP-Complete problems in polynomial time.


As for why quantum computers can efficiently solve BQP problems:

  1. The number of qubits in the computer is allowed to be a polynomial function of the instance size. For example, algorithms are known for factoring an $n$-bit integer using just over $2n$ qubits (Shor's algorithm).

  2. Usually, computation on a quantum computer ends with a measurement. This leads to a collapse of quantum state to one of the basis states. It can be said that the quantum state is measured to be in the correct state with high probability.

Interestingly, if we theoretically allow post-selection (which doesn't have any scalable practical implementation), we get the complexity class post-BQP:

In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error (in the sense that the algorithm is correct at least 2/3 of the time on all inputs). However, Postselection is not considered to be a feature that a realistic computer (even a quantum one) would possess, but nevertheless postselecting machines are interesting from a theoretical perspective.

I'd like to add what @Discrete lizard mentioned in the comments section. You have not explicitly defined what you mean by "can help", however, the rule of thumb in complexity theory is that if a quantum computer "can help" in terms of solving in polynomial time (with an error bound) iff the class of problem it can solve lies in BQP but not in P or BPP. The general relation between the complexity classes we discussed above is suspected to be:

$\text{P $\subseteq$ BPP $\subseteq$ BQP $\subseteq$ PSPACE}$

enter image description here

However, P=PSPACE, is an open problem in Computer Science. Also, the relationship between P and NP is not known yet.

  • $\begingroup$ The first part only answers the question "how is the set of efficient algorithms on quantum circuits called". Although looking at the problems in the class gives an idea of what problems are known to currently have better quantum algorithms than classical algorithms, this doesn't lead to a general statement. The second part comes closer to what is being asked for, although those are examples, not a general statement. The general statement is of course beyond current knowledge, but I think that is worth mentioning. $\endgroup$ – Discrete lizard Apr 4 '18 at 7:43
  • $\begingroup$ To be clear, the fact that a problem is in BQP doesn't mean that quantum computing "can help". We can only say for a problem A that QC helps if A is in BQP, but not in P (or BPP?). $\endgroup$ – Discrete lizard Apr 4 '18 at 7:45
  • $\begingroup$ sorry, i can accept one answer only... thanks a lot! $\endgroup$ – hiro protagonist Apr 7 '18 at 9:49
  • $\begingroup$ One aspect I can not find clearly back in your answer is the kind of problems that can be solved more efficiently by a quantum computer. In the first paragraph you mention that we have a rough idea but is this rough idea documented in the answer ? $\endgroup$ – JanVdA Jun 19 '18 at 12:34
  • $\begingroup$ @JanVdA All the standard quantum algorithms like Grover's, Shor's, etc give us rough ideas of what type of problems could be solved more efficiently by a quantum computer. I didn't feel the need of covering that in the answer as you'd find it in any general textbook on the subject or even Wiikipedia. The point is that we're not sure that there can't exist classical algorithms which will perform as well or better than those. $\endgroup$ – Sanchayan Dutta Jun 19 '18 at 13:20

There is no such general statement and it is unlikely there will be one soon. I will explain why this is the case. For a partial answer to your question, looking at the problems in the two complexity classes BQP and PostBQP might help.

The complexity classes that come closest to the problems that can be solved efficiently by quantum computers of the quantum gate model are

  1. BQP; and
  2. PostBQP

BQP consists of the problems that can be solved in polynomial time on a quantum circuit. Most important quantum algorithms, such as Shor's algorithm, solve problems in BQP.

PostBQP consists of the problems that can be solved in polynomial time on a quantum circuit that can additionally perform postselection. This is a lot more powerful, as PostBQP$=$PP, a class that contains PP.

However, there currently are no methods to practically implement postselection, so PostBQP is more of theoretical interest.

The relation between P, NP and BQP is currently unknown; and an open problem on the order of P vs. NP. As a general statement about what kinds of problems can be solved more efficiently using quantum computers must answer the BQP vs. P question (if BQP=P, then apparently quantum computers aren't more efficient (to complexity theorists, at least) )

  • $\begingroup$ Postselection can be achieved with a quantum processor that doesn't use postselection using classical post-processing. The issue is that it generally requires an exponential number of runs $\endgroup$ – Mithrandir24601 Apr 4 '18 at 7:50
  • 1
    $\begingroup$ @Mithrandir24601 So, there are no practical implementations of postselection. $\endgroup$ – Discrete lizard Apr 4 '18 at 7:54
  • 1
    $\begingroup$ There are, um, interesting uses for small numbers of qubits, but as far as I'm aware, there aren't any practical and scalable implementations, no $\endgroup$ – Mithrandir24601 Apr 4 '18 at 7:58
  • 1
    $\begingroup$ Can we really say that PostBQP comes anywhere close to problems which are efficiently solvable by quantum computers (in any model)? Your own remarks about practically implementing postselection would suggest not, and postselection is certainly not allowed in the definition of the unitary circuit model. Would not ZQP be a much better candidate (more restrictive than BQP in that it would in principle never produce an erroneous result, and of non-trivial interest because it contains integer factorisation)? $\endgroup$ – Niel de Beaudrap Apr 4 '18 at 21:34
  • 2
    $\begingroup$ I took your mention of "the quantum gate model" as an invitation to consider theoretical models of quantum computation, in which we list allowed operations. PostBQP is the class arising if you suppose that postselection is an allowed operation which has only constant cost. Of course, we can accommodate postselection just by making it part of the conditions we want on the measured output. But we can do the same for classical computation, and no-one seriously suggests that postselection is a technique for efficient classical computation (you can 'solve' NP-complete problems that way). $\endgroup$ – Niel de Beaudrap Apr 5 '18 at 7:37

Similar to Blue's picture, I like this one from Quanta Magazine better, since it seem to visually summarize what we are talking about. enter image description here


Your Answer

