4

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?

psitae
  • 1,390
  • 8
  • 25

2 Answers2

6

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

Greg Kuperberg
  • 1,506
  • 11
  • 16
3

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

Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83