Quantum phase estimation

Given controlled powers of a unitary $U$ and an eigenstate $U|\psi ⟩=e^{2\pi i\varphi }|\psi ⟩$, quantum phase estimation outputs an approximation to $\varphi$. If the input is a superposition of eigenstates, measurement selects an eigenphase with probability equal to the squared magnitude of its coefficient.

Let $L=2^t$, let $j_0$ be the nearest label to $L\varphi$, and let $m\ge 2$. The exact quantum phase estimation amplitude is $L^{-1}{\sum }_{a=0}^{L-1}{e}^{2\pi ia(\varphi -j/L)}$. The sine bound on circular distances gives probability at most $1/(4d_j^2)$, where $d_j$ is the centered distance from $j$ to $L\varphi$. At label distance $\ell$ from $j_0$, $|d_j|\ge \ell -1/2$, with at most two labels for each $\ell$. Since $(\ell -1/2{)}^{-2}\le [(\ell -1)\ell {]}^{-1}$, the tail telescopes to the displayed bound. Adding $u$ control qubits beyond $b$ desired phase bits gives circular accuracy below $2^{-b}$ with failure probability at most $[2(2^u-1){]}^{-1}$.

For register size $N=2^t$ and eigenphase $\varphi =2\pi n/N+ϵ$, the amplitude of decoded label $m$ is $N^{-1}{\sum }_{k=0}^{N-1}{e}^{ik(\varphi -2\pi m/N)}$. The finite geometric series gives $P(n)={\sin }^2(Nϵ/2)/[N^2{\sin }^2(ϵ/2)]$. If $N|ϵ|\ll 1$, this is $1-(N^2-1){ϵ}^2/12+O(N^4{ϵ}^4)$. Thus the nearest exactly representable phase is returned with probability near one, not with certainty unless the offset vanishes.

// Target: quantum-error-correction.bigb

Use CNOT gates to encode one logical qubit and $r-1$ zero ancillas into the repetition subspace spanned by $|0^r⟩,|1^r⟩$. Apply the phase gate in parallel to all $r$ physical qubits, then undo the encoding. The logical phase is multiplied by $r$ in one oracle-time layer. This copies computational-basis labels coherently rather than cloning an arbitrary quantum state. Blocks of sizes $1,2,4,\dots ,2^{n-1}$ prepare a dyadic Fourier phase state using $2^n-1$ parallel oracle applications.

For a $d$-dimensional unitary operator $V={\sum }_{j=1}^d{e}^{i{\varphi }_j}|v_j⟩⟨v_j|$, a maximally mixed state $I/d$ on its target is the equal mixture of these orthonormal eigenvectors. Therefore quantum phase estimation with register size $L$ produces label $m$ with probabilityThis follows by linearity of unitary time evolution and the Born rule on the spectral mixture. If every eigenphase has an exact $L$-grid label, that label has probability equal to its multiplicity divided by $d$. Otherwise the exact distribution has tails, and the nearest labels are guaranteed only the nearest-integer success bound for quantum phase estimation weighted by the corresponding spectral probabilities.

For a unitary operator eigenphase $\varphi$, an $n$-qubit quantum phase estimation register of size $L=2^n$ has output probability amplitudeChoose the nearest integer label $m$ to $L\varphi /(2\pi )$, with labels understood modulo $L$, and put $d=L\varphi /(2\pi )-m$, taking the representative $|d|\le 1/2$. The finite geometric series gives $|a_m|=|\sin (\pi d)|/[L|\sin (\pi d/L)|]$. For $0<|d|\le 1/2$, concavity of sine gives $|\sin (\pi d)|\ge 2|d|$, while $|\sin (\pi d/L)|\le \pi |d|/L$. Thus the probability of the nearest label is at least $4/{\pi }^2$. At $d=0$ it is exactly one. If two labels tie for nearest, each satisfies the bound.

