Concept record · edition 0.1.0
Quantum algorithm
What the term means here
A procedure designed for a quantum computer, with a specified input, circuit, measurement, and classical post-processing.
Why it matters
A claimed quantum advantage is meaningful only relative to a problem, algorithm, resource model, and classical comparison.
Related claims · 3
- qc-006
Shor’s algorithm gives polynomial-time quantum algorithms for integer factorization and discrete logarithms on a suitable quantum computer.
- qc-007
Grover’s search algorithm provides a quadratic query-speedup for unstructured search in its oracle model.
- qc-012
Claims about quantum applications require task-specific comparisons to credible classical baselines.
Sources used here
primary paper · verified
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Peter W. Shor · 1995
Primary source for the factoring and discrete-logarithm algorithm.
Source record →primary paper · verified
A Fast Quantum Mechanical Algorithm for Database Search
Lov K. Grover · 1996
Primary source for amplitude-amplification search.
Source record →