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.
32 entries · 34 records, sized variants folded
Atlas stars stay in this public list. Saving an entry to your workspace starts an unstarred private copy.
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.
quantum chemistryphase estimationground state energy
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 α.
principal ideal problemreal quadratic fieldideal class
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.