Explore quantum algorithms and circuits, with resource estimates, verification evidence, and sources.
◈Verification legend
Every record is classified by how it was verified. The badge shows the strongest tier of evidence; the chips list each method that applies.
≡Exact & formal
The defining behavior was checked exactly: a mathematical identity, a full statevector or stabilizer simulation, or an exhaustive basis-state truth table.
Direct mathematics
An analytic identity or closed-form derivation proves the defining property (e.g. H² = I, Y = iXZ).
Unitary / matrix equivalence
The circuit's unitary was computed and compared against the reference matrix.
Exact statevector simulation
A full statevector simulation reproduced the exact expected state or distribution.
Reversible classical logic was checked exhaustively (or at edge cases) on computational-basis inputs.
✓Strong empirical
The design was verified by construction plus measured evidence: statistical re-execution, small-instance analytic agreement, sub-block, echo, or invariant checks. Scale-specific bugs can still survive.
Statistical re-execution
Measured counts from independent executions agreed within statistical tolerance (e.g. TVD bounds).
Small-instance agreement
The same generator matched analytic results at tractable sizes; large instances are inferred.
The circuit follows a specification whose correctness argument is standard; the construction was audited against it.
◐Attested & literature
The record rests on external authority: peer-reviewed papers, standard textbooks, expert review, or evidence carried over from related verified entries. Nothing here was re-executed by this catalog.
Peer-reviewed paper
The record's claims trace to one or more peer-reviewed publications cited on the entry.
Textbook / standard citation
The behavior is standard material (e.g. Nielsen & Chuang, OpenQASM spec) and is cross-referenced, not re-derived.
Expert review
A named human reviewer with domain expertise checked the record.
Tangential evidence
Correctness is supported indirectly through related verified entries (e.g. a gate verified inside a verified algorithm).
○Automated & unreviewed
Only automated (LLM-assisted) review or an unreviewed community submission backs this record so far. Treat it as a starting point, not evidence.
LLM-assisted review
An LLM checked the record for internal consistency. Useful screening, not evidence of correctness.
Community submission
Submitted by the community and not yet through the review pipeline.
Let G be a finitely generated Abelian group and let H be a subgroup of G such that G/H is finite, and let f be a function on G with the promise that f(g1) = f(g2) if and only if g1 and g2 lie in the same coset of H. The task is to find H, that is, a set of generators for H, by making queries to f. Mosca and Ekert work order finding and period finding as G = Z with hidden subgroup rZ, Simon's problem as G = Z_2^l, and the discrete logarithm as G = Z_r × Z_r.
The class group of a number field is the finite abelian group of ideals modulo principal ideals. Computing it means computing the structure of that abelian group, not merely its order.
A parametrized entangling gate that applies e^{iλ} exactly when both qubits are |1⟩, generalizing CZ and forming the entangling primitive of the quantum Fourier transform.
Bound the quantum-computing resources a fault-tolerant quantum computer would need to price derivatives — autocallable and Target Accrual Redemption Forward (TARF) instruments serving as the paper's benchmark use cases — at a scale offering a quantum advantage over classical pricing.
Carry Shor's discrete-logarithm algorithm through concretely for the group of points on an elliptic curve over GF(p), and count the qubits and operations it needs, so that the cost of attacking elliptic-curve cryptography can be compared with the cost of attacking RSA at an equivalent classical security level.
Given elements a, b, c, f, g of the multiplicative group of a finite field F_q, decide whether the exponential congruence af^x + bg^y = c has a solution in nonnegative integers x and y, and find one if it does. The problem generalizes the discrete logarithm and is connected to the hidden subgroup problem over semidirect product groups.
Given black-box access to a finite ring R, not necessarily commutative, together with a list of generators for an ideal I in R, find an additive basis representation for I.
Given the specification of a nontrivial multiplicative character χ and an additive character indexed by β over a finite field F_{p^r}, estimate the angle γ modulo 2π in the Gauss sum G(F_{p^r}, χ, β) = √(p^r) · e^(iγ). The same question is then asked for Dirichlet characters over Z/nZ.
Given oracle access to a function f on the integers mod N together with the promise that f(x) = g(x+s) for a known function g and an unknown shift s, recover s.
Estimate a matrix element of a unitary irreducible representation of a group — a single entry of a matrix whose dimension may be exponentially large — to within an additive error, for the symmetric and alternating groups and for the unitary, special unitary and special orthogonal groups of polynomial highest weight.
Compute the ground-state energy of an atom or molecule, a calculation whose time the paper states scales exponentially with system size on a classical computer.
Price an option, or a portfolio of options — vanilla contracts, multi-asset contracts, and path-dependent contracts such as barrier options — on a gate-based quantum computer, in the setting where the paper takes classical Monte Carlo methods as its point of comparison.
Given a positive non-square integer d, Pell's equation is x² − dy² = 1 and the goal is to find all integer solutions. The least solution can have exponentially many bits, so it cannot be written down; the computational problem is instead to compute the integer part of the regulator R = ln(x₁ + y₁√d), from which the solution can be recovered.
Given an invertible ideal I in a real quadratic field, determine whether there exists an α with I = αZ[√d] — that is, whether the ideal is principal — and if there is, find α.
A quadratically signed weight enumerator is the sum S(A, B, x, y) = Σ (−1)^(bᵀBb) x^|b| y^(n−|b|) over the 0/1 vectors b with Ab = 0. Given that the diagonal of A is the identity, that k and l are positive integers, and a promise that |S(A, lwtr(A), k, l)| is at least (k² + l²)^(n/2)/2, determine the sign of S.
Prove that a given integer N is prime, or in most cases prove it composite and produce a witness, rather than merely declaring it probably prime as a randomized primality test does.
Evaluate risk measures of a financial position — Value at Risk and Conditional Value at Risk among them — where the classical route is a Monte Carlo simulation over sampled realisations of the uncertainty.
Given a real symmetric N × N matrix A whose rows are sparse — the non-zero positions and values of any row returned by an efficiently computable function rather than stored — together with an index j, an integer power m, an a priori bound b on the norm of A, a threshold g and a precision ε, decide whether the diagonal entry (A^m)_jj is at least g + εb^m or at most g − εb^m.
Given a function f and a positive semi-definite matrix A whose eigenvalues are λⱼ, estimate the spectral sum Tr[f(A)] = Σⱼ f(λⱼ), a family whose typical examples the paper gives as the von Neumann entropy, the trace of A⁻¹, the log-determinant and the Schatten p-norm, the last of which it says does not require the matrix to be positive semi-definite.
Fix a relation that permits replacing one substring by another. Given strings s, t and t′ of length L, let Δ(n) be the number of ways of reaching t from s in exactly n replacements minus the number of ways of reaching t′. Given a promise that |Δ(m)| ≥ εc^m for the input m, and a growth promise that Δ(n) ≤ c^n for every n, determine the sign of Δ(m).
Represent the spectrum of a quantum chemistry Hamiltonian, given in an arbitrary (for example molecular) orbital basis, as a block-encoded quantum circuit cheap enough to support phase estimation of a molecular eigenvalue.
In the spiked tensor model, an unknown signal vector v_sig in R^N of magnitude √N is hidden inside a p-th order tensor T0 = λ v_sig^⊗p + G, where G is noise whose entries are chosen independently from a Gaussian distribution of zero mean and unit variance and λ is a scalar representing a signal-to-noise ratio; the task called recovery is to infer v_sig to some accuracy given T0, and the simpler task called detection is to distinguish the case λ = 0 from λ = λ̄ for some λ̄ > 0, again just given T0. The paper treats the symmetrized and non-symmetrized cases as reducible to each other, and says that for odd p it is convenient in the analysis not to symmetrize T0 and to take complex G. Recovery is information-theoretically possible for λ much larger than N^((1-p)/2), but no polynomial-time algorithm is known that achieves that performance; the two best known algorithms are spectral and sum-of-squares, and for even p the spectral method works for λ much larger than N^(-p/4), with a variant conjectured to perform similarly for odd p. The regime this record is about is the hard one at and below that spectral threshold: write λ = α N^(-p/4), and the question is what recovery costs as α shrinks.
The unit group of a number field is the set of invertible algebraic integers inside it. By Dirichlet's unit theorem it is, up to a root of unity, free abelian of a rank determined by the field's real and complex embeddings, so computing it means finding a fundamental system of units.
Given a curve C of genus g over a finite field F_q, compute the numerator P(t) of its zeta function Z(C,t) = P(t)/((1−t)(1−qt)), a polynomial of degree 2g with integer coefficients, in time polynomial in g and log q jointly rather than in one at the expense of the other.