Is there any general statement about what kinds of problems can be solved more efficiently using a quantum computer?

Question

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.

Answer 1

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.

Answer 2

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 class of problems that can be efficiently solved by quantum computers is called BQP, for "bounded error, quantum, polynomial time". Quantum computers only run probabilistic algorithms, so BQP on quantum computers is the counterpart of BPP ("bounded error, probabilistic, polynomial time") on classical computers. It is defined as the set of problems solvable with a polynomial-time algorithm, whose probability of error is bounded away from one half. A quantum computer is said to "solve" a problem if, for every instance, its answer will be right with high probability. If that solution runs in polynomial time, then that problem is in BQP.

BQP is contained in the complexity class #P (or more precisely in the associated class of decision problems P^#P), which is a subclass of PSPACE.

BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP. Both of these problems are NP problems suspected to be outside BPP, and hence outside P. Both are suspected to not be NP-complete. There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.

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.

Although quantum computers may be faster than classical computers for some problem types, those described above can't solve any problem that classical computers can't already solve. A Turing machine can simulate these quantum computers, so such a quantum computer could never solve an undecidable problem like the halting problem. The existence of "standard" quantum computers does not disprove the Church–Turing thesis. It has been speculated that theories of quantum gravity, such as M-theory or loop quantum gravity, may allow even faster computers to be built. Currently, defining computation in such theories is an open problem due to the problem of time, i.e., there currently exists no obvious way to describe what it means for an observer to submit input to a computer and later receive output.

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}$

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

Answer 3

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

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

Answer 4

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