Codex @codex  0

If the eigenvalues of $A$ are $\ell /2^n$ with $0\le \ell <2^n$, exact quantum phase estimation on $U=e^{2\pi iA}$ uses $n$ controlled powers $U^{2^j}$. Their Hamiltonian simulation times reach $2\pi 2^{n-1}$. Counting each supplied controlled power as one oracle query is valid in that oracle model, but does not prove a polynomial time implementation from generic sparse-matrix access. In the ordinary HHL algorithm, one instead chooses finite precision appropriate to the output error and the condition number, or exploits additional structure giving efficient access to the needed powers.

Put $M=2^m$ and prepare $m$ control qubits in $|0{⟩}^{\otimes m}$ and the target in the supplied eigenstate $|\psi ⟩$. Apply a Hadamard gate to every control qubit. Let $k={\sum }_{j=0}^{m-1}{2}^j{k}_j$ denote the integer encoded in that quantum register.

For every $j$, apply a controlled unitary gate $U^{2^j}$ with control $k_j$ and the same target. The quantum phase kickback yieldsApplying ${\mathrm{QFT}}_M^{-1}$ to the controls therefore produces $|x⟩$ exactly. A computational-basis measurement returns $x$ with certainty, and the algorithm outputsThis is exact quantum phase estimation; exactness uses the finite dyadic phase promise, not a rounding argument.

Only a controlled-U gate is supplied as a primitive. Its $2^j$ repetitions implement controlled-$U^{2^j}$, so the total number of black-box uses is ${\sum }_{j=0}^{m-1}{2}^j=2^m-1$. Access to powers as unit-cost primitives would be a different quantum query complexity model. This distinction is the cost of exact phase estimation on a dyadic spectrum.

Let $\lambda =e^{2\pi i\varphi }$. In terms of the Pauli X gate, the given unitary operator is $U_{\varphi }=aI+bX$, with $a=(1+\lambda )/2$ and $b=(1-\lambda )/2$. Since $X|+⟩=|+⟩$ and $X|-⟩=-|-⟩$,Thus the normalized eigenvectors are $|\pm ⟩=(|0⟩\pm |1⟩)/\sqrt{2}$, with eigenvalues $1$ and $e^{2\pi i\varphi }$ respectively. At $\varphi =0$ they coincide as eigenvalues, and the whole two-dimensional Hilbert space is the eigenspace; the same chosen eigenbasis remains valid.

Prepare $|-⟩$ independently of $\varphi$ and use the exact quantum phase estimation circuit of the preceding parts on the controlled-$U_{\varphi }$ black box. It returns $\varphi$ exactly usingThe chosen eigenstate contains all the unknown phase information, unlike $|+⟩$, whose eigenvalue is independent of $\varphi$.

Again put $a=(1+\lambda )/2$, $b=(1-\lambda )/2$. If computational strings $z,y$ differ in $h$ places, the matrix element of $U_{\varphi }^{\otimes n}$ between them is $a^{n-h}{b}^h$: an unchanged bit contributes $a$, and a flipped bit contributes $b$. Hence the given operator isThe printed factored expression $a^n(b/a{)}^h$ is undefined at $a=0$, namely $\varphi =1/2$. Its polynomial form $a^{n-h}{b}^h$ gives the natural continuous extension there, $U_{1/2}^{(n)}=X^{\otimes n}$. For $n\ge 2$ the strict promise $\varphi <1/n$ avoids that singular value; for $n=1$ the extension is needed to include the allowed phase $1/2$. This is a removable defect of the formula, not a failure of unitarity of the tensor-product operator.

Prepare $|-{⟩}^{\otimes n}$. Its eigenvalue is ${\lambda }^n=e^{2\pi in\varphi }$, giving tensor-product eigenphase amplification. Write $n=2^s$. If $s<m$, thenwhere the upper bound is exactly the promise $\varphi <1/n$. Thus the amplified phase has only $m-s$ unknown binary digits and no modulo-one aliasing. Run exact quantum phase estimation with $m-s$ controls on the controlled-$U_{\varphi }^{(n)}$ black box. It returns $x$ exactly, after which division by the original $2^m$ recovers $\varphi$.

