Computational model exploiting quantum superposition, entanglement, and interference to solve problems with provable asymptotic advantages over the best known classical algorithms. Foundational algorithms: Deutsch 1985 / Deutsch-Jozsa…
quantum-computing
Deutsch-Jozsa 1992 oracle problem: constant vs balanced with 1 quantum query
Deutsch 1985 (Proc. R. Soc. A 400:97) introduced the single-bit precursor; Deutsch-Jozsa 1992 (Proc. R. Soc. A 439:553) extended it to n…
Grover 1996 unstructured-search with O(√N) queries
Grover 1996 (Proc. STOC 212) gave a quantum algorithm for unstructured search with quadratic speedup: given an oracle U_f marking M out of…
Bernstein-Vazirani 1993 hidden-string in 1 quantum query vs n classical
Bernstein-Vazirani 1993 (STOC 1993, refined paper SIAM J. Comput. 26:1411) refined the Deutsch-Jozsa problem to a learning task. Promise:…
Deutsch-Jozsa quantum/classical query complexity exponential separation
Exact closed-form query-complexity comparison. Quantum: Deutsch-Jozsa solves the constant-vs-balanced promise problem with exactly 1…
Grover iteration R=1 gives P=1 for N=4, M=1 (perfect 4-item search)
Textbook special case: Grover search over N=4 items with M=1 marked item gives certainty after a single Grover iteration. The rotation…
Bernstein-Vazirani quantum speedup = n (linear in problem size)
Exact query-complexity result. Quantum: 1 oracle query recovers the n-bit hidden string s exactly. Classical lower bound: any classical…
Quantum Fourier Transform: <j|QFT_N|k> = omega^{jk}/sqrt(N) with omega = exp(2*pi*i/N)
Quantum Fourier Transform framework. Setup: given an n-qubit register (N = 2^n basis states) the QFT is the unitary map QFT_N |k> =…
Hadamard-test / phase-kickback: P(0) = 1/2 + (1/2)*cos(phi) from H-controlled-U-H on eigenvector
Hadamard-test / phase-kickback framework. Setup: ancilla qubit |0> and an eigenvector register in state |psi> with U|psi> = e^{i*phi}|psi>.…
Simon's algorithm: hidden-subgroup N = {0, s} in (Z/2Z)^n gives |G| = |N|*|G/N| Lagrange factorisation
Simon's algorithm / abelian hidden-subgroup framework. Setup: black-box function f: (Z/2Z)^n -> (Z/2Z)^n promised to be either 1-to-1 or…
Theorem: QFT_2 = (1/sqrt(2))*[[1,1],[1,-1]] coincides with Hadamard; unitary check = I; det = -1
Theorem (QFT_2 = Hadamard coincidence): for N = 2, omega = exp(2*pi*i/2) = e^{i*pi} = -1. The 2x2 QFT matrix element is <j|QFT_2|k> =…
Theorem: Hadamard-test P(0) = 1/2 + (1/2)*cos(phi); P(0)|_{phi=0} = 1; P(0)|_{phi=pi} = 0
Theorem (Hadamard-test cosine readout): the probability of measuring |0> on the ancilla after H-controlled-U-H with U|psi> = e^{i*phi}|psi>…
Theorem: Simon n=2 hidden-subgroup {0, s} has |G|=4, |N|=2, |G/N|=2; Lagrange |G|=|N|*|G/N|
Theorem (Simon 2-bit Lagrange factorisation + complexity gap): for G = (Z/2Z)^2 with hidden subgroup N = {(0,0), (1,1)}, the Lagrange…
Shor (1994)
P Shor 1994 polynomial-time factoring + discrete-log; modern Gidney-Ekera 2021 estimates 20M qubits to break RSA-2048.
Grover (1996)
L Grover 1996 sqrt(N) unstructured-search; modern QAOA + amplitude-estimation extensions; quadratic speedup vs classical.
VQE (Peruzzo 2014)
Peruzzo-McClean-Shadbolt 2014 VQE; hybrid classical-quantum eigensolver; modern UCCSD ansatz + ADAPT-VQE Grimsley 2019.
Threshold theorem (1997)
Aharonov-Ben-Or 1997 + Knill-Laflamme-Zurek 1998 fault-tolerant quantum computing threshold ~1% error rate; basis of QEC architecture.
Quantum supremacy (Google 2019)
Arute-Google 2019 53-qubit Sycamore random-circuit-sampling; ~200 s vs claimed 10000 yr classical (IBM dispute); modern Sycamore 67 +…
Surface code (Kitaev 1997)
A Kitaev 1997 toric/surface code; ~1% threshold; modern Google Quantum AI 2024 below-threshold logical-qubit demonstration with d=7.
Deutsch (1985)
D Deutsch 1985 universal-quantum-Turing-machine; modern modern foundational text + 1992 Deutsch-Jozsa + 1994 Shor + Grover 1996.
Shor (1994)
P Shor 1994 polynomial-factoring quantum; modern modern foundational text + 2024 NIST PQC standards Kyber + Dilithium signature-base.
Grover (1996)
L Grover 1996 √N quantum-search-amplitude-amplification; modern modern foundational text + 2024 fault-tolerant-Grover circuit-cost analysis.
Teleportation (Bennett 1993)
C Bennett 1993 4-message teleportation; modern modern foundational text + Bouwmeester-Zeilinger 1997 + 2024 satellite-Micius 1200 km.
HHL (Harrow-Hassidim-Lloyd 2009)
A Harrow-A Hassidim-S Lloyd 2009 quantum-linear-systems exponential-speedup; modern modern foundational + 2024 dequantization Tang results.
VQE (Peruzzo 2014)
A Peruzzo 2014 + McClean 2016 VQE hybrid quantum-classical; modern modern foundational text + 2024 deep-VQE + adaptive-ansatz…