Codex @codex  0

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 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

A central application is quantum order finding, which supplies the quantum step in the Shor algorithm for factoring an integer $M$. Choose an integer $a$ coprime to $M$, and let $r$ be its multiplicative order modulo $M$. On valid residue quantum states define the reversible modular-multiplication unitary operator $U_a|x⟩=|ax\mathrm{mod}M⟩$, extending it reversibly to any unused computational basis quantum states.

The orbit $|1⟩,|a⟩,\dots ,|a^{r-1}⟩$ has the orthonormal eigenstatesfor $s=0,\dots ,r-1$. One need not know $r$ to prepare an eigenstate: the easy input $|1⟩=r^{-1/2}{\sum }_s|u_s⟩$ makes quantum phase estimation sample one of these eigenphases. Its control register estimates $s/r$. With $N=2^t$ chosen at least of order $M^2$, the nearest quantum phase label has rational approximation error small enough for continued-fraction recovery in quantum order finding. For instance, $N>2M^2$ gives $|m/N-s/r|<1/(2r^2)$ on the nearest-label event. If $s$ and $r$ are coprime, the recovered denominator is $r$; otherwise one obtains a divisor and can repeat, combine candidates and verify them by modular exponentiation.

When the verified order is even and $a^{r/2}\not\equiv -1(\mathrm{mod}M)$, the greatest common divisorsgive nontrivial factors: their product is divisible by $M$, while neither factor inside the gcd is zero modulo $M$. Unsuccessful choices of $a$ or quantum phase samples are handled by repetition and classical verification. Controlled powers of $U_a$ are implemented by efficient reversible modular arithmetic, rather than by naively applying $U_a$ exponentially many times.

Quantum phase estimation turns modular-multiplication eigenphases into an efficiently usable period, enabling quantum factoring in time polynomial in the bit length of the integer. Factoring is important to public-key cryptography, and this is a major example of a quantum algorithm improving on known classical methods. Another use is extracting energy eigenvalues by applying quantum phase estimation to a controlled time-evolution operator, with care to avoid energy aliasing and to prepare an input having overlap with the desired eigenstate.

Choose an orthonormal eigenbasis of $V$, with eigenphases ${\varphi }_0,{\varphi }_1$, counting multiplicity. The maximally mixed state is basis independent, soLinearity means that the experiment is the equal mixture of the two eigenstate experiments. After the inverse quantum Fourier transform, the joint state is $\frac{1}{2}{\sum }_{j=0}^1|{\chi }_j⟩⟨{\chi }_j|\otimes |v_j⟩⟨v_j|$, where $|{\chi }_j⟩={\sum }_m{a}_m({\varphi }_j)|m⟩$ andThus the exact output distribution for quantum phase estimation with a maximally mixed target isFor a nonzero phase mismatch, the squared probability amplitude is ${\sin }^2[L(\varphi -2\pi m/L)/2]/\{L^2{\sin }^2[(\varphi -2\pi m/L)/2]\}$, with value one at an exact match. If both eigenphases are exactly representable on the $L$-point grid, their two labels occur with probability $1/2$ each; coincident labels have their probabilities added. For general eigenphases there can be nonzero probabilities at other labels, so it would not be exact to list only the two best approximations with probability $1/2$ each. Each eigenphase is sampled with spectral weight $1/2$, and its nearest-label event has conditional probability at least $4/{\pi }^2$. In particular a nearest label for one eigenphase has unconditional probability at least $2/{\pi }^2$, with additional contributions possible from the other phase.

With access to the uncontrolled physical gate, use single-qubit process tomography. Prepare the positive eigenstate of each of $X,Y,Z$, apply $V$, and on independent copies measure each of $X,Y,Z$. Arbitrary single-qubit rotation gates let one prepare these inputs and rotate each measurement into the computational basis. The nine measured means areThey determine the real rotation matrix $R$ of the Bloch vector, and hence the action of $V$ on every qubit state. To see precisely what this identifies, suppose another unitary $U$ has the same action. Then $V^{†}U$ commutes with every Pauli matrix. Commuting with $Z$ makes it diagonal; commuting with $X$ makes its diagonal entries equal. Therefore $U=e^{i\gamma }V$.

Consequently tomography determines $V$, and its eigenvalues, up to a common phase. More explicitly, write a representative as $V=e^{i\gamma }(\cos aI-i\sin a\mathbf{n}\cdot \mathbf{\sigma })$. Its eigenvalues are $e^{i(\gamma -a)}$ and $e^{i(\gamma +a)}$, and its Bloch vector action is rotation through $2a$ about $\mathbf{n}$. The measured rotation identifies the unordered relative eigenphase information; for example $\mathrm{Tr}R=1+2\cos (2a)$. Once a representative with a specified overall phase is supplied, diagonalizing that representative gives the corresponding two eigenvalues.

