← AtlasesQuantum / Classical
Task definitions, connections, assumptions and primary references.
Tasks & methods
Each entry distinguishes its input access, required output, accuracy and costs. Some methods have several connection-specific guarantees.
Clifford circuits
Even highly entangled circuits can have an efficient classical description.
Definition
Sample computational-basis measurements after H, S and CNOT gates on a computational-basis input.
Task contract
- Input / access
- An explicit H/S/CNOT circuit, a computational-basis input, and computational-basis measurements.
- Required output
- Exact measurement samples and conditional probabilities, with a compact stabilizer description of the state.
- Precision
- The tableau simulation uses discrete arithmetic, so it needs no amplitude-rounding budget.
- Resources
- The displayed tableau algorithm uses O(n²) bits, O(n) work per elementary gate, and O(n²) work per measurement.
- Limits
- Arbitrary input states and non-Clifford gates are outside this guarantee. The compact description does not list all amplitudes.
Primary sources
Aaronson & Gottesman: Improved Simulation of Stabilizer Circuits (2004). Section III; tableau update rules
Stabilizer tableaux
Track Pauli constraints using bits instead of storing every amplitude.
Definition
A tableau records stabilizer generators, destabilizers and phases.
Task contract
- Input / access
- A stabilizer state represented by binary generators and phases, followed by explicit Clifford gates and basis measurements. For shadow records, the already acquired Clifford and outcome specify the stabilizer factor to store.
- Required output
- An updated compact stabilizer description, with probabilities or samples for the supported measurements. Shadow use stores a measurement record without simulating its acquisition.
- Precision
- Stabilizer algebra and measurement records are discrete and exact. A coherent sum of tableau states also needs phase-aware coefficient arithmetic.
- Resources
- O(n²) bits per stabilizer factor, with O(n) work per elementary gate and O(n²) per measurement in the displayed algorithm. An explicitly supplied coherent sum requires handling every term.
- Limits
- One tableau does not describe an arbitrary quantum state. Storing a shadow snapshot does not make its unknown input state classically simulable.
Primary sources
Aaronson & Gottesman: Improved Simulation of Stabilizer Circuits (2004). Section III; tableau update rules · Huang, Kueng & Preskill: Predicting Many Properties of a Quantum System from Very Few Measurements (2020). Theorem 1; Supplementary Proposition 1, Eq. (S38), and Lemma 3 (Pauli shadow norm 3^k). · Bravyi, Smith & Smolin: Trading classical and quantum computational resources (2016). Section IV and Appendix A: stabilizer decompositions and phase-aware overlap calculations. · Bravyi & Gosset: Improved classical simulation of quantum circuits dominated by Clifford gates (2016). Equations (2)–(4), v3; Section III and Appendices B–E for phase-aware stabilizer operations.
Small Schmidt rank
A small Schmidt rank throughout a computation keeps its tensor description compact.
Definition
Track a pure-state circuit whose maximum Schmidt rank χ over all bipartitions stays bounded at every step.
Task contract
- Input / access
- An explicit one- and two-qubit circuit with product input, whose maximum Schmidt rank χ over all bipartitions stays bounded throughout the computation.
- Required output
- A compact MPS state description and selected local or product-observable probabilities.
- Precision
- The stated rank supports an untruncated representation. Numerical rounding needs separate control, and truncating the representation requires an accumulated-error bound.
- Resources
- O(nχ²) coefficients and O(χ³) arithmetic per adjacent two-qubit gate. Bringing nonadjacent qubits together adds swap overhead.
- Limits
- The rank must remain small at intermediate steps. Low entropy or a simple final state alone does not establish this guarantee.
Primary sources
Vidal: Efficient Classical Simulation of Slightly Entangled Quantum Computations (2003). Lemmas 1–2 and Theorem 1
Matrix product states
Represent a state by a chain of tensors connected by small indices.
Definition
An MPS with bond dimension χ stores O(nχ²) coefficients for n qubits.
Task contract
- Input / access
- An available chain of tensors with bond dimension χ, plus specified gates or a product-form measurement event. Constructing the initial MPS is an additional requirement.
- Required output
- An updated compact state description or a selected event probability, depending on the connection. Time-evolution connections may return an approximate MPS.
- Precision
- Untruncated updates and contractions are exact arithmetic identities. Approximate time evolution needs separate budgets for time discretization, accumulated truncation error, and rounding.
- Resources
- O(nχ²) stored coefficients for qubits, with O(χ³) arithmetic per adjacent two-qubit gate and polynomial cost for a product-event contraction. A nearest-neighbor evolution sweep costs O(nχ³) at retained dimension χ.
- Limits
- Obtaining a useful small-bond MPS can be expensive. Fixed bond dimension does not guarantee accuracy when entanglement grows.
Primary sources
Vidal: Efficient Classical Simulation of Slightly Entangled Quantum Computations (2003). Lemmas 1–2 and Theorem 1 · Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction · Vidal: Efficient Simulation of One-Dimensional Quantum Many-Body Systems (2004). Equations (16), (22)–(25): local evolution, truncation error, Trotter error and update cost.
Circuit probability
Ask for the chance of a specified measurement event, rather than drawing a sample.
Definition
Given an explicit circuit, an efficiently given basis/product input and specified values of selected output bits, evaluate the probability of that event. Other output bits are ignored.
Task contract
- Input / access
- An explicit circuit, an efficiently specified basis or product input, and fixed values for selected output bits. Alternative connections may instead start from an already available statevector, MPS, or stabilizer decomposition.
- Required output
- One measurement-event probability, with unspecified output bits summed out. This is a scalar, not the full distribution or a sample.
- Precision
- Depends on the selected connection: exact arithmetic evaluation or an additive estimate with a stated confidence. Additive accuracy does not promise relative accuracy for rare events.
- Resources
- Depends on the representation: a general statevector scan takes O(2ⁿ) work, while an MPS contraction is polynomial in n and its bond dimension. Circuit tensor contraction has exponential dependence on wiring-graph width; coherent amplitude estimation requires controlled circuit access and O(1/ε) uses for additive ε at constant confidence.
- Limits
- A marginal is generally a sum of many squared amplitudes. No single displayed method provides efficient general exact probability evaluation, and producing the input representation is part of the cost.
Primary sources
Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction · Fatima & Markov: Faster Schrödinger-style simulation of quantum circuits (2020). Section 3: baseline Schrödinger simulation and statevector memory. · Vidal: Efficient Classical Simulation of Slightly Entangled Quantum Computations (2003). Lemmas 1–2 and Theorem 1 · Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application · Bravyi, Smith & Smolin: Trading classical and quantum computational resources (2016). Section IV and Appendix A: stabilizer decompositions and phase-aware overlap calculations. · Bravyi & Gosset: Improved classical simulation of quantum circuits dominated by Clifford gates (2016). Equations (2)–(4), v3; Section III and Appendices B–E for phase-aware stabilizer operations.
Tensor-network contraction
Sum over shared indices to turn a network of tensors into one number.
Definition
Circuit gates become tensors; matching wire indices are summed. Cost depends strongly on contraction width.
Task contract
- Input / access
- Explicit gate tensors and specified boundary conditions, or an already supplied tensor network. Probability calculations include the chosen event and input state; amplitude calculations fix both basis endpoints.
- Required output
- The scalar defined by that network, such as one complex amplitude, one event probability, or a chosen-angle QAOA expectation.
- Precision
- The contraction is an exact arithmetic identity. Finite-precision evaluation needs an error budget appropriate to the requested scalar.
- Resources
- For the circuit-event construction, cost is polynomial in circuit size times an exponential in the circuit wiring graph's treewidth. A QAOA cost term can instead be contracted over its backward light cone, giving polynomial total cost for fixed depth and degree.
- Limits
- The relevant graph includes individual gate instances, not just qubit connectivity. Large width is not a hardness proof, and computing one scalar does not automatically give a sampler.
Primary sources
Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction · Farhi, Goldstone & Gutmann: A Quantum Approximate Optimization Algorithm (2014). Sections I–II and V–VI; equations (2), (6), (12), (23)
Free fermions
Noninteracting fermions admit efficient classical measurement simulation.
Definition
Occupation-basis input, quadratic fermionic gates and occupation measurements.
Task contract
- Input / access
- An explicit quadratic fermionic circuit with occupation-basis input and occupation measurements.
- Required output
- Occupation probabilities, marginals, and samples obtained through determinant or Pfaffian formulas.
- Precision
- The guarantee counts arithmetic operations. Numerical gate parameters and accumulated rounding need a precision budget.
- Resources
- Polynomial arithmetic cost in the number of modes and circuit length.
- Limits
- Interacting fermions are excluded. The qubit matchgate correspondence used here requires nearest neighbors on a line.
Primary sources
Terhal & DiVincenzo: Classical Simulation of Noninteracting-Fermion Quantum Circuits (2002). Sections III–V · Jozsa & Miyake: Matchgates and classical simulation of quantum circuits (2008). Theorems 1–2 and Section 5: nearest-neighbor correspondence; multi-bit basis-input sampling uses Terhal–DiVincenzo.
Determinants & Pfaffians
Antisymmetry turns fermionic calculations into tractable matrix algebra.
Definition
Number-conserving amplitudes use determinants; broader Gaussian measurement formulas use Pfaffians.
Task contract
- Input / access
- Matrices derived from the specified free-fermion evolution and occupation event. Number-conserving amplitudes use determinants, while broader Gaussian measurement formulas use Pfaffians.
- Required output
- The required fermionic amplitudes or probabilities; conditional probability calculations support sampling in the stated free-fermion model.
- Precision
- Polynomial arithmetic bounds require separate numerical control when matrix entries are approximate.
- Resources
- The supported free-fermion probability and sampling calculations have polynomial cost in mode count and circuit length.
- Limits
- The similarity to permanent formulas is an analogy. Efficient determinant or Pfaffian calculations do not imply efficient permanent evaluation or boson sampling.
Primary sources
Terhal & DiVincenzo: Classical Simulation of Noninteracting-Fermion Quantum Circuits (2002). Sections III–V · Aaronson & Arkhipov: The Computational Complexity of Linear Optics (2013). Theorem 3.10; approximate-sampling conjectures
Boson sampling
Draw photon counts at the output of an ideal interferometer.
Definition
n indistinguishable single photons in distinct input modes of an m-mode passive, lossless interferometer.
Task contract
- Input / access
- An explicit m-by-n column-orthonormal interferometer matrix and n indistinguishable single photons occupying distinct input modes of an ideal passive, lossless device.
- Required output
- One output photon-occupation sample. The related permanent formula evaluates the probability of a specified occupation outcome.
- Precision
- The displayed classical sampler is exact in the arithmetic model. A finite-precision implementation needs separate error control.
- Resources
- The Clifford–Clifford algorithm uses O(n 2ⁿ + mn²) arithmetic per sample and O(m) additional working space beyond the input.
- Limits
- This upper bound is exponential in photon count and is not a hardness lower bound. Efficient Gaussian optical simulation has different input and measurement assumptions, so it does not cover ordinary boson sampling.
Primary sources
Clifford & Clifford: The Classical Complexity of Boson Sampling (2018). Theorem 1; Algorithm B · Aaronson & Arkhipov: The Computational Complexity of Linear Optics (2013). Theorem 3.10; approximate-sampling conjectures · Bartlett, Sanders, Braunstein & Nemoto: Efficient Classical Simulation of Continuous Variable Quantum Information Processes (2002). Theorem 2 and preceding finite-precision discussion; PRL 88, 097904. · Bartlett & Sanders: Efficient Classical Simulation of Optical Quantum Information Circuits (2002). Equation (7), main theorem, Gaussian-measurement and photon-counting discussion; PRL 89, 207903.
Permanent calculations
Like a determinant, but without alternating permutation signs.
Definition
Per(A) = Σσ ∏i Aᵢ,σ(i). For single-photon inputs, p(s)=|Per(A_s)|²/∏i sᵢ!, where A_s repeats output rows according to occupations sᵢ.
Task contract
- Input / access
- A specified matrix. For the boson-sampling connection, form the appropriate interferometer submatrix by repeating output rows according to the requested photon occupations.
- Required output
- The permanent scalar; its squared modulus with the occupation normalization gives a bosonic output probability. A sequence of related permanent calculations supports the displayed exact sampler.
- Precision
- The displayed sampling result uses exact arithmetic. Numerical permanent evaluation and cancellation require their own error control.
- Resources
- The displayed sampler takes O(n 2ⁿ + mn²) arithmetic per sample. That is the cost of the sampling algorithm, not a claimed bound for every arbitrary-matrix permanent task.
- Limits
- A permanent formula does not supply an efficient evaluator. Removing the determinant's alternating signs provides no transferable efficient-simulation guarantee.
Primary sources
Aaronson & Arkhipov: The Computational Complexity of Linear Optics (2013). Theorem 3.10; approximate-sampling conjectures · Clifford & Clifford: The Classical Complexity of Boson Sampling (2018). Theorem 1; Algorithm B · Terhal & DiVincenzo: Classical Simulation of Noninteracting-Fermion Quantum Circuits (2002). Sections III–V
Commuting-circuit amplitude
One circuit amplitude is a normalized partition function with complex weights.
Definition
For a two-body diagonal D, evaluate ⟨0ⁿ|H⊗ⁿ D H⊗ⁿ|0ⁿ⟩. This is an amplitude, not a sample.
Task contract
- Input / access
- A two-body diagonal circuit specified by real one- and two-qubit phase angles, surrounded by Hadamard gates, with all-zero input and output.
- Required output
- The complex return amplitude, equal to the associated complex Ising partition sum divided by 2ⁿ.
- Precision
- Additive error ε in the amplitude corresponds to additive error 2ⁿε in the unnormalized partition sum.
- Resources
- Translating the circuit description into the partition-sum description takes polynomial overhead. The scalar evaluation itself can still be expensive.
- Limits
- This connection concerns one amplitude, not sampling. Complex weights do not form an ordinary positive Boltzmann distribution, and the identity gives no efficient evaluation algorithm.
Primary sources
Bremner, Montanaro & Shepherd: Average-case Complexity versus Approximate Simulation of Commuting Quantum Computations (2016). Equation (1) and Appendix A
Complex Ising sum
Sum complex weights over all spin configurations.
Definition
For real Jᵢⱼ and hᵢ, evaluate Z = Σσ exp(i[Σi<j Jᵢⱼσᵢσⱼ + Σi hᵢσᵢ]), where σᵢ ∈ {−1,+1}.
Task contract
- Input / access
- An explicit graph with real coupling and field angles defining complex phase weights over all ±1 spin assignments.
- Required output
- The complex partition sum, or its normalized value after division by 2ⁿ. The normalized value equals the displayed commuting-circuit amplitude.
- Precision
- Normalization changes the additive-error scale by 2ⁿ. An ε-accurate normalized value is not an ε-accurate unnormalized sum.
- Resources
- Polynomial overhead converts between the phase-weight description and the two-body diagonal circuit. Evaluation is not supplied by that conversion.
- Limits
- This is a complex partition sum, not classical Ising energy minimization or an ordinary thermal sample. The equivalence asserts no efficient evaluator or sampler.
Primary sources
Bremner, Montanaro & Shepherd: Average-case Complexity versus Approximate Simulation of Commuting Quantum Computations (2016). Equation (1) and Appendix A
Integer factoring
A familiar number problem hides a periodicity problem.
Definition
Input: binary integer N. Output: its prime factors. This is a function problem, not a decision problem.
Task contract
- Input / access
- An integer N in binary. The represented quantum route implements modular arithmetic coherently, with classical preprocessing for even numbers and prime powers.
- Required output
- The prime factors of N as classical integers.
- Precision
- Exact integer factors with bounded failure probability; repetition reduces failure.
- Resources
- Shor's route uses quantum gates and classical work polynomial in log N. The reduction to order finding has polynomial classical overhead and polynomially many order-finding calls.
- Limits
- This is a function problem. The quantum upper bound does not prove a superpolynomial classical lower bound.
Primary sources
Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1997). Sections 3–4 (arithmetic and QFT), Section 5 (factoring), Section 6 (discrete logarithms)
Modular order finding
Find when repeated modular multiplication returns to one.
Definition
Given coprime a,N, return the least positive r such that aʳ = 1 mod N.
Task contract
- Input / access
- Coprime integers a,N. In the represented phase-estimation route, Uₐ|y⟩=|ay mod N⟩ on the valid subspace, the initial state is |1⟩, and controlled powers are implemented by modular exponentiation.
- Required output
- The least positive integer r with aʳ=1 mod N.
- Precision
- Exact r with bounded failure probability. O(log N) phase bits, continued fractions and repetition support reconstruction.
- Resources
- Polynomial gate and classical cost in log N in the represented factoring construction.
- Limits
- The bound uses efficient modular controlled powers. Generic phase estimation does not supply arbitrary powers at this cost.
Primary sources
Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1997). Sections 3–4 (arithmetic and QFT), Section 5 (factoring), Section 6 (discrete logarithms) · Cleve, Ekert, Macchiavello & Mosca: Quantum Algorithms Revisited (1998). Phase estimation and order finding
Phase estimation
Read an eigenvalue phase using controlled powers of a unitary.
Definition
For U|ψ⟩ = exp(2πiθ)|ψ⟩, estimate θ. A superposition gives eigenphases according to its spectral weights.
Task contract
- Input / access
- A prepared eigenstate of U, or a state with specified spectral overlap; controlled powers U^(2ʲ). Energy estimation also needs controlled Hamiltonian evolution and a known energy interval.
- Required output
- An m-bit phase estimate modulo 1. Superposed inputs produce eigenphases according to their spectral weights.
- Precision
- O(2⁻ᵐ) phase error at constant confidence in the ideal construction; controlled-evolution and gate errors require separate budgets.
- Resources
- O(m²) ideal Fourier gates plus m controlled powers. Implementing powers by repetition takes 2ᵐ−1 controlled-U uses; state preparation is additional.
- Limits
- Efficient Fourier transforms do not make arbitrary controlled powers free. This does not automatically prepare a useful eigenstate or the ground state.
Primary sources
Cleve, Ekert, Macchiavello & Mosca: Quantum Algorithms Revisited (1998). Phase estimation and order finding · Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation
HHL linear solver
Use eigenvalue information to apply an inverse matrix to an encoded vector.
Definition
The original algorithm combines Hamiltonian simulation, phase estimation, controlled rotation and amplification.
Preparation, output & cost
- Input / access
- Coherent sparse-matrix access, a conditioning promise, and a circuit preparing |b⟩ with inverse access.
- Required output
- A normalized solution state. Vector coordinates and the unnormalized solution norm are not returned; observable estimates require additional measurements.
- Costs
- Preparation, sparsity, conditioning and accuracy all enter the cost. Loading and readout are extra; no general end-to-end exponential speedup is claimed.
Task contract
- Input / access
- N×N Hermitian A, s nonzeros per row; coherent reversible access to nonzero indices and values; eigenvalue magnitudes in [1/κ,1]; |b⟩ preparation unitary and its inverse, at cost T_B.
- Required output
- Normalized |x⟩, not N printed coordinates.
- Precision
- Euclidean state error ε for the prepared solution with workspace reset; measurement error is separate.
- Resources
- Original bound Õ(κ T_B + log N · s²κ²/ε), under the stated access model. Historical, not optimal.
- Limits
- Arbitrary data loading and full-vector readout are excluded. No unconditional exponential classical separation is claimed.
Primary sources
Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation
Linear-system solution state
Prepare the normalized solution as amplitudes. Reading all its entries is another task.
Definition
Prepare |x⟩ = A⁻¹|b⟩ / ‖A⁻¹b‖. The output does not include a classical list of coordinates or its norm.
Task contract
- Input / access
- Hermitian A and coherent preparation of |b⟩ with inverse access. The represented HHL route requires sparse index/value access; the represented QSVT route requires an exact block encoding. Both impose a condition-number promise.
- Required output
- Normalized |x⟩ = A⁻¹|b⟩ / ‖A⁻¹b‖, rather than all N coordinates or the solution norm.
- Precision
- Euclidean error ε in the prepared state. Each construction must budget approximation error before normalization; observable measurement has a separate error budget.
- Resources
- Depends on the selected construction: HHL charges sparsity, κ, ε and |b⟩ preparation; the shown QSVT construction charges polynomial degree, encoding queries and amplification. Select a connection to see its resource bound.
- Limits
- The two access models are different. Input loading, normalization-dependent success and classical readout can remove an apparent advantage; neither route returns a full classical vector.
Primary sources
Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation · Gilyén, Su, Low & Wiebe: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2019). Corollary 18 (real polynomial SVT), Theorem 41 (pseudoinverse), Section 4.1 (block encoding), Theorem 56 (Hermitian polynomial transformation); STOC 2019, preprint 2018. Section 5.3 and Corollary 64 (Gibbs filtering). · Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
Observable estimation
Estimate one accessible statistic of a prepared state.
Definition
For a bounded efficiently measurable M, estimate ⟨x|M|x⟩ to a stated additive error.
Task contract
- Input / access
- Fresh preparations of the state and efficient measurement access to a bounded Hermitian observable. The readout connection uses ‖M‖≤1; Pauli-sum energy estimation and controlled-unitary tests specify other access in their connections.
- Required output
- One classical expectation estimate, such as ⟨x|M|x⟩ or a trial state’s energy.
- Precision
- For the normalized readout route: additive δ at constant confidence. State-preparation error must fit the bias budget.
- Resources
- O(δ⁻²) independent preparations for the normalized readout route, each at its preparation cost. Decomposition weights and controlled operations add route-specific costs.
- Limits
- An arbitrary dense observable is not automatically easy to measure. Estimating a chosen state’s energy or cut objective does not certify the optimum or reconstruct the state.
Primary sources
Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation · Farhi, Goldstone & Gutmann: A Quantum Approximate Optimization Algorithm (2014). Sections I–II and V–VI; equations (2), (6), (12), (23) · Peruzzo et al.: A Variational Eigenvalue Solver on a Photonic Quantum Processor (2014). Results: Quantum expectation estimation; Quantum variational eigensolver · Aharonov, Jones & Landau: A Polynomial Quantum Algorithm for Approximating the Jones Polynomial (2009). Section 2.2 (Hadamard test); Section 3.3 (averaging and error); Algorithmica 55, 395–421, preprint 2005.
Circuit acceptance
Distinguish a circuit that usually accepts from one that usually rejects.
Definition
Promise p(accept) ≥ 2/3 or p(accept) ≤ 1/3. Return which case holds.
Task contract
- Input / access
- An explicit circuit promised to accept with probability at least 2/3 or at most 1/3.
- Required output
- One bit identifying the promised case.
- Precision
- The probability-estimation or simulation error and failure probability must preserve the decision margin.
- Resources
- The shown reduction uses one suitable probability-estimation call plus polynomial overhead. Its evaluation cost depends on the selected simulation or quantum construction.
- Limits
- The gap promise is essential. Exact probability values and exponentially fine amplitude estimates are not required.
Primary sources
Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction · Aharonov, van Dam, Kempe, Landau, Lloyd & Regev: Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation (2007). Theorem 1.1 and circuit-to-adiabatic construction; Theorem 1.3 gives a geometric variant; preprint first posted in 2004
Circuit sampling
Draw one output bit string from a specified circuit.
Definition
Explicit n-qubit, constant-arity unitary circuit on |0ⁿ⟩, followed by computational-basis measurement.
Task contract
- Input / access
- An explicit n-qubit circuit of constant-arity unitary gates, a basis input, and computational-basis output measurement.
- Required output
- A bit string drawn from the circuit's output distribution. A statevector simulator also computes the complete amplitude vector along the way.
- Precision
- The displayed general classical simulator is exact in the arithmetic model. Numerical gate representation and rounding need an error budget.
- Resources
- Direct statevector simulation takes O((T+1) 2ⁿ) arithmetic, including sample preparation, and stores O(2ⁿ) complex entries for T gates.
- Limits
- This exponential upper bound is not a hardness proof. Efficient simulation guarantees elsewhere require additional circuit or state structure.
Primary sources
Fatima & Markov: Faster Schrödinger-style simulation of quantum circuits (2020). Section 3: baseline Schrödinger simulation and statevector memory.
Statevector simulator
Store every amplitude. General and direct, but memory doubles with each qubit.
Definition
Schrödinger simulation updates an explicit vector of 2ⁿ complex amplitudes.
Task contract
- Input / access
- An explicit basis input and constant-arity circuit, represented by its gate list. The direct pure-state method stores every amplitude.
- Required output
- The full output vector, from which amplitudes, basis samples, and event probabilities can be obtained.
- Precision
- Gate updates are exact in the arithmetic model. Amplitude readout inherits vector error, and event probabilities also require controlled summation error.
- Resources
- O(2ⁿ) complex entries and O((T+1) 2ⁿ) arithmetic including sample preparation. Once the vector exists, one amplitude is an O(1) lookup, while a general marginal can require an O(2ⁿ) scan.
- Limits
- Fast readout after simulation does not remove the exponential preparation and storage cost. General noisy mixed-state propagation is a separate density-matrix method.
Primary sources
Fatima & Markov: Faster Schrödinger-style simulation of quantum circuits (2020). Section 3: baseline Schrödinger simulation and statevector memory. · Jones, Brown, Bush & Benjamin: QuEST and High Performance Simulation of Quantum Computers (2019). Section II.B.1, Eq. (2): full density matrix stored as a 2n-qubit vector; local updates imply the stated exponential arithmetic cost. Scientific Reports 9, 10736.
Clifford + T circuits
A few non-Clifford gates can be cheaper to simulate than a full statevector.
Definition
Sample selected output bits of an explicit H/S/CNOT/T circuit with n qubits, c Clifford gates and t T gates, starting from |0ⁿ⟩.
Task contract
- Input / access
- An explicit H/S/CNOT/T circuit starting from all-zero input, with n qubits, c Clifford gates, t T gates, and w selected output bits.
- Required output
- A sample from a distribution within ℓ₁ error ε of the requested output distribution.
- Precision
- The Bravyi–Gosset bound controls distribution error. It does not promise relative accuracy for each output probability.
- Resources
- The displayed historical algorithm has polynomial factors in n, c, t, and w, with a non-Clifford contribution proportional to 2^(γt) t³w³/ε⁴ up to logarithmic factors, where γ = −2 log₂(cos(π/8)) ≈ 0.228. The full expression is given on the simulation connection.
- Limits
- The guarantee is exponential in T count and does not claim the best current exponent. Clifford-only tableau simulation cannot simply absorb arbitrary T gates.
Primary sources
Bravyi & Gosset: Improved classical simulation of quantum circuits dominated by Clifford gates (2016). Equations (2)–(4), v3; Section III and Appendices B–E for phase-aware stabilizer operations. · Aaronson & Gottesman: Improved Simulation of Stabilizer Circuits (2004). Section III; tableau update rules
Stabilizer decompositions
Represent a state as a coherent sum of simpler stabilizer states.
Definition
|ψ⟩ = Σⱼ cⱼ|φⱼ⟩, with χ stabilizer terms, complex coefficients and relative phases retained.
Task contract
- Input / access
- An explicitly supplied coherent decomposition into χ stabilizer states with complex coefficients and retained relative phases. Sampling via magic-state decompositions starts from the specified Clifford + T circuit instead.
- Required output
- An updated coherent decomposition or one event probability, depending on the operation. The Clifford + T connection separately supplies an approximate sampling algorithm.
- Precision
- Exact stabilizer algebra still requires controlled coefficient arithmetic. Probability readout includes cross terms, and approximate decompositions alone do not guarantee relative accuracy for rare events.
- Resources
- Clifford updates cost χ times polynomial overhead, and direct event evaluation through pairwise overlaps costs O(χ² poly(n)). Producing a useful decomposition is an additional cost.
- Limits
- A coherent sum is not a probabilistic mixture. Discarding phase or interference between its terms changes the state and its probabilities.
Primary sources
Bravyi, Smith & Smolin: Trading classical and quantum computational resources (2016). Section IV and Appendix A: stabilizer decompositions and phase-aware overlap calculations. · Bravyi & Gosset: Improved classical simulation of quantum circuits dominated by Clifford gates (2016). Equations (2)–(4), v3; Section III and Appendices B–E for phase-aware stabilizer operations. · Aaronson & Gottesman: Improved Simulation of Stabilizer Circuits (2004). Section III; tableau update rules
Matchgates
These qubit gates hide a free-fermion calculation.
Definition
G(A,B) acts as A and B in even/odd parity sectors, with det A = det B. Gates act on adjacent qubits on a line, with computational-basis input/output.
Task contract
- Input / access
- Explicit equal-determinant matchgates acting on adjacent qubits on a line, with computational-basis input and output measurement.
- Required output
- The same measurement distribution as the corresponding quadratic fermionic circuit, enabling basis-output probabilities, marginals, and samples.
- Precision
- The model correspondence is exact. Numerical gate parameters and simulation arithmetic require error control.
- Resources
- Polynomial description translation followed by polynomial free-fermion simulation in system size and circuit length.
- Limits
- Arbitrary nonadjacent qubit matchgates do not inherit this guarantee. Adding next-nearest-neighbor gates permits universal computation with encoding.
Primary sources
Jozsa & Miyake: Matchgates and classical simulation of quantum circuits (2008). Theorems 1–2 and Section 5: nearest-neighbor correspondence; multi-bit basis-input sampling uses Terhal–DiVincenzo. · Terhal & DiVincenzo: Classical Simulation of Noninteracting-Fermion Quantum Circuits (2002). Sections III–V
Hamiltonian simulation
Implement physical time evolution on a quantum computer.
Definition
Implement exp(−iHt) for a time-independent Hermitian H, with a specified operator-norm error. Access to H and the input state must be supplied.
Task contract
- Input / access
- A time-independent Hermitian H, time t and a supplied input state. Access depends on the method: implementable term exponentials, coherent LCU primitives, or a block encoding with controlled/inverse access.
- Required output
- A circuit implementing approximate exp(−iHt) on the supplied state.
- Precision
- Specified operator-norm error ε. Synthesis errors, ancilla failure and controlled-use requirements are budgeted by the selected construction.
- Resources
- Depends on the selected connection: product formulas count term evolutions; LCU and qubitization count their encoding or selected-term queries. Query implementation and input preparation remain costs.
- Limits
- These are quantum simulation routes, not efficient classical descriptions of arbitrary dynamics. None automatically provides a useful initial state or cheap arbitrary Hamiltonian access.
Primary sources
Childs, Su, Tran, Wiebe & Zhu: Theory of Trotter Error with Commutator Scaling (2021). Proposition 15, first-order Lie–Trotter commutator error bound; published as Theory of Trotter Error with Commutator Scaling. · Berry, Childs, Cleve, Kothari & Somma: Simulating Hamiltonian dynamics with a truncated Taylor series (2015). Section II, equations (6)–(10); Section III, equations (18)–(23); PRL 114, 090502. · Low & Chuang: Hamiltonian Simulation by Qubitization (2019). Theorems 1–4; equation (8) and Section 6; Quantum 3, 163.
Trotter formulas
Alternate easy evolutions to approximate their combined dynamics.
Definition
For H = Σⱼ Hⱼ, repeat short-time exponentials of individual terms. The algebraic formula also underlies classical numerical methods.
Task contract
- Input / access
- A decomposition H=ΣⱼHⱼ and implementable short-time term evolutions. The MPS application additionally assumes a one-dimensional nearest-neighbor system and an initial MPS.
- Required output
- An approximate evolution unitary in the quantum connection; an approximate classical evolved-state description in the MPS connection.
- Precision
- First-order unitary error is bounded by t²C/(2r), C=Σⱼ<ₖ‖[Hⱼ,Hₖ]‖. MPS evolution additionally accumulates truncation error.
- Resources
- For L terms, Lr term evolutions. A nearest-neighbor MPS sweep costs O(nχ³) arithmetic at retained bond dimension χ. These count different implementations.
- Limits
- Fixed MPS bond dimension does not guarantee accuracy. The product identity does not make arbitrary dynamics efficiently classically simulable.
Primary sources
Childs, Su, Tran, Wiebe & Zhu: Theory of Trotter Error with Commutator Scaling (2021). Proposition 15, first-order Lie–Trotter commutator error bound; published as Theory of Trotter Error with Commutator Scaling. · Vidal: Efficient Simulation of One-Dimensional Quantum Many-Body Systems (2004). Equations (16), (22)–(25): local evolution, truncation error, Trotter error and update cost. · Vidal: Efficient Classical Simulation of Slightly Entangled Quantum Computations (2003). Lemmas 1–2 and Theorem 1
Circuit amplitude
One complex number, including its phase, for a specified input and output.
Definition
Evaluate ⟨y|U|x⟩ for an explicit circuit U and basis strings x,y. Its squared modulus is the probability of that complete output.
Task contract
- Input / access
- An explicit circuit and specified basis input and output strings. The Hadamard-test estimator additionally needs controlled circuit implementation; the signed-path connection restricts gates to Hadamard and Toffoli.
- Required output
- One complex amplitude, retaining phase. Its squared modulus gives the probability of that complete output string, not a general marginal.
- Precision
- Depends on the selected connection: exact arithmetic evaluation or additive estimates of real and imaginary parts. Amplitude error η gives complete-outcome probability error at most 2η+η².
- Resources
- Reading an already computed vector entry is constant work, but preparing that vector can be exponential. Tensor cost depends on contraction width, signed-path enumeration is exponential in Hadamard count, and Hadamard testing uses O(ε⁻² log(1/δ)) controlled circuit calls for component error ε and joint failure δ.
- Limits
- Additive estimation does not promise relative accuracy for exponentially small amplitudes. One amplitude does not supply the full output distribution or a sampler.
Primary sources
Dawson, Haselgrove, Hines, Mortimer, Nielsen & Osborne: Quantum computing and polynomial equations over the finite field Z₂ (2005). Equations (3)–(6): signed path counts over F₂; Section V discusses limitations. · Fatima & Markov: Faster Schrödinger-style simulation of quantum circuits (2020). Section 3: baseline Schrödinger simulation and statevector memory. · Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction · Aharonov, Jones & Landau: A Polynomial Quantum Algorithm for Approximating the Jones Polynomial (2009). Section 2.2 (Hadamard test); Section 3.3 (averaging and error); Algorithmica 55, 395–421, preprint 2005.
Path sums
Add contributions from alternative computational histories, retaining interference.
Definition
The signed path formulation shown here uses Hadamard and Toffoli gates.
Task contract
- Input / access
- An explicit Hadamard/Toffoli circuit with h Hadamard gates and fixed basis endpoints.
- Required output
- The real amplitude as the difference between positive and negative path counts, scaled by 2^(−h/2).
- Precision
- The displayed construction uses exact integer counts. Approximate counting requires a separate bound on cancellation error.
- Resources
- Direct enumeration costs O(2ʰ poly(circuit size)). The Boolean-equation translation has polynomial construction cost plus two exact counting calls.
- Limits
- The signed-path formulation shown here does not cover arbitrary complex gates without a different weighted representation. It supplies no efficient generic Monte Carlo method.
Primary sources
Dawson, Haselgrove, Hines, Mortimer, Nielsen & Osborne: Quantum computing and polynomial equations over the finite field Z₂ (2005). Equations (3)–(6): signed path counts over F₂; Section V discusses limitations.
Boolean solution counting
Counting solutions can recover interference as a difference of two counts.
Definition
Count satisfying assignments to a polynomial-size system of equations over the field F₂.
Task contract
- Input / access
- A polynomial-size system of equations over F₂. The circuit connection builds systems for positive and negative Hadamard/Toffoli histories while retaining wire variables or compact arithmetic-circuit descriptions.
- Required output
- The exact number of satisfying assignments. Two such counts recover the displayed circuit amplitude after subtraction and normalization.
- Precision
- Exact counts are required by the displayed reduction. Approximate counts need additional cancellation control before they can guarantee amplitude accuracy.
- Resources
- Constructing the two circuit-derived systems takes polynomial overhead. Solving the counting tasks is not supplied by the reduction.
- Limits
- Counting assignments is different from finding one assignment or deciding whether one exists. Expanding compact expressions into all monomials can destroy the polynomial description bound.
Primary sources
Dawson, Haselgrove, Hines, Mortimer, Nielsen & Osborne: Quantum computing and polynomial equations over the finite field Z₂ (2005). Equations (3)–(6): signed path counts over F₂; Section V discusses limitations.
Classical shadows
Reuse randomized measurement records to estimate many properties.
Definition
A classical estimator built from repeated quantum measurements. It requires physical copies or an independently available sampler.
Task contract
- Input / access
- Independent physical copies of ρ, or an independently available measurement sampler; the displayed guarantee uses randomized local-Pauli measurements for M fixed Pauli strings of weight at most k.
- Required output
- Classical records and estimates of the specified Pauli expectations.
- Precision
- Additive ε simultaneously for all M fixed Pauli strings, with failure at most δ.
- Resources
- The displayed local-Pauli guarantee uses O(3ᵏ log(M/δ)/ε²) copies. Classical processing also depends on M and k.
- Limits
- The method does not supply the measurement outcomes by classical circuit simulation. This bound does not cover arbitrary k-local observables or full tomography.
Primary sources
Huang, Kueng & Preskill: Predicting Many Properties of a Quantum System from Very Few Measurements (2020). Theorem 1; Supplementary Proposition 1, Eq. (S38), and Lemma 3 (Pauli shadow norm 3^k). · Aaronson & Gottesman: Improved Simulation of Stabilizer Circuits (2004). Section III; tableau update rules
Many Pauli observables
Estimate many correlations from the same batch of measurements.
Definition
Estimate tr(Pⱼρ) for M specified Pauli strings, each acting nontrivially on at most k qubits.
Task contract
- Input / access
- Independent copies of ρ; M fixed Pauli strings of weight ≤k. The displayed route uses randomized local-Pauli measurements.
- Required output
- M expectation estimates.
- Precision
- Additive ε simultaneously, with failure ≤δ.
- Resources
- O(3ᵏ log(M/δ)/ε²) copies; classical processing also depends on M and k.
- Limits
- Not full tomography or a classical circuit simulator. Arbitrary k-local observables have a different bound.
Primary sources
Huang, Kueng & Preskill: Predicting Many Properties of a Quantum System from Very Few Measurements (2020). Theorem 1; Supplementary Proposition 1, Eq. (S38), and Lemma 3 (Pauli shadow norm 3^k).
Shor’s algorithms
Use hidden periodicity to find factors and discrete logarithms.
Definition
Efficient quantum arithmetic and Fourier measurements, followed by classical number-theoretic reconstruction.
Task contract
- Input / access
- Choose the represented arithmetic problem: a binary integer N for factoring, or a prime modulus p, generator g and h for the discrete-logarithm route. Both require efficient reversible modular arithmetic.
- Required output
- Classical prime factors of N, or the exponent x modulo p−1 with h=gˣ, for the selected problem. Fourier measurements feed classical number-theoretic reconstruction.
- Precision
- Exact integer outputs with bounded failure probability. In the factoring route, an approximate QFT with inverse-polynomial total error in input bit length suffices; factors are checked classically.
- Resources
- Polynomial quantum gates and classical work in log N for factoring or log p for the represented discrete-logarithm route. Arithmetic and Fourier implementation costs are included in the algorithm.
- Limits
- The QFT alone does not return factors. Other group presentations need their own efficient arithmetic and encoding assumptions, and the factoring upper bound is not a classical hardness proof.
Primary sources
Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1997). Sections 3–4 (arithmetic and QFT), Section 5 (factoring), Section 6 (discrete logarithms) · Coppersmith: An approximate Fourier transform useful in quantum factoring (1994). IBM report RC 19642 (1994), archived 2002; Fourier circuit construction
Discrete logarithm
Reverse exponentiation in a finite cyclic group.
Definition
Given g, h=gˣ, and the order r of g, return x modulo r. Efficient coherent group arithmetic is required for the quantum algorithm.
Task contract
- Input / access
- A finite cyclic group element g of known order r and h=gˣ. The hidden-subgroup route assumes unique encodings and coherent group operations. The represented Shor application specializes to prime modulus p and a generator of order p−1.
- Required output
- The exponent x modulo r as a classical integer.
- Precision
- An exact exponent with bounded failure probability for the represented algorithms.
- Resources
- The hidden-subgroup reduction has polynomial overhead in log r plus group-operation cost. The represented prime-modulus quantum application has polynomial cost in log p.
- Limits
- Known group order, encoding and efficient coherent arithmetic are explicit access assumptions. Costs for a particular presentation do not transfer automatically to other groups.
Primary sources
Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1997). Sections 3–4 (arithmetic and QFT), Section 5 (factoring), Section 6 (discrete logarithms) · Mosca & Ekert: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer (1999). Section 2 (input presentation and discrete-log example); Sections 3–4 (Fourier/eigenvalue sampling)
Quantum Fourier transform
Expose periodic structure in quantum amplitudes.
Definition
For a finite abelian group G, its quantum Fourier transform maps computational basis states to superpositions indexed by characters of G. For the cyclic example N=2ⁿ, map |x⟩ to N⁻¹ᐟ² Σy exp(2πixy/N)|y⟩. For (Z₂)ⁿ the transform is H⊗n, as used by Simon. These are distinct group transforms. The output remains a quantum state; efficient implementations require an appropriate group representation.
Task contract
- Input / access
- A quantum register indexed by a finite abelian group with an appropriate representation. Distinguish the cyclic transform on N=2ⁿ labels from the transform on (Z₂)ⁿ used by Simon's algorithm.
- Required output
- A quantum state whose amplitudes have undergone the group Fourier transform, indexed by characters. Measurement and application-specific processing are additional operations.
- Precision
- Ideal transforms are exact; gate and transform-approximation errors require a budget for the selected application. In the cyclic m-qubit construction, truncating small rotations gives transform error δ.
- Resources
- For the cyclic N=2ⁿ transform, O(n²) ideal rotation gates, or O(n log(n/δ)) for the stated truncated approximation, plus finite-gate synthesis. For (Z₂)ⁿ the transform is H⊗n. The selected application also pays for oracle calls, controlled powers or arithmetic.
- Limits
- The output is a state, not all classical Fourier coefficients. State loading and coefficient readout are not free. A fast transform does not make arbitrary controlled powers efficient or imply general classical simulation.
Primary sources
Cleve, Ekert, Macchiavello & Mosca: Quantum Algorithms Revisited (1998). Phase estimation and order finding · Coppersmith: An approximate Fourier transform useful in quantum factoring (1994). IBM report RC 19642 (1994), archived 2002; Fourier circuit construction · Simon: On the Power of Quantum Computation (1997). Definition 3.1 and Theorem 3.2; Fourier-twice routine and linear equations; SIAM J. Comput. 26(5), 1474–1483. · Mosca & Ekert: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer (1999). Section 2 (input presentation and discrete-log example); Sections 3–4 (Fourier/eigenvalue sampling) · Cooley & Tukey: An Algorithm for the Machine Calculation of Complex Fourier Series (1965). Mathematics of Computation 19, 297–301; equations (1)–(7)
Fast Fourier transform
Compute all Fourier coefficients of a classical vector.
Definition
The Cooley–Tukey algorithm evaluates a length-N discrete Fourier transform in O(N log N) arithmetic operations for N=2ⁿ.
Task contract
- Input / access
- An explicit classical vector of length N, with N=2ⁿ for the represented Cooley–Tukey bound.
- Required output
- All N classical discrete Fourier coefficients, with normalization and sign chosen by convention.
- Precision
- Numerical approximation and arithmetic precision must be budgeted; the displayed operation count does not fix a bit-precision guarantee.
- Resources
- O(N log N) arithmetic operations for the represented power-of-two transform.
- Limits
- The QFT analogy compares a shared matrix in different input/output representations. It does not make explicit classical coefficient output equivalent to preparing a transformed quantum state.
Primary sources
Cooley & Tukey: An Algorithm for the Machine Calculation of Complex Fourier Series (1965). Mathematics of Computation 19, 297–301; equations (1)–(7) · Coppersmith: An approximate Fourier transform useful in quantum factoring (1994). IBM report RC 19642 (1994), archived 2002; Fourier circuit construction
Abelian hidden subgroup
Recover the symmetry that makes a function repeat.
Definition
Known finite product of cyclic groups G; coherent f is constant on, and distinct between, cosets of H. Output generators for H.
Task contract
- Input / access
- A finite abelian group G given as a known product of cyclic groups, and coherent access to f that is constant on each coset of H and distinct between cosets.
- Required output
- Classical generators for the hidden subgroup H.
- Precision
- Exact subgroup generators with bounded failure probability. Fourier approximation error must be budgeted across samples.
- Resources
- The represented Fourier-sampling route is polynomial in log|G| and encoding size, charging the cost of the oracle.
- Limits
- The group presentation and hiding promise are required. This does not solve arbitrary nonabelian hidden-subgroup problems.
Primary sources
Mosca & Ekert: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer (1999). Section 2 (input presentation and discrete-log example); Sections 3–4 (Fourier/eigenvalue sampling) · Kitaev: Quantum measurements and the Abelian Stabilizer Problem (1995). Abelian stabilizer and Fourier-transform algorithms
Grover's search
Find a marked candidate with fewer oracle checks.
Definition
Repeated reflections amplify marked candidates in a uniform superposition. Query savings exclude the cost of building the checking oracle.
Task contract
- Input / access
- A coherent Boolean marking oracle, efficient uniform-state preparation and the required reflections. SAT use supplies a reversible formula checker.
- Required output
- A marked candidate; unknown-count schedules also support a bounded-error report that none exists.
- Precision
- Constant success probability in the displayed bounds, with suitable repetition or schedule. Returned SAT witnesses can be checked independently.
- Resources
- For exactly one marked item among N, O(√N) oracle calls; with known t>0 marked items, O(√(N/t)) iterations. SAT over n variables has the displayed worst-case O(2ⁿᐟ²) predicate-call bound.
- Limits
- Oracle construction and evaluation are not free. Unknown t needs a schedule and empty cases need a timeout. No advantage over the best classical SAT solver is asserted.
Primary sources
Grover: A fast quantum mechanical algorithm for database search (1996). Search algorithm and success analysis · Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application · Boyer, Brassard, Høyer & Tapp: Tight bounds on quantum searching (1998). Sections 3–4: multiple/unknown solutions and the zero-solution timeout
Unstructured search
Find one item that passes a yes/no check.
Definition
Oracle f on N candidates. Output x with f(x)=1, or report none with bounded error.
Task contract
- Input / access
- A Boolean oracle on N candidates; quantum use requires coherent access and efficient uniform preparation. The displayed Grover connection specializes to exactly one marked item.
- Required output
- An index x with f(x)=1, or a bounded-error report that none exists.
- Precision
- Bounded error. The exactly-one promise in the displayed connection excludes the empty case; unknown counts need the search schedule described at Grover.
- Resources
- O(√N) quantum oracle calls in the represented exactly-one case. Construction and evaluation costs of an instance’s oracle are additional.
- Limits
- The search interface does not grant free access to an arbitrary classical database. Structure in an explicit input may permit different algorithms.
Primary sources
Boyer, Brassard, Høyer & Tapp: Tight bounds on quantum searching (1998). Sections 3–4: multiple/unknown solutions and the zero-solution timeout · Grover: A fast quantum mechanical algorithm for database search (1996). Search algorithm and success analysis
SAT search
Find values of Boolean variables that satisfy every clause.
Definition
For n-variable formulas, search N=2ⁿ assignments. Return a witness or bounded-error none.
Task contract
- Input / access
- An explicit Boolean formula of size L on n variables, with a reversible checker for assignments when using the quantum route.
- Required output
- A satisfying assignment, or a bounded-error report that none exists.
- Precision
- Exact checking of a returned assignment; the algorithm may fail with a specified bounded probability.
- Resources
- The displayed quantum search route uses O(2ⁿᐟ²) predicate calls in the worst case, plus oracle construction and gate overhead polynomial in the formula size.
- Limits
- This remains exponential in n. The unstructured-search route does not exploit all formula structure and is not a claimed improvement over the best classical SAT algorithms.
Primary sources
Grover: A fast quantum mechanical algorithm for database search (1996). Search algorithm and success analysis · Boyer, Brassard, Høyer & Tapp: Tight bounds on quantum searching (1998). Sections 3–4: multiple/unknown solutions and the zero-solution timeout
Amplitude amplification
Boost a successful quantum branch without measuring each attempt.
Definition
Given preparation A, inverse A⁻¹, and a success reflection, amplify initial success probability a>0.
Task contract
- Input / access
- A coherent preparation A, its inverse, and reflections identifying the initial and success subspaces; initial success probability a>0.
- Required output
- Increased success probability for the same target branch, rather than an estimate of its probability.
- Precision
- The represented bounds use ideal reflections with an appropriate iteration count. Approximate state preparation and rotations need the selected application’s error budget.
- Resources
- The represented known-success-fraction search uses O(1/√a) iterations, each using A, A⁻¹ and reflections. Unknown success fractions require a schedule; HHL also charges condition-dependent preparation cost.
- Limits
- Ordinary samples do not give inverse or reflection access. Zero success cannot be amplified, and estimating a probability is a different task.
Primary sources
Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application · Boyer, Brassard, Høyer & Tapp: Tight bounds on quantum searching (1998). Sections 3–4: multiple/unknown solutions and the zero-solution timeout · Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation
Amplitude estimation
Estimate how often a quantum circuit succeeds.
Definition
Estimate a=‖ΠA|0⟩‖² using coherent preparation A, its inverse and the success reflection. The original phase-estimation construction also requires controlled applications of the amplification iterate.
Preparation, output & cost
- Input / access
- Coherent preparation and its inverse, a success reflection, and controlled operations for the original construction.
- Required output
- A classical estimate with additive error, not an exact probability or guaranteed relative accuracy for rare events.
- Costs
- O(1/ε) coherent uses at constant confidence. Each use costs preparation, control and synthesis; ordinary samples do not provide this access.
Task contract
- Input / access
- Coherent preparation A, A⁻¹ and a success reflection. The original phase-estimation construction also requires controlled applications of the amplification iterate.
- Required output
- A classical estimate of a=‖ΠA|0⟩‖²; represented applications estimate a probability, bounded mean, additive count or overlap.
- Precision
- Additive ε at constant confidence in the displayed route. Confidence amplification, rotation error and gate error are separate budgets.
- Resources
- O(1/ε) coherent iterate or preparation/inverse uses at constant confidence; boosting confidence adds overhead. Charge each state-preparation, value-oracle, control and synthesis operation.
- Limits
- Ordinary independent samples do not provide this access. The query saving is not an end-to-end runtime comparison, and additive accuracy does not imply useful relative accuracy for tiny probabilities.
Primary sources
Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application · Montanaro: Quantum speedup of Monte Carlo methods (2015). Section 1; Algorithm 1 and Theorem 3 for bounded outputs · Brassard, Høyer & Tapp: Quantum Counting (1998). Section 2, Theorems 2.1–2.3 (amplification); Section 4, Theorem 4.1 (counting error) · Aharonov, Jones & Landau: A Polynomial Quantum Algorithm for Approximating the Jones Polynomial (2009). Section 2.2 (Hadamard test); Section 3.3 (averaging and error); Algorithmica 55, 395–421, preprint 2005.
Mean estimation
Estimate the average output of a randomized process.
Definition
For X∈[0,1], return μ̂ within additive ε of E[X] with specified confidence. Access may be classical samples or a coherent sampler.
Task contract
- Input / access
- A random variable X∈[0,1]. Choose either independent classical sample access, or the stronger coherent sampler/value-circuit access with inverse and controlled operations required by the displayed quantum route.
- Required output
- A classical estimate of E[X].
- Precision
- Additive ε. The classical bound states failure δ; the displayed quantum bound states constant confidence, with rotation error budgeted.
- Resources
- Classical averaging: O(ε⁻² log(1/δ)) samples. Displayed amplitude-estimation route: O(1/ε) coherent sampler/value uses at constant confidence. Each access has its own implementation cost.
- Limits
- These are different input-access models. Correlated or biased classical samples need additional analysis; the quantum bound does not assume a free conversion from a classical sampler.
Primary sources
Montanaro: Quantum speedup of Monte Carlo methods (2015). Section 1; Algorithm 1 and Theorem 3 for bounded outputs
Monte Carlo
Average independent random samples.
Definition
For bounded outputs, sample averaging estimates their expectation; sampling cost is part of the runtime.
Task contract
- Input / access
- Independent classical samples X∈[0,1].
- Required output
- Estimate of E[X].
- Precision
- Additive ε with failure δ.
- Resources
- O(ε⁻² log(1/δ)) samples, each at its sampling cost.
- Limits
- Correlation or biased sampling needs a separate error analysis.
Primary sources
Montanaro: Quantum speedup of Monte Carlo methods (2015). Section 1; Algorithm 1 and Theorem 3 for bounded outputs
Approximate counting
Estimate how many candidates satisfy a predicate.
Definition
For f:[N]→{0,1}, estimate t=Σx f(x). This node uses additive error εN, not an exact count.
Task contract
- Input / access
- Coherent reversible predicate f, including controlled use; uniform preparation over N=2ⁿ candidates.
- Required output
- Approximate count t̂.
- Precision
- Additive εN, constant confidence.
- Resources
- O(1/ε) predicate calls.
- Limits
- Small additive fraction error does not ensure a useful relative error for rare solutions, or an exact count.
Primary sources
Brassard, Høyer & Tapp: Quantum Counting (1998). Section 2, Theorems 2.1–2.3 (amplification); Section 4, Theorem 4.1 (counting error) · Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
MaxCut
Split a graph into two sides, cutting as much edge weight as possible.
Definition
Given an explicit graph with nonnegative rational edge weights, find a bit string maximizing C(x)=Σij wᵢⱼ(xᵢ+xⱼ−2xᵢxⱼ). Approximation guarantees on individual connections may restrict the graph family.
Task contract
- Input / access
- An explicit graph with nonnegative rational edge weights. The stated QAOA approximation guarantee additionally restricts the graph to unweighted 3-regular instances.
- Required output
- The optimization task asks for a maximum-weight cut. QAOA supplies candidate cuts and, on the specified graph family with suitable angles, a guarantee on expected value rather than an optimum certificate.
- Precision
- The QUBO encoding preserves the rational objective exactly. Approximate quantum circuit execution must budget angle and gate errors separately from its approximation ratio.
- Resources
- The QUBO encoding uses one variable per vertex and one term per edge with polynomial bit overhead. The specified p=1 QAOA circuit uses O(n+m) ideal gates per sample, plus angle preprocessing and repeated sampling.
- Limits
- Encoding MaxCut as QUBO does not solve it. The 0.6924 expected approximation guarantee is family-specific and does not establish a quantum advantage over classical algorithms.
Primary sources
Farhi, Goldstone & Gutmann: A Quantum Approximate Optimization Algorithm (2014). Sections I–II and V–VI; equations (2), (6), (12), (23) · Lucas: Ising Formulations of Many NP Problems (2014). Section 1.2 and Ising/QUBO representation; mappings use explicit objective identities
QUBO
Optimize a quadratic expression whose variables are bits.
Definition
Given rational coefficients, minimize q(x)=c+Σi aᵢxᵢ+Σi<j bᵢⱼxᵢxⱼ over x∈{0,1}ⁿ. Output a minimizing assignment and its value.
Task contract
- Input / access
- Explicit rational constant, linear, and quadratic coefficients for a function of n binary variables.
- Required output
- A minimizing bit assignment and its objective value. Changing coordinates converts these to an Ising minimizer and energy.
- Precision
- The displayed QUBO/Ising transformation uses exact rational arithmetic and retains the additive constant.
- Resources
- The conversion keeps n variables and has polynomial coefficient-conversion cost. This does not bound the cost of finding the minimizer.
- Limits
- This is an optimization task. The equivalence gives no thermal sampler, complex partition-sum evaluator, or general fast optimization algorithm.
Primary sources
Lucas: Ising Formulations of Many NP Problems (2014). Section 1.2 and Ising/QUBO representation; mappings use explicit objective identities
Ising optimization
Choose up/down spins to minimize a classical energy.
Definition
Minimize E(s)=c+Σi hᵢsᵢ+Σi<j Jᵢⱼsᵢsⱼ over s∈{−1,+1}ⁿ, with explicit rational coefficients. This asks for an optimal spin assignment, not a thermal sample or partition sum.
Task contract
- Input / access
- Explicit rational fields and pair couplings defining a classical energy on ±1 spins. Individual connections impose further conditions, such as polynomial-size integer coefficients for the displayed efficient-precision energy reduction.
- Required output
- The task asks for an optimal spin assignment. QAOA instead supplies candidates, while the adiabatic connection supplies an optimum only under its stated path, gap, and unique-ground-state assumptions.
- Precision
- The QUBO coordinate change is exact. Recovering an optimum through the displayed integer-energy reduction uses error below 1/3 before normalization, with each oracle call's failure probability controlled.
- Resources
- QUBO conversion costs polynomial overhead. The restricted ground-energy self-reduction uses O(n) adaptive calls, QAOA candidate generation uses O(p(n+m)) rotations before routing, and adiabatic cost depends on the supplied path's gap and derivatives.
- Limits
- No displayed connection guarantees efficient optimization of arbitrary instances. Binary-encoded large weights alter normalized precision requirements, and this energy task is distinct from a partition sum or thermal sample.
Primary sources
Lucas: Ising Formulations of Many NP Problems (2014). Section 1.2 and Ising/QUBO representation; mappings use explicit objective identities · Kempe, Kitaev & Regev: The Complexity of the Local Hamiltonian Problem (2006). Definitions 2–3; Theorem 1; diagonal classical instances in Introduction · Farhi, Goldstone & Gutmann: A Quantum Approximate Optimization Algorithm (2014). Sections I–II and V–VI; equations (2), (6), (12), (23) · Jansen, Ruskai & Seiler: Bounds for the Adiabatic Approximation with Applications to Quantum Computation (2007). Theorem 3, especially equation (6)
QAOA
Alternate problem and mixing gates, then sample candidate solutions.
Definition
For explicit diagonal cost C and B=Σi Xᵢ, prepare |ψ⟩=e⁻ⁱβpB e⁻ⁱγpC ⋯ e⁻ⁱβ₁B e⁻ⁱγ₁C|+⟩ⁿ with p layers and chosen angles. Classical angle optimization is an additional task.
Task contract
- Input / access
- An explicit diagonal cost, the transverse-field mixer, a layer count p, and chosen angles. Selecting or optimizing the angles is an additional classical task.
- Required output
- A prepared trial state, candidate assignments after measurement, or its estimated expected objective. These are not general certificates of optimality.
- Precision
- Rotation synthesis and finite-shot error need separate budgets from optimization quality. For a nonzero nonnegative total edge weight, the normalized MaxCut objective can be estimated to additive δ with O(δ⁻²) samples at constant confidence.
- Resources
- An Ising cost with m nonzero pair couplings uses O(p(n+m)) rotations per preparation before routing overhead. Expected MaxCut value can also be evaluated classically in polynomial time for fixed graph degree and depth through local light cones.
- Limits
- The stated p=1 approximation bound applies to unweighted 3-regular MaxCut and is an expectation guarantee. No general approximation ratio, easy angle optimization, or quantum advantage is asserted.
Primary sources
Farhi, Goldstone & Gutmann: A Quantum Approximate Optimization Algorithm (2014). Sections I–II and V–VI; equations (2), (6), (12), (23) · Lucas: Ising Formulations of Many NP Problems (2014). Section 1.2 and Ising/QUBO representation; mappings use explicit objective identities · Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction
VQE
Vary a trial state to lower its measured energy.
Definition
Prepare |ψ(θ)⟩, estimate ⟨ψ(θ)|H|ψ(θ)⟩, and optimize θ classically. The variational energy upper-bounds the true ground energy. A small parameter count does not guarantee easy optimization.
Task contract
- Input / access
- An explicit measurable Hamiltonian, typically a supplied Pauli decomposition, and repeatable preparation of a parameterized trial-state family.
- Required output
- Measured trial-state energies and parameters found by the classical optimizer. Adding the measurement-error allowance to a measured energy gives a ground-energy upper bound at that confidence.
- Precision
- Measurement accuracy is separate from ansatz error and optimization error. An additive ε energy estimate does not mean the returned value lies within ε of the true ground energy.
- Resources
- Coefficient-weighted Pauli sampling uses O((sum of absolute coefficients)²/ε²) trial preparations for additive ε at constant confidence. Multiply evaluation cost by the optimizer's number of steps, for which no general polynomial bound is supplied.
- Limits
- A small parameter count does not guarantee easy optimization. An energy upper bound alone neither solves additive-ε ground-energy estimation nor certifies a nearby ground state.
Primary sources
Peruzzo et al.: A Variational Eigenvalue Solver on a Photonic Quantum Processor (2014). Results: Quantum expectation estimation; Quantum variational eigensolver
Ground-state energy
Estimate a Hamiltonian's smallest eigenvalue.
Definition
Given an explicit polynomial-size list of bounded local Hermitian terms H=Σj Hⱼ, output E with |E−λmin(H)|≤ε. This scalar task does not supply a ground state or a guarantee that preparing one is easy.
Task contract
- Input / access
- An explicit polynomial-size list of bounded local Hermitian terms and a target additive error ε. Phase-estimation access additionally requires controlled evolution, a known spectral interval, and repeatable state preparation with promised ground-space weight η.
- Required output
- A scalar within ε of the smallest eigenvalue. The VQE connection supplies an upper bound instead, so it does not by itself meet this two-sided estimation specification.
- Precision
- Accuracy is additive in the supplied Hamiltonian's energy scale. Resolving a local-Hamiltonian promise requires error below half its threshold gap, with bounded failure probability.
- Resources
- No general efficient algorithm is asserted. Under the phase-estimation access and overlap promises, O(1/η) trials suffice at constant overall confidence with logarithmic confidence overhead and O(1/ε) evolution time per accurate trial; evolution time is not gate count.
- Limits
- Returning an energy does not prepare a ground state. Useful input overlap, Hamiltonian simulation cost, and any normalization-dependent precision are additional requirements.
Primary sources
Kempe, Kitaev & Regev: The Complexity of the Local Hamiltonian Problem (2006). Definitions 2–3; Theorem 1; diagonal classical instances in Introduction · Abrams & Lloyd: A Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and Eigenvectors (1999). Eigenvalue estimation algorithm; initial-state overlap requirement · Cleve, Ekert, Macchiavello & Mosca: Quantum Algorithms Revisited (1998). Phase estimation and order finding · Peruzzo et al.: A Variational Eigenvalue Solver on a Photonic Quantum Processor (2014). Results: Quantum expectation estimation; Quantum variational eigensolver
Local Hamiltonian
Is the minimum energy below one threshold or above another?
Definition
Given local H with polynomially bounded term norms and thresholds a<b separated by at least 1/poly(n), promise λmin(H)≤a or λmin(H)≥b. Decide which. General 2-local qubit instances are QMA-complete.
Task contract
- Input / access
- An explicit local Hamiltonian with polynomially bounded term norms and thresholds a<b separated by at least an inverse polynomial. The instance promises ground energy at most a or at least b.
- Required output
- One bit identifying which side of the promised gap contains the ground energy.
- Precision
- An energy estimate with additive error strictly below half the gap and bounded failure probability resolves the decision.
- Resources
- The displayed reduction makes one ground-energy estimation call with polynomial overhead. General 2-local qubit instances are QMA-complete; the reduction does not supply an efficient estimator.
- Limits
- No answer is specified inside the promise gap. This decision task does not request a ground state or the full ground-energy value.
Primary sources
Kempe, Kitaev & Regev: The Complexity of the Local Hamiltonian Problem (2006). Definitions 2–3; Theorem 1; diagonal classical instances in Introduction
Adiabatic computation
Slowly change a Hamiltonian to follow its ground state.
Definition
Start in a known ground state and evolve along a specified smooth local Hamiltonian path. Runtime guarantees depend on its spectral gap and derivatives. The general model can implement quantum circuits with polynomial overhead.
Task contract
- Input / access
- A specified smooth local Hamiltonian path, a known initial ground state, and sufficient gap and derivative information for the chosen runtime guarantee. The Ising optimization connection assumes an isolated nondegenerate ground state throughout, including a unique minimizing endpoint.
- Required output
- A state following the ground state within the chosen adiabatic and implementation errors, then the requested measurement. A specially constructed circuit-dependent path can reproduce a bounded-error circuit's decision.
- Precision
- Adiabatic state error and implementation error both count. Circuit compilation must keep output error below the amplified decision margin.
- Resources
- The displayed sufficient adiabatic runtime worsens with inverse gap, path derivatives, and inverse target error. The circuit-to-adiabatic construction supplies a polynomial-size path and polynomial runtime in circuit size and inverse accuracy.
- Limits
- The circuit construction does not provide a fast algorithm for an arbitrary supplied optimization path. A suitable path or inverse-polynomial gap is not guaranteed for arbitrary Ising instances.
Primary sources
Aharonov, van Dam, Kempe, Landau, Lloyd & Regev: Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation (2007). Theorem 1.1 and circuit-to-adiabatic construction; Theorem 1.3 gives a geometric variant; preprint first posted in 2004 · Jansen, Ruskai & Seiler: Bounds for the Adiabatic Approximation with Applications to Quantum Computation (2007). Theorem 3, especially equation (6) · Lucas: Ising Formulations of Many NP Problems (2014). Section 1.2 and Ising/QUBO representation; mappings use explicit objective identities
Markov-chain search
Walk between candidates until a marked one is reached.
Definition
A finite reversible ergodic Markov chain P, its stationary distribution π, and a marking predicate define a search problem. Quantum use additionally requires coherent setup and transition operations.
Task contract
- Input / access
- A finite reversible ergodic chain and a marking predicate. The displayed quantum route needs coherent stationary-state setup S, reversible updates/inverses at cost U, and coherent checking C; gap δ>0 and marked stationary mass at least ε when nonempty.
- Required output
- A marked state or a bounded-error report that the marked set is empty, for the represented quantum search construction.
- Precision
- Constant bounded error with sufficiently accurate coherent operations.
- Resources
- The represented quantum route costs O(S+ε⁻¹ᐟ²(δ⁻¹ᐟ²U+C)); this is not a bound for every use of a classical Markov chain.
- Limits
- Ordinary classical transition sampling does not automatically supply coherent updates or the stationary-state preparation. Gap, marked mass and all access costs are essential.
Primary sources
Magniez, Nayak, Roland & Santha: Search via Quantum Walk (2011). Theorem 3; Sections 2–4; phase-estimation reflection in Theorem 6
Quantum-walk search
Search a structured space using coherent walk steps and interference.
Definition
Quantize a reversible Markov chain using coherent transitions, then use reflections to find a marked state. Its costs include setup, updates, checking, stationary marked mass, and the chain's spectral gap.
Task contract
- Input / access
- Coherent stationary-state setup S, reversible transition unitaries and their inverses at cost U, coherent marking check C; absolute spectral gap δ=1−maxλ≠1|λ|>0 and marked stationary mass at least ε when nonempty.
- Required output
- A marked state or a bounded-error empty report.
- Precision
- Constant bounded error with adequately accurate coherent operations.
- Resources
- O(S+ε⁻¹ᐟ²(δ⁻¹ᐟ²U+C)).
- Limits
- Ordinary classical transition sampling does not automatically supply coherent access. These costs cannot be omitted.
Primary sources
Magniez, Nayak, Roland & Santha: Search via Quantum Walk (2011). Theorem 3; Sections 2–4; phase-estimation reflection in Theorem 6
Element distinctness
Find two equal values in a list, or report that all differ.
Definition
Given coherent value-query access to x₁,…,xN in a finite alphabet, return i≠j with xᵢ=xⱼ, or report none, with bounded error. Element distinctness is an oracle problem here, not free loading of a stored file.
Task contract
- Input / access
- Coherent reversible value oracle for N entries in an alphabet of size M.
- Required output
- An equal pair or a bounded-error no-duplicate report.
- Precision
- Discrete exact values; constant algorithmic failure probability.
- Resources
- O(N²ᐟ³) value queries; the standard construction stores O(N²ᐟ³) entries plus their indices.
- Limits
- This is a query bound, not total runtime including data loading, memory operations or implementing the oracle.
Primary sources
Ambainis: Quantum Walk Algorithm for Element Distinctness (2007). Theorems 3–4 and Sections 3–5; query and memory bounds; preprint first posted in 2003
Block encoding
Place a scaled matrix inside a larger quantum operation.
Definition
An (α,a,η) block encoding U satisfies ‖A−α(⟨0ᵃ|⊗I)U(|0ᵃ⟩⊗I)‖≤η. The normalization α and the circuit implementing U are part of the input model.
Task contract
- Input / access
- A matrix A, normalization α, ancilla count a and a circuit U whose signal block obeys ‖A−α(⟨0ᵃ|⊗I)U(|0ᵃ⟩⊗I)‖≤η. Construction and access to U are part of the model.
- Required output
- A quantum unitary interface containing an approximation to A/α in its selected ancilla block, not an explicit classical matrix output.
- Precision
- η is the operator-norm error in A at the stated normalization. The represented QSVT and qubitization input routes assume η=0 and budget later polynomial and circuit errors separately.
- Resources
- Depend on the construction, α and the selected downstream connection. The represented LCU construction uses one SELECT, one PREPARE and its inverse, with ceil(log₂ L) index qubits for L terms.
- Limits
- A compact matrix dimension alone is insufficient. Constructing the encoding may be expensive, α may exceed ‖A‖ substantially, and inverse/controlled access and signal reflections must be supplied when a connection requires them.
Primary sources
Gilyén, Su, Low & Wiebe: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2019). Corollary 18 (real polynomial SVT), Theorem 41 (pseudoinverse), Section 4.1 (block encoding), Theorem 56 (Hermitian polynomial transformation); STOC 2019, preprint 2018. Section 5.3 and Corollary 64 (Gibbs filtering). · Berry, Childs, Cleve, Kothari & Somma: Simulating Hamiltonian dynamics with a truncated Taylor series (2015). Section II, equations (6)–(10); Section III, equations (18)–(23); PRL 114, 090502. · Low & Chuang: Hamiltonian Simulation by Qubitization (2019). Theorems 1–4; equation (8) and Section 6; Quantum 3, 163.
LCU
Combine simple quantum operations into a useful matrix.
Definition
For A=ΣⱼcⱼUⱼ with cⱼ≥0 and α=Σⱼcⱼ, prepare coefficient amplitudes, select Uⱼ coherently, then unprepare. Complex coefficient phases may be absorbed into Uⱼ.
Task contract
- Input / access
- A=ΣⱼcⱼUⱼ with cⱼ≥0 and α=Σⱼcⱼ>0; PREPARE|0⟩=Σⱼ√(cⱼ/α)|j⟩, its inverse, and coherent SELECT=Σⱼ|j⟩⟨j|⊗Uⱼ. Complex coefficient phases may be absorbed into the unitaries.
- Required output
- A unitary (PREPARE†⊗I) SELECT (PREPARE⊗I) whose selected block is A/α. Application-specific processing can use this block.
- Precision
- The block identity is exact for exact primitives. Approximate preparation and selection contribute implementation error that must be budgeted for the selected application.
- Resources
- One SELECT, one PREPARE and its inverse for the represented block construction; ceil(log₂ L) index qubits for L terms. Charge each primitive's implementation separately.
- Limits
- α and the costs of coefficient preparation and term selection matter. This interface alone is not a normalized application of A or a complete Hamiltonian simulation; the Taylor-simulation connection specifies its separate amplification, approximation and time costs.
Primary sources
Berry, Childs, Cleve, Kothari & Somma: Simulating Hamiltonian dynamics with a truncated Taylor series (2015). Section II, equations (6)–(10); Section III, equations (18)–(23); PRL 114, 090502.
Qubitization
Turn a matrix spectrum into quantum-walk angles.
Definition
A Hermitian signal H/α encoded in a unitary is converted into invariant two-dimensional rotations with eigenphases ±arccos(λ(H)/α). Signal processing can then transform those rotations.
Task contract
- Input / access
- An exact block encoding of H/α for Hermitian H, controlled encoding and inverse access, and a reflection about the signal ancilla state.
- Required output
- A qubitized iterate with eigenphases ±arccos(λ(H)/α) in its invariant signal subspaces, adding a signal qubit if needed.
- Precision
- The spectral identity is exact in the ideal input model. Approximate inputs require a separate error budget; subsequent signal processing has its own synthesis and approximation error.
- Resources
- O(1) encoding/inverse queries per iterate and O(a) elementary gates for a encoding ancillas. A degree-d signal-processing sequence uses O(d) iterates plus reflections and rotations.
- Limits
- The iterate is not exp(−iHt). A chosen spectral transformation still requires an admissible approximating polynomial, computable phases and the access specified by its connection.
Primary sources
Low & Chuang: Hamiltonian Simulation by Qubitization (2019). Theorems 1–4; equation (8) and Section 6; Quantum 3, 163. · Low & Chuang: Optimal Hamiltonian Simulation by Quantum Signal Processing (2017). Theorem 1; quantum signal-processing construction and Chebyshev/Fourier correspondence; PRL 118, 010501.
QSP
Program a function using a sequence of small rotations.
Definition
Interleaving a signal-dependent SU(2) rotation with chosen phase rotations produces an admissible bounded polynomial response. Polynomial degree controls the number of signal calls; parity and unitarity constraints matter.
Task contract
- Input / access
- A signal-dependent SU(2) rotation and a valid phase sequence for the desired bounded polynomial response. Classical design must respect parity and unitarity/completion constraints; a qubitized signal requires controlled access when its construction calls for it.
- Required output
- A quantum sequence encoding the selected admissible polynomial response to the signal. The same sequence can act across invariant spectral subspaces.
- Precision
- The selected polynomial response is exact in the ideal model. Approximation error relative to the desired function and phase/gate synthesis error both require explicit budgets.
- Resources
- Degree d sets O(d) signal calls plus phase rotations and reflections. For the represented synthesis route, classical phase synthesis is polynomial in d and log(1/ε).
- Limits
- Not every truncated Chebyshev series is admissible without rescaling or completion. A low-degree useful approximant is still needed. Matrix and state outputs depend on the selected application rather than on QSP alone.
Primary sources
Low & Chuang: Optimal Hamiltonian Simulation by Quantum Signal Processing (2017). Theorem 1; quantum signal-processing construction and Chebyshev/Fourier correspondence; PRL 118, 010501. · Haah: Product Decomposition of Periodic Functions in Quantum Signal Processing (2019). Constructive product decomposition and numerical-precision analysis; Quantum 3, 190; arXiv v4 (2020). · Low & Chuang: Hamiltonian Simulation by Qubitization (2019). Theorems 1–4; equation (8) and Section 6; Quantum 3, 163. · Gilyén, Su, Low & Wiebe: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2019). Corollary 18 (real polynomial SVT), Theorem 41 (pseudoinverse), Section 4.1 (block encoding), Theorem 56 (Hermitian polynomial transformation); STOC 2019, preprint 2018. Section 5.3 and Corollary 64 (Gibbs filtering).
QSVT
Apply a polynomial to every singular value at once.
Definition
If A/α=WΣV†, an odd polynomial p gives Wp(Σ)V†. For even p the standard construction acts on a single singular-vector space. Real p must be bounded on [−1,1] and obey its degree parity.
Task contract
- Input / access
- A projected unitary encoding A/α, inverse access, efficient signal-space phase reflections, and a real degree-d polynomial bounded by 1 on [−1,1] with matching parity. The represented block-input connection assumes an exact (α,a,0) encoding.
- Required output
- A block encoding of the selected singular-value transform. For A/α=WΣV† and odd p this is Wp(Σ)V†; the standard even-parity construction acts on one singular-vector space.
- Precision
- Exact for the ideal encoded input and admissible polynomial; polynomial approximation, phase synthesis and gates determine error in an implemented application. The state-filter connection separately specifies an arbitrary-parity construction and normalization error.
- Resources
- O(d) queries to the encoding and its inverse and O(ad) additional elementary gates in the represented exact-block route. Charge encoding construction and phase synthesis; state preparation and amplification are separate application costs.
- Limits
- For non-Hermitian A, a singular-value transform is not generally p(A). Normalization α, polynomial degree and any application success amplitude matter. The method does not by itself return a classical vector or guarantee efficient state preparation.
Primary sources
Gilyén, Su, Low & Wiebe: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2019). Corollary 18 (real polynomial SVT), Theorem 41 (pseudoinverse), Section 4.1 (block encoding), Theorem 56 (Hermitian polynomial transformation); STOC 2019, preprint 2018. Section 5.3 and Corollary 64 (Gibbs filtering). · Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
Chebyshev approximation
Design the polynomial behind a quantum transformation.
Definition
Approximate a scalar function on [−1,1] by p(x)=ΣₖcₖTₖ(x), where Tₖ(cos θ)=cos(kθ). Accuracy, degree, interval and boundedness must be checked for the chosen function.
Task contract
- Input / access
- A scalar function, target interval and tolerance, represented by a polynomial p(x)=ΣₖcₖTₖ(x) on [−1,1], with Tₖ(cos θ)=cos(kθ). Quantum use additionally requires the selected response's boundedness, parity and completion constraints.
- Required output
- Classical polynomial coefficients approximating the selected function. The represented QSP design connection further converts an admissible polynomial into classical phase parameters.
- Precision
- Accuracy, degree, interval and boundedness must be checked for the chosen function. Function-approximation and phase-synthesis errors must both fit the selected application's tolerance.
- Resources
- Polynomial degree is function- and tolerance-dependent. Degree d sets O(d) quantum signal uses after synthesis; the represented phase-synthesis algorithm is polynomial in d and log(1/ε).
- Limits
- An arbitrary truncated Chebyshev series need not be admissible for QSP without rescaling or completion. Classical polynomial design alone does not imply classical simulation of the resulting quantum circuit.
Primary sources
Low & Chuang: Optimal Hamiltonian Simulation by Quantum Signal Processing (2017). Theorem 1; quantum signal-processing construction and Chebyshev/Fourier correspondence; PRL 118, 010501. · Low & Chuang: Hamiltonian Simulation by Qubitization (2019). Theorems 1–4; equation (8) and Section 6; Quantum 3, 163. · Haah: Product Decomposition of Periodic Functions in Quantum Signal Processing (2019). Constructive product decomposition and numerical-precision analysis; Quantum 3, 190; arXiv v4 (2020).
Matrix-function state
Filter or reweight spectral components of a prepared vector.
Definition
Given Hermitian H, a real function f, a circuit preparing |b⟩ and an encoding of H, prepare f(H)|b⟩/‖f(H)b‖ when the denominator is nonzero. This does not output a classical matrix or all vector entries.
Task contract
- Input / access
- Hermitian H, real f and a circuit preparing |b⟩. The represented QSVT route assumes an exact encoding U of H/α, controlled-U and U†, inverse state preparation, and degree-d real p approximating f(αx)/c with c>0 and |p(x)|≤1/2 on [−1,1].
- Required output
- An approximation to f(H)|b⟩/‖f(H)b‖ when the denominator is nonzero, obtained by selecting the signal ancillas.
- Precision
- For s=‖f(H)b‖/c>0 and total polynomial/block error η<s/2, normalized-state error is O(η/s). The represented arbitrary-parity construction has its own controlled-encoding requirement.
- Resources
- O(d) encoding queries per attempt, including one controlled-U. Success probability Θ(s²) gives O(1/s²) expected repetitions or O(1/s) amplification overhead for constant success. Charge state preparation and its inverse.
- Limits
- A small success amplitude or high polynomial degree can remove efficiency. This returns a quantum state, not a classical matrix or all vector entries. The Gibbs connection specifies additional thermal-state assumptions.
Primary sources
Gilyén, Su, Low & Wiebe: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2019). Corollary 18 (real polynomial SVT), Theorem 41 (pseudoinverse), Section 4.1 (block encoding), Theorem 56 (Hermitian polynomial transformation); STOC 2019, preprint 2018. Section 5.3 and Corollary 64 (Gibbs filtering). · Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
Hadamard test
Read an overlap through one control qubit.
Definition
Given |ψ⟩ preparation and controlled-U, an ancilla measurement yields a ±1 variable with mean Re⟨ψ|U|ψ⟩. Changing the ancilla phase gives the imaginary part.
Task contract
- Input / access
- A preparation circuit for |ψ⟩ and controlled-U. An ancilla phase choice selects the real or imaginary part of the overlap. Coherent amplitude-estimation use additionally requires inverse and controlled preparation access and a success reflection.
- Required output
- A ±1 measurement outcome with mean Re⟨ψ|U|ψ⟩, or Im⟨ψ|U|ψ⟩ after the phase change. Repeated use gives a classical overlap estimate.
- Precision
- Independent-sample use estimates the selected component to additive ε with failure at most δ. The represented circuit-amplitude application budgets joint failure across the two components.
- Resources
- Independent sampling uses O(ε⁻² log(1/δ)) state preparations and controlled-unitary calls. With the extra coherent access on the amplitude-estimation connection, O(1/ε) coherent preparation/inverse uses give constant confidence, with O(log(1/δ)) amplification overhead.
- Limits
- Controlled access and input preparation are costs. General observables need suitable measurement access or a decomposition. Additive overlap estimates do not provide exact or relative-error evaluation of exponentially small amplitudes.
Primary sources
Aharonov, Jones & Landau: A Polynomial Quantum Algorithm for Approximating the Jones Polynomial (2009). Section 2.2 (Hadamard test); Section 3.3 (averaging and error); Algorithmica 55, 395–421, preprint 2005. · Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
Simon's algorithm
Recover an XOR symmetry by solving sampled binary equations.
Definition
Hadamards, one coherent function query, and Hadamards yield random y with y·s=0 over F₂. Repeated samples and classical elimination recover the hidden mask under Simon's promise.
Task contract
- Input / access
- A coherent reversible oracle f:{0,1}ⁿ→{0,1}ᵐ, m≥n, promised injective or exactly two-to-one with f(x)=f(y) iff y=x or y=x⊕s for a unique nonzero s.
- Required output
- The hidden nonzero bit mask s, or 0ⁿ in the injective case. Fourier samples give binary equations that are solved classically.
- Precision
- Exact bits with zero error in the original expected-time algorithm; candidate verification uses the promise. Ideal gates give exact Fourier-sample distributions.
- Resources
- O(n) expected oracle calls plus polynomial classical binary linear algebra and Hadamard gates. Each Fourier sample uses 2n Hadamards, one function query and oracle ancillas.
- Limits
- This is an oracle-model algorithm. Promise violations and the cost of constructing the oracle are not covered. Its Fourier group is (Z₂)ⁿ, not the cyclic group Z₂ⁿ.
Primary sources
Simon: On the Power of Quantum Computation (1997). Definition 3.1 and Theorem 3.2; Fourier-twice routine and linear equations; SIAM J. Comput. 26(5), 1474–1483. · Mosca & Ekert: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer (1999). Section 2 (input presentation and discrete-log example); Sections 3–4 (Fourier/eigenvalue sampling)
Hidden XOR mask
Find the bit pattern that leaves a function unchanged.
Definition
Oracle f:{0,1}ⁿ→{0,1}ᵐ, m≥n, promised either injective or exactly two-to-one with f(x)=f(y) iff y=x or y=x⊕s for a unique nonzero s. Return s, or 0ⁿ in the injective case.
Task contract
- Input / access
- An oracle f:{0,1}ⁿ→{0,1}ᵐ, m≥n, promised injective or exactly two-to-one with f(x)=f(y) iff y=x or y=x⊕s for a unique nonzero s. Simon's quantum route requires coherent reversible oracle access.
- Required output
- The nonzero mask s, or 0ⁿ for an injective f.
- Precision
- The represented Simon algorithm returns exact bits with zero error in expected time. The exact reduction to abelian HSP instead transfers that solver's failure guarantee.
- Resources
- Simon's route uses O(n) expected oracle calls and polynomial classical binary linear algebra. The HSP reduction uses the same oracle over (Z₂)ⁿ with polynomial classical overhead.
- Limits
- The injective/two-to-one promise is essential. Oracle-construction cost is additional, and this special abelian subgroup problem does not cover arbitrary nonabelian HSP.
Primary sources
Simon: On the Power of Quantum Computation (1997). Definition 3.1 and Theorem 3.2; Fourier-twice routine and linear equations; SIAM J. Comput. 26(5), 1474–1483. · Mosca & Ekert: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer (1999). Section 2 (input presentation and discrete-log example); Sections 3–4 (Fourier/eigenvalue sampling)
Gibbs-state preparation
Prepare a thermal state at a specified temperature.
Definition
Given a Hamiltonian H and inverse temperature β≥0, prepare ρβ=exp(−βH)/Z, Z=tr(exp(−βH)), or a purification. Error is measured in trace distance. The output is not a list of thermal probabilities or the partition function.
Preparation, output & cost
- Input / access
- The represented β≥1 route needs a normalized-H block encoding with controlled/inverse access, entangled-pair preparation and a certified success lower bound.
- Required output
- An approximate Gibbs-state purification. No partition function or classical list of thermal probabilities is returned.
- Costs
- Filter degree, success amplification and preparation all count. Success can be exponentially small, so this is not generic efficient thermalization.
Task contract
- Input / access
- The represented spectral-filter route uses D=2ⁿ, Hermitian H with ‖H‖≤1, an exact (1,a,0) block encoding with controlled/inverse access, β≥1, and preparation of |Φ_D⟩. It requires a certified 0<q₀≤q=e^(−β)Z/D, where Z=tr(exp(−βH)); q₀=exp(−2β) always suffices in this regime.
- Required output
- A purification whose reduced state approximates ρβ=exp(−βH)/Z. Apply a constant-rescaled filter F/c, F=exp(−β(H+I)/2), to one half of |Φ_D⟩, then discard the reference after success. For example c=4 leaves room for |p|≤1/2.
- Precision
- Trace distance O(ε) when filter/circuit error η=O(ε√q₀). Signal success is Θ(q), including the constant rescaling; amplification gives constant heralded success and independent attempts increase overall success.
- Resources
- A bounded polynomial filter uses d=O(√β log(1/η)) encoding queries. Expected amplified cost is O(d/√q), plus repeated entangled-pair preparation, phase synthesis and other gates.
- Limits
- This is one represented route in the β≥1 regime, not a generic efficient thermalization claim. q can be exponentially small. Physical inverse temperature rescales with H, and the output supplies neither a list of thermal probabilities nor a partition-function estimate.
Primary sources
Gilyén, Su, Low & Wiebe: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2019). Corollary 18 (real polynomial SVT), Theorem 41 (pseudoinverse), Section 4.1 (block encoding), Theorem 56 (Hermitian polynomial transformation); STOC 2019, preprint 2018. Section 5.3 and Corollary 64 (Gibbs filtering). · Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
Quantum rejection sampling
Reweight amplitudes while preserving the states they label.
Definition
Given a preparation oracle for Σᵢπᵢ|ξᵢ⟩|i⟩, convert it to Σᵢσᵢ|ξᵢ⟩|i⟩. Known nonnegative normalized amplitude profiles and inverse access support one version; a stronger variant accepts implementable amplitude ratios and a source-state reflection.
Task contract
- Input / access
- The represented amplitude-profile route uses known nonnegative normalized π,σ with supp(σ)⊆supp(π), an oracle O|0⟩=Σᵢπᵢ|ξᵢ⟩|i⟩ for unknown normalized |ξᵢ⟩, O†, and ratio-controlled rotations. Set R=max_{σᵢ>0} σᵢ/πᵢ.
- Required output
- The reweighted coherent state Σᵢσᵢ|ξᵢ⟩|i⟩, preserving the states attached to each label.
- Precision
- Exact target and certainty with ideal profile data and adjusted amplification phases. Finite rotations need an explicit state-error budget.
- Resources
- O(R) calls to O and O† for the represented exact target. Charge classical profile processing and each ratio-controlled rotation separately.
- Limits
- Ordinary samples do not supply inverse preparation access. Large amplitude ratios or expensive profile access can remove the speedup. The stronger HHL resampling connection uses a different interface with ideal eigenvalue labels, implementable ratios and a source-state reflection; its cost is not the full HHL runtime.
Primary sources
Ozols, Roetteler & Roland: Quantum rejection sampling (2012). Theorem 1, Sections 4.1–4.3 (known profiles and strong variant), Section 5.1 (HHL reweighting); ITCS 2012, 290–308. · Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation
Tasks & methods: connections
Entanglement alone does not make a circuit hard to simulate.
A binary tableau reproduces Clifford measurement samples and conditional probabilities.
Arbitrary inputs and non-Clifford gates are outside this guarantee. A tableau does not enumerate 2ⁿ amplitudes.
- Input / access
- Explicit H/S/CNOT gates; basis-state input; basis measurements.
- Required output
- Exact samples plus a compact classical state description.
- Precision
- Discrete arithmetic; no amplitude rounding.
- Resources
- O(n²) bits; O(n) per elementary gate and O(n²) per measurement in this algorithm.
Aaronson & Gottesman: Improved Simulation of Stabilizer Circuits (2004). Section III; tableau update rules
The intermediate states, not just the final state, control the cost.
An MPS tracks the evolution while its bond dimensions stay small.
Low entropy or a simple final state alone is insufficient. Truncation needs an accumulated-error bound.
- Input / access
- Explicit one/two-qubit gate list, product input; maximum Schmidt rank χ bounded throughout.
- Required output
- Compact state description and local/product-observable probabilities.
- Precision
- Untruncated representation at the stated rank; numerical rounding is separate.
- Resources
- O(nχ²) coefficients; O(χ³) arithmetic per adjacent two-qubit gate. Swaps add overhead.
Vidal: Efficient Classical Simulation of Slightly Entangled Quantum Computations (2003). Lemmas 1–2 and Theorem 1
Circuit geometry can make exact probability calculations tractable.
Contract a network representing the requested circuit measurement event.
This uses the gate-instance wiring graph, not merely qubit connectivity. Large width is not a hardness proof. It does not print the full distribution.
- Input / access
- Explicit constant-arity circuit with T gates; efficiently given basis/product input; event fixing selected output bits, with others ignored. G is the circuit wiring graph.
- Required output
- One event probability, including marginals.
- Precision
- Arithmetic-operation bound; exact gate representation or a numerical error budget is required.
- Resources
- T^O(1) exp(O(tw(G))). Logarithmic treewidth gives polynomial cost.
Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction
A compact tensor state is useful because selected outputs can be contracted.
Contract the MPS with local measurement projectors to evaluate an event.
Obtaining the MPS may be expensive. This is not an efficient method for arbitrary circuit outputs.
- Input / access
- An available MPS description with bond dimension χ and product-form measurement event.
- Required output
- One event probability.
- Precision
- Exact arithmetic identity; finite precision requires controlled contraction error.
- Resources
- Polynomial in n and χ for this chain network.
Vidal: Efficient Classical Simulation of Slightly Entangled Quantum Computations (2003). Lemmas 1–2 and Theorem 1 · Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction
Fermionic interference can be tracked with polynomial-size matrices.
Compute occupation probabilities and sample through determinant/Pfaffian formulas.
Interacting fermions are excluded. This does not allow arbitrary nonlocal qubit matchgates; the usual qubit translation is nearest-neighbor on a line.
- Input / access
- Explicit quadratic fermionic circuit; occupation-basis input and measurements.
- Required output
- Probabilities, marginals and samples.
- Precision
- Polynomial arithmetic cost; numerical gate parameters need a precision budget.
- Resources
- Polynomial in the mode count and circuit length.
Terhal & DiVincenzo: Classical Simulation of Noninteracting-Fermion Quantum Circuits (2002). Sections III–V
An exact classical boson sampler exists, but its photon-count dependence is exponential.
Clifford–Clifford sample using a sequence of related permanent calculations.
An exponential upper bound is not a lower bound. This is not an efficient general classical simulator.
- Input / access
- Explicit m×n column-orthonormal interferometer matrix; n distinct occupied inputs, ideal indistinguishable photons.
- Required output
- One exact output occupation sample in the arithmetic model.
- Precision
- Exact model; finite-precision implementations need separate error control.
- Resources
- O(n 2ⁿ + mn²) arithmetic time per sample; O(m) additional working space, beyond the input.
Clifford & Clifford: The Classical Complexity of Boson Sampling (2018). Theorem 1; Algorithm B
Two similar-looking permutation sums lead to very different known algorithms.
Compare antisymmetric fermionic amplitudes with symmetric bosonic amplitudes.
Efficient determinant algorithms do not imply efficient permanent evaluation or boson sampling.
- Input / access
- Matched matrix formulas: determinant uses permutation signs; permanent omits them.
- Required output
- A mathematical comparison, not a task translation.
- Precision
- No approximation or simulation guarantee is asserted.
- Resources
- No resource transfer follows from this analogy.
Terhal & DiVincenzo: Classical Simulation of Noninteracting-Fermion Quantum Circuits (2002). Sections III–V · Aaronson & Arkhipov: The Computational Complexity of Linear Optics (2013). Theorem 3.10; approximate-sampling conjectures
A quantum amplitude and a complex statistical-mechanics sum are the same scalar after normalization.
Translate evaluation of this two-body IQP amplitude into this complex Ising sum, and back.
These are complex weights, not an ordinary positive Boltzmann distribution. The identity gives no efficient evaluator or sampler.
- Input / access
- D = exp(i[Σi<j JᵢⱼZᵢZⱼ + Σi hᵢZᵢ]); explicit real angles and graph.
- Required output
- Complex amplitude a, or normalized partition function Z/2ⁿ.
- Precision
- Additive error ε in a corresponds to 2ⁿε in unnormalized Z.
- Resources
- Polynomial overhead to translate descriptions. Evaluation can still be expensive.
Bremner, Montanaro & Shepherd: Average-case Complexity versus Approximate Simulation of Commuting Quantum Computations (2016). Equation (1) and Appendix A
An order-finding solver is enough to build a factoring algorithm.
Use exact orders and gcd calculations, with random choices and repetition, to find factors.
This proves an algorithmic route, not a superpolynomial classical lower bound for factoring.
- Input / access
- Binary N; classical preprocessing for even numbers and prime powers; coprime a.
- Required output
- Prime factors with bounded failure probability.
- Precision
- Exact integer answers; repeat to reduce failure.
- Resources
- Polynomial classical overhead in log N and polynomially many order-finding calls.
Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1997). Sections 3–4 (arithmetic and QFT), Section 5 (factoring), Section 6 (discrete logarithms)
Order finding is phase estimation applied to modular arithmetic.
Estimate eigenphases of modular multiplication, then recover the order with continued fractions and repetition.
Generic phase estimation is not polylogarithmic in inverse error for free. Efficient controlled powers are essential here.
- Input / access
- Uₐ|y⟩ = |ay mod N⟩ on the valid subspace, starting from |1⟩; controlled powers implemented by modular exponentiation.
- Required output
- The integer order r, with bounded failure probability.
- Precision
- O(log N) phase bits suffice for rational reconstruction with repetition.
- Resources
- Polynomial gate and classical cost in log N in the factoring construction.
Cleve, Ekert, Macchiavello & Mosca: Quantum Algorithms Revisited (1998). Phase estimation and order finding · Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1997). Sections 3–4 (arithmetic and QFT), Section 5 (factoring), Section 6 (discrete logarithms)
The same spectral tool appears inside quantum linear solving.
Phase estimation of exp(iAt) supplies approximate eigenvalues for a controlled inverse-eigenvalue rotation.
This edge is a subroutine use, not a reduction between complete input/output tasks.
- Input / access
- Sparse-access Hermitian A, controlled Hamiltonian simulation and an efficiently prepared |b⟩.
- Required output
- An intermediate eigenvalue register used inside HHL.
- Precision
- Small eigenvalues require finer resolution; conditioning matters.
- Resources
- Hamiltonian simulation time and accuracy enter the total HHL bound.
Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation
A logarithmic-sized quantum output need not contain a readable list of numbers.
Prepare amplitudes proportional to the solution of Ax=b.
Arbitrary data loading and full-vector readout are excluded. No unconditional exponential classical separation is claimed.
- Input / access
- N×N Hermitian A, s nonzeros per row; coherent reversible access to nonzero indices and values; eigenvalue magnitudes in [1/κ,1]; |b⟩ preparation unitary and its inverse, at cost T_B.
- Required output
- Normalized |x⟩, not N printed coordinates.
- Precision
- Euclidean state error ε for the prepared solution with workspace reset; measurement error is separate.
- Resources
- Original bound Õ(κ T_B + log N · s²κ²/ε), under the stated access model. Historical, not optimal.
Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation
A useful output can be one measurement statistic instead of a full vector.
Repeated preparations and bounded measurements estimate ⟨x|M|x⟩.
An arbitrary dense M is not automatically easy to measure. This does not reconstruct x or its norm.
- Input / access
- Fresh preparations of |x⟩ and an efficient measurement of a Hermitian M with ‖M‖ ≤ 1.
- Required output
- One real expectation estimate.
- Precision
- Additive δ at constant confidence; state error must be small enough for the bias budget.
- Resources
- O(δ⁻²) preparations by independent measurement; each incurs preparation cost.
Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation
A single probability estimate can answer a promised yes/no question.
Estimate the acceptance probability to additive error strictly below 1/6, then threshold at 1/2.
The acceptance promise is essential. This does not require exact probabilities or exponentially precise amplitudes.
- Input / access
- Explicit circuit promised to have acceptance probability ≥2/3 or ≤1/3.
- Required output
- One decision bit.
- Precision
- The probability oracle must meet its error guarantee with the desired success probability.
- Resources
- One probability-estimation call and polynomial overhead.
Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction
The straightforward simulator stores the entire state.
Compute amplitudes, then draw a basis sample.
Exponential upper bound, not a hardness proof.
- Input / access
- T explicit constant-arity gates; n qubits; basis input.
- Required output
- Statevector and samples.
- Precision
- Exact arithmetic model; rounding needs an error budget.
- Resources
- O((T+1)·2ⁿ) arithmetic including sample preparation; O(2ⁿ) complex entries.
Fatima & Markov: Faster Schrödinger-style simulation of quantum circuits (2020). Section 3: baseline Schrödinger simulation and statevector memory.
Once the full vector is available, one amplitude is directly accessible.
Read its y coordinate.
The exponential preparation cost remains.
- Input / access
- Already computed output vector for input x.
- Required output
- Complex amplitude.
- Precision
- Inherits vector error.
- Resources
- O(1) array access after simulation.
Fatima & Markov: Faster Schrödinger-style simulation of quantum circuits (2020). Section 3: baseline Schrödinger simulation and statevector memory.
An event may include many possible output strings.
Sum |ψᵧ|² over matching strings.
A marginal is not generally one amplitude squared.
- Input / access
- Available normalized statevector; output-bit constraints.
- Required output
- One marginal probability.
- Precision
- Controlled summation and vector error.
- Resources
- O(2ⁿ) scan in general.
Fatima & Markov: Faster Schrödinger-style simulation of quantum circuits (2020). Section 3: baseline Schrödinger simulation and statevector memory.
Fixing every boundary wire turns a circuit into a scalar tensor contraction.
Contract gate entries to calculate ⟨y|U|x⟩.
A poor contraction order can be costly. This does not provide a sampler automatically.
- Input / access
- Explicit constant-arity gates and basis boundary strings.
- Required output
- One complex amplitude.
- Precision
- Exact identity; numerical contraction needs error control.
- Resources
- Polynomial prefactor times exponential in contraction width.
Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction
Interference becomes cancellation between computational paths.
Enumerate paths for Hadamard/Toffoli circuits.
No efficient generic Monte Carlo claim. Arbitrary complex gates need another weighted formulation.
- Input / access
- Explicit circuit with h Hadamards; fixed basis endpoints.
- Required output
- Real amplitude.
- Precision
- Exact integer counts and 2^(−h/2).
- Resources
- O(2ʰ·poly(circuit size)) by enumeration.
Dawson, Haselgrove, Hines, Mortimer, Nielsen & Osborne: Quantum computing and polynomial equations over the finite field Z₂ (2005). Equations (3)–(6): signed path counts over F₂; Section V discusses limitations.
Path signs can be represented by Boolean equations.
Count positive and negative paths separately.
Counting is not supplied for free.
- Input / access
- Hadamard/Toffoli path description and endpoints.
- Required output
- N₊ and N₋, hence the amplitude.
- Precision
- Exact counts; approximate counts need separate cancellation control.
- Resources
- Polynomial construction plus two counting calls.
Dawson, Haselgrove, Hines, Mortimer, Nielsen & Osborne: Quantum computing and polynomial equations over the finite field Z₂ (2005). Equations (3)–(6): signed path counts over F₂; Section V discusses limitations.
Non-Clifford resources, rather than qubits alone, can control simulation cost.
Approximate sampling through magic-state decompositions.
Exponential in t; not a best-current exponent claim.
- Input / access
- Explicit circuit; n,c,t as defined; w measured bits.
- Required output
- A sample within ℓ₁ error ε.
- Precision
- Distribution error ε, not relative error on every probability.
- Resources
- Historical bound Õ(w(w+t)(c+t)+w(n+t)³+2^(γt)t³w³/ε⁴), where γ = −2 log₂(cos(π/8)) ≈ 0.228.
Bravyi & Gosset: Improved classical simulation of quantum circuits dominated by Clifford gates (2016). Equations (2)–(4), v3; Section III and Appendices B–E for phase-aware stabilizer operations.
The efficient stabilizer machinery still applies to each component.
Update each stabilizer term through Clifford gates, preserving coefficients and phases.
A coherent sum is not a probabilistic mixture. Interference between terms cannot be discarded.
- Input / access
- χ explicitly supplied stabilizer terms and coefficients.
- Required output
- Updated coherent decomposition.
- Precision
- Exact stabilizer algebra; coefficient arithmetic needs precision control.
- Resources
- χ times polynomial overhead per Clifford update.
Bravyi, Smith & Smolin: Trading classical and quantum computational resources (2016). Section IV and Appendix A: stabilizer decompositions and phase-aware overlap calculations. · Bravyi & Gosset: Improved classical simulation of quantum circuits dominated by Clifford gates (2016). Equations (2)–(4), v3; Section III and Appendices B–E for phase-aware stabilizer operations. · Aaronson & Gottesman: Improved Simulation of Stabilizer Circuits (2004). Section III; tableau update rules
Overlaps between stabilizer components determine measurement probabilities.
Evaluate Σⱼₖ cⱼ* cₖ ⟨φⱼ|Π|φₖ⟩.
An approximate decomposition alone does not promise relative accuracy for rare events.
- Input / access
- Exact χ-term normalized decomposition; basis-event projector Π.
- Required output
- One event probability.
- Precision
- Exact arithmetic identity; numerical cancellation needs care.
- Resources
- O(χ²·poly(n)) via pairwise stabilizer overlaps.
Bravyi, Smith & Smolin: Trading classical and quantum computational resources (2016). Section IV and Appendix A: stabilizer decompositions and phase-aware overlap calculations. · Bravyi & Gosset: Improved classical simulation of quantum circuits dominated by Clifford gates (2016). Equations (2)–(4), v3; Section III and Appendices B–E for phase-aware stabilizer operations.
Adjacent matchgates become quadratic fermionic evolution.
Translate this sampling task to the free-fermion model.
Ordinary nonadjacent qubit matchgates do not inherit this guarantee. Allowing next-nearest neighbors permits universal computation with encoding.
- Input / access
- Adjacent equal-determinant matchgates on a line; basis-state input and measurement.
- Required output
- Identical occupation/basis sample distribution.
- Precision
- Exact model correspondence; parameter errors must be controlled.
- Resources
- Polynomial description translation.
Jozsa & Miyake: Matchgates and classical simulation of quantum circuits (2008). Theorems 1–2 and Section 5: nearest-neighbor correspondence; multi-bit basis-input sampling uses Terhal–DiVincenzo. · Terhal & DiVincenzo: Classical Simulation of Noninteracting-Fermion Quantum Circuits (2002). Sections III–V
Splitting time into small steps gives an implementable quantum circuit.
Approximate exp(−iHt) by r repetitions of term exponentials.
A quantum algorithm. The formula does not make arbitrary dynamics efficiently classically simulable.
- Input / access
- H=Σⱼ₌₁ᴸ Hⱼ; bounded Hermitian terms with efficiently implementable exponentials.
- Required output
- Approximate evolution unitary.
- Precision
- First-order error ≤ t² C/(2r), C=Σⱼ<ₖ ‖[Hⱼ,Hₖ]‖; synthesis errors are additional.
- Resources
- Lr term evolutions; choose r≥max(1,ceil(t²C/(2ε))).
Childs, Su, Tran, Wiebe & Zhu: Theory of Trotter Error with Commutator Scaling (2021). Proposition 15, first-order Lie–Trotter commutator error bound; published as Theory of Trotter Error with Commutator Scaling.
Time evolution supplies the controlled unitary needed for energy estimation.
Use U=exp(−iHτ) in phase estimation.
Does not automatically prepare the ground state. The controlled operations and state preparation must be implemented.
- Input / access
- Controlled evolution at selected times; an input state with spectral overlap; a known energy interval to avoid phase aliasing.
- Required output
- An energy estimate drawn according to input spectral weights.
- Precision
- Energy error δ requires an appropriate phase and simulation-error budget.
- Resources
- Standard phase estimation uses total evolution time O(1/δ) at constant confidence, plus implementation overhead.
Cleve, Ekert, Macchiavello & Mosca: Quantum Algorithms Revisited (1998). Phase estimation and order finding · Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation
The same short local evolutions can update a compressed classical state.
Apply adjacent two-site Trotter gates to an MPS, optionally truncating bonds.
Fixed χ does not guarantee accuracy. Growing entanglement can require exponentially large bonds.
- Input / access
- One-dimensional nearest-neighbor Hamiltonian on qubits (or fixed local dimension), initial MPS and a time-step/error budget.
- Required output
- Approximate classical description of the evolved state.
- Precision
- Budget Trotter error plus accumulated state error from truncations; a sum of discarded Schmidt weights alone is not a general final-state error bound.
- Resources
- O(nχ³) arithmetic per nearest-neighbor sweep at retained bond dimension χ.
Vidal: Efficient Simulation of One-Dimensional Quantum Many-Body Systems (2004). Equations (16), (22)–(25): local evolution, truncation error, Trotter error and update cost. · Vidal: Efficient Classical Simulation of Slightly Entangled Quantum Computations (2003). Lemmas 1–2 and Theorem 1
One batch supports many local Pauli estimates.
Predict all M expectations using randomized local-Pauli measurements.
Not full tomography or a classical circuit simulator. Arbitrary k-local observables have a different bound.
- Input / access
- Independent copies of ρ; M fixed Pauli strings of weight ≤k.
- Required output
- M expectation estimates.
- Precision
- Additive ε simultaneously, with failure ≤δ.
- Resources
- O(3ᵏ log(M/δ)/ε²) copies; classical processing also depends on M and k.
Huang, Kueng & Preskill: Predicting Many Properties of a Quantum System from Very Few Measurements (2020). Theorem 1; Supplementary Proposition 1, Eq. (S38), and Lemma 3 (Pauli shadow norm 3^k).
Clifford measurement snapshots have efficient stabilizer descriptions.
Store U†|b⟩ for each random Clifford U and observed bit string b.
The unknown input need not be stabilizer. This does not simulate acquisition of its outcomes.
- Input / access
- Already acquired Clifford measurement records.
- Required output
- Compact factors defining shadow snapshots.
- Precision
- Exact discrete records.
- Resources
- O(n²) bits per stabilizer factor.
Huang, Kueng & Preskill: Predicting Many Properties of a Quantum System from Very Few Measurements (2020). Theorem 1; Supplementary Proposition 1, Eq. (S38), and Lemma 3 (Pauli shadow norm 3^k). · Aaronson & Gottesman: Improved Simulation of Stabilizer Circuits (2004). Section III; tableau update rules
An amplitude determines a full output probability, but a marginal needs more information.
Return |a|² for the specified complete basis string.
For partial output events, sum over compatible complete outcomes or use a direct marginal method.
- Input / access
- a = ⟨y|U|x⟩ for basis strings x,y.
- Required output
- Probability of observing all bits of y.
- Precision
- Amplitude additive error η yields probability error at most 2η+η².
- Resources
- Constant arithmetic after computing a.
Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction
A quantum algorithm returns actual integer factors.
Combine order finding with classical factor extraction.
This upper bound does not prove classical factoring requires superpolynomial time.
- Input / access
- Binary N; modular arithmetic implemented coherently.
- Required output
- Prime factors of N.
- Precision
- Exact integers with bounded failure probability.
- Resources
- Polynomial quantum gates and classical work in log N.
Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1997). Sections 3–4 (arithmetic and QFT), Section 5 (factoring), Section 6 (discrete logarithms)
Fourier measurements also reverse modular exponentiation.
Recover x from h=gˣ.
Other group presentations require their own efficient arithmetic and encoding assumptions.
- Input / access
- Prime modulus p, generator g and h; efficient reversible modular arithmetic.
- Required output
- x modulo p−1.
- Precision
- Exact exponent with bounded error.
- Resources
- Polynomial cost in log p.
Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1997). Sections 3–4 (arithmetic and QFT), Section 5 (factoring), Section 6 (discrete logarithms)
The unknown exponent becomes a subgroup slope.
Find the kernel of f(a,b)=gᵃh⁻ᵇ.
Knowing the group order and implementing its arithmetic are explicit assumptions.
- Input / access
- Known order r, h=gˣ, domain Zr×Zr; unique encodings and coherent group operations.
- Required output
- Generators of H={(xb,b):b∈Zr}, from which x is recovered.
- Precision
- Exact subgroup with bounded failure.
- Resources
- Polynomial overhead in log r, plus group-operation cost.
Mosca & Ekert: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer (1999). Section 2 (input presentation and discrete-log example); Sections 3–4 (Fourier/eigenvalue sampling)
Repeated Fourier samples reveal the hidden subgroup.
Measure characters trivial on H and reconstruct H.
This does not solve arbitrary nonabelian hidden-subgroup problems.
- Input / access
- Known cyclic-factor presentation of finite abelian G; coherent coset-hiding f.
- Required output
- Generators for H.
- Precision
- Bounded failure; QFT approximation error budgeted across samples.
- Resources
- Polynomial in log|G| and encoding size, charging oracle cost.
Mosca & Ekert: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer (1999). Section 2 (input presentation and discrete-log example); Sections 3–4 (Fourier/eigenvalue sampling) · Kitaev: Quantum measurements and the Abelian Stabilizer Problem (1995). Abelian stabilizer and Fourier-transform algorithms
An inverse Fourier transform turns phase into readable bits.
Decode the control register after controlled powers of U.
An efficient Fourier circuit does not make arbitrary controlled powers free.
- Input / access
- Eigenstate of U; controlled U^(2ʲ), j=0,…,m−1.
- Required output
- An m-bit phase estimate.
- Precision
- O(2⁻ᵐ) phase error modulo 1 at constant confidence; implementation error is budgeted separately.
- Resources
- O(m²) ideal Fourier gates plus m controlled powers. Implementing those powers by repetition takes 2ᵐ−1 controlled-U calls; input-state preparation and gate synthesis add cost.
Cleve, Ekert, Macchiavello & Mosca: Quantum Algorithms Revisited (1998). Phase estimation and order finding
Factoring uses Fourier structure plus arithmetic.
Transform the periodic register before measurement.
The transform alone neither loads arbitrary data nor returns factors.
- Input / access
- Period encoded by modular exponentiation.
- Required output
- Samples used for rational reconstruction.
- Precision
- An approximate QFT with inverse-polynomial total error in the input bit length suffices; exact factors are verified classically.
- Resources
- O(m²) ideal rotation gates for an m-qubit exact QFT; truncating small rotations reduces this to O(m log(m/δ)) for transform error δ. Finite-gate synthesis adds cost.
Coppersmith: An approximate Fourier transform useful in quantum factoring (1994). IBM report RC 19642 (1994), archived 2002; Fourier circuit construction
A shared Fourier matrix does not mean identical computational tasks.
Compare the discrete Fourier matrix up to normalization and sign convention in two representations.
Loading amplitudes and reading every coefficient erase the naive input/output comparison. No efficient general classical simulation follows.
- Input / access
- Quantum amplitudes versus an explicit classical vector; N=2ⁿ.
- Required output
- QFT: a state. FFT: N classical coefficients.
- Precision
- Numerical or gate approximation must be budgeted.
- Resources
- QFT: O(n²) ideal rotation gates. FFT: O(N log N) arithmetic.
Coppersmith: An approximate Fourier transform useful in quantum factoring (1994). IBM report RC 19642 (1994), archived 2002; Fourier circuit construction · Cooley & Tukey: An Algorithm for the Machine Calculation of Complex Fourier Series (1965). Mathematics of Computation 19, 297–301; equations (1)–(7)
A single hidden marked item takes O(√N) quantum queries.
Amplify and measure a marked candidate.
This is an oracle bound, not free access to an arbitrary classical database.
- Input / access
- Coherent Boolean oracle with exactly one marked item; efficient uniform preparation.
- Required output
- A marked index.
- Precision
- Constant success probability, amplified by repetition.
- Resources
- O(√N) queries for one marked item.
Grover: A fast quantum mechanical algorithm for database search (1996). Search algorithm and success analysis
Checking an assignment supplies the search oracle.
Encode formula evaluation reversibly.
Formula structure may enable faster algorithms.
- Input / access
- An explicit Boolean formula of size L on n variables.
- Required output
- The same satisfying assignment, or bounded-error none.
- Precision
- Exact predicate evaluation.
- Resources
- N=2ⁿ candidates; polynomial oracle-construction and evaluation overhead in L.
Grover: A fast quantum mechanical algorithm for database search (1996). Search algorithm and success analysis · Boyer, Brassard, Høyer & Tapp: Tight bounds on quantum searching (1998). Sections 3–4: multiple/unknown solutions and the zero-solution timeout
A square-root saving over exhaustive search is not polynomial-time SAT.
Apply unknown-solution search with a timeout.
No advantage over the best classical SAT algorithm is asserted.
- Input / access
- Reversible formula checker on n-bit assignments.
- Required output
- A satisfying assignment, or bounded-error none.
- Precision
- Constant failure probability; independently verify any returned witness.
- Resources
- O(2ⁿᐟ²) predicate calls in the worst case, plus gate overhead.
Boyer, Brassard, Høyer & Tapp: Tight bounds on quantum searching (1998). Sections 3–4: multiple/unknown solutions and the zero-solution timeout
Grover search is amplitude amplification starting uniformly.
Use Hadamards as A and the predicate as the success reflection.
Unknown t needs a search schedule; no-solution cases need a timeout.
- Input / access
- N=2ⁿ candidates; t>0 marked items.
- Required output
- A marked candidate with constant success.
- Precision
- Ideal reflections; choose repetitions for the success fraction.
- Resources
- O(√(N/t)) iterations when t is known.
Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application · Boyer, Brassard, Høyer & Tapp: Tight bounds on quantum searching (1998). Sections 3–4: multiple/unknown solutions and the zero-solution timeout
Linear-system preparation uses amplification too.
Amplify the branch where the inverse-eigenvalue rotation succeeds.
Conditioning and state preparation are still charged.
- Input / access
- Original HHL circuit and its inverse, including preparation of |b⟩, a success flag, and spectral promise 1/κ≤|λ(A)|≤1.
- Required output
- Higher-probability preparation of the same solution state.
- Precision
- State and rotation errors remain part of HHL error.
- Resources
- O(κ) coherent repetitions in the original construction, each including its state-preparation and inversion costs.
Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation
The amplification operator encodes success probability in its eigenphases.
Form Q=−A S₀ A⁻¹ SΠ, where S₀ and SΠ change the signs of |0⟩ and the success subspace.
At a=0 or a=1 the occupied subspace has dimension one. Amplifying success and estimating its probability have different outputs.
- Input / access
- Unitary A, inverse A⁻¹ and the two reflections; a=sin²θ with 0<a<1.
- Required output
- Eigenvalues exp(±2iθ) on the two-dimensional span of the success and failure components of A|0⟩.
- Precision
- Exact operator identity in the ideal circuit.
- Resources
- One Q uses one A and one A⁻¹ plus reflections.
Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
Phase estimation reads the success probability.
Estimate θ for the amplification iterate and return sin²θ.
Those powers must be implemented; the method assumes coherent inverse access.
- Input / access
- Controlled powers of Q; its prepared starting state.
- Required output
- A classical estimate â.
- Precision
- Additive ε at constant confidence.
- Resources
- O(1/ε) uses of Q in the original method.
Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
Coherent repetition reduces the accuracy-dependent query count.
Treat the desired output event as the success flag.
This is not exact probability evaluation or classical simulation. Gate synthesis contributes error and cost.
- Input / access
- Circuit A, A⁻¹, their controlled versions and an efficient event reflection.
- Required output
- One event probability estimate.
- Precision
- Additive ε at constant confidence.
- Resources
- O(1/ε) coherent circuit uses.
Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
A bounded numerical output can become a success probability.
Rotate an ancilla using the value X∈[0,1].
Ordinary samples alone do not supply the required unitary access.
- Input / access
- A coherently implemented sampler and value circuit, their inverses, and controlled versions needed for the original amplitude-estimation construction.
- Required output
- Estimate of E[X].
- Precision
- Additive ε at constant confidence; include rotation error.
- Resources
- O(1/ε) coherent sampler/value uses.
Montanaro: Quantum speedup of Monte Carlo methods (2015). Section 1; Algorithm 1 and Theorem 3 for bounded outputs
Independent sampling estimates the same mean with different access.
Average bounded samples.
Correlation or biased sampling needs a separate error analysis.
- Input / access
- Independent classical samples X∈[0,1].
- Required output
- Estimate of E[X].
- Precision
- Additive ε with failure δ.
- Resources
- O(ε⁻² log(1/δ)) samples, each at its sampling cost.
Montanaro: Quantum speedup of Monte Carlo methods (2015). Section 1; Algorithm 1 and Theorem 3 for bounded outputs
For uniform candidates, success probability is the marked fraction.
Estimate a=t/N and multiply by N.
Small additive fraction error does not ensure a useful relative error for rare solutions, or an exact count.
- Input / access
- Coherent reversible predicate f, including controlled use; uniform preparation over N=2ⁿ candidates.
- Required output
- Approximate count t̂.
- Precision
- Additive εN, constant confidence.
- Resources
- O(1/ε) predicate calls.
Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application · Brassard, Høyer & Tapp: Quantum Counting (1998). Section 2, Theorems 2.1–2.3 (amplification); Section 4, Theorem 4.1 (counting error)
Every cut is already a quadratic function of bits.
Minimize −C(x), then read x as the two sides of the cut.
The map encodes the problem; it does not solve the QUBO.
- Input / access
- Explicit weighted graph.
- Required output
- A maximum cut from an exact QUBO minimizer.
- Precision
- Exact rational transformation.
- Resources
- One variable per vertex and one quadratic term per edge, with polynomial bit overhead.
Farhi, Goldstone & Gutmann: A Quantum Approximate Optimization Algorithm (2014). Sections I–II and V–VI; equations (2), (6), (12), (23) · Lucas: Ising Formulations of Many NP Problems (2014). Section 1.2 and Ising/QUBO representation; mappings use explicit objective identities
QUBO and classical Ising optimization are the same objective in different coordinates.
Convert minimizing assignments in either direction, retaining the additive constant.
No claim about complex partition sums, quantum transverse fields, or thermal sampling.
- Input / access
- Explicit rational quadratic coefficients.
- Required output
- Minimizer and energy in the other encoding.
- Precision
- Exact rational arithmetic.
- Resources
- n variables remain n variables; polynomial coefficient-conversion cost.
Lucas: Ising Formulations of Many NP Problems (2014). Section 1.2 and Ising/QUBO representation; mappings use explicit objective identities
QAOA has a concrete MaxCut guarantee on unweighted 3-regular graphs.
At p=1, suitable angles give expected cut value at least 0.6924 times optimum on that graph family.
The bound is family-specific and does not establish a quantum advantage over classical approximation algorithms.
- Input / access
- Unweighted 3-regular graph; angles from the paper's analysis.
- Required output
- Cut samples, not an optimum certificate.
- Precision
- Angle and gate errors must keep the desired expectation loss within budget.
- Resources
- O(n+m) ideal elementary gates per sample; preprocessing and repeated sampling add cost.
Farhi, Goldstone & Gutmann: A Quantum Approximate Optimization Algorithm (2014). Sections I–II and V–VI; equations (2), (6), (12), (23)
An Ising objective supplies QAOA's problem gates.
Measure a chosen-angle QAOA state to obtain candidate spin assignments and evaluate their energies classically.
No general efficient optimum or approximation-ratio guarantee is asserted.
- Input / access
- Explicit hᵢ,Jᵢⱼ, layer count p and angles.
- Required output
- Candidates with exactly evaluable classical objective values.
- Precision
- Rotation synthesis and finite-shot uncertainty are separate from optimization quality.
- Resources
- O(p(n+m)) one/two-qubit rotations before routing overhead, for m nonzero pair couplings.
Farhi, Goldstone & Gutmann: A Quantum Approximate Optimization Algorithm (2014). Sections I–II and V–VI; equations (2), (6), (12), (23) · Lucas: Ising Formulations of Many NP Problems (2014). Section 1.2 and Ising/QUBO representation; mappings use explicit objective identities
A shallow QAOA cost term only depends on a small neighborhood.
Contract each cost term's backward light cone to evaluate the expected objective at given angles.
Growing p or degree can remove the shortcut. Easy expectation evaluation does not imply easy sampling.
- Input / access
- MaxCut circuit at depth p on an explicit degree-d graph.
- Required output
- Expected cut value; no full-distribution sampling claim.
- Precision
- Exact tensor identity; finite arithmetic requires an error budget.
- Resources
- Polynomial in n for fixed d,p; local neighborhoods can have O(dᵖ) vertices, with exponential contraction cost in that size.
Farhi, Goldstone & Gutmann: A Quantum Approximate Optimization Algorithm (2014). Sections I–II and V–VI; equations (2), (6), (12), (23) · Markov & Shi: Simulating Quantum Computation by Contracting Tensor Networks (2008). Theorem 1.1; circuit-to-network construction
Candidate samples also estimate the QAOA objective.
Average C(x)/W, where W is total nonnegative edge weight.
This estimates a chosen circuit's mean, not the optimal cut value.
- Input / access
- Fresh preparations and computational-basis measurement; W>0.
- Required output
- One normalized expected cut estimate.
- Precision
- Additive δ with constant confidence.
- Resources
- O(δ⁻²) independent samples; multiply by preparation cost.
Farhi, Goldstone & Gutmann: A Quantum Approximate Optimization Algorithm (2014). Sections I–II and V–VI; equations (2), (6), (12), (23)
VQE evaluates energy through accessible measurements.
Estimate H=Σj hⱼPⱼ by measuring its Pauli terms on fresh trial states.
An arbitrary dense Hamiltonian need not have a short accessible decomposition.
- Input / access
- Explicit Pauli decomposition and repeatable trial-state preparation.
- Required output
- Trial-state energy.
- Precision
- Additive ε, constant confidence.
- Resources
- Sampling term j proportional to |hⱼ| gives O((Σj|hⱼ|)²/ε²) preparations, plus Pauli-measurement cost.
Peruzzo et al.: A Variational Eigenvalue Solver on a Photonic Quantum Processor (2014). Results: Quantum expectation estimation; Quantum variational eigensolver
Every normalized trial state gives an upper bound on the minimum energy.
Search an ansatz for low energy and report its value with measurement uncertainty.
An upper bound alone does not solve additive-ε ground-energy estimation or certify proximity to the ground state.
- Input / access
- Explicit measurable H and trial-state family.
- Required output
- If the measured estimate has error at most ε, its value plus ε is an energy upper bound at that confidence.
- Precision
- Measurement error does not bound the ansatz or optimization error.
- Resources
- Cost per energy evaluation times the number of optimizer steps; no general polynomial bound on those steps.
Peruzzo et al.: A Variational Eigenvalue Solver on a Photonic Quantum Processor (2014). Results: Quantum expectation estimation; Quantum variational eigensolver
A classical spin energy becomes a diagonal quantum Hamiltonian.
Replace sᵢ by Zᵢ. Minimum-energy queries plus fixing spins recover a minimizing assignment.
General noncommuting local Hamiltonians are a larger family. Binary-encoded exponentially large weights change the precision requirement after normalization.
- Input / access
- For this efficient-precision reduction, integer coefficients of magnitude poly(n).
- Required output
- Optimal classical spins from O(n) adaptive ground-energy calls.
- Precision
- Error below 1/3 in unscaled energy allows integer rounding. After polynomial normalization, inverse-polynomial precision suffices. If calls can fail, amplify each to failure O(1/n) before the O(n) adaptive calls.
- Resources
- n qubits and the same local terms; polynomial classical overhead and logarithmic confidence amplification when needed.
Kempe, Kitaev & Regev: The Complexity of the Local Hamiltonian Problem (2006). Definitions 2–3; Theorem 1; diagonal classical instances in Introduction · Lucas: Ising Formulations of Many NP Problems (2014). Section 1.2 and Ising/QUBO representation; mappings use explicit objective identities
Sufficient energy precision answers the promised yes/no problem.
Estimate λmin(H), then compare with (a+b)/2.
No promise is made for ground energy between a and b.
- Input / access
- A promised local-Hamiltonian instance with a<b.
- Required output
- One decision bit.
- Precision
- Additive error strictly below (b−a)/2, with bounded failure probability.
- Resources
- One ground-energy estimation call and polynomial overhead.
Kempe, Kitaev & Regev: The Complexity of the Local Hamiltonian Problem (2006). Definitions 2–3; Theorem 1; diagonal classical instances in Introduction
Phase estimation reads energies that are present in its input state.
Estimate the ground energy if the prepared state's ground-space weight is at least η>0, repeating and selecting the smallest accurate estimate.
Preparing an input with useful overlap is not supplied by phase estimation. Evolution time is not gate count.
- Input / access
- Controlled Hamiltonian evolution, a known spectral interval, and repeatable input-state preparation with promised overlap η.
- Required output
- Ground-energy estimate with bounded failure probability.
- Precision
- Additive ε; individual failure rates must be reduced before taking the minimum.
- Resources
- O(1/η) trials at constant overall confidence, logarithmic amplification overhead, and O(1/ε) evolution time per accurate trial.
Abrams & Lloyd: A Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and Eigenvectors (1999). Eigenvalue estimation algorithm; initial-state overlap requirement · Cleve, Ekert, Macchiavello & Mosca: Quantum Algorithms Revisited (1998). Phase estimation and order finding
Slow evolution can prepare an optimal spin state if a suitable gapped path is available.
Follow a known nondegenerate ground state to an Ising Hamiltonian with a unique minimizing assignment, then measure.
Neither such a path nor an inverse-polynomial gap is guaranteed for arbitrary Ising optimization. The unique-ground-state restriction avoids an endpoint degeneracy claim.
- Input / access
- A twice-smooth path with isolated nondegenerate ground state throughout; explicit gap and derivative bounds.
- Required output
- Optimal spins with failure bounded by the adiabatic error.
- Precision
- State error ε from the adiabatic theorem, plus implementation error.
- Resources
- A sufficient runtime scales as ε⁻¹[(D₁+D₂)/g²+D₁²/g³], up to constants, for g the minimum gap and Dk bounds on path derivatives.
Jansen, Ruskai & Seiler: Bounds for the Adiabatic Approximation with Applications to Quantum Computation (2007). Theorem 3, especially equation (6) · Lucas: Ising Formulations of Many NP Problems (2014). Section 1.2 and Ising/QUBO representation; mappings use explicit objective identities
The general adiabatic model can carry out any bounded-error quantum circuit computation.
Build a circuit-dependent local Hamiltonian path, recover the circuit output, and measure its acceptance bit.
This construction is not a fast algorithm for an arbitrary supplied Ising instance or arbitrary adiabatic path.
- Input / access
- An explicit finite quantum circuit and requested simulation accuracy.
- Required output
- Its acceptance decision, with the circuit promise preserved by an adequate error budget.
- Precision
- Choose state/output error below the amplified decision margin.
- Resources
- Polynomial construction size and runtime in the circuit size and inverse accuracy, using the constructed inverse-polynomial gap.
Aharonov, van Dam, Kempe, Landau, Lloyd & Regev: Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation (2007). Theorem 1.1 and circuit-to-adiabatic construction; Theorem 1.3 gives a geometric variant; preprint first posted in 2004
A reversible classical chain supplies a quantum search construction.
Find a marked state or detect that none exists using the quantized chain.
Ordinary classical transition sampling does not automatically supply coherent access. These costs cannot be omitted.
- Input / access
- Coherent stationary-state setup S, reversible transition unitaries and their inverses at cost U, coherent marking check C; absolute spectral gap δ=1−maxλ≠1|λ|>0 and marked stationary mass at least ε when nonempty.
- Required output
- A marked state or a bounded-error empty report.
- Precision
- Constant bounded error with adequately accurate coherent operations.
- Resources
- O(S+ε⁻¹ᐟ²(δ⁻¹ᐟ²U+C)).
Magniez, Nayak, Roland & Santha: Search via Quantum Walk (2011). Theorem 3; Sections 2–4; phase-estimation reflection in Theorem 6
Phase estimation is also a search tool.
Separate a walk's stationary eigenphase from other phases to approximate reflection about the stationary state.
This is a subroutine, not a standalone sampling reduction.
- Input / access
- Controlled quantum-walk steps and their inverses, a lower bound Δ on the phase gap, and clean ancillas.
- Required output
- A coherent reflection used inside the search algorithm.
- Precision
- Operator error ξ on the relevant walk subspace with ancillas initialized to zero.
- Resources
- O(Δ⁻¹ log(1/ξ)) controlled walk or inverse uses, plus logarithmic-register phase-estimation gates; for the reversible construction Δ is at least on the order of √δ.
Magniez, Nayak, Roland & Santha: Search via Quantum Walk (2011). Theorem 3; Sections 2–4; phase-estimation reflection in Theorem 6
Searching over subsets finds repeated list values with fewer oracle calls.
Run a walk on stored subsets and look for a subset containing a duplicate pair.
This is a query bound, not total runtime including data loading, memory operations or implementing the oracle.
- Input / access
- Coherent reversible value oracle for N entries in an alphabet of size M.
- Required output
- An equal pair or a bounded-error no-duplicate report.
- Precision
- Discrete exact values; constant algorithmic failure probability.
- Resources
- O(N²ᐟ³) value queries; the standard construction stores O(N²ᐟ³) entries plus their indices.
Ambainis: Quantum Walk Algorithm for Element Distinctness (2007). Theorems 3–4 and Sections 3–5; query and memory bounds; preprint first posted in 2003
Coefficient preparation and controlled selection encode A/α.
Use U=(PREPARE†⊗I) SELECT (PREPARE⊗I).
Constructing PREPARE and SELECT can be expensive. α can greatly exceed ‖A‖.
- Input / access
- A=ΣⱼcⱼUⱼ, cⱼ≥0, α=Σⱼcⱼ>0; PREPARE|0⟩=Σⱼ√(cⱼ/α)|j⟩; SELECT=Σⱼ|j⟩⟨j|⊗Uⱼ.
- Required output
- A unitary with upper-left block A/α.
- Precision
- Exact identity for exact primitives; approximate primitives contribute implementation error.
- Resources
- One SELECT, one PREPARE and its inverse; ceil(log₂ L) index qubits for L terms.
Berry, Childs, Cleve, Kothari & Somma: Simulating Hamiltonian dynamics with a truncated Taylor series (2015). Section II, equations (6)–(10); Section III, equations (18)–(23); PRL 114, 090502.
A Hermitian block supplies the signal for a quantum walk.
Construct the qubitized iterate, adding a signal qubit if needed.
The iterate is not e^(−iHt); its angles still need processing.
- Input / access
- Exact block encoding of H/α, H Hermitian; controlled encoding and inverse; reflection about its ancilla state.
- Required output
- An iterate with eigenphases ±arccos(λ/α) in the signal subspaces.
- Precision
- Exact spectral identity in the ideal model; approximate input requires a separate error budget.
- Resources
- O(1) encoding/inverse queries per iterate and O(a) elementary gates for a encoding ancillas.
Low & Chuang: Hamiltonian Simulation by Qubitization (2019). Theorems 1–4; equation (8) and Section 6; Quantum 3, 163.
Each eigenvalue supplies one two-dimensional rotation.
Apply the same chosen phase sequence across all invariant spectral subspaces.
A useful low-degree approximant and computable phases are still required.
- Input / access
- Qubitized iterate W, controlled access when required, and valid phase parameters.
- Required output
- A circuit encoding the selected bounded spectral response.
- Precision
- Ideal response exact for the selected admissible polynomial; synthesis errors add.
- Resources
- O(d) uses of W for degree d, plus reflection/rotation cost.
Low & Chuang: Hamiltonian Simulation by Qubitization (2019). Theorems 1–4; equation (8) and Section 6; Quantum 3, 163. · Low & Chuang: Optimal Hamiltonian Simulation by Quantum Signal Processing (2017). Theorem 1; quantum signal-processing construction and Chebyshev/Fourier correspondence; PRL 118, 010501.
Polynomial approximation turns a desired response into circuit parameters.
Convert an admissible polynomial approximation into a sequence of signal-processing phases.
Not every truncated Chebyshev series is admissible without rescaling or completion. No classical simulation claim follows.
- Input / access
- Classical coefficients, target interval and tolerance; parity/completion constraints satisfied.
- Required output
- Classical phase parameters for a quantum sequence.
- Precision
- Approximation error and phase-synthesis error must both fit the target tolerance.
- Resources
- Degree d sets O(d) quantum signal uses; Haah gives a classical synthesis algorithm polynomial in d and log(1/ε).
Low & Chuang: Optimal Hamiltonian Simulation by Quantum Signal Processing (2017). Theorem 1; quantum signal-processing construction and Chebyshev/Fourier correspondence; PRL 118, 010501. · Haah: Product Decomposition of Periodic Functions in Quantum Signal Processing (2019). Constructive product decomposition and numerical-precision analysis; Quantum 3, 190; arXiv v4 (2020).
Scalar signal processing lifts to singular-value transformations.
Use the two-dimensional subspaces defined by a projected unitary and its inverse.
For non-Hermitian A this is a singular-value transform, not the ordinary polynomial p(A).
- Input / access
- Encoding U with signal projectors; a real degree-d polynomial bounded by 1 on [−1,1] with matching parity.
- Required output
- A block encoding of the corresponding singular-value transform.
- Precision
- Exact in the ideal polynomial model; phase and gate errors must be budgeted.
- Resources
- O(d) queries to U and U† plus phase-controlled reflections.
Gilyén, Su, Low & Wiebe: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2019). Corollary 18 (real polynomial SVT), Theorem 41 (pseudoinverse), Section 4.1 (block encoding), Theorem 56 (Hermitian polynomial transformation); STOC 2019, preprint 2018. Section 5.3 and Corollary 64 (Gibbs filtering).
The matrix block is the input interface for QSVT.
Alternate U, U† and signal-space phase rotations.
Polylogarithmic matrix dimension alone is insufficient: encoding construction, α and polynomial degree remain costs.
- Input / access
- Exact (α,a,0) encoding U; inverse access and efficient signal reflections.
- Required output
- A circuit transforming the singular values of A/α.
- Precision
- Polynomial and circuit approximations determine error; this edge assumes exact encoded input.
- Resources
- Degree d costs O(d) oracle calls and O(ad) additional elementary gates.
Gilyén, Su, Low & Wiebe: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2019). Corollary 18 (real polynomial SVT), Theorem 41 (pseudoinverse), Section 4.1 (block encoding), Theorem 56 (Hermitian polynomial transformation); STOC 2019, preprint 2018. Section 5.3 and Corollary 64 (Gibbs filtering).
Signal processing converts walk angles into physical time evolution.
Approximate exp(−iαtx) on the normalized spectrum.
This is a quantum simulation algorithm. The bound neither prepares the input state nor classically describes the output.
- Input / access
- Exact Hermitian block encoding H/α and controlled encoding/inverse access; time t.
- Required output
- An implementation of exp(−iHt).
- Precision
- Operator-norm error ε with O(ε) heralded failure in the cited construction.
- Resources
- O(α|t|+log(1/ε)) queries is a convenient upper bound; each query and phase synthesis has its own gate cost.
Low & Chuang: Hamiltonian Simulation by Qubitization (2019). Theorems 1–4; equation (8) and Section 6; Quantum 3, 163.
Short Taylor expansions give another simulation construction.
Split time into segments and implement each polynomial with LCU and robust oblivious amplification.
A poor decomposition increases T. This cost is for the cited Taylor construction, not a claim of optimality.
- Input / access
- Hermitian H=ΣⱼcⱼUⱼ, cⱼ≥0; coherent term selection, coefficient preparation and inverses; T=|t|Σⱼcⱼ.
- Required output
- An evolution circuit whose successful ancilla block approximates exp(−iHt).
- Precision
- Operator-norm error O(ε) in the successful block and O(ε) failure; discarding ancillas gives O(ε) state error in the cited robust construction.
- Resources
- For T≥1, O(T log(T/ε)/log log(T/ε)) selected-term uses asymptotically, plus coefficient preparation and other gates.
Berry, Childs, Cleve, Kothari & Somma: Simulating Hamiltonian dynamics with a truncated Taylor series (2015). Section II, equations (6)–(10); Section III, equations (18)–(23); PRL 114, 090502.
A block of p(H/α) can reweight an input state.
Apply the transformed encoding to |b⟩ and select the signal ancillas.
A small success amplitude or high polynomial degree can remove efficiency. No full classical vector is returned.
- Input / access
- Exact Hermitian encoding U, controlled-U, U†; |b⟩ preparation and inverse; real degree-d p approximating f(αx)/c, c>0, with |p(x)|≤1/2 on [−1,1].
- Required output
- The normalized state proportional to f(H)|b⟩, approximately.
- Precision
- With s=‖f(H)b‖/c>0 and η<s/2, total polynomial/block error η gives O(η/s) normalized-state error.
- Resources
- O(d) encoding queries per attempt, including one controlled-U. Success probability Θ(s²): O(1/s²) expected repetitions, or O(1/s) amplification overhead at constant success. Charge state preparation.
Gilyén, Su, Low & Wiebe: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2019). Corollary 18 (real polynomial SVT), Theorem 41 (pseudoinverse), Section 4.1 (block encoding), Theorem 56 (Hermitian polynomial transformation); STOC 2019, preprint 2018. Section 5.3 and Corollary 64 (Gibbs filtering). · Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
Polynomial inversion avoids estimating every eigenvalue first.
Approximate 1/(2κx), apply it to |b⟩, and amplify the successful branch.
This simple construction is not the best known condition-number dependence. Observable readout still has its own accuracy cost.
- Input / access
- Exact (1,a,0) encoding of Hermitian A with 1/κ≤|λ(A)|≤1, κ≥2; coherent |b⟩ preparation and inverses.
- Required output
- A state ε-close to A⁻¹|b⟩/‖A⁻¹b‖.
- Precision
- Choose block approximation O(ε/κ) so normalization preserves O(ε) state error.
- Resources
- O(κ log(κ/ε)) encoding queries per attempt; amplification overhead O(κ/‖A⁻¹b‖), at worst O(κ). Charge state preparation.
Gilyén, Su, Low & Wiebe: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2019). Corollary 18 (real polynomial SVT), Theorem 41 (pseudoinverse), Section 4.1 (block encoding), Theorem 56 (Hermitian polynomial transformation); STOC 2019, preprint 2018. Section 5.3 and Corollary 64 (Gibbs filtering). · Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
One ancilla can measure the expectation of a Hermitian unitary.
Average the ±1 Hadamard-test outcomes.
This edge covers Hermitian unitaries. General observables need a decomposition or other measurement access.
- Input / access
- Fresh |ψ⟩ preparations and controlled-M for a Hermitian unitary M, such as a Pauli operator.
- Required output
- A classical estimate of ⟨ψ|M|ψ⟩.
- Precision
- Additive ε with failure at most δ.
- Resources
- O(ε⁻² log(1/δ)) preparations and controlled-M calls.
Aharonov, Jones & Landau: A Polynomial Quantum Algorithm for Approximating the Jones Polynomial (2009). Section 2.2 (Hadamard test); Section 3.3 (averaging and error); Algorithmica 55, 395–421, preprint 2005.
Interference estimates an amplitude instead of squaring it.
Use V=Xʸ U Xˣ so ⟨0|V|0⟩=⟨y|U|x⟩, and measure both components.
Additive estimation is not exact or relative-error evaluation. Exponentially small amplitudes can require exponentially many calls.
- Input / access
- Explicit circuit U with controlled implementation; basis strings x,y; Xˣ and Xʸ flip the corresponding bits.
- Required output
- Additive estimates of the real and imaginary amplitude components.
- Precision
- Each component within ε with joint failure at most δ.
- Resources
- O(ε⁻² log(1/δ)) controlled circuit uses, each including all gates of U.
Aharonov, Jones & Landau: A Polynomial Quantum Algorithm for Approximating the Jones Polynomial (2009). Section 2.2 (Hadamard test); Section 3.3 (averaging and error); Algorithmica 55, 395–421, preprint 2005.
The Hadamard-test mean can use amplitude estimation.
Treat ancilla outcome 0 as success and convert p to the mean 2p−1.
Controlled-unitary access and long coherent sequences replace independent samples; gate synthesis and input preparation remain costs.
- Input / access
- Coherent Hadamard-test preparation circuit, inverse, controlled versions and a success reflection.
- Required output
- A classical estimate of its real or imaginary overlap.
- Precision
- Additive ε at constant confidence.
- Resources
- O(1/ε) coherent preparation/inverse uses; confidence amplification adds O(log(1/δ)).
Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application · Aharonov, Jones & Landau: A Polynomial Quantum Algorithm for Approximating the Jones Polynomial (2009). Section 2.2 (Hadamard test); Section 3.3 (averaging and error); Algorithmica 55, 395–421, preprint 2005.
Fourier samples expose linear constraints on the mask.
Collect a spanning set of sampled constraints and solve over F₂.
The speedup is in the oracle model. Promise violations and oracle-construction costs are not covered.
- Input / access
- A coherent reversible oracle for f satisfying the injective/two-to-one promise; n-bit inputs and m-bit outputs.
- Required output
- The hidden nonzero s, or 0ⁿ for an injective f.
- Precision
- Exact bits with zero error in the original expected-time algorithm; candidate verification uses the promise.
- Resources
- O(n) expected oracle calls plus polynomial classical binary linear algebra and Hadamard gates.
Simon: On the Power of Quantum Computation (1997). Definition 3.1 and Theorem 3.2; Fourier-twice routine and linear equations; SIAM J. Comput. 26(5), 1474–1483.
The mask generates the hidden subgroup.
Use the same f over G=(Z₂)ⁿ and ask for generators of H.
This is a special abelian HSP. It says nothing about arbitrary nonabelian hidden subgroups.
- Input / access
- Simon's promised oracle; H={0,s}, or H={0} for injective f.
- Required output
- Subgroup generators immediately identify s.
- Precision
- Exact reduction; transfer the HSP solver's failure guarantee.
- Resources
- No extra function-query cost beyond the HSP instance; polynomial classical overhead.
Simon: On the Power of Quantum Computation (1997). Definition 3.1 and Theorem 3.2; Fourier-twice routine and linear equations; SIAM J. Comput. 26(5), 1474–1483. · Mosca & Ekert: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer (1999). Section 2 (input presentation and discrete-log example); Sections 3–4 (Fourier/eigenvalue sampling)
The Fourier transform over the XOR group is especially simple.
Use H⊗ⁿ before the function query and on its input register afterward.
The group is (Z₂)ⁿ, not the cyclic group Z₂ⁿ. Classical linear algebra is still required to recover s.
- Input / access
- Simon oracle and all-zero registers; Fourier transform over (Z₂)ⁿ.
- Required output
- Uniform samples y satisfying y·s=0 when s≠0; uniform y for an injective f.
- Precision
- Exact distribution with ideal gates.
- Resources
- 2n Hadamard gates and one function query per sample, plus oracle ancillas.
Simon: On the Power of Quantum Computation (1997). Definition 3.1 and Theorem 3.2; Fourier-twice routine and linear equations; SIAM J. Comput. 26(5), 1474–1483. · Mosca & Ekert: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer (1999). Section 2 (input presentation and discrete-log example); Sections 3–4 (Fourier/eigenvalue sampling)
Filter half of a maximally entangled pair, then normalize.
Apply a constant-rescaled filter F/c, F=exp(−β(H+I)/2), to the first register of |Φ_D⟩. For example c=4 leaves room for |p|≤1/2. Discard the reference register after success.
q can be exponentially small; this is not generic efficient thermalization. The physical inverse temperature rescales with H. The β≥1 edge states one regime; no partition-function estimate is returned.
- Input / access
- D=2ⁿ; Hermitian H with ‖H‖≤1 and an exact (1,a,0) block encoding plus controlled/inverse access; β≥1; |Φ_D⟩ preparation; a certified lower bound 0<q₀≤q=e^(−β)Z/D. The bound q₀=exp(−2β) always suffices.
- Required output
- A purification whose reduced state approximates ρβ; constant heralded success after amplification.
- Precision
- Trace distance O(ε) for filter/circuit error η=O(ε√q₀); signal success is Θ(q), including constant rescaling. Independent attempts increase overall success.
- Resources
- A bounded polynomial filter uses d=O(√β log(1/η)) encoding queries. Expected amplified cost O(d/√q), plus repeated pair preparation, phase synthesis and other gates.
Gilyén, Su, Low & Wiebe: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2019). Corollary 18 (real polynomial SVT), Theorem 41 (pseudoinverse), Section 4.1 (block encoding), Theorem 56 (Hermitian polynomial transformation); STOC 2019, preprint 2018. Section 5.3 and Corollary 64 (Gibbs filtering). · Brassard, Høyer, Mosca & Tapp: Quantum Amplitude Amplification and Estimation (2002). Section 2, Theorems 2–3 and equations (1)–(5); Section 4, Theorem 12 and its counting application
A controlled accept flag reshapes the amplitude profile.
Use accept amplitudes σᵢ/(Rπᵢ), then amplify the accept subspace.
Ordinary samples do not supply O†. Large amplitude ratios or expensive profile access can remove the speedup.
- Input / access
- Known normalized π,σ≥0 with supp(σ)⊆supp(π); O|0⟩=Σᵢπᵢ|ξᵢ⟩|i⟩ for unknown normalized |ξᵢ⟩; O† and ratio rotations; R=max_{σᵢ>0} σᵢ/πᵢ.
- Required output
- The target coherent state Σᵢσᵢ|ξᵢ⟩|i⟩.
- Precision
- Exact target and certainty with ideal profile data and adjusted amplification phases; finite rotations need an explicit state-error budget.
- Resources
- O(R) calls to O and O† for the exact target; charge classical profile processing and every ratio-controlled rotation separately.
Ozols, Roetteler & Roland: Quantum rejection sampling (2012). Theorem 1, Sections 4.1–4.3 (known profiles and strong variant), Section 5.1 (HHL reweighting); ITCS 2012, 290–308.
HHL inversion contains a coherent resampling step.
With eigenvalues labelled, accept component λᵢ with amplitude 1/(κλᵢ), then uncompute the labels.
This identifies a subroutine, not the full runtime of HHL. Exact eigenvalue labels are an access assumption, not free information.
- Input / access
- Positive-definite A with spectrum in [1/κ,1]; ideal coherent eigenvalue-labelling oracle and inverse; |b⟩ preparation/reflection; implementable reciprocal rotations.
- Required output
- The normalized A⁻¹|b⟩ branch used by HHL.
- Precision
- Exact state in the ideal spectral-oracle model. Approximate phase estimation and rotations need the separate HHL error analysis.
- Resources
- Expected O(κ/‖A⁻¹b‖) spectral-label/reflection uses for the strong resampling step; charge their implementation and |b⟩ preparation.
Ozols, Roetteler & Roland: Quantum rejection sampling (2012). Theorem 1, Sections 4.1–4.3 (known profiles and strong variant), Section 5.1 (HHL reweighting); ITCS 2012, 290–308. · Harrow, Hassidim & Lloyd: Quantum Algorithm for Solving Linear Systems of Equations (2009). Main algorithm; Appendix on observable estimation
Density matrix renormalization group (DMRG)
Related to Matrix product states.
Optimize a compact tensor state to approximate a many-body ground state.
For an explicitly specified one-dimensional local Hamiltonian, finite-system DMRG repeatedly optimizes a small part of the state and keeps the most important Schmidt components while sweeping along the chain. Its state can be represented as an MPS with bond dimension χ, using O(n d χ²) coefficients for n sites of local dimension d. The result is an approximate ground-state MPS and its variational energy; this is a ground-state optimization method. Runtime includes local eigenvalue solves, tensor contractions and all sweeps. A small χ can miss important entanglement, and sweeps can stall. Bond-dimension and convergence checks are needed; the method has no general guarantee of finding an arbitrary Hamiltonian’s ground state efficiently.
Rommer & Östlund: Class of ansatz wave functions for one-dimensional spin systems and their relation to the density matrix renormalization group (1997). Sections II–IV; matrix-product variational form and DMRG fixed-point connection. Phys. Rev. B 55, 2164. · White: Density matrix renormalization group algorithms with a single center site (2005). Page 1: finite-system DMRG step and sweep; convergence limitations. Phys. Rev. B 72, 180403(R).
Quasiprobability simulation
Related to Circuit probability.
Estimate an output probability by averaging signed trajectories.
For a product input, explicit bounded-arity gates and a product measurement effect E, choose a finite normalized frame and dual. Write Wρ, WU and WE for their compatible quasiprobabilities. Define M=‖Wρ‖₁ × (∏g maxλ Σλ′ |WUg(λ′|λ)|) × maxλ |WE(λ)|. Sampling initial values and transitions according to their absolute weights produces an unbiased estimator bounded by M. For 0<ε,δ<1, ceil(2M² ε⁻² ln(2/δ)) independent trajectories suffice for additive probability error ε with failure ≤δ, for M>0. Initial sampling, local transition sampling, normalizers and effect evaluation must be efficiently available; their costs and rounding errors remain charged. A product frame and fixed local dimension make the local access manageable. Large negativity can make M exponential. This estimates one probability, not a relative error on rare outcomes or an automatic sampler for the complete distribution.
Pashayan, Wallman & Bartlett: Estimating outcome probabilities of quantum circuits using quasiprobabilities (2015). Equations (2), (6), (10)–(12); product-input, bounded-arity gate and product-measurement access assumptions.
Continuous-variable Gaussian simulation
Related to Boson sampling.
Gaussian optical states can be tracked using means and covariances.
Given Gaussian input moments and explicit Gaussian operations, a classical simulator updates O(m²) real parameters for m modes and draws Gaussian measurement outcomes with polynomial arithmetic cost. This covers Gaussian channels, homodyne or heterodyne detection, and efficiently computed feed-forward that preserves Gaussian conditional states. Finite squeezing, detector resolution, parameter precision and accumulated rounding error require a numerical budget. Non-Gaussian inputs or measurements fall outside the guarantee. In particular, ordinary boson sampling uses occupied Fock inputs and photon counting. Gaussian boson sampling still uses photon counting, so its Gaussian input alone does not put it inside this simulation theorem. The 2002 extension includes mixed Gaussian states and Gaussian noise.
Bartlett, Sanders, Braunstein & Nemoto: Efficient Classical Simulation of Continuous Variable Quantum Information Processes (2002). Theorem 2 and preceding finite-precision discussion; PRL 88, 097904. · Bartlett & Sanders: Efficient Classical Simulation of Optical Quantum Information Circuits (2002). Equation (7), main theorem, Gaussian-measurement and photon-counting discussion; PRL 89, 207903. · Aaronson & Arkhipov: The Computational Complexity of Linear Optics (2013). Theorem 3.10; approximate-sampling conjectures · Hamilton, Kruse, Sansoni, Barkhofen, Silberhorn & Jex: Gaussian Boson Sampling (2017). Abstract and Gaussian-state photon-pattern probabilities: Gaussian inputs measured in the Fock basis. Phys. Rev. Lett. 119, 170501.
Sample/query-access low-rank linear solving
Related to HHL linear solver.
Classical sampling can reproduce selected linear-algebra outputs under strong data-access promises.
One sufficient case: A has rank at most k, ‖A‖≤1, every nonzero singular value is at least 1/κ, and nonzero b lies in the column space of A. Assume fast entry queries to b, plus queries to A, its row norms and its Frobenius norm, row sampling proportional to squared row norm, and within-row sampling proportional to squared entry magnitude. For 0<ε,η<1, Chia et al. construct an implicit x̃ satisfying ‖x̃−A⁺b‖≤ε‖A⁺b‖ with failure probability at most η. Their Algorithm 1 preprocessing takes Õ(κ¹⁶k⁶‖A‖F⁶/ε⁶), with logarithmic dimension and confidence factors suppressed. The output supports classical entry queries and squared-magnitude sampling with further polynomial cost. Building the input sampling data structure must also be charged. This covers low-rank, well-conditioned instances with this access model; it does not classically simulate general sparse full-rank HHL, prepare its quantum output state, or list every solution coordinate in logarithmic time.
Chia, Gilyén, Lin, Lloyd, Tang & Wang: Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension (2020). Definitions 1–3, Algorithm 1 and Theorem 4; Section 2.1.1 data-access structures. ISAAC 2020, 47:1–47:17.
Density-matrix and noisy-circuit simulation
Related to Statevector simulator.
Track a mixed quantum state and its explicitly specified noise channels.
Given an initial density matrix ρ and explicit quantum channels, update ρ→Σj KjρKj† using supplied Kraus operators satisfying Σj Kj†Kj=I. A full n-qubit density matrix stores 4ⁿ complex entries. For channels acting on a fixed number of qubits with bounded Kraus rank, direct local updates take O(4ⁿ) arithmetic per channel; larger channel descriptions incur additional cost. The output is the full mixed state, from which specified probabilities and observables can be computed. This direct propagation has numerical roundoff and model error but no trajectory-sampling error. Noise parameters must be supplied; the simulator does not infer them from hardware. Mixed states and noise are covered generally at exponential memory cost, so adding noise alone gives no efficient classical-simulation guarantee.
Jones, Brown, Bush & Benjamin: QuEST and High Performance Simulation of Quantum Computers (2019). Section II.B.1, Eq. (2): full density matrix stored as a 2n-qubit vector; local updates imply the stated exponential arithmetic cost. Scientific Reports 9, 10736.
Ground-state preparation by spectral filtering
Related to Ground-state energy.
Keep a ground-state component already present in an initial state.
A quantum algorithm, distinct from returning the lowest energy. Assume a nondegenerate ground state |ψ₀⟩, exact (α,a,0) block encoding of H with controlled and inverse access, and preparation of |φ⟩ and its inverse. Known promises are |⟨ψ₀|φ⟩|≥γ>0 and λ₀≤μ−Δ/2<μ+Δ/2≤λ₁ for Δ>0. A polynomial approximates the projector below μ; amplitude amplification raises its success probability. Lin–Tong give expected O((α/(γΔ)) log(1/(γε))) encoding queries and O(1/γ) initial-state preparations for output overlap |⟨ψ₀|ψout⟩|≥1−ε. Gate synthesis and oracle construction are additional costs. Small overlap or gap can make the method expensive. Finding the separating energy bound is another task when it is not supplied. This prepares a quantum state, not all classical eigenvector entries.
Lin & Tong: Near-optimal ground state preparation (2020). Section 3, promises (P1)–(P2), Theorem 6. Fidelity there is unsquared state overlap; Quantum 4, 372.
Quantum complexity classes
Arrows A → B mean A ⊆ B: every yes/no language in A is in B. Double arrows mean equality. No drawn containment claims strictness. The class map uses total-language versions, classical bit-string inputs, uniform algorithms and standard finite gate sets. Promised circuit acceptance and Local Hamiltonian are identified explicitly as PromiseBQP and PromiseQMA examples in the task links. Sampling, function output and state preparation are distinct from decision-language problems. Distance and height are layout choices, not numerical difficulty.
Containment arrows mean that every language in the source class is in the target class. They do not assert strict containment. A double arrow denotes equality.
P
Efficient deterministic classical decisions.
A language has a deterministic algorithm running in time polynomial in the input bit length.
Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions.
Related task: Clifford circuits
Clifford acceptance thresholds are in P.
For explicit H/S/CNOT circuits, basis input and a specified bit pattern on a chosen subset of final computational-basis measurements, a stabilizer tableau computes that pattern’s probability exactly in polynomial time. Comparing it with a rational threshold is a decision problem in P. This excludes arbitrary Boolean predicates on the measured string. The atlas node itself asks for samples, which is a different output requirement.
Aaronson & Gottesman: Improved Simulation of Stabilizer Circuits (2004). Section III; tableau update rules
BPP
Efficient randomized classical decisions.
A polynomial-time randomized algorithm answers correctly with probability at least 2/3 on every input. Repetition reduces error.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits.
BQP
Efficient quantum decisions.
A uniform polynomial-size quantum circuit family decides a language with success probability at least 2/3 on every input. Standard finite universal gates and classical bit-string inputs are assumed.
Ethan Bernstein & Umesh Vazirani: Quantum Complexity Theory (1997). Definition of BQP, bounded-error amplification, and simulation of probabilistic computation: BPP ⊆ BQP.
Related task: Circuit acceptance
Circuit acceptance is PromiseBQP-complete.
For an explicitly given circuit, promise acceptance probability at least 2/3 or at most 1/3. Running it gives membership; compiling any uniform bounded-error quantum computation gives hardness. This is a promise-problem counterpart of BQP, not a total-language completeness claim.
Ethan Bernstein & Umesh Vazirani: Quantum Complexity Theory (1997). Definition of BQP, bounded-error amplification, and simulation of probabilistic computation: BPP ⊆ BQP.
Related task: Integer factoring
Factoring has a quantum polynomial-time algorithm.
Producing the full prime factorization is a function task. A corresponding decision question, whether N has a nontrivial divisor at most k, is in BQP by factoring and comparing. Shor does not establish a separation from classical polynomial time.
Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1997). Sections 3–4 (arithmetic and QFT), Section 5 (factoring), Section 6 (discrete logarithms)
Related task: Boson sampling
Boson sampling has a different output type.
Boson sampling asks for a random output from a distribution. BQP classifies yes/no decisions. Neither efficient quantum sampling nor a permanent formula by itself classifies the whole sampling task as BQP or #P. Its approximation assumptions remain in the task map.
Aaronson & Arkhipov: The Computational Complexity of Linear Optics (2013). Theorem 3.10; approximate-sampling conjectures
NP
Short classical proofs with deterministic verification.
Yes instances have a polynomial-length bit-string witness accepted by a deterministic polynomial-time verifier. No witness is accepted on a no instance.
Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions.
Related task: SAT search
SAT decision is NP-complete.
Asking whether a Boolean formula has a satisfying assignment is NP-complete. The atlas node asks to produce an assignment, a search task. SAT search is solvable using polynomially many adaptive SAT-decision calls through variable fixing.
Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions.
MA
Short classical proofs with randomized verification.
A polynomial-length classical witness is checked by a randomized polynomial-time verifier. Some witness is accepted with probability ≥2/3 on yes instances; every witness is accepted with probability ≤1/3 on no instances.
Chris Marriott & John Watrous: Quantum Arthur-Merlin Games (2005). Sections 1–2 (proof-system definitions), Theorem 3.3 (amplification), Theorem 3.4 (QMA ⊆ PP). Elementary inclusions are consequences of these definitions.
QCMA
Classical proofs checked by a quantum computer.
Like MA, but the verifier is quantum. The proof remains a polynomial-length classical bit string, supplied before the verifier runs.
Scott Aaronson & Greg Kuperberg: Quantum Versus Classical Proofs and Advice (2007). Section 1: QMA and QCMA definitions. A QCMA verifier can measure a supplied witness in the computational basis, proving QCMA ⊆ QMA.
QMA
Quantum proofs checked by a quantum computer.
A polynomial-qubit witness is checked in quantum polynomial time. Some state succeeds with probability ≥2/3 on yes instances; every state succeeds with probability ≤1/3 on no instances.
Chris Marriott & John Watrous: Quantum Arthur-Merlin Games (2005). Sections 1–2 (proof-system definitions), Theorem 3.3 (amplification), Theorem 3.4 (QMA ⊆ PP). Elementary inclusions are consequences of these definitions. · Scott Aaronson & Greg Kuperberg: Quantum Versus Classical Proofs and Advice (2007). Section 1: QMA and QCMA definitions. A QCMA verifier can measure a supplied witness in the computational basis, proving QCMA ⊆ QMA.
Related task: Local Hamiltonian
Local Hamiltonian with a promise gap is PromiseQMA-complete.
For polynomially many explicitly described 2-local qubit terms of polynomially bounded norm, and rational thresholds a<b with inverse-polynomial gap, decide whether the minimum eigenvalue is ≤a or ≥b, under that promise. The gap is between decision thresholds, not a promise of a spectral gap above the ground state. No claim is made for arbitrary precision or for outputting a ground state.
Kempe, Kitaev & Regev: The Complexity of the Local Hamiltonian Problem (2006). Definitions 2–3; Theorem 1; diagonal classical instances in Introduction
AWPP
A counting upper bound for quantum computation.
A normalized GapP function approximates a language’s 0/1 answer with bounded error and stays in [0,1] on every input. GapP counts accepting minus rejecting branches; the normalizing positive integer is computable in polynomial time.
Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples.
PostBQP
Quantum decisions with postselection.
A uniform polynomial-size quantum circuit over Hadamard and Toffoli gates may condition on a designated outcome of nonzero, potentially exponentially small probability. Conditioned on that event, the answer is correct with probability at least 2/3 on every input. Postselection is an additional formal resource.
Scott Aaronson: Quantum Computing, Postselection, and Probabilistic Polynomial-Time (2005). Definition 1 and Theorem 4 (PostBQP = PP). Use a standard finite gate set, such as Hadamard and Toffoli, and nonzero postselection probability.
PP
Decide which answer has a strict majority of random branches.
A polynomial-time randomized machine accepts with probability >1/2 on yes instances and ≤1/2 on no instances. The advantage can be exponentially tiny, so polynomially many experimental runs need not reveal it.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples.
Related task: Circuit probability
An exact acceptance threshold can be PP-complete.
For Hadamard/Toffoli circuits with an explicit basis input and a designated output bit, deciding whether its acceptance probability exceeds 1/2 is PP-complete. Membership follows by summing signed computation paths; hardness follows by implementing a PP machine’s random bits and reversible classical computation. The gap from 1/2 can be exponentially small. This differs from returning the exact probability or estimating it to inverse-polynomial additive error.
Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples. · Scott Aaronson: Quantum Computing, Postselection, and Probabilistic Polynomial-Time (2005). Definition 1 and Theorem 4 (PostBQP = PP). Use a standard finite gate set, such as Hadamard and Toffoli, and nonzero postselection probability.
QIP
Interactive proofs with quantum messages.
A polynomial-time quantum verifier exchanges polynomially many polynomial-size quantum messages with an unbounded prover. Completeness and soundness are separated by a constant gap.
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay & John Watrous: QIP = PSPACE (2011). Main equality and Section 2: polynomial-round quantum interactive proofs. Conference version STOC 2010; journal JACM 2011.
PSPACE
Decisions using polynomial classical memory.
A deterministic classical algorithm uses space polynomial in the input length. Its running time may be exponential.
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay & John Watrous: QIP = PSPACE (2011). Main equality and Section 2: polynomial-round quantum interactive proofs. Conference version STOC 2010; journal JACM 2011. · Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples.
L
Classical decisions using logarithmic memory.
A deterministic machine decides the language with a read-only input tape and O(log n) writable work space. The input itself does not count toward work space.
Walter J. Savitch: Relationships between Nondeterministic and Deterministic Tape Complexities (1970). Space-bounded machine and configuration-reachability framework. L ⊆ NL is definitional; NL ⊆ P follows by searching its polynomial-size configuration graph, not by applying the squared-space bound alone.
NL
Logarithmic memory with nondeterministic choices.
A nondeterministic machine uses O(log n) work space. A yes input has an accepting computation branch; a no input has none. A representative problem is reachability in a directed graph.
Walter J. Savitch: Relationships between Nondeterministic and Deterministic Tape Complexities (1970). Space-bounded machine and configuration-reachability framework. L ⊆ NL is definitional; NL ⊆ P follows by searching its polynomial-size configuration graph, not by applying the squared-space bound alone.
RP
Randomized decisions with no false positives.
A polynomial-time randomized machine accepts yes inputs with probability at least 1/2 and never accepts no inputs. Repetition improves success while keeping the one-sided guarantee.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
coRP
Randomized decisions with no false negatives.
The complement of RP: yes inputs are always accepted, while no inputs are rejected with probability at least 1/2. An accepting answer may be wrong, but a rejecting answer is reliable.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
coNP
Short classical proofs that an answer is no.
The complements of NP languages. For example, Boolean unsatisfiability is in coNP: its no instances have satisfying assignments that can be verified in polynomial time. Membership alone does not give short certificates for yes instances.
Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions. · Larry J. Stockmeyer: The Polynomial-Time Hierarchy (1976). Definition of the polynomial hierarchy, its quantified characterizations and collapse properties. NP and coNP are its first level.
PH
A hierarchy of alternating existence and universal questions.
The union of all fixed finite levels Σₖᴾ and Πₖᴾ. Each level allows a constant number of alternating blocks of existential and universal quantifiers over polynomial-length strings, followed by a polynomial-time predicate. The level may depend on the language but not the input length.
Larry J. Stockmeyer: The Polynomial-Time Hierarchy (1976). Definition of the polynomial hierarchy, its quantified characterizations and collapse properties. NP and coNP are its first level. · Larry J. Stockmeyer & Albert R. Meyer: Word Problems Requiring Exponential Time (Preliminary Report) (1973). Section 4, Theorem 4.1 (fixed-level quantified characterization) and Theorem 4.3 (quantified Boolean formulas and polynomial space). Polynomial-space evaluation recursively enumerates the quantified assignments.
EXP
Classical decisions in exponential time.
Also called EXPTIME: the union of deterministic time bounds 2^(n^k) over constants k. This permits more than polynomial time, while remaining a bounded resource class. The time hierarchy theorem proves P ≠ EXP.
Juris Hartmanis & Richard E. Stearns: On the Computational Complexity of Algorithms (1965). Deterministic time hierarchy. The strict inclusion P ⊊ EXP is a standard consequence of time hierarchy, not an assumption. · Chris Marriott & John Watrous: Quantum Arthur-Merlin Games (2005). Sections 1–2 (proof-system definitions), Theorem 3.3 (amplification), Theorem 3.4 (QMA ⊆ PP). Elementary inclusions are consequences of these definitions.
ZPP
Always-correct randomized decisions in expected polynomial time.
A randomized algorithm returns the correct yes/no answer with probability 1, and its expected running time is polynomial on every input. Equivalently, a bounded polynomial-time algorithm can output the correct answer or “undecided”, with at least 1/2 probability of answering and zero probability of a wrong answer. ZPP = RP ∩ coRP.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
Complexity containments & equalities
P → BPP
Deterministic algorithms are randomized algorithms that ignore their coins.
Any P decision algorithm also satisfies the BPP definition.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Zero error remains zero error.
- Resources
- Polynomial time; no randomness is needed.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits.
P → NP
A verifier may solve the problem itself and ignore the proof.
Every P language has a polynomial-time NP verifier.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Exact acceptance.
- Resources
- Polynomial time; the witness may be empty.
Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions.
BPP → BQP
Quantum circuits can reproduce randomized classical computation.
A quantum computer can run any bounded-error classical decision algorithm.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- The usual 2/3 versus 1/3 gap when bounded error is involved.
- Resources
- Polynomial overhead using reversible computation and random-bit preparation.
Ethan Bernstein & Umesh Vazirani: Quantum Complexity Theory (1997). Definition of BQP, bounded-error amplification, and simulation of probabilistic computation: BPP ⊆ BQP.
BPP → MA
A randomized verifier may ignore the proof.
Any BPP decision procedure is an MA verifier.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- The usual 2/3 versus 1/3 gap when bounded error is involved.
- Resources
- Polynomial time; the witness may be empty.
Chris Marriott & John Watrous: Quantum Arthur-Merlin Games (2005). Sections 1–2 (proof-system definitions), Theorem 3.3 (amplification), Theorem 3.4 (QMA ⊆ PP). Elementary inclusions are consequences of these definitions. · John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits.
NP → MA
A randomized verifier can run deterministic verification.
Every NP proof system is an MA proof system.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Perfect completeness and soundness already meet the MA thresholds.
- Resources
- Same witness and polynomial verification time.
Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions. · Chris Marriott & John Watrous: Quantum Arthur-Merlin Games (2005). Sections 1–2 (proof-system definitions), Theorem 3.3 (amplification), Theorem 3.4 (QMA ⊆ PP). Elementary inclusions are consequences of these definitions.
MA → QCMA
Quantum verification can reproduce randomized classical verification.
An MA proof remains valid with a quantum verifier.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- The usual 2/3 versus 1/3 gap when bounded error is involved.
- Resources
- Polynomial overhead; witness stays classical.
Chris Marriott & John Watrous: Quantum Arthur-Merlin Games (2005). Sections 1–2 (proof-system definitions), Theorem 3.3 (amplification), Theorem 3.4 (QMA ⊆ PP). Elementary inclusions are consequences of these definitions. · Ethan Bernstein & Umesh Vazirani: Quantum Complexity Theory (1997). Definition of BQP, bounded-error amplification, and simulation of probabilistic computation: BPP ⊆ BQP. · Scott Aaronson & Greg Kuperberg: Quantum Versus Classical Proofs and Advice (2007). Section 1: QMA and QCMA definitions. A QCMA verifier can measure a supplied witness in the computational basis, proving QCMA ⊆ QMA.
BQP → QCMA
A quantum verifier may ignore the proof.
Any BQP algorithm gives a QCMA proof system.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- The usual 2/3 versus 1/3 gap when bounded error is involved.
- Resources
- Polynomial quantum time; no witness needed.
Ethan Bernstein & Umesh Vazirani: Quantum Complexity Theory (1997). Definition of BQP, bounded-error amplification, and simulation of probabilistic computation: BPP ⊆ BQP. · Scott Aaronson & Greg Kuperberg: Quantum Versus Classical Proofs and Advice (2007). Section 1: QMA and QCMA definitions. A QCMA verifier can measure a supplied witness in the computational basis, proving QCMA ⊆ QMA.
QCMA → QMA
Classical witnesses are a special case of quantum witnesses.
Use a QMA verifier that first measures its witness as classical bits, then runs the QCMA verifier.
Measuring first ensures a malicious superposition gives only a mixture of classical witnesses. No strict separation is asserted.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- The usual 2/3 versus 1/3 gap when bounded error is involved.
- Resources
- Polynomial quantum time; same witness length in qubits.
Scott Aaronson & Greg Kuperberg: Quantum Versus Classical Proofs and Advice (2007). Section 1: QMA and QCMA definitions. A QCMA verifier can measure a supplied witness in the computational basis, proving QCMA ⊆ QMA.
BQP → AWPP
Quantum acceptance probabilities have a suitable counting representation.
Every BQP language has an AWPP description.
The counting representation is not an efficient algorithm for evaluating its counts.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- The usual 2/3 versus 1/3 gap when bounded error is involved.
- Resources
- Polynomial-size counting-machine description, not a polynomial-time classical simulation.
Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples.
AWPP → PP
The sign of a shifted counting function distinguishes the cases.
An AWPP normalized count can be thresholded by a PP machine.
This is a decision-class upper bound, not an efficient practical simulation.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- AWPP’s gap allows a sign comparison at the midpoint.
- Resources
- Polynomial machine description; PP may require an exponentially small bias.
Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples.
QMA → PP
Quantum verification fits inside unbounded-error counting.
Decide a QMA language: yes instances admit a witness accepted with probability at least 2/3, while every witness on a no instance is accepted with probability at most 1/3.
Does not produce a witness, ground state, or efficient classical simulation.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Standard QMA gap is amplified exponentially; the resulting PP bias need not be noticeable.
- Resources
- Amplification preserves witness size; a GapP expression tests the amplified acceptance operator’s trace.
Chris Marriott & John Watrous: Quantum Arthur-Merlin Games (2005). Sections 1–2 (proof-system definitions), Theorem 3.3 (amplification), Theorem 3.4 (QMA ⊆ PP). Elementary inclusions are consequences of these definitions.
BQP → PostBQP
Ordinary quantum algorithms are the case without discarded runs.
A BQP algorithm is a PostBQP algorithm with an always-successful postselection flag.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- The BQP error bound is unchanged.
- Resources
- Polynomial quantum circuit size.
Scott Aaronson: Quantum Computing, Postselection, and Probabilistic Polynomial-Time (2005). Definition 1 and Theorem 4 (PostBQP = PP). Use a standard finite gate set, such as Hadamard and Toffoli, and nonzero postselection probability.
PostBQP ↔ PP
Postselected quantum decisions equal unbounded-error classical decisions.
Translate either decision model into the other.
Postselection is a formal resource. Repeating a physical experiment until the rare event occurs can take exponential time.
- Input / access
- A classical instance of a language described by either model.
- Required output
- The same yes/no language is decided.
- Precision
- Constant conditional error for PostBQP; arbitrarily small nonzero bias for PP.
- Resources
- Uniform polynomial-size descriptions; postselection may have exponentially small probability.
Scott Aaronson: Quantum Computing, Postselection, and Probabilistic Polynomial-Time (2005). Definition 1 and Theorem 4 (PostBQP = PP). Use a standard finite gate set, such as Hadamard and Toffoli, and nonzero postselection probability.
QMA → QIP
A single quantum proof is a special case of an interactive proof.
The QIP verifier can receive one witness and run the QMA check.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- The usual 2/3 versus 1/3 gap when bounded error is involved.
- Resources
- One prover-to-verifier message; polynomial verification time.
Chris Marriott & John Watrous: Quantum Arthur-Merlin Games (2005). Sections 1–2 (proof-system definitions), Theorem 3.3 (amplification), Theorem 3.4 (QMA ⊆ PP). Elementary inclusions are consequences of these definitions. · Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay & John Watrous: QIP = PSPACE (2011). Main equality and Section 2: polynomial-round quantum interactive proofs. Conference version STOC 2010; journal JACM 2011.
PP → PSPACE
Count accepting computation branches using polynomial memory.
A deterministic machine can decide the PP majority exactly.
Polynomial space does not imply polynomial running time.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Exact integer counts resolve even an exponentially small probability bias.
- Resources
- Enumerate exponentially many polynomial-length random strings while reusing work space and a polynomial-bit counter.
Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples.
QIP ↔ PSPACE
Quantum interactive proofs and polynomial space decide the same languages.
Every such proof protocol has a polynomial-space decision procedure, and every PSPACE language has a quantum interactive proof.
Neither direction gives a polynomial-time algorithm without the unbounded prover.
- Input / access
- A classical instance of a language described by either model.
- Required output
- The same yes/no language is decided.
- Precision
- Standard bounded-error proof gap; polynomial-space semidefinite-program approximation suffices.
- Resources
- Polynomial verifier time and communication on the QIP side; polynomial memory on the PSPACE side.
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay & John Watrous: QIP = PSPACE (2011). Main equality and Section 2: polynomial-round quantum interactive proofs. Conference version STOC 2010; journal JACM 2011.
L → NL
Deterministic logspace is a special case of nondeterministic logspace.
An NL machine can use a single computation branch.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Exact yes/no decisions.
- Resources
- O(log n) work space.
Walter J. Savitch: Relationships between Nondeterministic and Deterministic Tape Complexities (1970). Space-bounded machine and configuration-reachability framework. L ⊆ NL is definitional; NL ⊆ P follows by searching its polynomial-size configuration graph, not by applying the squared-space bound alone.
NL → P
A logspace machine has only polynomially many configurations.
Build or explore its configuration graph and check whether an accepting configuration is reachable.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Exact yes/no decisions.
- Resources
- Deterministic polynomial time; it need not preserve logarithmic space.
Walter J. Savitch: Relationships between Nondeterministic and Deterministic Tape Complexities (1970). Space-bounded machine and configuration-reachability framework. L ⊆ NL is definitional; NL ⊆ P follows by searching its polynomial-size configuration graph, not by applying the squared-space bound alone.
P → RP
A deterministic algorithm already has no false positives.
Ignore the random bits.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Zero error meets the RP condition.
- Resources
- The same polynomial running time.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
P → coRP
A deterministic algorithm already has no false negatives.
Ignore the random bits.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Zero error meets the coRP condition.
- Resources
- The same polynomial running time.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
RP → BPP
One-sided error is a special case of bounded two-sided error.
Repeat the RP algorithm and accept if any run accepts.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Yes acceptance rises from at least 1/2 to at least 2/3; no acceptance remains zero.
- Resources
- A constant number of repeats gives the conventional BPP gap.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
coRP → BPP
A one-sided randomized guarantee also meets bounded-error requirements.
Repeat the coRP algorithm and reject if any run rejects.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Yes acceptance stays one; no acceptance drops to at most 1/3.
- Resources
- A constant number of repeats gives the conventional BPP gap.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
RP → NP
An accepting random tape is a short witness.
The NP verifier checks the RP machine on a guessed sequence of random bits.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- A yes input has an accepting tape; a no input has none.
- Resources
- Polynomial witness length and deterministic polynomial verification time.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
coRP → coNP
Complementing RP ⊆ NP gives coRP ⊆ coNP.
A rejecting random tape certifies that the coRP answer should be no.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Exact deterministic verification of the rejecting tape.
- Resources
- Polynomial witness length for no instances.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
NP → PH
NP is the existential part of PH’s first level.
Use a single existential block for the NP witness.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Exact yes/no decisions.
- Resources
- Polynomial-length quantified strings and a polynomial-time predicate.
Larry J. Stockmeyer: The Polynomial-Time Hierarchy (1976). Definition of the polynomial hierarchy, its quantified characterizations and collapse properties. NP and coNP are its first level.
coNP → PH
coNP is the universal part of PH’s first level.
Express a yes answer by requiring that every proposed NP counterexample fail verification.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Exact yes/no decisions.
- Resources
- A single universal block over polynomial-length strings.
Larry J. Stockmeyer: The Polynomial-Time Hierarchy (1976). Definition of the polynomial hierarchy, its quantified characterizations and collapse properties. NP and coNP are its first level.
BPP → PH
Bounded-error randomness can be described inside the polynomial hierarchy.
The Sipser–Gács–Lautemann theorem places BPP in Σ₂ᴾ ∩ Π₂ᴾ.
The quantifiers do not give a deterministic polynomial-time algorithm. This theorem does not place BQP in PH.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Starting with bounded error, amplification supports the quantified characterization.
- Resources
- A constant number of polynomial-length quantifier blocks.
Clemens Lautemann: BPP and the Polynomial Hierarchy (1983). Main theorem: BPP ⊆ Σ₂ᴾ ∩ Π₂ᴾ, hence BPP ⊆ PH. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
MA → PH
Classical randomized proof verification lies within the polynomial hierarchy.
MA is contained in Σ₂ᴾ ∩ Π₂ᴾ, hence in PH.
This uses a classical verifier. No analogous QMA ⊆ PH assertion is made.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- The bounded-error MA convention is equivalent to perfect completeness with bounded soundness.
- Resources
- Polynomial-length witnesses and a fixed number of quantifier blocks.
Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
PH → PSPACE
Quantified choices can be enumerated while reusing memory.
Evaluate the quantified polynomial-time predicate recursively, storing only current assignments and counters.
Containment does not assert that the two classes differ.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Exact yes/no decisions.
- Resources
- Polynomial space; enumeration can take exponential time.
Larry J. Stockmeyer: The Polynomial-Time Hierarchy (1976). Definition of the polynomial hierarchy, its quantified characterizations and collapse properties. NP and coNP are its first level. · Larry J. Stockmeyer & Albert R. Meyer: Word Problems Requiring Exponential Time (Preliminary Report) (1973). Section 4, Theorem 4.1 (fixed-level quantified characterization) and Theorem 4.3 (quantified Boolean formulas and polynomial space). Polynomial-space evaluation recursively enumerates the quantified assignments.
PSPACE → EXP
A halting polynomial-space deterministic computation has exponentially many possible configurations.
Run the machine: a repeated configuration would loop, so a decider halts before that happens.
Whether PSPACE = EXP is unresolved. The strict P ⊊ EXP theorem does not settle this intermediate inclusion.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Exact yes/no decisions.
- Resources
- At most 2^poly(n) time for a fixed polynomial-space decider.
Walter J. Savitch: Relationships between Nondeterministic and Deterministic Tape Complexities (1970). Space-bounded machine and configuration-reachability framework. L ⊆ NL is definitional; NL ⊆ P follows by searching its polynomial-size configuration graph, not by applying the squared-space bound alone. · Chris Marriott & John Watrous: Quantum Arthur-Merlin Games (2005). Sections 1–2 (proof-system definitions), Theorem 3.3 (amplification), Theorem 3.4 (QMA ⊆ PP). Elementary inclusions are consequences of these definitions.
coNP → PP
Counting distinguishes no counterexample from one or more.
Let c(x) count the polynomial-length counterexamples accepted by a coNP verifier. The GapP function 1 − 2c(x) is positive exactly when x is a yes instance, which gives a PP decision procedure.
This containment does not give a bounded-error randomized algorithm or assert strictness. Equivalently, it follows from NP ⊆ PP and PP being closed under complement.
- Input / access
- A classical bit string specifying an instance of any language in coNP.
- Required output
- The same yes/no language is decided.
- Precision
- The signed count is at least 1 on yes instances and at most −1 on no instances. The corresponding probabilistic bias can be exponentially small.
- Resources
- Polynomial-size counting-machine description and polynomial-time probabilistic computation with unbounded error.
Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions. · Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples.
P → ZPP
A deterministic polynomial-time algorithm is already always correct.
Ignore random bits and run the deterministic decider.
No strict separation is asserted.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- Zero error.
- Resources
- Worst-case polynomial time also bounds expected time.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
ZPP → RP
An always-correct expected-time algorithm can be cut off to get one-sided error.
Run for twice a polynomial upper bound on its expected time; reject if it has not finished.
A timeout can produce a false negative. This transformation does not give a worst-case polynomial-time zero-error algorithm.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- No false positives; yes inputs are accepted with probability at least 1/2.
- Resources
- The cutoff gives worst-case polynomial time. Markov’s inequality bounds the timeout probability by 1/2.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
ZPP → coRP
Reverse the timeout answer to obtain the other one-sided guarantee.
Run for twice a polynomial upper bound on its expected time; accept if it has not finished.
A timeout can produce a false positive. Conversely, an RP decider and a coRP decider can be repeated until one gives its reliable answer, establishing ZPP = RP ∩ coRP.
- Input / access
- A classical bit string specifying an instance of any language in the source class.
- Required output
- The same yes/no language is decided.
- Precision
- No false negatives; no inputs are rejected with probability at least 1/2.
- Resources
- Worst-case polynomial time with timeout probability at most 1/2 by Markov’s inequality.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
Open complexity questions
Does quantum computation beat every randomized classical algorithm?
open. BPP ⊆ BQP is proved. An unconditional strict separation for these language classes is not known. Oracle separations demonstrate advantages in restricted access models, not a resolution of the unrelativized question.
Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples. · Ran Raz & Avishay Tal: Oracle Separation of BQP and PH (2022). Main theorem gives an oracle with BQP not contained in PH, hence not in NP. This does not imply the unrelativized separation.
Where is NP relative to BQP?
open. Neither NP ⊆ BQP nor BQP ⊆ NP is known. Shor’s factoring algorithm and Grover’s search speedup do not put all NP problems in BQP.
Charles H. Bennett, Ethan Bernstein, Gilles Brassard & Umesh Vazirani: Strengths and Weaknesses of Quantum Computing (1997). Random-oracle lower bounds for NP versus quantum algorithms. These are oracle results, not unconditional NP versus BQP separations. · Ran Raz & Avishay Tal: Oracle Separation of BQP and PH (2022). Main theorem gives an oracle with BQP not contained in PH, hence not in NP. This does not imply the unrelativized separation. · Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1997). Sections 3–4 (arithmetic and QFT), Section 5 (factoring), Section 6 (discrete logarithms)
Are quantum proofs stronger than classical proofs?
open. QCMA ⊆ QMA is proved; unconditional equality or strict containment remains open. Bostanci, Haferkamp, Nirkhe and Zhandry give a classical-oracle separation (STOC 2026), which concerns a relativized model.
Scott Aaronson & Greg Kuperberg: Quantum Versus Classical Proofs and Advice (2007). Section 1: QMA and QCMA definitions. A QCMA verifier can measure a supplied witness in the computational basis, proving QCMA ⊆ QMA. · John Bostanci, Jonas Haferkamp, Chinmay Nirkhe & Mark Zhandry: Separating QMA from QCMA with a Classical Oracle (2026). Abstract and main classical-oracle separation theorem. STOC 2026; arXiv v2 dated January 17, 2026. Relativized separation, not an unconditional separation.
Where is BQP relative to PH?
open. BPP is contained in PH, but neither BQP ⊆ PH nor PH ⊆ BQP is known without oracles. Raz and Tal construct an oracle relative to which BQP is not contained in PH. That result does not prove the ordinary unrelativized separation.
Clemens Lautemann: BPP and the Polynomial Hierarchy (1983). Main theorem: BPP ⊆ Σ₂ᴾ ∩ Π₂ᴾ, hence BPP ⊆ PH. · Ran Raz & Avishay Tal: Oracle Separation of BQP and PH (2022). Main theorem gives an oracle with BQP not contained in PH, hence not in NP. This does not imply the unrelativized separation.
Complexity implications
If BPP ≠ BQP
Assume the known inclusion BPP ⊆ BQP is strict.
There would be a total yes/no problem solvable by a uniform quantum algorithm in polynomial time with bounded error, but by no classical randomized polynomial-time algorithm that has bounded error on every input. In this precise worst-case decision sense, quantum computation would have greater polynomial-time expressive power.
This does not say every quantum algorithm is faster, establish an exponential speedup, give useful input sizes, compare today’s hardware, or prove an advantage for sampling or state preparation. The inequality remains open.
Ethan Bernstein & Umesh Vazirani: Quantum Complexity Theory (1997). Definition of BQP, bounded-error amplification, and simulation of probabilistic computation: BPP ⊆ BQP. · Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples.
If BQP ⊆ BPP
Assume every BQP language is in BPP.
Then BQP = BPP, because BPP ⊆ BQP is already proved. Every efficiently solvable quantum decision language would have a classical randomized polynomial-time decider.
Class equality allows different polynomial running times and does not supply a practical compiler. It does not by itself assert efficient classical reproduction of every quantum output distribution, full state, or physical process.
Ethan Bernstein & Umesh Vazirani: Quantum Complexity Theory (1997). Definition of BQP, bounded-error amplification, and simulation of probabilistic computation: BPP ⊆ BQP. · Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples.
If P = PSPACE
Assume polynomial time and polynomial space decide the same languages.
Every displayed class between P and PSPACE would equal P: ZPP, RP, coRP, BPP, NP, coNP, MA, BQP, QCMA, QMA, AWPP, PP, PostBQP, PH, and QIP. These equalities follow by sandwiching each class between P and PSPACE.
This does not force L or NL to equal P. EXP would still be strictly larger than P by deterministic time hierarchy. The premise is a hypothesis, not a known theorem.
Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples. · Chris Marriott & John Watrous: Quantum Arthur-Merlin Games (2005). Sections 1–2 (proof-system definitions), Theorem 3.3 (amplification), Theorem 3.4 (QMA ⊆ PP). Elementary inclusions are consequences of these definitions. · Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay & John Watrous: QIP = PSPACE (2011). Main equality and Section 2: polynomial-round quantum interactive proofs. Conference version STOC 2010; journal JACM 2011. · Larry J. Stockmeyer: The Polynomial-Time Hierarchy (1976). Definition of the polynomial hierarchy, its quantified characterizations and collapse properties. NP and coNP are its first level. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045. · Juris Hartmanis & Richard E. Stearns: On the Computational Complexity of Algorithms (1965). Deterministic time hierarchy. The strict inclusion P ⊊ EXP is a standard consequence of time hierarchy, not an assumption.
If QMA = BQP
Assume quantum proofs add no decision-language power beyond BQP.
Any language with efficiently checkable quantum proofs could be decided in quantum polynomial time without a supplied witness. Since NP ⊆ MA ⊆ QCMA ⊆ QMA and BQP ⊆ QCMA, this would also give QCMA = BQP and NP ⊆ BQP.
For the total-language convention used here, this is a statement about deciding languages. It does not automatically extend to the corresponding promise classes, nor produce accepting quantum witnesses or ground states. It gives no classical polynomial-time algorithm.
Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions. · Chris Marriott & John Watrous: Quantum Arthur-Merlin Games (2005). Sections 1–2 (proof-system definitions), Theorem 3.3 (amplification), Theorem 3.4 (QMA ⊆ PP). Elementary inclusions are consequences of these definitions. · Scott Aaronson & Greg Kuperberg: Quantum Versus Classical Proofs and Advice (2007). Section 1: QMA and QCMA definitions. A QCMA verifier can measure a supplied witness in the computational basis, proving QCMA ⊆ QMA. · Ethan Bernstein & Umesh Vazirani: Quantum Complexity Theory (1997). Definition of BQP, bounded-error amplification, and simulation of probabilistic computation: BPP ⊆ BQP.
If NP ⊆ BQP
Assume all NP decision languages have bounded-error quantum polynomial-time algorithms.
SAT and every other NP-complete decision problem would be solvable in quantum polynomial time. SAT search would also be efficient: determine assignment bits using polynomially many SAT-decision calls, with error reduced sufficiently before each call.
This is an open containment hypothesis. It would not imply P = NP or BQP ⊆ NP. Grover’s quadratic black-box speedup and Shor’s factoring algorithm do not establish the premise.
Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions. · Ethan Bernstein & Umesh Vazirani: Quantum Complexity Theory (1997). Definition of BQP, bounded-error amplification, and simulation of probabilistic computation: BPP ⊆ BQP. · Charles H. Bennett, Ethan Bernstein, Gilles Brassard & Umesh Vazirani: Strengths and Weaknesses of Quantum Computing (1997). Random-oracle lower bounds for NP versus quantum algorithms. These are oracle results, not unconditional NP versus BQP separations. · Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1997). Sections 3–4 (arithmetic and QFT), Section 5 (factoring), Section 6 (discrete logarithms)
If P = NP
Assume nondeterministic polynomial-time decisions can be made deterministically in polynomial time.
Then PH collapses to P. Because BPP and MA lie in PH, they would also equal P, as would coNP, ZPP, RP, and coRP.
P = NP alone is not known to imply BQP = P, QMA = P, or P = PSPACE. Classical certificate finding would become efficient by self-reduction, but an equality of decision classes does not itself provide useful runtime constants.
Larry J. Stockmeyer: The Polynomial-Time Hierarchy (1976). Definition of the polynomial hierarchy, its quantified characterizations and collapse properties. NP and coNP are its first level. · Stephen A. Cook: The Complexity of Theorem-Proving Procedures (1971). Nondeterministic polynomial-time acceptance and polynomial reducibility; Theorem 1. P ⊆ NP is immediate from the machine definitions. · Clemens Lautemann: BPP and the Polynomial Hierarchy (1983). Main theorem: BPP ⊆ Σ₂ᴾ ∩ Π₂ᴾ, hence BPP ⊆ PH. · Oded Goldreich & David Zuckerman: Another Proof that BPP ⊆ PH (and More) (2011). Theorems 1 and 3; Section 4, Definition 4 gives ZPP and ZPP = RP ∩ coRP; Section 5.1 defines RP and complement classes; Section 5.2, especially Proposition 8 and inclusion 6, gives MA ⊆ Σ₂ᴾ ∩ Π₂ᴾ. Early version ECCC TR97-045.
A separation we can prove: P ⊊ EXP
No unproved hypothesis: the deterministic time hierarchy theorem applies.
Some decision languages are decidable in time 2^poly(n) but cannot be decided by any deterministic polynomial-time algorithm. Thus not every inclusion in the overall landscape can collapse to equality.
The theorem does not identify which step between P and EXP separates in this map. In particular, it does not settle P versus NP, BPP versus BQP, P versus PSPACE, or PSPACE versus EXP.
Juris Hartmanis & Richard E. Stearns: On the Computational Complexity of Algorithms (1965). Deterministic time hierarchy. The strict inclusion P ⊊ EXP is a standard consequence of time hierarchy, not an assumption.
BPP ≠ BQP would also imply P ≠ PSPACE
Assume BPP ≠ BQP for the uniform, bounded-error decision-language classes shown here.
The proved chain is P ⊆ BPP ⊆ BQP ⊆ PSPACE. If P = PSPACE, every class in that chain would equal P, forcing BPP = BQP. Taking the contrapositive gives BPP ≠ BQP ⇒ P ≠ PSPACE.
The implication follows from proved containments, but its premise remains an unproved separation. It is not a proof of either separation. P ≠ PSPACE alone does not establish BPP ≠ BQP, and the statement is not a claim about hardware speed or every quantum task.
John Gill: Computational Complexity of Probabilistic Turing Machines (1977). Definitions of probabilistic polynomial-time classes BPP and PP; P ⊆ BPP follows by ignoring random bits. · Ethan Bernstein & Umesh Vazirani: Quantum Complexity Theory (1997). Definition of BQP, bounded-error amplification, and simulation of probabilistic computation: BPP ⊆ BQP. · Lance Fortnow & John Rogers: Complexity Limitations on Quantum Computation (1999). Definitions 2.1, 2.3 and 2.5; Theorem 2.2 (GapP closure), Theorem 3.1 (BQP ⊆ AWPP), Theorem 3.3, Corollary 3.5 (PP ⊆ PSPACE). The coNP ⊆ PP edge applies the sign characterization to 1 minus twice the number of counterexamples.