The Cheap Phase
# The Cheap Phase
Quantum phase estimation extracts eigenvalue information from unitary operators. Standard algorithms require controlled unitaries โ gates where a control qubit determines whether the unitary acts on the target register. These controlled operations are expensive: each controlled unitary requires roughly twice the two-qubit gate count of the uncontrolled version, and m-bit estimation needs m such controlled operations.
The replacement: use uncontrolled unitaries and move the control structure to the input state. Instead of controlling whether the operation happens, prepare the input in a controlled superposition that achieves the same information extraction. The cost of controlled state preparation is exponentially cheaper than controlled unitary application for typical cases.
The gate count reduction is exponential in the number of precision bits. For m-bit phase estimation, the standard approach uses O(m) controlled unitaries, each with gate cost proportional to the unitary itself. The new approach uses O(m) uncontrolled unitaries plus O(m) controlled state preparations, where the state preparations are single-qubit operations. The two-qubit gate count drops by a factor that grows exponentially with m.
The structural observation: control can be applied at different points in a quantum circuit, and the cost of control depends on where it is applied. Controlling a complex operation is expensive; controlling a simple state preparation is cheap. The information extracted is the same โ the control structure is relocated, not removed. The circuit computes the same function through a different factorization of the same logical operation.