For the phase gate $R_a=\mathrm{diag}(1,e^{2\pi ia/2^n})$, apply powers $R_a^{2^{n-1}},\dots ,R_a$ to a uniform quantum superposition on $n$ qubits. Binary positional weights multiply the phases into $e^{2\pi iax/2^n}$ on basis vector $|x⟩$. The inverse quantum Fourier transform returns $|a⟩$ exactly, by orthogonality of roots of unity. Preparing the powers by repeated applications uses $2^n-1$ copies of $R_a$; this does not claim a number of gate calls polynomial in $n$. If $a$ is odd, its powers generate the entire set of dyadic phase gates because $a$ has a modular inverse modulo $2^n$.

An eigenstate with phase $\varphi$ becomes an eigenstate with phase $n\varphi$ under the tensor product of $n$ copies of the unitary operator. A promise $0\le \varphi <1/n$ prevents modulo-one aliasing. For $n=2^s$ and dyadic $\varphi =x/2^m$, exact quantum phase estimation then needs $m-s$ phase bits and $2^{m-s}-1$ queries to a supplied joint controlled oracle. This is a saving in joint-oracle calls, not in the total number of individual oracle invocations needed to build that joint operation.

Choose eigenphase representatives $0\le {\varphi }_j<1$ for a unitary operator $U$ and a positive integer $M$. Its positive-phase fractional power acts on each eigenstate by $e^{2\pi i{\varphi }_j/M}$. This branch uses arguments in $[0,2\pi )$ and can differ from the usual complex principal branch using $(-\pi ,\pi ]$. For exactly dyadic phases, exact quantum phase estimation stores each label in a coherent phase register; bitwise phase gates multiply it by the required phase, and inverse phase estimation removes the labels. Keeping the phase register unmeasured preserves arbitrary eigenstate superpositions and resets the ancilla qubits. With only controlled-$U$ and controlled-$U^{-1}$ primitives, the direct method uses $2(2^n-1)$ oracle calls for $n$ exact phase bits.

Let a Hermitian operator $A$ have dyadic eigenvalues ${\lambda }_j=c_j/2^t$ in $[0,1)$ for known $t$, with controlled access to the unitary operator $U=e^{2\pi iA}$. This interval ensures that different eigenvalues have different eigenphases; exact representability alone would not exclude phase aliasing, as $0$ and $1$ both give phase zero. Let a real function $h$ obey $|h({\lambda }_j)|\le 1$, and assume the required quantum variable rotations are available. Coherent exact quantum phase estimation, a quantum variable rotation and uncomputation implementPostselection on flag one gives $h(A)|b⟩$ normalized, with probability $\Vert h(A)|b⟩{\Vert }^2$, provided this vector is nonzero. Erasing the eigenvalue label by uncomputation is essential to preserve coherence between different eigenvectors. On this dyadic spectrum, $U^{2^t}=I$ gives $U^{-1}=U^{2^t-1}$, so reversing the phase-estimation gates is possible using forward controlled-$U$ calls. The choice $h(\lambda )=\lambda$ multiplies by $A$; a scaled reciprocal gives the different filter used in the HHL algorithm.

If $|b⟩$ lies in the kernel of $A$, then $A|b⟩=0$ has no normalized quantum state. A request to produce that normalized vector with positive probability is consequently undefined. For example, $A=\mathrm{diag}(0,1/2)$ on one qubit has distinct dyadic eigenvalues, but annihilates $|0⟩$. The corrected filtering assertion requires $A|b⟩\ne 0$; it cannot be repaired by assigning a positive success probability to this input.

For $0\le A<I$ and normalized $|b⟩={\sum }_j{\beta }_j|u_j⟩$, filtering by $h(\lambda )=\lambda$ succeeds withThe inequality follows by replacing each nonnegative ${\lambda }_j^2$ by its minimum and using ${\sum }_j|{\beta }_j{|}^2=1$. Equality holds exactly when all occupied eigenvectors belong to the minimum-eigenvalue eigenspace. If ${\lambda }_{\min }=0$, success is positive exactly for inputs outside the kernel of $A$.

If $U|\psi ⟩=e^{2\pi ij/N}|\psi ⟩$, controlled powers of $U$ applied to a uniform $N$-state control register produceThese states are the Fourier basis. Applying the inverse quantum Fourier transform and measuring returns $j$ with probability one.