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.
27 public entries
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.
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.
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.
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
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.
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.
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.
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.
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 an oracle that returns the value p(x) of an unknown degree-d polynomial p over the finite field GF(q) at any queried point x, determine the coefficients of p using as few queries as possible.
Given oracle access to a spherically symmetric function f from R^d to an arbitrary set S, locate its center of symmetry to a fixed precision using as few queries as possible.