Where quantum speedups come from
Search, factoring and the complexity questions behind advantage. Four sourced contributions to read in sequence.
- STOP 1 OF 4 · Search an unstructured space
Lov K. Grover
1996 · A quadratic advantage for unstructured search
Grover introduced an algorithm that finds a marked item using a number of oracle queries proportional to the square root of the search space. His STOC paper explains the constructive interference behind the result. This is a query-complexity improvement for a specified search problem, not a claim that every database workload becomes faster.
Sole author of the original quantum-search algorithm paper.
Read the contribution in context - STOP 2 OF 4 · Use mathematical structure
Peter W. Shor
1994 · Factoring and discrete logarithms in polynomial time
Shor presented quantum algorithms whose runtime scales polynomially for integer factoring and discrete logarithms. The result concerns an ideal quantum computational model and does not imply that contemporary devices can break deployed cryptographic keys.
Originator and sole author of the cited factoring and discrete-logarithm paper.
Read the contribution in context - STOP 3 OF 4 · Take a quantum walk
Andrew M. Childs
2003 · A quantum-walk exponential separation
Childs and five coauthors constructed a graph-traversal problem in an oracle model that a continuous-time quantum walk solves exponentially faster than classical algorithms can. The model and input-access assumptions are essential to interpreting this theoretical speedup.
Coauthored theoretical result by Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann and Daniel A. Spielman.
Read the contribution in context - STOP 4 OF 4 · Examine the assumptions
Scott Aaronson
2010 · The complexity case for boson sampling
With Alex Arkhipov, Aaronson analyzed sampling from linear-optical circuits and gave complexity-theoretic reasons that efficient classical simulation would have unlikely consequences. The paper helped define an experimental route to testing quantum computational advantage without requiring a universal programmable quantum computer.
Joint theoretical work by Scott Aaronson and Alex Arkhipov; the hardness conclusions depend on stated complexity assumptions.
Read the contribution in context