Academy K

Quantum Parallelism Limitations

InterviewConceptualquantum parallelismmeasurementspeedup

Related module: Early algorithms

Problem statement

A quantum computer can evaluate a function ff on all 2n2^n inputs simultaneously:

∣0⟩⊗n∣0⟩→H⊗n12n∑x=02n−1∣x⟩∣0⟩→Uf12n∑x=02n−1∣x⟩∣f(x)⟩|0\rangle^{\otimes n}|0\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle|0\rangle \xrightarrow{U_f} \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle|f(x)\rangle
  1. Why can't you just measure to get all f(x)f(x) values?
  2. What types of problems can still benefit from quantum parallelism?
  3. Give an example of a problem that quantum parallelism doesn't help.

Practise this problem

Verify you understand it—not just that you read the answer.

Learn the foundations

The Quantum Computing track covers this topic and more in depth.