Glossary

For a Hamiltonian written as Σ h_j P_j, the sum λ = Σ |h_j|, which is the LCU subnormalization and controls simulation cost.

A group in which the order of combination does not matter, a·b = b·a, such as bit strings under XOR or integers modulo N under addition.

Evolution under a slowly varying Hamiltonian H(s), which keeps a system near the instantaneous ground state when the change is slow compared with the gap.

Encoding an optimization problem’s cost in a final Hamiltonian and evolving adiabatically from an easy initial Hamiltonian.

A result giving conditions, in terms of the gap and the rate of change of H(s), under which evolution follows an instantaneous eigenstate.

Repeated application of Q = R_ψ S_G, which rotates a prepared state by 2θ toward the good subspace, raising success from sin²θ to sin²((2k+1)θ).

Phase estimation applied to the Grover iterate, estimating p to precision ε with O(1/ε) calls to A and A†.

An auxiliary qubit, usually initialized to |0⟩, used as scratch space by a subroutine.

The chosen structure of a parameterized circuit, encoding an assumption about where good answers lie.

The Fourier transform circuit with small-angle rotations omitted. Keeping rotations down to 2π/2^b gives error below 2πn/2^b with O(nb) gates.

The operator-norm distance between an implemented operation or block and the intended one.

A Boolean function that takes the value 1 on exactly half of its inputs.

Growth of a walk’s typical distance linearly in time, as in quantum walks on a line.

A parameter landscape whose gradients are exponentially small in the number of qubits, making training require exponentially many shots.

Comparing an algorithm’s performance with strong alternatives across instance sizes, with full resource accounting.

A one-query algorithm that recovers a hidden string s from an oracle for f(x) = s·x by applying Hadamards, a phase query, and Hadamards. Classical algorithms need n queries.

A number 0.b₁b₂…b_m = Σ b_j 2^{−j}. A phase e^{2πi·0.b₁b₂…} splits into one factor per bit.

The oracle U_f|x⟩|y⟩ = |x⟩|y ⊕ f(x)⟩, which adds the function value into a target register.

x·z = x₁z₁ ⊕ … ⊕ xₙzₙ, the parity of the positions where two bit strings both have a 1.

A unitary U whose top-left block, with ancillas in |0⟩, equals A/α for a matrix A and subnormalization α ≥ ‖A‖.

T_d(x) = cos(d arccos x), a degree-d polynomial bounded by 1 on [−1, 1]; the top-left entry of W(x)^d.

The bound Pr[|X − μ| > ε] ≤ Var(X)/ε². For an average of R independent bits it gives error probability at most 1/(4Rε²), so precision ε costs on the order of 1/ε² repetitions.

The best known classical method for the same task, input model, and success criterion, against which a quantum method is compared.

The classical computation that turns measurement samples into the algorithm’s answer, such as solving equations or applying continued fractions.

The bit string of measurement outcomes, stored classically and available to later operations.

A coherent evaluation |x⟩|y⟩|0^w⟩ ↦ |x⟩|y ⊕ f(x)⟩|0^w⟩ that preserves its input, adds the answer into a target, and returns its workspace to zero on every basis input with no input-dependent phase.

An entangled resource state made by preparing qubits in |+⟩ and applying controlled-Z between neighbours on a graph.

Access in which one use of the input acts linearly on a superposition of questions, as a unitary operation. It is an assumption of the problem, not automatic.

A superposition-based combination of operations that adds amplitudes, as opposed to a random choice that adds probabilities.

The register in a coined walk that labels the direction of the next move, making the shift reversible.

A discrete quantum walk on states |c, x⟩ that alternates a coin unitary on c with a shift of x conditioned on c.

[A, B] = AB − BA. It vanishes when A and B commute and controls the error of product formulas.

Bennett’s pattern for clean reversible evaluation: compute the answer with garbage, copy the answer into a target, then run the computation backwards to clear the garbage.

κ = σ_max/σ_min, the ratio of the largest to the smallest singular value of a matrix.