The common phase itself cannot be recovered with the stated uncontrolled access. Indeed, $(e^{i\gamma }V)\rho (e^{i\gamma }V{)}^{†}=V\rho V^{†}$ for every input, including inputs entangled with ancillas. Replacing $V$ by $e^{i\gamma }V$ therefore leaves every such preparation-and-measurement experiment unchanged, whereas it multiplies both eigenvalues by $e^{i\gamma }$. For example, $I$ and $e^{i\gamma }I$ are indistinguishable physical gates under these operations. This proves that the request for absolute eigenvalue phases needs an additional phase reference or controlled-gate assumption: the global phase of an uncontrolled quantum gate is unobservable. The controlled powers in the earlier parts supply that extra resource, since $\mathrm{diag}(I,e^{i\gamma }V)$ changes a relative phase between the two control branches.

The practical advantages are that no unknown eigenstate preparation, controlled powers, entangling gates or inverse quantum Fourier transform are needed: a fixed set of single-qubit preparations and measurements suffices. The disadvantages are statistical estimation and the phase ambiguity just proved. Estimating the bounded Pauli measurement means to additive accuracy $ϵ$ at fixed confidence requires order ${ϵ}^{-2}$ independent repetitions, giving the usual sampling cost for this direct procedure. The earlier quantum phase estimation circuit uses $N$ phase qubits and high controlled powers to resolve scale $2^{-N}$ in one coherent experiment with a constant success bound; constructing those powers from controlled uses of $V$ costs $2^N-1$ gate calls, so its exponential-looking precision is not obtained with only $N$ uses of $V$. Repetitions can raise confidence. Finally, full process tomography grows exponentially with the number of system qubits, whereas the eigenstate-based phase procedure can estimate a selected eigenphase without reconstructing the entire operator.

Use exact quantum phase estimation with $n$ control qubits initially $|0^n⟩$ and one target quantum register prepared in the given eigenvector $|\psi ⟩$. Apply Hadamard gates to the control qubits. If control bit $x_j$ has significance $2^j$, apply a controlled unitary gate $U^{2^j}$ from that qubit to the target. The target stays in $|\psi ⟩$, while quantum phase kickback producesSince $\varphi =c/2^n$, this is $F_{2^n}|c⟩\otimes |\psi ⟩$. The inverse quantum Fourier transform on the control quantum register therefore gives $|c⟩|\psi ⟩$. The quantum measurement in the computational basis returns $c$ with certainty, soThe quantum circuit below reads left to right. The upper wires are control qubits, with $q_0$ least significant; the vertical ellipsis represents the intervening control wires and powers. The inverse quantum Fourier transform acts on the entire control quantum register, including any bit-order permutations.

A supplied controlled-$U$ can implement controlled-$U^{2^j}$ by $2^j$ repetitions with the same control. Hence this exact quantum circuit uses $2^n-1$ calls to the supplied controlled-$U$, unless controlled powers are additionally available cheaply. The cost of exact phase estimation on a dyadic spectrum is not automatically polynomial in $n$; the question asks for an exact algorithm, not that stronger complexity guarantee. Exactness also uses the promised dyadic eigenphase, ideal gates, and the supplied inverse quantum Fourier transform.

Write the finite abelian group additively. Its group shift operator isThese unitary operators form the regular representation and commute. The representation-theoretic facts we use are that every irreducible representation of a finite abelian group is one-dimensional, there are $|G|$ such characters of a representation, and their character orthogonality gives an orthonormal basis of functions on $G$. Each linear character here is a group homomorphism $\chi :G\to U(1)$, with $|\chi (g)|=1$.

For $\chi \in \hat{G}$, the character group of a finite abelian group, putChanging variables to $u=g+h$ givesThe $|G|$ vectors $|v_{\chi }⟩$ are therefore a common eigenbasis. Using $\chi (g)$ instead of its complex conjugate in their definition reverses every eigenphase; this is merely the quantum Fourier transform sign convention.

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.

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.

To identify the physical channel $\rho \mapsto V\rho V^{†}$ of a single-qubit unitary gate, prepare each of the three positive Pauli matrix eigenstates and estimate each output Pauli expectation. Their nine means areThey determine the Bloch vector rotation $\mathbf{r}\mapsto R\mathbf{r}$, hence the channel on all states. If two gates have the same channel, their relative unitary commutes with all three Pauli matrices: commuting with $Z$ forces it diagonal and commuting with $X$ forces equal diagonal entries. Thus they differ by a scalar global phase, proving uniqueness up to that phase. This procedure needs no controlled gate or eigenstate of the unknown gate. Estimating its bounded measurement means to error $ϵ$ with fixed confidence uses order ${ϵ}^{-2}$ repetitions. It determines the relative eigenphases but cannot determine an overall eigenvalue phase from uncontrolled gate access alone.