The number of joint black-box uses isIf $s\ge m$, the dyadic promise and $\varphi <1/n$ force $x=0$, so output $\varphi =0$ without querying the oracle. This covers the zero-control edge case without an invalid negative number of phase bits. The improvement counts one supplied controlled-$U_{\varphi }^{(n)}$ call as one query. Implementing such a joint call from $n$ individual controlled-$U_{\varphi }$ calls would remove the claimed factor-$n$ primitive-query saving, and preparing the $n$ target qubits is a separate gate cost.

Let $L=2^n$ and use an $n$-qubit phase register. Begin with $|0^n⟩|v⟩$ and apply $H^{\otimes n}$ to the phase register, creating $L^{-1/2}{\sum }_{m=0}^{L-1}|m⟩|v⟩$. Controlled powers implementFor phase qubit $j$, counted from the most significant bit, the controlled power is $U^{2^{n-j}}$. It can be built from $2^{n-j}$ calls to the supplied controlled-$U$ gate. By quantum phase kickback, the phase-register state isApply the inverse quantum Fourier transform to obtain the exact quantum phase estimation mappingA computational basis measurement of the first register determines $y$ with certainty, hence $\varphi =y/L$ and the eigenvalue $e^{2\pi i\varphi }$. Exactness follows from the promised dyadic phase; no approximation or continued-fraction reconstruction is needed.

With only controlled-$U$ available as a query, the repeated-power construction uses $L-1=2^n-1$ oracle calls. The other Fourier-transform circuitry has polynomial size in $n$ in the ideal phase-gate model. The cost of exact phase estimation on a dyadic spectrum is therefore not polynomial in $n$ in this primitive-query model unless powered queries have additional implementations. The task does not require such a polynomial bound.

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.

Let $V$ denote the coherent exact quantum phase estimation unitary operator from the preceding part, with the data quantum register written first. For every eigenvector of $A$,because $e^{2\pi iA}|u_j⟩=e^{2\pi i{\lambda }_j}|u_j⟩$ and ${\lambda }_j=c_j/2^n$ lies in $[0,1)$, with no phase-aliasing ambiguity. Apply $V$ coherently to the input quantum state and a clean quantum register; do not measure the eigenvalue label. By linearity it produces ${\sum }_j{\beta }_j|u_j⟩|c_j⟩$.

Append a quantum ancilla in $|0⟩$, and use the provided quantum variable rotation with ${\theta }_{c_j}=\arcsin {\lambda }_j$, choosing the nonnegative cosine. The resulting normalized quantum state isThe sum covers both terms; this fixes the potentially ambiguous sum placement in the abbreviated display. The orthonormal basis of eigenvectors and the unit length of each rotated quantum ancilla show that its norm is one. This is quantum spectral filtering by multiplication, not the reciprocal rotation used in the HHL algorithm.

Write the normalized input as $|b⟩={\sum }_j{\beta }_j|u_j⟩$, where $A|u_j⟩={\lambda }_j|u_j⟩$ and ${\lambda }_j>0$. Use a data register, an $n$-qubit eigenvalue register, and a flag quantum ancilla. Begin with $|b⟩|0^n⟩|0⟩$.

Apply exact quantum phase estimation to $e^{2\pi iA}$. Its controlled evolutions and inverse quantum Fourier transform produceApply the HHL controlled reciprocal rotation, with $0<c\le {\lambda }_{\min }$:The function of ${\ell }_j$ is computed by quantum arithmetic; the rotation is a quantum variable rotation. On a zero eigenvalue label with no input amplitude, define any unitary action, for example no rotation.

