SlotLayer 0
Walk a graph to the vertex you want
When candidates sit on a graph and the work done at one vertex is still worth something at its neighbour, walk the graph instead of sampling it — and pay per move rather than per candidate.
A rule naming the neighbours of any vertex, a rule saying whether a vertex is marked, somewhere to start — one named vertex, or a distribution over them — and the size bounds the schedule is computed from: the number of vertices, the depth, the maximum degree, or the size of the subsets a vertex stands for. Which of those a method needs is a property of the walk, not of the slot.
A marked vertex, with the evidence it is marked already in hand from the work stored on it — or the report that the graph holds none, at a stated failure probability.
This one, drawn
From Search graph with a marked set to A marked item, with its query bill
A circle is an object you are holding. Each line between the two ends is one recorded way through this slot; where a way is built from smaller slots, those are its own lines. Circles are named on hover, and each one is a link.
Nothing drawn here has a recorded way through it that this figure leaves shut. See it on the map
Why this is a layer
Both routes here inherit a detector — a bit saying whether a marked vertex exists — and have to turn it into a finder, and they do it differently — which is the choice a reader actually makes. Szegedy's quantization of a Markov chain, and Belovs's later reading of it through effective resistance, certify a bit: whether a marked vertex exists. Ambainis converts that into a witness by construction, because the vertex his walk lands on carries the queried values that prove it marked, so measuring it hands over the colliding pair. Montanaro converts it by search, running the detector on subtree after subtree down the tree, which costs him a factor of for the descent and another for tightening each detection's confidence, and buys the right to a walk on a graph nobody laid out in advance — he says so against the earlier work directly: "in prior work it is usually assumed that the input graph is known in advance, and moreover that the initial state of the quantum walk is the stationary distribution of the corresponding random walk". That the two families are genuinely different, rather than one framework at two settings, is the literature's own verdict rather than this map's: Magniez and Nayak, using Szegedy's route where Ambainis's had not worked, conclude that group commutativity and triangle finding together "give strong evidence that the walks due to Ambainis are not comparable with the ones due to Szegedy".
Ways to do this
2 methods recorded
- Walk over subsets that remember their queries
Make each vertex a subset of the input together with the values already queried for it, so that stepping to a neighbouring subset costs one query rather than a fresh batch. Grover diffusion over which element to add or remove supplies the moves, and a phase flip on subsets that already contain the answer supplies the direction.
- Walk the backtracking tree itself
Take the tree a classical backtracking algorithm would have explored — never built, never known in advance — and walk it from the root. Phase estimation on the walk operator says whether a solution is down there at all; running that test on subtree after subtree turns the answer into the solution.
Routes that skip this layer
No recorded route avoids this step.
This is a step inside
Nothing in this graph needs this as a step, so it is where a reading starts.
In the Atlas
No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.