Algorithms

Hadamard Test

A quantum circuit that estimates the real or imaginary part of the expectation value of a unitary operator by using an ancilla qubit and controlled operations.

Chrome solids checkerboard

The Hadamard test is a fundamental quantum subroutine that estimates Re(⟨ψ∣U∣ψ⟩)\text{Re}(\langle\psi|U|\psi\rangle) or Im(⟨ψ∣U∣ψ⟩)\text{Im}(\langle\psi|U|\psi\rangle) for a unitary operator UU and a quantum state ∣ψ⟩|\psi\rangle. It uses a single ancilla qubit, a Hadamard gate, and a controlled-UU operation. The Hadamard test is a building block for quantum phase estimation, overlap estimation, and many other quantum algorithms.

The circuit

The Hadamard test circuit for estimating Re(⟨ψ∣U∣ψ⟩)\text{Re}(\langle\psi|U|\psi\rangle):

|0⟩ ──[H]──●──[H]──[M]
           │
|ψ⟩ ──────[U]──────────

Step by step:

  1. Initialize: Ancilla in ∣0⟩|0\rangle, system in ∣ψ⟩|\psi\rangle. Joint state: ∣0⟩∣ψ⟩|0\rangle|\psi\rangle.
  2. Hadamard on ancilla: 12(∣0⟩+∣1⟩)∣ψ⟩\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)|\psi\rangle
  3. Controlled-UU: 12(∣0⟩∣ψ⟩+∣1⟩U∣ψ⟩)\frac{1}{\sqrt{2}}(|0\rangle|\psi\rangle + |1\rangle U|\psi\rangle)
  4. Hadamard on ancilla: 12∣0⟩(∣ψ⟩+U∣ψ⟩)+12∣1⟩(∣ψ⟩−U∣ψ⟩)\frac{1}{2}|0\rangle(|\psi\rangle + U|\psi\rangle) + \frac{1}{2}|1\rangle(|\psi\rangle - U|\psi\rangle)
  5. Measure ancilla:

P(0)=12(1+Re(⟨ψ∣U∣ψ⟩))P(0) = \frac{1}{2}(1 + \text{Re}(\langle\psi|U|\psi\rangle)) P(1)=12(1−Re(⟨ψ∣U∣ψ⟩))P(1) = \frac{1}{2}(1 - \text{Re}(\langle\psi|U|\psi\rangle))

The real part is extracted as:

Re(⟨ψ∣U∣ψ⟩)=P(0)−P(1)\text{Re}(\langle\psi|U|\psi\rangle) = P(0) - P(1)

To estimate the imaginary part, insert an S†S^\dagger gate on the ancilla before the second Hadamard. This shifts the measurement to probe Im(⟨ψ∣U∣ψ⟩)\text{Im}(\langle\psi|U|\psi\rangle) instead.

Applications

Quantum phase estimation: When ∣ψ⟩|\psi\rangle is an eigenstate of UU with eigenvalue e2πiθe^{2\pi i\theta}, the Hadamard test gives Re(e2πiθ)=cos⁡(2πθ)\text{Re}(e^{2\pi i\theta}) = \cos(2\pi\theta). Repeating with powers of UU (U,U2,U4,…U, U^2, U^4, \ldots) and classical post-processing recovers θ\theta bit by bit. This is the iterative form of quantum phase estimation.

Overlap estimation: Setting U=∣ϕ⟩⟨ψ∣/⟨ψ∣ϕ⟩U = |\phi\rangle\langle\psi|/\langle\psi|\phi\rangle (when constructible) or using related techniques, the Hadamard test can estimate the overlap ∣⟨ψ∣ϕ⟩∣2|\langle\psi|\phi\rangle|^2 between two quantum states.

Spectral analysis: The Hadamard test can be used to estimate the spectral function Re(⟨ψ∣e−iHt∣ψ⟩)\text{Re}(\langle\psi|e^{-iHt}|\psi\rangle) for a Hamiltonian HH, which encodes information about the energy spectrum.

Variational algorithms: In some formulations of VQE, Hadamard tests estimate off-diagonal terms in the Hamiltonian that cannot be directly measured in a single Pauli basis.

Cost analysis

The dominant cost of the Hadamard test is the controlled-UU operation. If UU is implemented as a circuit of GG gates, the controlled version typically requires O(G)O(G) additional gates plus multi-controlled operations. For Hamiltonian simulation where U=e−iHtU = e^{-iHt}, the controlled version doubles the circuit depth.

The statistical cost of estimating Re(⟨ψ∣U∣ψ⟩)\text{Re}(\langle\psi|U|\psi\rangle) to precision ϵ\epsilon is O(1/ϵ2)O(1/\epsilon^2) shots, following standard sampling statistics.

Estimating a real or imaginary overlap

The Hadamard test is one of the most versatile primitives in quantum algorithms. It converts a question about a quantum operator (the expectation value of a unitary) into a measurable probability on a single ancilla qubit. Understanding this technique provides the foundation for phase estimation, spectral methods, and many variational algorithm techniques. It also demonstrates the power of controlled operations and the role of interference in extracting information from quantum systems.

See also