Academy K

Query Complexity Lower Bounds

HardDerivationquery complexityadversary methodlower bounds

Related module: Search and amplitude amplification

Problem statement

Grover's algorithm finds a marked item among NN with O(N)O(\sqrt{N}) queries. The BBBV theorem proves this is optimal.

  1. State the quantum query complexity model.
  2. Why is Ω(N)\Omega(\sqrt{N}) a lower bound for unstructured search?
  3. What does this imply about the power of quantum computers?

Hints

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.