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.
Method
Koopman-von Neumann lift to phase-space densities
Represent nonlinear non-Hamiltonian classical dynamics by the Liouville equation for the phase-space density; the generalized Koopman-von Neumann formulation recasts that as a Schrödinger equation with a Hermitian Hamiltonian operator and a unitary propagator. The lift is exact, and its cost is dimensional rather than an approximation error.
Open the full recordFills the slot: Embed a nonlinear system into a linear one
Applies to nonlinear non-Hamiltonian classical dynamics on phase space. Joseph's efficiency claim holds when the Koopman-von Neumann Hamiltonian is sparse, and is stated relative to a deterministic Eulerian discretization of the Liouville equation. The lifted object is a distribution over phase space, so recovering a single trajectory or a pointwise value is a separate readout problem.
, , , , and a truncation or lift parameter (Carleman truncation level , a phase-space grid, the level-set dimension, the homotopy order).
Nonlinear initial-value problem → Linear ODE systemcarry the density as an amplitude
The lifted object is the phase-space density, not a trajectory. For ODEs with an arbitrary vector field, conservation of the density is the Liouville equation , whose Liouville operator is the adjoint of the advection operator and coincides with it, both anti-Hermitian, only when — the general case is exactly what this lift has to handle. assumption: The lift's postulate is that the density is the inner product of a complex probability amplitude with its adjoint, , so that , together with an assumed equation of motion for the phase, ; the phase has no effect on the classical dynamics and is not measurable within it, so the choice of is a choice of gauge, the trivial choice being the constrained classical action. assumption: Expectations are read back as , which requires the density normalized to yield unit probability after integration over all of phase space. Differentiating then gives , and multiplying by gives the generalized Koopman-von Neumann equation , which has the form of a Schrödinger equation : promoting , and every function of the coordinates to an operator by its formal Taylor series gives . Integration by parts over proves Hermitian, so the propagator of is unitary for any set of ODEs, not only Hamiltonian ones; solved by characteristics along it is explicit, with . The branch of is irrelevant to the classical system, but Joseph records that the phase shift set by the Maslov index , which counts the zeros of the Jacobian along the trajectory, must be accounted for to obtain the correct semiclassical phase factor — a framework he leaves for future work. Because is linear in , Heisenberg's equations for the coordinates are exactly the classical ones, , and the uncertainty principle binds each only to its own conjugate momentum and never one original variable to another, so there is "complete fidelity to the classical phase space evolution". Nothing is truncated and there is no convergence parameter; the price is dimensional, being the quantization of the constrained Hamiltonian on twice the classical phase-space dimension, whose momenta are Lagrange multipliers enforcing the equations of motion.
assumption
A linear generator with any inhomogeneity, a lift map, a readout map, and an error bound as a function of the truncation parameter.
None found yet.
given a classical system presented as first order in time,
dx/dt = v(x,t), x in R^d, v an arbitrary vector field
# nonlinear, and not required to be Hamiltonian; a PDE reaches this form
# through the method of lines
# the object lifted is the phase-space density, not a trajectory
write the Liouville equation for conservation of the PDF f on phase space:
d f/dt + f div v = d_t f + div( v f ) = 0
# the KvN postulate
set f = psi^dagger psi, i.e. psi = f^(1/2) e^(i phi)
choose W(x,t) and let the phase obey
d_t phi + v . grad phi = -W(x,t)/hbar
# within classical dynamics phi is not measurable, so W is a gauge
# choice; W = 0 is the constrained classical action
differentiate psi and multiply by i hbar:
i hbar d_t psi = -i hbar (1/2)( v . grad + div v ) psi + W psi
# a Schroedinger equation, i hbar d_t psi = H_hat psi
promote x -> x_hat, P -> P_hat = -i hbar grad, and every function of the
coordinates to an operator by its formal Taylor series:
H_hat = (1/2)( P_hat . v_hat + v_hat . P_hat ) + W_hat
# Hermitian over <phi|psi> = int phi^dagger(x,t) psi(x,t) d^d x, by integration
# by parts, for ANY set of ODEs -- Hamiltonian or not, dissipative or not --
# so the propagator U_hat of i hbar d_t U_hat = H_hat U_hat is unitary
# no truncation, hence no convergence parameter: the lift is exact
return H_hat (Hermitian), U_hat (unitary), the lift f -> psi, and the readout
f = psi^dagger psi, <O> = int O f d^d x
# the lifted object is a distribution over phase space, so a single
# trajectory or a pointwise value is a separate readout problem
# the price is dimensional, not an approximation error: H_hat is the
# quantization of the constrained Hamiltonian H = P . v(x,t) + W(x,t) on twice
# the classical phase space dimension, the momenta acting as Lagrange
# multipliers that enforce the equations of motionQuantum simulation of classical dynamics is exponentially more efficient than a deterministic Eulerian discretization of the Liouville equation if the Koopman-von Neumann Hamiltonian is sparse (abstract). No unconditional end-to-end query count for a general nonlinear system is stated.
None found yet.
None found yet.
None found yet.
Every paper cited here has been read in full, and none reports a run.
None found yet.
References
Where the routes meet
11 problems nothing else needs — the places a reader arrives. Open a line to see what is recorded inside it, or click its name to go there.
13 lines have something recorded inside that you have not opened.
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
Solve a nonlinear ODE dy/dt = F(y)
- Embed a nonlinear system into a linear one — opens into 6 · a way across — click it to open it here
- Solve a linear ODE du/dt = A(t)u + b(t) — opens into 9 · a way across — click it to open it here
- Choose a time discretization or propagator approximation → Quantum linear solve — open
- Choose a time discretization or propagator approximation — opens into 6 · a way across — click it to open it here
- Quantum linear solve — opens into 5 · a way across — click it to open it here
- Simulate Hamiltonian evolution → Estimate an observable — open
- Simulate Hamiltonian evolution — opens into 3 · a way across — click it to open it here
- Estimate an observable — opens into 4 · a way across — click it to open it here
Estimate an excited-state energy
- Variational quantum deflation — opens into 3 · a way across — click it to open it here
- Subspace-search variational eigensolver — opens into 3 · a way across — click it to open it here
- Quantum subspace expansion
- Quantum equation of motion
- Folded-spectrum variational eigensolver — opens into 3 · a way across — click it to open it here
- Penalty-constrained variational eigensolver — opens into 3 · a way across — click it to open it here
- Multistate contracted variational eigensolver — opens into 3 · a way across — click it to open it here
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