A representation x = a₀ + 1/(a₁ + 1/(a₂ + …)) computed by Euclid’s algorithm. Its truncations are the convergents.

Evolution e^{−iHt} with H the (weighted) adjacency matrix of a graph.

The ability to apply a unitary conditioned on a control qubit. The global phase of the unitary then becomes physically significant.

The two-qubit gate that multiplies |11⟩ by e^{iθ} and leaves other basis states unchanged. It is symmetric in its two qubits.

The operations controlled-U^{2^j} used by phase estimation. By repetition they cost 2^m − 1 uses of controlled-U for m control qubits.

The operation |0⟩⟨0| ⊗ I + |1⟩⟨1| ⊗ U, which applies U only when a control qubit is 1. It depends on the global phase chosen for U.

A fraction obtained by truncating a continued fraction. Any fraction p/q with |x − p/q| < 1/(2q²) is a convergent of x.

A shifted copy x·H of a subgroup H; in Simon’s problem the collision pair {x, x⊕s} is a coset of {0ⁿ, s}.

The quantity a variational algorithm minimizes, usually an expectation value estimated by measurement.

The process of turning classical data into a quantum state or a coherently queryable oracle. Its cost must be included in an end-to-end comparison.

A problem whose required output for each input is a single bit: yes or no.

A measurement followed by classically controlled operations gives the same output statistics as coherent control followed by measurement at the end.

Constructing classical algorithms that match a proposed quantum speedup when given comparable sampling access to the input.

A one-query quantum algorithm that decides whether an n-bit Boolean function promised to be constant or balanced is constant, by measuring the zero amplitude after Hadamards, a phase query, and Hadamards.

Given coherent access to a hidden function f from one bit to one bit, decide whether f(0) equals f(1). One quantum query suffices; two classical queries are necessary for an exact answer.

Growth of a walk’s typical distance like √t, characteristic of classical random walks.

An oracle implementation that leaves input-dependent garbage in its workspace. It fails interference experiments that a clean oracle passes.

Writing a state as a combination Σ c_s|u_s⟩ of eigenstates of an operator. Phase estimation then returns eigenphase φ_s with probability |c_s|².

A state that an operation changes only by a factor: V|u⟩ = λ|u⟩. For a unitary V the eigenvalue λ has magnitude one.

The factor λ in V|u⟩ = λ|u⟩. For a unitary operation it is a phase e^{iφ}.

A circuit that block-encodes f(H/α) = Σ f(λ_j/α)|v_j⟩⟨v_j| given a block encoding of H/α.

Deciding whether a list of N items contains two equal entries; quantum walks solve it with O(N^{2/3}) queries, which is optimal.

The difference between the two smallest eigenvalues of a Hamiltonian, the energies of its ground state and first excited state.

A problem whose required output is a number within a stated tolerance of a target quantity, with a stated failure probability.

A modification of amplification, possible when p is known exactly, that reaches success probability exactly 1.

The average ⟨ψ|O|ψ⟩ of an observable’s measured values over many repetitions.

Amplification with a randomly chosen iteration count whose range grows geometrically, finding a marked item with O(1/√p) expected calls when p is unknown.

The set of states a parameterized circuit can reach. Greater expressiveness costs more gates and parameters.

If r, the order of a mod L, is even and a^{r/2} ≢ −1, then gcd(a^{r/2} ± 1, L) are nontrivial factors of L.

A comparison of methods at the same problem instance, error in the same norm, gate set, and access model, counting all overheads such as ancillas and rotation synthesis.

Using a mid-circuit measurement outcome to choose a later gate or measurement basis.

Amplification using modified phases so that success probability never decreases, whatever the unknown p.

A Fourier basis state on a translation-invariant graph such as a cycle; each is an eigenvector of the adjacency matrix.

A state such as M^{−1/2} Σ_y e^{−2πiy/M}|y⟩, which is an eigenstate of adding a constant modulo M.

