Quantum phase estimation

Input. An integer $m\ge 1$; an $m$-qubit phase register; a finite-dimensional system register $H$; a unitary $U:H\to H$; a unit eigenvector $\psi$ with promised phase $\theta \in [0,1)$; and one of the forward access capabilities in Eigenphase estimation access model.

Output. A classical label $y\in \{0,\dots ,Q-1\}$ and its phase estimate $y\mathrm{/}Q$, where $Q=2^m$.

Instructions.

1. Initialize the phase register in $\mathrm{\mid }{0}^m⟩$ and the system register in $\psi$.
2. Apply the Hadamard $H=(X+Z)\mathrm{/}\sqrt{2}$ of Exact one-qubit gates and rotations to each phase wire. This prepares $Q^{-1\mathrm{/}2}{\sum }_{x=0}^{Q-1}\mathrm{\mid }x⟩\otimes \psi$ in the declared big-endian order.
3. For $j=0,\dots ,m-1$, apply the supplied controlled $U^{2^j}$ to control wire $q_{m-1-j}$ and the system. Under single controlled-unitary access, implement that operation with $2^j$ sequential calls to $C(U)$, as specified by the access model.
4. Apply the inverse of the positive-sign exact binary QFT circuit of Positive-sign cyclic quantum Fourier transform and Exact binary QFT circuit correctness. Construct it by reversing the chronological gate list and replacing each gate by its adjoint, including the final swaps and negating controlled-phase angles.
5. Perform the computational-basis projective measurement on the phase register. Its specified Lüders instrument has branch map $Z\mapsto (\mathrm{\mid }y⟩⟨y\mathrm{\mid }\otimes I_H)Z(\mathrm{\mid }y⟩⟨y\mathrm{\mid }\otimes I_H)$ for each label $y$ (Finite projective measurements, Finite instruments and conditional states). Output the observed label $y$ and the ratio $y\mathrm{/}Q$.

The inverse in step 4 is the inverse QFT, not $U^{-1}$; a forward QPE run makes no controlled inverse-unitary query. The coherent prefix is the circuit through step 4 before measurement. A consumer that coherently uncomputes this prefix needs the separate controlled inverse-power capability from Eigenphase estimation access model.

For the instrument clause in step 5, let ${\mathcal{H}}_{\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}}=({\mathbb{C}}^2{)}^{\otimes m}\otimes H$ and $P_y=\mathrm{\mid }y⟩⟨y\mathrm{\mid }\otimes I_H$. Tensor products of these operators act factorwise on elementary tensors by Tensor products of finitely many linear maps. The phase-register basis projectors are self-adjoint idempotents, mutually orthogonal and complete, so $(P_y{)}_{y=0}^{Q-1}$ is a projective measurement on ${\mathcal{H}}_{\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}}$ (Finite projective measurements, Finite registers and their ordered computational bases, Ordered tensor registers, their inner product, and wire permutations). The space ${\mathcal{H}}_{\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}}$ is nonzero and finite-dimensional because $m\ge 1$ and the input includes a unit vector in finite-dimensional $H$ (Eigenphase estimation access model). For every $v\in {\mathcal{H}}_{\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}}$, $⟨P_{y}v,v⟩=⟨P_y^{2}v,v⟩=⟨P_{y}v,P_{y}v⟩\ge 0.$ Thus each $P_y$ is nonnegative (Non-negative and positive operators) and the complete family is a finite POVM (Finite POVMs and their outcome law). Since $P_y$ is itself nonnegative and $P_y^2=P_y$, uniqueness of the nonnegative square root gives $P_y^{1\mathrm{/}2}=P_y$ (A non-negative operator has a unique non-negative square root). Applying The square-root Lüders maps form an instrument to this POVM therefore proves that the branch maps $Z\mapsto P_{y}Z{P}_y$ specified in step 5 form a valid finite instrument.