Estimate the eigenphase of a unitary

Why this is a layer

The methods here differ in a resource trade a reader has to make deliberately, and Dobsicek et al. state both sides of it in one sentence: to reach a precision of order $1/2^m$ "it is possible to run either log m rounds (iterations) with m ancillary qubits or m log(m) rounds with only a single ancilla". So the choice is ancillas against rounds — hold a whole register coherent and finish quickly, or hold one qubit and pay in sequential measurements with classical feedback between them. Which is cheaper is a property of the machine rather than of the algorithm, and their own motivation says so: "As long as the number of qubits is a limiting factor, implementations of phase estimation with only a single ancillary qubit will be of foremost importance." A cost model that says "phase estimation" without saying which of the two has not said what the machine is being asked for.

Ways to do this

2 methods recorded

• Phase estimation into an ancilla register

  Put a register of ancillas into superposition, apply controlled U raised to each power of two into it, and let the phase accumulate across the register. The register then holds the phase in the Fourier basis, and one transform back turns it into bits you can measure.

• Iterative phase estimation on one ancilla

  Use one ancilla and measure it, over and over, least significant bit first. Each measured bit is fed back classically as a rotation angle on the next round, so the register the other route holds in superposition is replaced by a classical string that grows one bit at a time.

Routes that skip this layer

No recorded route avoids this step.

This is a step inside

• Ground-state energy by phase estimation

  Prepare a state that already overlaps the ground state, evolve it under the molecular Hamiltonian, and read the energy off the accumulated phase. Nothing is optimized and nothing is varied — the answer is a measured eigenvalue, and the whole difficulty moves into the starting state.

• 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.

In the Atlas

• Quantum counting

  Estimates how many items in an unstructured search space satisfy an oracle, without checking them one by one.

• Estimating Gauss sums over finite fields and rings

  Given the specification of a nontrivial multiplicative character χ and an additive character indexed by β over a finite field F_{p^r}, estimate the angle γ modulo 2π in the Gauss sum G(F_{p^r}, χ, β) = √(p^r) · e^(iγ). The same question is then asked for Dirichlet characters over Z/nZ.

• Diagonal entries of powers of a sparse symmetric matrix

  Given a real symmetric N × N matrix A whose rows are sparse — the non-zero positions and values of any row returned by an efficiently computable function rather than stored — together with an index j, an integer power m, an a priori bound b on the norm of A, a threshold g and a precision ε, decide whether the diagonal entry (A^m)_jj is at least g + εb^m or at most g − εb^m.

• String rewriting derivation counts

  Fix a relation that permits replacing one substring by another. Given strings s, t and t′ of length L, let Δ(n) be the number of ways of reaching t from s in exactly n replacements minus the number of ways of reaching t′. Given a promise that |Δ(m)| ≥ εc^m for the input m, and a growth promise that Δ(n) ≤ c^n for every n, determine the sign of Δ(m).