Sign outOpen workspaceSign in

SlotLayer 2

Amplify a success branch

Take a routine whose output lands in the wanted subspace only with probability aa, and raise that probability to near 1 using quadratically fewer repetitions than restarting the routine would need.

Takes

The preparation unitary AA and its inverse, a reflection about ∣0⟩\lvert 0\rangle, and a reflection marking the good subspace — the Grover operator Q=−AS0A−1SχQ = -A S_0 A^{-1} S_\chi must be applicable at arbitrary powers. Individual variants additionally require a lower bound on aa, or a per-branch stopping flag.

Returns

A routine that produces the wanted branch with a stated failure probability, together with the query count and the maximum sequential depth consumed.

This one, drawn

Amplify a success branchFixed-point amplificationVariable-time amplificationFixed-point amplification — click the name to read about itFixed-point amplificationVariable-time amplification — click the name to read about itVariable-time amplificationRoutine with a good branch — you start hereReliable routine — you finish here

Drag to pan. Pinch, or hold ctrl and scroll, to zoom. Arrow keys pan, plus and minus zoom, zero resets the view.

From Routine with a good branch to Reliable routine

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

Every LCU and block-encoding construction succeeds only on an all-zeros ancilla flag, so this layer is structural rather than optional. Its realizations demand different things: textbook amplification needs the success amplitude to be known, fixed-point amplification needs only a lower bound on it, and variable-time amplification needs the amplified routine to break into stages that stop at different times. What changes between them is the maximum sequential depth, which is the resource a coherence-limited device actually runs out of first.

Ways to do this

2 methods recorded

  • Fixed-point amplification

    Replace the ±1±1 reflections of textbook amplification with tuned phase shifts, so the iteration converges on the target instead of rotating past it — which is what happens when the initial success amplitude is known only as a lower bound.

  • Variable-time amplification

    When the branches of the amplified routine stop at different times, amplify in nested stages so branches that finish early are not charged at the worst-case depth.

Routes that skip this layer

These do not fill the slot. They replace the span it belongs to, so this layer is not on their path at all.

  • Eigenstate filtering inversion

    Construct the minimax-optimal polynomial that is 1 at a target eigenvalue and uniformly small outside a spectral gap, and apply it through quantum signal processing. For a linear system ∣x>|x> is the null eigenstate of a Hamiltonian built from AA and ∣b>|b>, so one application of the filter solves it once a starting state with non-trivial overlap is supplied.

This is a step inside

  • HHL: eigenvalue inversion by phase estimation

    Prepare ∣b>|b>, run phase estimation against e−iAte^{-iAt} to write eigenvalue estimates into an ancilla register, apply a controlled rotation with amplitude proportional to 1/λ~1/λ̃, uncompute the estimation and post-select on the rotation ancilla. The success amplitude is about 1/κ1/κ, so the procedure is amplified O(κ)O(κ) times.

  • QSVT matrix inversion

    Block-encode AA, apply the quantum singular value transformation with an odd polynomial approximating a scaled 1/x1/x away from the origin, then amplify. Because it acts on singular values, AA need not be Hermitian or sparse — only block-encodable.

  • Chebyshev LCU inversion

    Expand an approximation of 1/x1/x in Chebyshev polynomials and implement that expansion directly through the quantum walk associated with a sparse AA, rather than through Hamiltonian simulation. Phase estimation is never used, which is what removes the poly(1/ε)\mathrm{poly}(1/\varepsilon) bottleneck.

  • Truncated-Taylor LCU simulation

    Truncate the Taylor series of e−iHte^{-iHt} over short segments and implement the truncated sum as a linear combination of unitaries — PREPARE loads the coefficients, SELECT applies the terms, PREPARE†† unprepares — with the all-zeros ancilla flag amplified.

In the Atlas

  • Amplitude amplification

    The general framework behind Grover's algorithm: boosting the success probability of any subroutine with a known reflection structure.