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.
267 entries · 284 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.
Find a better parameterized ansatz for the quantum approximate optimization algorithm (QAOA) applied to combinatorial optimization problems such as Max-Cut, where the standard, fixed-form QAOA ansatz is not known to be optimal and no systematic method exists for improving on it.
Give polynomial-time quantum algorithms for three average-case lattice problems in parameter regimes where none was known: the short integer solution problem under the infinity norm, the learning-with-errors problem when the input is supplied as LWE-like quantum states rather than classical samples, and the extrapolated dihedral coset problem.
lattice problemslearning with errorsshort integer solution
Backtracking is the general classical technique for exploiting problem structure in constraint satisfaction: explore a tree of partial assignments and prune the branches a predicate rules out. The question is whether an arbitrary backtracking algorithm — any predicate and any branching heuristic — can be sped up quantumly, rather than replaced by brute-force search over the whole assignment space.
Sample from the output distribution of a rudimentary optical device: identical photons are generated, sent through a network of beamsplitters and phase shifters, and then non-adaptively measured to count the photons in each mode. The question is whether a classical computer can do the same sampling efficiently.
The phase-only sibling of the Toffoli gate that applies a -1 phase exactly when all three qubits are |1⟩, symmetric in all three qubits and the natural three-qubit generalization of CZ.
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.
Determine the ground state of weakly-interacting, non-covalently bonded molecules — the weakly-bound intermolecular regime that variational quantum algorithms applied to strongly-bound, covalently-bonded systems with full molecular-orbital bases had left largely unexplored — using a coarse-grained representation of the electronic response suited to a VQA.
A controlled version of the Hadamard gate that puts the target into superposition only when the control qubit is |1⟩, a canonical example of promoting a single-qubit gate to a controlled operation.
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.
A parametrized controlled gate that applies an RZ(θ) rotation to the target exactly when the control is |1⟩, the entangling generalization of RZ used when a Z-rotation itself needs to be conditioned on another qubit.
A controlled version of the Pauli-Y gate that flips the target bit and attaches a ±i phase exactly when the control qubit is |1⟩, completing the CX/CY/CZ family of controlled Paulis.
Evaluate candidate designs for a simplified cooling system within an engineering design process that normally requires numerous computationally intensive numerical simulations, in a way that avoids the data input/output overhead that otherwise erodes any quantum speedup on such simulation tasks.
Simulate strongly correlated fermionic systems — notoriously hard for classical computers — on a quantum computer with 2D or linear (1D) nearest-neighbor qubit-qubit couplings, of the kind typical of superconducting transmon qubit arrays, including preparing the relevant quantum states and evolving the system in time, with the Fermi-Hubbard model as a worked example.
Given N coins of which exactly k are counterfeit, where the real coins all share one weight and the counterfeit coins all share another, and given a pan balance that can compare the weight of any pair of subsets of the coins but reports only whether they balance or tilt, identify all of the counterfeit coins in as few weighings as possible.
A two-qubit permutation gate defined as two CNOTs with reversed control and target applied back to back — a genuinely different two-CNOT gate from SWAP (which uses three), and notable for not being self-inverse.
Given a set of constraints over a finite field, such as a max-XORSAT instance or the task of finding a degree-n polynomial over 𝔽ₚ that approximates a given data set as well as possible, produce an assignment that satisfies as many constraints as possible.
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.
Given oracle access to two unknown probability distributions P and Q on an N-element set — in the Zoo's setup, black boxes A and B whose domain is the integers 1 through T and whose range is the integers 1 through N, with the distribution over outputs induced by choosing uniformly at random among allowed inputs — approximate the L1 distance between the two distributions to constant precision.
Find quantum circuits that diagonalize a given input Hamiltonian, that is, approximate its eigenstates, without resorting to brute-force optimization of an unstructured variational circuit, which runs into barren plateaus.
The maximally entangling two-qubit gate native to IBM's newer superconducting processors, built from an 'echoed' pair of opposite-sign cross-resonance pulses around a control-qubit X flip, and locally equivalent to CX.
Given oracle access to a weighted graph on N vertices of maximum degree d whose edge weights are conductances, so that an edge of weight w carries resistance 1/w, estimate the effective resistance between a chosen pair of vertices s and t to within a factor of 1 + ε. Wang poses it as ENA-ER: for a network with |V| = N, deg(G) ≤ d, edge conductances normalized to 1 ≤ w_e ≤ c for every edge — equivalently edge resistances in [1/c, 1] — and spectral gap λ2(L_G) ≥ λ > 0, estimate R_eff(s, t) up to multiplicative error ε, succeeding with probability at least 2/3, given a procedure Pv that on input a vertex index and a number k returns the k-th edge incident to that vertex and a procedure Pe that on input an edge index returns that edge's two endpoints and its weight, both of which Wang assumes can be implemented in time poly(log(N)).
effective resistanceelectrical networkquantum walk
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.
Determine the role quantum dynamical effects play in the efficiency of exciton (energy) transfer within photosynthetic molecular arrays — such as the Fenna-Matthews-Olson (FMO) protein complex, whose long-lived coherence had recently been demonstrated experimentally — that interact with a thermal bath.
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.
The two-site Fermi-Hubbard dimer Hamiltonian, mapped to qubits via the Jordan-Wigner transformation: nearest-neighbor hopping competing with on-site Coulomb repulsion.
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.
A three-qubit controlled-swap gate that conditionally exchanges two target qubits, useful for reversible routing logic and as a component of the SWAP test for state overlap.
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.
Prepare the thermal Gibbs state of an interacting quantum system on a quantum computer, and use that preparation to evaluate the system's partition function to a target accuracy.
We are given an undirected graph G on n vertices, known explicitly in advance, together with oracle access to a labeling of the vertices by 1 and 0; the graph collision problem is to decide, by querying that labeling, whether there exist a pair of vertices, connected by an edge, both of which are labeled 1. Only the labeling is queried and never the graph, which is why Magniez, Santha and Szegedy can restate the task as deciding whether the set of vertices of value 1 forms an independent set in G. It is not either of the two problems it is easily confused with: collision finding asks for two arguments of a two-to-one function that share a value, and element distinctness drops that promise and asks whether any two of N items are equal. Those two share a single other Zoo entry, Collision Finding and Element Distinctness, and a single record here, element-distinctness; neither of them has a graph or an edge relation in it.
Given access only to an oracle that, for a pair of integers in {1, 2, ..., n}, says whether the corresponding vertices of an n-vertex graph are joined by an edge, decide a property of that graph or find a structure in it, such as connectivity, a minimum spanning tree, a lowest weight path, or a triangle, using as few queries as possible.
Given only an oracle that, for a vertex of an N-vertex graph of degree d together with an index j in {1, 2, ..., d}, returns that vertex's j-th neighbor or null when the vertex has degree less than d, decide in as few queries as possible whether the graph is bipartite or far from bipartite — far meaning that a constant fraction of the edges would have to be removed to achieve bipartiteness — and, in the same model, whether the graph is an expander or far from being one.
Given a list of k generators for a group G together with black-box access to group multiplication, decide whether G is commutative using as few queries to that black box as possible.
group commutativityblack-box groupelement distinctness
Given a finite group G presented only through an oracle that takes an ordered pair of element labels and returns the label of their product, compute the order of G from the labels of a set of generators, and decide whether a given bitstring is the label of a group element — in the constructive form of the membership question, exhibiting that element as a product of the generators.
The minimal-basis (STO-3G) H₂ electronic Hamiltonian after Jordan-Wigner/parity mapping and two-qubit tapering: the canonical small-molecule target for variational quantum eigensolver (VQE) demonstrations.
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.
Adapt the Harrow-Hassidim-Lloyd (HHL) quantum linear-systems algorithm, most of whose components current noisy quantum hardware cannot reach, into a form that near-term devices can actually execute, and demonstrate it on an application.
Given a subgraph of the Boolean hypercube on bit strings of length n, whose edges all run from smaller to larger Hamming weight, decide whether it contains a path from the all-zeros vertex 0^n to the all-ones vertex 1^n.
The single-qubit no-op gate that leaves every state exactly unchanged, used as a placeholder in circuit diagrams, a timing/idle slot on real hardware, and the base case for gate-composition identities.
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.
Given a hard combinatorial problem, rewrite it as an Ising spin model whose lowest-energy spin configurations are exactly that problem's solutions, so that a machine which minimizes energy can be pointed at the problem at all.
The classical (longitudinal-field) Ising Hamiltonian expressed as a diagonal SparsePauliOp: a foundational Z-only spin model with no quantum superposition dynamics of its own.
A two-qubit gate that swaps |01⟩ and |10⟩ while attaching a factor of i, arising naturally from XY-type physical couplings and native to several superconducting and photonic platforms.
Given a braid on n strands with m crossings and an integer k, compute a certain additive approximation to the Jones polynomial of the link obtained by closing the braid, evaluated at the primitive root of unity e^(2πi/k).
Given a first-order linear differential equation d/dt x = A(t)x + b(t) with N-dimensional vectors x and b and an N×N matrix A, and given an initial condition x(0), produce the solution x(t) at a later time t to precision ε, in the sense that the normalized vector x(t)/‖x(t)‖ returned is at distance at most ε from the exact solution.
Encode a linear kinetic plasma problem — modeling electrostatic linear waves, driven by a spatially localized external current, in a one-dimensional Maxwellian electron plasma — into a quantum circuit that solves the resulting linear system.
kinetic plasmavlasov-ampere systemquantum signal processing
Given the low autocorrelation binary sequences (LABS) problem, an optimization problem that is classically intractable even for moderately sized instances, determine whether QAOA can act as an algorithmic component that provides an advantage over the best classical exact solvers.
Given oracle access to k matrices of size n × n, where a query names a matrix index x together with a pair of indices i, j and returns the ij entry of the x-th matrix, decide whether all k of the matrices commute with one another.
Compute the product of two n × n matrices over a semiring rather than a ring — the (max, min) product, the distance product, and the Boolean product — where the absence of subtraction rules out the fast algebraic algorithms that make ring matrix multiplication cost n^ω. The question the paper poses is whether anything beats the Õ(n^(5/2)) that follows from applying Grover search or quantum minimum-finding entry by entry.
The maximally mixed state ρ = I/2ⁿ: the unique n-qubit state invariant under every unitary, carrying zero information and maximal (n-bit) von Neumann entropy.
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
Determine the value at the root of a read-once Boolean formula, canonically a NAND tree on N variables, given only oracle access to the variables and using as few queries as possible.
Given a system of nonlinear ordinary differential equations, in the primary algorithm's case a dissipative quadratic n-dimensional system, produce the solution at a chosen evolution time T to error ε, encoded in the amplitudes of a quantum state.
The NOON state (|N,0⟩+|0,N⟩)/√2: a two-mode entangled state with all N particles in one mode or the other, the standard resource for Heisenberg-limited interferometric phase estimation.