An outcome of the Fourier transform. A pattern of period r in a register of size N produces frequencies at multiples of N/r.

Input-dependent intermediate values left in the workspace by a reversible computation. In a quantum algorithm garbage acts as a which-path record.

Applying a gate by teleporting a state through an entangled resource and measuring in a chosen basis, followed by an outcome-dependent correction.

A common factor e^{iθ} multiplying an entire state or operation. It has no observable effect unless the operation is controlled.

Two binary trees joined at their leaves by a random cycle, on which a continuous quantum walk traverses exponentially faster than any classical algorithm.

The span of basis states marked as successful by a predicate. Amplification increases the weight of a prepared state in this subspace.

An optimization method that repeatedly moves parameters opposite to the gradient of the cost function.

The eigenstate of a Hamiltonian with the lowest eigenvalue (energy).

A set with an operation that is closed and associative, has an identity element, and gives every element an inverse; for example bit strings under XOR or integers modulo N under addition.

The operator Q = R_ψ S_G, the product of a reflection about the marked subspace’s complement and a reflection about the prepared state.

The circuit H, controlled-U, H, measure on a control qubit. Outcome 0 has probability (1 + Re⟨ψ|U|ψ⟩)/2.

The operation H^{⊗n}, which maps |x⟩ to 2^{−n/2} Σ_z (−1)^{x·z}|z⟩. It is its own inverse.

A Hermitian operator H that generates evolution e^{−iHt}; its eigenvalues are energies.

Constructing a circuit V with ‖V − e^{−iHt}‖ ≤ ε for a given Hamiltonian H, time t, and error ε.

Errors from decoherence and imperfect gates, which bias measured expectation values.

Estimation error of order 1/N with N total uses of the evolution, achievable with coherent powers.

A procedure that may work well in practice without a proof of its performance.

An unknown bit string that determines an oracle’s behavior and that an algorithm must recover.

Given a function on a group that is constant exactly on the cosets of an unknown subgroup, find the subgroup. Efficiently solvable by Fourier sampling for abelian groups.

The expected number of steps for a walk to first reach a marked set.

The set of all problem instances an algorithm must handle, usually indexed by a size parameter. Scaling claims are statements about the whole family.

The ability to apply the inverse of a given unitary. For a sealed box this is an additional assumption; for a known gate sequence it follows by reversing the gates.

F_N†, which maps the phase ramp N^{−1/2} Σ_k e^{2πijk/N}|k⟩ back to |j⟩.

The eigenvalues e^{±2iθ} of the Grover iterate on the good–bad plane, which encode the success probability p = sin²θ.

Phase estimation with one control qubit, reading phase bits from last to first and using earlier outcomes to correct later stages.

The Chebyshev expansion of cos(τx) and sin(τx) with Bessel-function coefficients, which decay rapidly beyond degree τ.

The graph whose vertices are r-subsets of an N-element set, adjacent when they differ in one element.

Solving linear equations in which variables are bits and addition is XOR. Gaussian elimination works as usual.

A block encoding of Σ a_j U_j built from PREPARE, SELECT, and PREPARE†, with subnormalization Σ |a_j|.

A resource state such as T|+⟩ that, consumed by Clifford operations and measurement, implements a non-Clifford gate.

A Clifford-only protocol that converts many noisy magic states into fewer, higher-fidelity ones.

Combining independent runs of a decision algorithm by outputting the most common answer. It amplifies any fixed advantage over 1/2 exponentially in the number of runs.

A random process whose next state depends only on the current state, described by a transition matrix.

Single-qubit rotations applied before measurement so that a Pauli X or Y is measured as Z.

A model in which an entangled resource state is prepared in advance and the computation proceeds by adaptive single-qubit measurements.

A measurement performed before the end of a computation, whose outcome can control later operations.

The Dürr–Høyer algorithm, which finds the minimum of N values with O(√N) queries by repeated threshold searches.

The smallest separation between the ground and first excited energies along an adiabatic path; runtime scales roughly as its inverse square.

