Frontier physics

Quantum algorithms (Shor, Grover)

Quantum algorithms use interference and entanglement to speed up selected problems, not every computation.

A quantum algorithm is a sequence of unitary gates, measurements, and classical processing. It aims to produce useful output distributions with fewer resources than the best known classical approach in a specified complexity model.

T_{\mathrm{Grover}}=O(\sqrt{N}),\qquad T_{\mathrm{classique}}=O(N);\quad T_{\mathrm{Shor}}=\operatorname{poly}(n)\ (\text{portes quantiques})

Definition: Quantum speedup

An improvement in computational resources relative to a specified classical model. A speedup claim must account for data access, output sampling, errors, and classical pre- and post-processing.

A state vector rotates in a two-dimensional plane; idealized Grover illustration, not noisy hardware.

Grover and Shor

Grover amplifies marked-state amplitude by alternating an oracle with inversion about the mean; unstructured search needs order $\sqrt N$ queries. Shor uses the quantum Fourier transform and period finding to factor in polynomial time in input bits, in a gate model with error correction.

Example: Grover query count

For $N=10^4$ items, estimate classical oracle queries and the order of Grover queries.

Solution

Classical search takes order $N=10^4$ queries; Grover takes order $\sqrt N=10^2$ . Constants depend on success probability and oracle convention.

Quantum algorithms do not make every answer available for readout: measurement returns one sample, so interference must amplify the desired amplitude. In Grover search, an oracle marks the target and amplitude amplification rotates the state by roughly $\pi/4$ per iteration toward it, requiring order $\sqrt N$ queries. Shor’s algorithm uses periodicity of modular multiplication to factor in quantum polynomial time, though practical advantage depends on error correction and hardware.

Query complexity is not the same as total runtime: state preparation, error correction, and readout costs all matter in applications. An algorithmic analysis must specify the oracle model and input distribution; an asymptotic advantage can disappear for small data or costly preprocessing. A key research question is which problem classes retain an advantage when ideal circuits are replaced by fault-tolerant machines.

What is the query complexity of Grover search over N unstructured items?

Which statement best describes Shor’s algorithmic advantage?

References

Michael A. Nielsen, Isaac L. Chuang (2010). Quantum Computation and Quantum Information