Kitaev Phase Estimation
A single-ancilla phase estimation scheme that reconstructs the eigenphase from measurement statistics without an inverse Fourier transform.
A statistical approach
Kitaev's phase estimation, like the iterative variant, uses a single ancilla qubit and avoids the quantum Fourier transform. Instead of adaptive bit-by-bit feedback, it estimates the eigenphase by collecting measurement statistics of the ancilla for several powers of the unitary and combining them with classical post-processing.
Hadamard-test measurements
For a unitary U with eigenstate |u> and eigenphase phi (U|u> = exp(2 pi i phi)|u>), a Hadamard test on controlled-U^{2^k} yields an ancilla measurement whose probability of 0 is (1 + cos(2 pi 2^k phi))/2. Inserting an S gate on the ancilla gives access to the sine, so from many shots one estimates both cos and sin of 2 pi 2^k phi, and hence the angle 2^k phi modulo one.
Reconstruction
- Estimate 2^k phi mod 1 for k = 0, 1, ..., t-1 from measurement statistics.
- The k = 0 measurement pins down phi coarsely.
- Higher k measurements refine the finer bits, resolving the ambiguity from lower k.
- Combine the estimates to reconstruct phi to precision about 2^-t.
Why it avoids the QFT
The inverse QFT in standard phase estimation is essentially a device for combining phase information across scales coherently. Kitaev's method does this combination classically: each power of U probes a different scale, and the classical algorithm stitches the estimates together, handling the modular ambiguity by cross-checking neighboring scales. This shifts complexity from quantum circuit depth to classical processing and shot count.
Trade-offs and context
The advantages are a single ancilla and no QFT, easing hardware requirements. The costs are many measurements per power and a classical reconstruction step, plus the need for enough shots to resolve each cosine and sine to sufficient accuracy. Kitaev phase estimation, iterative phase estimation, and standard QPE occupy a spectrum trading qubits, circuit depth, classical processing, and measurement count.