The non-commuting layer e^{−iβΣX_j} in QAOA that turns cost-dependent phases into changes of probability.

The number of steps a random walk needs for its distribution to come close to the stationary distribution; of order 1/δ for spectral gap δ.

The difference between a physical system and the Hamiltonian used to describe it, independent of the simulation algorithm.

Addition that wraps around at a fixed modulus, such as (a + b) mod 2ⁿ. The wrap-around keeps the map reversible on a fixed number of bits.

The operation |k⟩|y⟩ ↦ |k⟩|a^k y mod L⟩, implemented by controlled multiplications by precomputed constants a^{2^j} mod L.

Estimating an expected value by averaging random samples; precision ε costs order 1/ε² samples classically.

The theorem that general Hamiltonians cannot be simulated for time t with a number of operations sublinear in t.

A matrix that changes the length of some vectors. It cannot be applied deterministically by a quantum circuit, only as a block of a larger unitary.

Amplification of a block encoding of a scaled unitary using reflections on the ancillas only, so that it works for unknown input states.

Estimating ⟨ψ|O|ψ⟩ from repeated measurements; operator-norm evolution error ε changes it by at most 2‖O‖ε.

The two-qubit circuit (controlled-Z, then measurement at angle α) that moves a state to an auxiliary qubit while applying HP(−α) up to a Pauli X.

The largest factor by which an operator stretches a normalized vector: ‖A‖ = max ‖Aψ‖ over unit ψ. It bounds the worst-case effect of an error operator.

Hamiltonian simulation using O(αt + log(1/ε)) block-encoding calls, matching lower bounds.

An operation that gives access to a hidden function or input, specified by its action on basis states, such as U_f|x⟩|y⟩ = |x⟩|y ⊕ f(x)⟩. Its internal construction is not part of the query count.

The smallest r > 0 with a^r ≡ 1 (mod L), defined when gcd(a, L) = 1.

Finding the order r of a modulo L. Phase estimation of modular multiplication on the state |1⟩ samples s/r for random s.

States with zero inner product. They can be distinguished with certainty by measuring in a basis that contains them.

The decrease in success probability when amplification continues past the optimal number of iterations.

dE/dθ = [E(θ + π/2) − E(θ − π/2)]/2 for a parameter entering through a single Pauli rotation.

A fixed gate sequence with adjustable rotation angles, producing a family of trial states.

A CNOT ladder that computes the parity of several qubits into one, used to apply a phase depending on that parity and then uncomputed.

With d signal calls, the implemented polynomial has the parity of d.

A Pauli gate applied, depending on a measurement outcome, to remove a known byproduct and make the result deterministic.

The unitary e^{−iθP} for a Pauli string P, implemented by basis changes, a CNOT parity ladder, and one Z rotation.

A classical record of Pauli byproducts that have not been physically corrected, used to reinterpret later measurement outcomes.

A tensor product of single-qubit operators I, X, Y, Z. Pauli strings form a basis for Hermitian matrices on n qubits.

A game modelling which intermediate values a reversible computation stores: a stage may be computed or uncomputed only while its predecessor is stored.

The smallest shift r under which a pattern or function repeats: f(x + r) = f(x).

The difference between an intended and an implemented phase. An error δ in every phase changes any normalized state by at most δ.

The algorithm that estimates an eigenphase φ of U by applying controlled powers U^{2^j} to an eigenstate and an inverse Fourier transform to the controls.

The rotation angles φ₀, …, φ_d in a quantum signal processing sequence, which determine the implemented polynomial.

The smallest nonzero eigenphase of a quantum walk operator; for Szegedy walks it is at least 2√δ.

The single-qubit gate P(θ) = diag(1, e^{iθ}). Special cases are Z = P(π), S = P(π/2), and T = P(π/4).

The effect by which an operation acting on a target in an eigenstate multiplies the controlling branch by the eigenvalue, moving information from the target into a relative phase.

