ConceptIntermediateAlgorithmic techniques

Quantum Parallelism

Quantum parallelism means applying $U_f$ once to a superposition of all inputs, producing a superposition of all $(x,f(x))$; measurement yields only one pair, so it is useless without 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.

Mathematical formula

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

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