2
$\begingroup$

Scott Aaronson's blog notably states:

Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.

Is this a statement of a law, as in, is there some no-go theorem that prevents this, or is this a statement about what we know, that is, it's possible in theory, but we have not found an algorithm that does this?

Edit: People are pointing out that the word 'simply' carries the meaning of the popular science explanations, whereby once the quantum state contains all the possible amplitudes, then the computer tells us the one we're looking for.

Now, the first part seems manifestly possible to me. It's not hard to create a quantum state who's amplitudes do represent all the possibilities at once. So what if we drop the word 'simply' from his statement. Is there some complicated mechanism that can cancel out all the other possibilities?

It seems like as long as 1) Every gate is unitary and 2) Every measurement is Hermitian, it's a valid quantum circuit. And the task is to determine that to-be-specified complicated mechanism.

Why isn't this an active area of research?

$\endgroup$
  • $\begingroup$ You'd better ask Scott Aaronson, or at least give the link to the blog post. $\endgroup$ – kludg Nov 8 at 8:48
  • 1
    $\begingroup$ well, the "proof" is that if quantum computers worked that way, any search problem would be trivially solvable by building an "algorithm trying all possible solutions at once". Building quantum algorithms would be trivial. Quantum mechanics simply does not work that way. $\endgroup$ – glS Nov 8 at 16:36
  • $\begingroup$ @glS Please see my edit. Once the quantum state contains all the possibilities, is it possible to sift through them and find the once you want? $\endgroup$ – psitae Nov 9 at 2:00
  • $\begingroup$ Do you know much about Grover’s algorithm? I believe this corresponds to the complicated way of canceling amplitudes to which you refer. And further do you know of the BBBV theorem - which is a no-go theorem I believe of the kind you add asking? The BBBV theorem says that Grover’s algorithm for unstructured search is optimal. $\endgroup$ – Mark S Nov 9 at 2:11
  • 1
    $\begingroup$ @psitae - See my extended answer. $\endgroup$ – Greg Kuperberg Nov 12 at 1:16
6
$\begingroup$

The point is that free parallel computation or cloning of your existence is a wholesale misinterpretation of the concept of quantum superposition. Quantum states are analogous to probability distributions. If you might wash the dishes or you might wash the floor and you flip a coin to decide which one, then no one takes that to mean that you will wash both of them in parallel. Quantum superposition is the same sort of thing, except with complex-valued amplitudes rather than real-valued probabilities. That fact leads to some amazing effects and extra computational power --- but it's still statistics, not replication. In that sense, quantum algorithms are much more similar to randomized algorithms than to parallel computation.


To address the amended version of the question, there is a fundamental result that Grover's algorithm is optimal for unstructured search, i.e., a search whose predicate $f(x) = \text{yes}$ is given by a black-box algorithm. Grover's algorithm gives you only a quadratic speedup, which means that unstructured search still takes exponential time, just with a better exponent. Thus, with the black-box assumption, free parallel search is provably impossible for a quantum computer.

On the other hand, if the predicate is given by a white-box algorithm, then you can't even prove that something as good as free parallel search is classically impossible, because this is exactly the question $\mathsf{P}$ vs $\mathsf{NP}$. There is a more specific conjecture that with a bad enough predicate your only option is exhaustive search or similar; it is a version of the exponential time hypothesis. I think that reasonable people in QC believe the same exponential time hypothesis for quantum computing too, except for the square root that you get from Grover's algorithm. (Or, if I can't speak for reasonable people, I tend to believe it.)

$\endgroup$
3
$\begingroup$

The statement is meant to get in front of any misconceptions, for example by the science press, about how quantum computers operate.

It's not a "no-go" in the sense of a theorem, nor do I believe many researchers have spent much time considering a possible algorithm that "simply tries all possible solutions at once."

I believe it's meant to say that quantum computers achieve a speedup through means such as, especially, constructive and destructive interference, as opposed to "simply trying all the possible solutions at once."

$\endgroup$
  • 2
    $\begingroup$ Indeed, researchers haven't spent much time considering a possible algorithm that "simply tries all possible solutions at once." That's because you don't have to spend very much time at all to see that, for the most obvious meaning of "simply" (i.e., the meaning which is used by popular presentations of QM and QC), this couldn't work unless a randomised algorithm would also work. $\endgroup$ – Niel de Beaudrap Nov 8 at 23:39
  • $\begingroup$ @NieldeBeaudrap I've edited the question so that we can discuss unsimple quantum algorithms. $\endgroup$ – psitae Nov 9 at 2:01

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.