Grover's algorithm solves the search problem: find an element satisfying a property in an unsorted list of n elements. It uses O(sqrt(n)) quantum queries and O(n) gates. The classical lower bound is Omega(n) queries. Why does quantum provide this quadratic speedup, and why is it limited to quadratic?
AQuantum computers are exponentially faster than classical computers and can solve any problem in polynomial time
BGrover's algorithm uses superposition to query all n elements simultaneously, then amplifies the amplitude of the correct answer. The speedup is exactly sqrt(n) due to the structure of amplitude amplification — the correct state's amplitude grows as O(sqrt(n)) iterations
CGrover's algorithm uses exponential speedup and proves quantum computers can factor any number quickly
DThe quantum speedup is logarithmic, not quadratic, as stated in the question
Grover's algorithm works by initializing a superposition of all n states, then iteratively applying an 'oracle' (checks the property) and a 'diffusion operator' (amplifies the marked state's amplitude). After k iterations, the amplitude of the marked state is O(sin((2k+1)θ)) where sin(θ) = 1/sqrt(n). The amplitude is maximum at k ≈ pi/(4θ) ≈ pi*sqrt(n)/4, yielding O(sqrt(n)) iterations. This quadratic speedup is conjectured optimal: the quantum query lower bound (by Bennett et al.) shows Omega(sqrt(n)) queries are necessary for any quantum algorithm solving search. The limitation arises from the probabilistic nature of quantum measurement: measuring a state with amplitude O(1/sqrt(n)) requires O(sqrt(n)) amplification steps.
Question 2 Short Answer
Quantum algorithms for solving linear systems (HHL algorithm) promise exponential speedup over classical Gaussian elimination. However, many speedup claims are controversial because they ignore hidden computational costs. Explain one major caveat in the HHL algorithm's complexity analysis.
Think about your answer, then reveal below.
Model answer: The HHL algorithm solves A*x = b in time poly(log(n), 1/epsilon, condition_number(A)) where the conditioning of the matrix A is a factor. However, the output is not the full vector x — the algorithm outputs a quantum state encoding x. To read out the answer, you must measure, which yields only one coordinate per run. Extracting the full solution classically requires n quantum runs (or post-processing via tomography), recovering only O(1) advantage. Additionally, the algorithm requires (1) an efficient quantum representation of A (not always available), (2) a way to prepare the initial state |b> (non-trivial), and (3) estimation of the condition number (classically hard). When these hidden costs are included, the exponential speedup often disappears.
This caveat is crucial: quantum speedup claims must account for state preparation, measurement, and problem-specific subroutines. Many 'quantum machine learning' algorithms cite HHL-like speedups while glossing over these costs, leading to overstated claims of quantum advantage.
Question 3 Multiple Choice
Variational Quantum Algorithms (VQA) like the Quantum Approximate Optimization Algorithm (QAOA) use a parameterized quantum circuit with angles optimized classically. Unlike Shor's and Grover's algorithms which offer unconditional speedup, QAOA's advantage is unclear. What is the main challenge in proving that QAOA outperforms classical optimization?
AQAOA is proven to be faster than all classical algorithms, so the challenge is only in engineering the quantum hardware
BThe challenge is comparing QAOA's performance to the best classical approximation algorithms, and analyzing whether quantum effects provide genuine advantage or merely different algorithmic structure
CQAOA cannot work on real quantum hardware due to noise and decoherence, so no speedup is possible
DClassical computers can simulate QAOA exactly, so any speedup must be exponential to be worthwhile
VQAs are hybrid: a parameterized quantum circuit prepares a state, you measure the energy (classical), then optimize the parameters classically (e.g., gradient descent). The quantum circuit has p layers ('depth p'), and the class of states it can prepare grows with p. For QAOA on MAX-SAT, the quantum circuit prepares a superposition designed to solve the optimization problem. However, for reasonable depth p (which is necessary to avoid exponential gate counts), the quantum states are not qualitatively different from classical Ansatze — classical algorithms can achieve comparable approximation ratios with careful design. Proving QAOA's speedup requires comparing to the best classical algorithms for the same problem, and for many problems, classical approximation algorithms are not far behind. The research question is genuinely open.
Question 4 True / False
The complexity class BQP (Bounded-error Quantum Polynomial) contains decision problems solvable in polynomial time by a quantum computer with error probability at most 1/3. BQP likely contains problems outside P (e.g., factoring, assuming Shor's algorithm is correct), but the relationship between BQP and NP is unknown.
TTrue
FFalse
Answer: True
This is a major open question in quantum computational complexity. BQP is believed to be incomparable with NP: factoring is in BQP (Shor) but not believed to be NP-hard (it's not known to be in NPC), and there are believed to be problems in NP not in BQP, and vice versa. If NP ⊆ BQP, quantum computers would solve NP-hard problems in polynomial time, but this is not believed true — most researchers think quantum computers cannot solve NP-complete problems efficiently. Understanding where BQP sits relative to the classical polynomial hierarchy is a frontier in quantum complexity theory.