TopicIntermediateEstablished concept

Quantum Parallelism

Quantum Parallelism

Quantum parallelismQuantum Parallelism: Quantum parallelism is applying an operator U_f once to a superposition of all inputs, producing a superposition of all (x,f(x)); but measurement yields a single pair, s… is applying an operator $U_f$ once to a superposition of all inputs, producing a superposition of all $(x,f(x))$; but measurement yields a single pair, so it is useless without carefully designed interference.

For a function $f:\{0,1\}^n\to\{0,1\}$ we define the reversible operator $U_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle$. Applying it to the uniform superposition gives $$U_f\Big(\tfrac{1}{\sqrt{2^n}}\sum_x|x\rangle\Big)|0\rangle=\tfrac{1}{\sqrt{2^n}}\sum_x|x\rangle|f(x)\rangle.$$ A single call to $U_f$ "computes" $f$ on all inputs in the linear sense. This is called quantum parallelism.

But this description is misleading if taken literally. Measurement gives a single random pair $(x,f(x))$, which is what can be obtained classically by evaluating $f$ on a random input. The values cannot all be read. The benefit requires further processing that makes the amplitudes interfere so as to reveal a global property of $f$, such as being constant or balanced (Deutsch–Jozsa), its periodicity (Simon and Shor), or the position of a marked item (Grover). So the more precise statement is that the quantum advantage, when there is one, comes from interference and entanglement, and that parallelism alone is not enough. This is also why there is no general exponential speed-up for search: Grover's quadratic bound is proved to be optimal.

That is why the phrase "a quantum computer tries all solutions at once" should be avoided in educational writing.

q0q1q2HHHHXHUf
Deutsch–Jozsa circuit: Hadamard, oracle Uf, Hadamard, measurement

Mathematical formulation

$$U_f\,\frac{1}{\sqrt{2^n}}\sum_x|x\rangle|0\rangle=\frac{1}{\sqrt{2^n}}\sum_x|x\rangle|f(x)\rangle$$

Worked example

For $n=2$ and $f(x)=x_0$ (the lowest bit): the state is $\tfrac12(|00\rangle|0\rangle+|01\rangle|1\rangle+|10\rangle|0\rangle+|11\rangle|1\rangle)$. Measuring all the qubits gives one of the four pairs with probability $\tfrac14$, i.e. information about a single value only. Bernstein–Vazirani, by contrast, extracts the whole hidden string with one call thanks to interference.

Try it yourself: Deutsch–Jozsa Algorithm

Loading the simulator…

The full experiment page

Test your understanding

The quiz needs JavaScript.

Related topics

References

  1. Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.
  2. David Deutsch (1985). Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400(1818):97–117 doi:10.1098/rspa.1985.0070