A different model of computation, with a different complexity landscape.
9 topics · 13 curated works
No prior grounding assumed.
Quantum Mechanical Computers
Richard P. Feynman · 1985
Sketches how a reversible, unitary machine built from quantum gates acting on qubits could carry out computation without the energy dissipation an…
Assumes you know the vocabulary.
The Physical Implementation of Quantum Computation
David P. DiVincenzo · 2000
Lays out five criteria any physical system must meet to serve as a quantum computer, giving competing hardware platforms, trapped ions,…
+1 more at this level
Primary sources and full treatments.
Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer
David Deutsch · 1985
Defines a universal quantum computer and argues the Church-Turing thesis should be a statement about physics, since which functions are efficiently…
+9 more at this level
12 of 13 works
Richard P. Feynman
Sketches how a reversible, unitary machine built from quantum gates acting on qubits could carry out computation without the energy dissipation an irreversible classical computer requires.
David P. DiVincenzo
Lays out five criteria any physical system must meet to serve as a quantum computer, giving competing hardware platforms, trapped ions, superconducting circuits and others, a common checklist to be judged against.
John Preskill
Names the current era of noisy, intermediate-scale quantum devices and argues they may find useful applications before fault-tolerant quantum computers exist, though this is not guaranteed.
link checked 17 Sept 2026David Deutsch
Defines a universal quantum computer and argues the Church-Turing thesis should be a statement about physics, since which functions are efficiently computable depends on which physical laws hold.
link checked 17 Sept 2026Adriano Barenco et al.
Shows that a small set of one- and two-qubit gates, including controlled-NOT, is sufficient to build any quantum computation, giving quantum circuits a universal gate set.
link checked 17 Sept 2026Lov K. Grover
Gives a quantum algorithm that finds a marked item among N unsorted possibilities in roughly the square root of N steps, a quadratic speed-up proven optimal for the problem.
link checked 17 Sept 2026A. R. Calderbank & Peter W. Shor
Constructs the first family of quantum error-correcting codes proven to protect quantum information against noise at a constant rate, showing quantum computation need not be destroyed by decoherence.
Peter W. Shor
Gives an algorithm that factors integers in polynomial time on a quantum computer, undermining the hardness assumption RSA encryption relies on.
26 pageslink checked 17 Sept 2026Richard Cleve, Artur Ekert, Chiara Macchiavello & Michele Mosca
Reworks the Deutsch-Jozsa, Simon and Shor algorithms as instances of one quantum circuit technique, estimating the eigenvalues of a unitary operator, showing what these seemingly different speed-ups have in common.
Michel Boyer, Gilles Brassard, Peter Hoyer & Alain Tapp
Generalises Grover's search algorithm and proves its quadratic speed-up is optimal, so no quantum algorithm can search an unsorted database faster.
Lieven M. K. Vandersypen et al.
Reports the first physical execution of Shor's algorithm, factoring 15 into 3 and 5 on a seven-qubit NMR quantum computer, showing the algorithm works on real hardware and not only on paper.
John Watrous
Surveys how complexity classes such as BQP relate to their classical counterparts, and what is and is not known about the power quantum computers add to computation.
This subject genuinely sits in more than one domain. These fields approach the same ground with different methods.