The operation |x⟩ ↦ (−1)^{f(x)}|x⟩, which records a Boolean function in signs. One query to U_f with the target in |−⟩ implements it.

The grid spacing 1/2^m of phase estimation with m control qubits. The nearest grid point is obtained with probability at least 4/π².

Producing the phase e^{2πiv/M} by adding v modulo M into a reusable Fourier state, which kicks the phase back onto the controlling register.

Finding a low-degree bounded polynomial close to a target function on a region; its degree is the query cost of the transformation.

Keeping a run only when a measurement gives a chosen outcome. Its cost is the inverse success probability, or its square root with amplification.

A known unitary A with A|0ⁿ⟩ = |ψ⟩. Unlike a supplied copy of |ψ⟩, it can be inverted and controlled.

The circuit that loads coefficient weights √(a_j/α) into an ancilla register in the LCU construction.

An approximation of e^{−i(A+B)t} by products of e^{−iAδ} and e^{−iBδ} over short steps δ; also called Trotterization.

Sequential application of two block encodings with separate ancillas, encoding AB/(αβ).

The factorization of F_N|x⟩ into single-qubit states, one per output bit, each with a phase set by a binary fraction of x.

A restriction on the allowed inputs that an algorithm may assume without checking. On inputs that violate the promise, the problem places no requirement on the output.

A problem whose allowed inputs are restricted by a promise; behavior on other inputs is unconstrained.

The quantum approximate optimization algorithm, alternating cost-phase layers e^{−iγC} with mixer layers e^{−iβB} and optimizing the angles.

Quantum random-access memory: a device or circuit that queries classical data at a superposition of addresses. Its size grows with the data stored.

A reduction of a cost from order T to order √T, as in search and amplitude estimation.

The unitary F_N|x⟩ = N^{−1/2} Σ_y e^{2πixy/N}|y⟩. For N = 2ⁿ it has a circuit of O(n²) gates.

Preparing a state proportional to A⁻¹|b⟩ from a block encoding of A and a preparation of |b⟩.

Alternating signal calls W(x) with Z-rotations to implement a chosen polynomial P(x) as a matrix entry.

The framework that applies a polynomial to the singular values of a block-encoded matrix by alternating the encoding, its inverse, and projector-controlled phases.

Turning a Hermitian block encoding of H/α into a walk W whose eigenphases are ±arccos(λ_j/α), one two-dimensional plane per eigenvalue.

One application of an oracle, whatever state it acts on, including a superposition of inputs.

The number of oracle queries an algorithm uses, ignoring all other operations. Lower bounds in this model hold for every algorithm with the stated access.

A proof that every algorithm in a given access model needs at least a certain number of queries, such as Ω(√N) for unstructured search.

A process that moves from a vertex to a random neighbour at each step, described by a transition matrix P.

An operation that fixes a chosen state or subspace and negates every orthogonal direction, such as 2|ψ⟩⟨ψ| − I.

A circuit that applies the desired operation on one outcome and an undoable operation on another, repeated until success; exact, with a random number of attempts.

Listing queries, gates, depth, qubits, precision, repetitions, postselection, and classical processing separately, so that no cost is hidden.

A count of qubits, gates, depth, and time for a concrete instance, under stated assumptions about the gate set and error correction.

Arithmetic implemented as a permutation of basis states, such as modular addition, so that it can act on superpositions.

An estimation schedule of powers and repetitions designed to bound the error even when individual outcomes are noisy.

A complex number ω with ω^N = 1. The N-th roots e^{2πik/N} are equally spaced on the unit circle, and their k-th powers sum to zero unless N divides k.

A problem whose required output is a random draw whose distribution is close to a specified target distribution.

A problem whose required output is a witness satisfying a condition, or a report that none exists.

The multiplexed operation Σ_j |j⟩⟨j| ⊗ U_j that applies the j-th unitary on the branch where the ancilla is |j⟩.

The inverse QFT with each qubit measured as soon as it is final and the remaining controlled rotations replaced by classically controlled single-qubit rotations.

