About this map
Sections
What this is
Quantum algorithms are not written from scratch. They are assembled from a small number of reusable steps, and almost every published method is a different route through the same handful of them.
This is a map of those routes. Circles are the things an algorithm can be holding. Lines are the steps that carry you from one to the next. A method is a path across.
Nothing here is generated. Every line was read out of a paper and checked against it.
How to read it
- Something you can hold — a state, a matrix, a circuit, an answer.
- The same, in the middle of a step you have opened.
- A step. Someone has published a way through it.
- A step whose way through has not been pinned to one method.
- A step nothing published fills yet.
- A step you have opened. What is drawn inside it is how it was done.
- There is a record in the repository for this one.
How to move around
- Two fingers move the map. Pinch to zoom, or hold ctrl and scroll.
- Click a step to open it in place — everything else stays where it is.
- Click a name to read the full record without leaving the map.
- Arrow keys move, plus and minus zoom, zero puts it back.
What a line is claiming
A solid line means a paper puts those two steps together and we have the citation. A long-dashed line means the route is recorded but no single method has been named for that step. A short-dashed line means nothing published fills it — the step is real, the way through is not written yet.
A count after a step's name — ×T/h, ×O(κ) — means the route walks that step that many times rather than once. It is the source's own symbol, and the card says what it stands for and what one turn costs. A step with no count is a step no source we read said is repeated, which is not the same as one taken once.
A line drawn nested under another, on the soft shaded band behind it, is a narrower version of the line above it: the same construction, re-analysed or re-tuned, filling the same step. It is why two lines can draw the identical interior and still be two entries. Lines outside the band are alternatives to their neighbours, not versions of them.
The map does not hide the gaps. An empty step is drawn as an empty step.
What is not here yet
The map covers the algorithm literature. The repository covers circuits and primitives. They overlap less than you would expect, and where a method has no record we say so on its page rather than leaving the space blank.
Where something named here does have a record, its name links straight to it.
Process
Recover the period of a periodic function
Given a function you can evaluate in superposition and a promise that it repeats, find what it repeats by. This is the engine underneath factoring, discrete logarithms and a row of classical number-theory problems that had no efficient algorithm at all — and the whole difficulty is that the period is read out of an interference pattern rather than looked up.
Open the full recordExpand it here — a map of just this
- Takes
- A circuit evaluating f on a superposition of inputs, the promise that f is periodic, the kind of object its period is (an integer in a finite cyclic group, an irrational real, a lattice of rank r), and — where the period is not an integer — the precision wanted.
- Returns
- The period: an exact integer where the group is finite, or an approximation to the requested precision together with the classical post-processing that turned the measured samples into it.
The routes here are separated by **what kind of thing the period is allowed to be**, and that is a difference in what is possible rather than in cost. Hallgren states it against Shor directly: the structure behind Pell's equation is "a group-like subset of the reals modulo an irrational number", and "this prevents direct application of Shor's algorithms" — an irrational period cannot be written down, so the continued-fraction step that finishes the integer route has nothing to finish. Going from one irrational period to a lattice of them costs again, and for a stated reason: the lattice method "only appears to work for a constant number of dimensions because the rounding introduces new noise into the distribution that is not present in the integer lattice case". So a claim that a problem "reduces to period finding" has said nothing until it says which of the three. The wider family these belong to is the **hidden subgroup problem**, which is deliberately not drawn as a node beside them: it also contains instances with no period interpretation at all — Hallgren names graph isomorphism as one of the "still unsolved problems" it covers — so a node for it would be a family standing beside three of its own members.
- Period finding in a finite cyclic group
Evaluate the function across a superposition of exponents, transform the input register, and measure. What comes back is a multiple of the sample size divided by the period, near enough that a continued-fraction expansion recovers the period exactly — and once it is exact it can be checked classically, so the whole quantum part may fail and be retried.
- Period finding over the reals
When the period is irrational there is no exact answer to land on, so the function is evaluated on a discretisation of the reals and the period is approximated instead. Two samples are taken rather than one, and the continued-fraction step runs on their ratio — the same idea as the integer route, doing a job the integer route cannot do at all.
- Finding a lattice of periods
Some functions repeat in several independent directions at once, so what is hidden is not one period but a lattice of them. Sampling the dual lattice and reconstructing a basis from the samples replaces the continued fraction, and the rounding that makes real-valued directions representable is what limits how many directions can be handled.
None found yet.
No field holds this yet — the model is still being designed.
- Zeta function of a curve over a finite field
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.
- Ideals in a finite black-box ring
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.
Covered in the repository.
Where the routes meet
Every circle is drawn once. This step has no smaller object recorded inside it, so the strands between its two circles are the recorded ways of taking it — one strand per method.
3 recorded ways of doing Recover the period of a periodic function. Nothing smaller is recorded inside it, so there is no object in the middle to draw.
Everything on this figure that opens is open.
Of the routes that have been taken apart, 15 are built entirely from named slots, 15 hand off part of the work and finish the rest themselves, and 20 are one undivided act. None of the three is a defect; they are different things to reuse.
Every line on this figure, in words
The lines on this figure
- Every line on this figure is one a recorded source takes.
Open the cardRead the full write-up
Where you are
Path
- Recover the period of a periodic function
Ways through: 3
Routes that skip it
No recorded route avoids this step.
Narrower kinds
Nothing recorded is a narrower kind of this.
Every step you can open
1 of these have an object recorded in the middle; the rest open into the methods that fill them.
- Solve a nonlinear ODE dy/dt = F(y)
- Replace a spatial domain with a finite grid
- Discretize a PDE into one linear system
- Embed a nonlinear system into a linear one
- Solve a linear ODE du/dt = A(t)u + b(t)
- Recast a non-Hermitian generator as Hamiltonian evolution
- Choose a time discretization or propagator approximation
- Quantum linear solve
- Matrix function
- QSP phase factors
- Polynomial approximation
- Block-encode a matrix
- Prepare an input state
- Amplify a success branch
- Simulate Hamiltonian evolution
- Estimate an observable
- Compile a circuit to a specific device
- Satisfy the hardware connectivity constraint
- Approximate a continuous rotation in a discrete gate set
- Recover a noiseless expectation value by post-processing
- Build logical qubits at a target logical error rate
- Estimate a Hamiltonian's ground-state energy
- Choose a parameterised trial state
- Minimise the objective over the parameters
- Estimate an excited-state energy
- Measure what the machine can actually do
- Recover the period of a periodic function
- Estimate the eigenphase of a unitary
- Find the item a check accepts
- Walk a graph to the vertex you want
- Search a cost Hamiltonian for the assignment it minimises
What is on this map, counted
What is here, counted
147 nodes — 31 slots and 116 methods.
76 of the 147 link to a record in the Atlas, between them naming 89 records. The rest name papers and nothing else: this graph describes work the catalogue has not got yet, and the nodes with no record are the list of what a corpus pass has to go and read.
0 slots have no method recorded, and 32 methods have not been taken apart. Both are shown as what they are rather than left blank.
Every claim here rests on a source. This graph cites 140 papers; they and the 172 the Atlas cites alone are registered in one place, with what each reports and everywhere it is cited from. Papers