Hadamard test

In plain terms

Quantum algorithms constantly need expectation values. An operator is a transformation of a quantum state, a rotation of it, say, and its expectation value in a given state is the number you get by comparing the state with its transformed version, how much of the original survives and with what phase. That number lives in the amplitudes, and amplitudes aren't things a measurement returns.

The Hadamard test converts the number into a coin. One helper qubit, an ancilla, is put into a superposition of its two readings and controls whether the operator acts, so in one branch it does and in the other it doesn't. Closing the superposition makes the two histories interfere, and the ancilla's bias towards reading zero is exactly the real part of the expectation value. A complex number has a real part and an imaginary part, and a small phase adjustment on the ancilla before the final step reads the imaginary part instead.

Flip the coin enough times and the number emerges. It's the parent trick behind the swap test and behind half of the variational quantum algorithms.

In CSD

The Hadamard test is the parent witness of the corpus's ancilla-interferometry family, the algorithms that read a quantity off the interference of a single helper qubit. Three facts are proved, that the probability the ancilla reads zero is exactly one half plus half the real part of the expectation value, that the probability of reading one is the complement, and that the difference between the two is exactly the real part itself. A fourth theorem recovers the swap test as the instance in which the operator is the swap of two registers, tying parent to child.

The standing disclaimer applies, as the algorithms consume the programme's unitary- evolution pillar and don't support the foundations.

Mathematically

H on the ancilla, controlled-U, H again, on |0> tensor psi, and the ancilla marginals are (1 plus-or-minus Re<psi, U psi>)/2. The corpus proves P(0) = (1 + Re<psi, U psi>)/2 (hadamard_test_prob), the complementary outcome, and the sign reading P(0) - P(1) = Re<psi, U psi> (hadamard_test_prob_diff). The estimator is linear in the operator, which is what makes it the general-purpose expectation-value primitive.

The corpus also closes the family loop, as at U the swap on a doubled system the test's bias reproduces the swap test's (hadamard_test_swap_closed), tying parent to child in one theorem.

Related entries

• swap testThe swap test measures how alike two quantum states are without learning anything about what either one is, so it's a comparison that keeps both secrets.
• phase estimationPhase estimation, the workhorse subroutine of quantum computing, carries a guarantee, as if you read the dial at the nearest tick you're right at least four divided by pi squared of the time, a little over forty percent, however fine the dial.
• Deutsch-Jozsa algorithmThe Deutsch-Jozsa algorithm settles a question with a single query where any exact classical method needs exponentially many, and the problem it solves is useless by design and historic for exactly that reason.
• Bernstein-Vazirani algorithmA hidden string of bits costs one classical question per bit, or exactly one quantum question in total, so the Bernstein-Vazirani algorithm is the cleanest single-query win the field has.
• amplitude estimationPoint phase estimation at the rotation inside amplitude amplification and the success probability itself becomes measurable, quadratically faster than sampling could ever learn it.