The permutation |c, x⟩ ↦ |c, x ± 1⟩ (or along edge c) in a coined walk.

The polynomial-time quantum algorithm for factoring (and discrete logarithms) that reduces factoring to order finding and solves order finding by phase estimation.

Dividing measurements among Hamiltonian terms, optimally in proportion to |h_j|σ_j, giving variance at most λ²/R.

The statistical uncertainty in an expectation value estimated from a finite number of measurements, falling as 1/√R.

The one-qubit unitary W(x) = e^{iθX} with x = cos θ, whose top-left entry is the signal x.

Given a two-to-one function with f(x) = f(y) exactly when y = x ⊕ s, find s. Quantum algorithms need O(n) queries; bounded-error classical algorithms need Ω(2^{n/2}).

A stretch factor σ_j in A|w_j⟩ = σ_j|u_j⟩, with orthonormal input and output directions. The largest equals ‖A‖.

Oracles that return the positions and values of the nonzero entries in each row of a sparse matrix.

Writing a Hermitian H as Σ λ_j |v_j⟩⟨v_j| with real eigenvalues and orthonormal eigenvectors, so that functions of H act eigenvalue by eigenvalue.

A bounded polynomial approximating a step function on the spectrum, used to project onto eigenvalues in a chosen range.

δ = 1 − |λ₂| for a Markov chain, where λ₂ is its second-largest eigenvalue in magnitude; the classical mixing time is of order 1/δ.

Estimation error of order 1/√N from N independent repetitions, the same scaling as classical sampling.

Applying a non-Clifford gate by consuming a magic state with Clifford operations, measurement, and a conditional correction.

A probability distribution π left unchanged by one step of a Markov chain, πP = π; uniform for a symmetric chain.

Optimization using noisy estimates of the objective or gradient.

A subset of a group that is itself a group under the same operation, such as {0ⁿ, s} under XOR.

The factor α in a block encoding of A/α. It is at least ‖A‖, and success probabilities scale as 1/α².

The condition a run must satisfy to count as correct, such as exact correctness on every input or correctness with probability at least 2/3.

The probability p = sin²θ that measuring the prepared state gives a marked outcome.

Recursively constructed product formulas of any even order 2k, with error O(t^{2k+1}/r^{2k}).

The step e^{−iδA/2}e^{−iδB}e^{−iδA/2}, whose error over r steps is O(t³/r²).

The quantum walk W = R_B R_A built from two reflections determined by a Markov chain’s transition probabilities.

The single-qubit gate diag(1, e^{iπ/4}). In many fault-tolerant schemes it is far more expensive than Clifford gates, so T count is a key cost measure.

Amplified search for an item whose value is below a given threshold, used as a step in minimum finding.

Reducing the number of stored intermediate values by recomputing them when needed, at the cost of more gates.

The number of Toffoli gates in a circuit, a common cost measure for reversible arithmetic in fault-tolerant settings.

The reversible gate |a⟩|b⟩|t⟩ ↦ |a⟩|b⟩|t ⊕ ab⟩, which computes AND into a target while keeping its inputs.

Whether an ansatz’s optimum can be found with reasonable resources, distinct from whether it contains a good state.

The difference between a product formula and the exact evolution. For first order it is at most t²‖[A,B]‖/(2r).

The number r of repetitions of a product-formula step; more steps reduce the Trotter error.

Running a computation in reverse to restore intermediate registers to their initial state after the result has been used or copied.

For any state, ⟨ψ|H|ψ⟩ ≥ E₀, with equality only for ground states.

A hybrid algorithm that minimizes the measured energy of a parameterized trial state with a classical optimizer.

Finding a marked vertex by amplitude amplification in which reflection about the stationary state uses phase estimation of a walk, at cost S + (1/√ε)(U/√δ + C).

Any part of the state whose value differs between computational branches. Branches with orthogonal records cannot interfere, whether or not the record is measured.

The ancilla qubits a subroutine uses temporarily. A clean subroutine returns them to their initial state.