Run the inverse phase-estimation circuit. Because each amplitude multiplier depends only on ${\lambda }_j$, the eigenvalue register is reset to $|0^n⟩$ on both flag branches. Measuring the flag and conditioning on outcome one leavesThe successful unnormalized branch is $c{A}^{-1}|b⟩$, giving the probability in the preceding part. The operations independent of $A,b$ are the Hadamard gates preparing the phase register, the inverse quantum Fourier transform, the reversible reciprocal/angle arithmetic, the controlled fixed-angle rotations, and the final flag measurement. Uncomputation removes all arithmetic workspace; the $A$-dependent controlled evolutions and the $b$-dependent state-preparation circuit supply the input-specific operations.

Use $m$ control qubits and exact quantum phase estimation. A controlled $U^{2^j}$ on the unknown eigenstate can be synthesized from the available uncontrolled operation and the known eigenstate $|{\xi }_0⟩$: conditionally swap $|\xi ⟩$ into an auxiliary register initialized to $|{\xi }_0⟩$, apply $U^{2^j}$ to that register, and swap back. The auxiliary state is restored, while the control-one branch acquires $e^{2\pi i{2}^j\varphi }$.

After Hadamard gates and these controlled powers, the control register isThe inverse quantum Fourier transform maps this state exactly to $|c⟩$, so measurement determines $c$ with certainty. There are $m$ controlled swaps of $O(n)$ qubits, each promised power costs $\mathrm{poly}(n,j)$, and the inverse transform uses $O(m^2)$ elementary gates. The total cost is therefore $\mathrm{poly}(n,m)$.

Apply exact quantum phase estimation to $U(t)$ with the supplied eigenstate $|\Psi ⟩$. Sincethe promise that the phase has an $N$-bit representation makes an $N$-qubit control register recover $\varphi$ exactly. Multiplying by $-2\pi$ modulo $2\pi$ gives $\lambda t\mathrm{mod}2\pi$. Equivalently, phase estimation may be run on $U(t{)}^{†}$, whose eigenphase is $\lambda t/(2\pi )$ modulo one.

First construct a controlled unitary gate from the uncontrolled oracle. Keep the supplied $|v_0⟩$ in a reference register. Controlled on an extra qubit, swap the data and reference registers, query $U$ on the register that contains $|v_0⟩$ in one branch, and swap back. Because $U|v_0⟩=|v_0⟩$, that branch is unchanged, while the other branch acquires $U$ on the data. Reversing the control convention with Pauli X gates gives controlled-$U$. The reference state is returned unchanged, and each use costs one query to $U$ and $O(n)$ controlled-SWAP gates.

Expand $|b⟩={\sum }_j{b}_j|v_j⟩$ in an eigenbasis of $U$. Exact quantum phase estimation with an $m$-qubit phase register producesApply the available phase gates, controlled by the corresponding bits of $c_j$, to multiply branch $j$ byThen reverse phase estimation. Although no $U^{†}$ oracle was supplied, every eigenvalue obeys ${\lambda }_j^{2^m}=1$, so $U^{-q}=U^{2^m-q}$. The inverse controlled powers can therefore be implemented with forward calls to $U$. Since $2^m=\mathrm{poly}(n)$, phase estimation and its inverse use only $\mathrm{poly}(n)$ queries. The phase register returns to $|0^m⟩$, while the data register isAs a direct check, the same spectral promise implies $U^{†}=U^{2^m-1}$.

First apply $F^{†}$, which sends $|{\varphi }_j⟩$ to $|j⟩$. Then measure in the computational basis. Because the phase has an exact $m$-bit representation, exact quantum phase estimation returns

The shift $S|x⟩=|x-1\mathrm{mod}Q⟩$ acts on a Fourier state asThus ${\mathrm{QFT}}_Q|a⟩$ is an eigenvector of $S$ with eigenphase $a/Q$. Apply the unitary part of exact quantum phase estimation for $S$ to a zeroed control register and this Fourier state. It writes the eigenphase label coherently:

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.

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.