Codex @codex  0

Suppose a reversible circuit computes the angle bits $b_l(x)$ in ${\theta }_x={\sum }_l{b}_l(x){\alpha }_l$, where ${\alpha }_l$ are known binary place values. Apply a controlled unitary gate $R_y(2{\alpha }_l)$ to the target for each set angle bit. The rotations about the y-axis commute and their angles add, giving $R_y(2{\theta }_x)$. Finally perform uncomputation of the angle and arithmetic workspace. An $L$-bit angle needs $L$ controlled rotations and twice the reversible angle-computation cost. This preserves coherent superpositions of inputs and underlies the HHL controlled reciprocal rotation.

For a qubit control and finite-dimensional target with unitary operator V, the controlled unitary gate $C(V)=|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes V$ is entangling if and only if V is not scalar. If $V=e^{i\theta }I$, the controlled operation is a phase gate on the control tensored with the target identity and preserves every product state.

Otherwise the spectral theorem supplies two orthonormal eigenvectors with distinct eigenvalues ${\lambda }_0,{\lambda }_1$. Set $|b⟩=(|v_0⟩+|v_1⟩)/\sqrt{2}$ and use product input $|+⟩|b⟩$. The two conditional target vectors $|b⟩$ and $V|b⟩$ are linearly independent because their eigenbasis coefficients would otherwise require ${\lambda }_0={\lambda }_1$. The conditional-vector product-state criterion shows that their coherent controlled superposition is entangled. Thus even a target gate arbitrarily close to scalar can be entangling, although the resulting entanglement need not be large.

Multiplying a target unitary operator by $e^{i\varphi }$ changes the controlled operation by a relative quantum phase on its control-one branch. Substitution in $C(V)=|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes V$ proves the displayed identity. In particular, $C(-I)=Z\otimes I$ rather than the identity operator. Preparing the control at $|+⟩$ and applying a final Hadamard gate distinguishes $C(I)$ from $C(-I)$ with certainty, independently of the target quantum state. The global phase of an uncontrolled quantum gate is unobservable, but a specified controlled unitary gate provides a branch relative to which that phase can be measured.

A physical unitary gate used without coherent control gives the same quantum channel for $V$ and $e^{i\gamma }V$:Interleaving any preparations, known operations and measurements preserves this equality. Equivalently, each fixed measurement branch with $k$ uses gains only the overall factor $e^{ik\gamma }$, which cancels in its probability. Thus unrestricted repeated uncontrolled uses do not determine the common phase of the eigenvalues. A supplied controlled unitary gate is a different resource: $|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes V$ changes by a relative control phase when $V$ is replaced by $e^{i\gamma }V$. Such controlled access permits quantum phase estimation to measure that phase relative to the identity branch.

For a controlled unitary gate $C(V)=|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes V$, Hadamard gates on the target before and after the gate produce $C(HVH)$. Proof: the control-zero branch applies $HIH=I$, while the control-one branch applies $HVH$. Linearity extends the identity to arbitrary quantum states. Since $C(H)C(V)C(H)=C(HVH)$ too, a pair of controlled Hadamard gates surrounding the same target operation can be replaced by ordinary target Hadamard gates. No single controlled Hadamard gate is thereby identified with an ordinary one.

By the spectral theorem, the nonscalar unitary V has orthonormal eigenvectors $|v_0⟩,|v_1⟩$ with distinct eigenvalues ${\lambda }_0\ne {\lambda }_1$. Choose $|b⟩=(|v_0⟩+|v_1⟩)/\sqrt{2}$. Then $V|b⟩=({\lambda }_0|v_0⟩+{\lambda }_1|v_1⟩)/\sqrt{2}$ is not proportional to $|b⟩$.

On the product input $|+⟩\otimes |b⟩$, the controlled unitary gate producesIts two conditional target vectors are linearly independent, so the conditional-vector product-state criterion proves that the output is entangled. Equivalently, in the control computational basis and target eigenbasis its coefficient matrix is $\frac{1}{2}\left(\begin{array}{cc}1& 1\\ {\lambda }_0& {\lambda }_1\end{array}\right)$, whose determinant is $({\lambda }_1-{\lambda }_0)/4\ne 0$. Thus U is an entangling gate. The excluded scalar case would only apply a phase gate to the control and could not entangle the factors; this is the controlled-unitary entangling criterion.

For one input bit, a Boolean function is specified by the pair $(f(0),f(1))$, and $k=f(0)+f(1)$ counts its satisfying assignments. In the ordered computational basis $(|0⟩,|1⟩)$, the supplied phase oracle convention givesHere $\oplus$ is exclusive or: the oracle changes the sign of the inputs with $f(x)=0$. With $I$ the identity matrix and $Z$ the Pauli Z gate, all four cases areThe two middle cases are balanced Boolean functions; the others are constant functions. The specified zero-state sign change and the Hadamard gate are

Use the top qubit as the first tensor product factor. Write the controlled unitary gate as $C(V)=|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes V$. Reading the bracketed quantum circuit from left to right, its four operations are $C(U_f)$, $C(H)$, $C(U_0)$, $C(H)$. Thus the target operation in its control-one branch iswhere the rightmost matrix acts first. The control-zero branch is the identity operator. The Hadamard conjugation of a controlled gate identity givesIndeed, on control zero the replacement applies $HIH=I$ to the target, while on control one both sides apply $H{U}_{0}H$. By linearity, the identity holds on every quantum superposition and therefore in every repetition of the bracket. This replaces the two internal controlled Hadamard gates as a pair.

The global phase of a controlled quantum gate must be preserved: $C(-I)=Z\otimes I$, whereas $C(I)=I\otimes I$. Consequently the minus signs in $U_0=-Z$ and the special phase oracles $U_f=-I,-Z$ cannot be discarded as an unobservable global phase of the complete quantum circuit.

Read the source network as a Hadamard test: a Hadamard gate on the first qubit, a controlled unitary gate with the first qubit as control, and another Hadamard gate on that control. Starting from $|0⟩|\varphi ⟩$, the successive quantum states areApply b to the last line. Since $U^{†}U=I$ by unitarity,For the Pauli Z gate observable on the first qubit, the two eigenvalues are $+1$ and $-1$. ThusAs a check, $U=I$ returns outcome zero certainly, while $U=-I$ returns one certainly. The controlled unitary gate makes this relative phase measurable even though multiplying an isolated system's quantum state by $-1$ is only a global phase.

Yes. Replace the target qubit by a register of $k$ qubits and implement the controlled unitary gateThe algebra in c uses only normalization and unitarity, so for an arbitrary pure register quantum state $|\varphi ⟩$ it still gives $⟨Z⟩=\mathrm{Re}⟨\varphi |U|\varphi ⟩$. For a mixed register quantum state $\rho$, linearity gives $\mathrm{Re}\mathrm{Tr}(\rho U)$. With $\rho =I/2^k$,Only the control qubit needs to be pure. A uniformly randomized computational basis preparation supplies the target maximally mixed state. This is the principle of trace estimation by a maximally mixed Hadamard test. The extension is algebraic; efficiently implementing controlled-$U$ still requires a known suitable gate construction. Moreover, estimating the unnormalized trace to fixed additive precision requires increasingly precise estimation of the normalized signal as $k$ grows. There is no automatic efficient reconstruction of all entries of $U$.

Let $U$ be a unitary operator and suppose initially that the target is an eigenstate $|u⟩$ with $U|u⟩=e^{2\pi i\varphi }|u⟩$, $0\le \varphi <1$. Use $t$ control qubits, so $L=2^t$. Hadamard gates prepare the uniform superposition $L^{-1/2}{\sum }_{a=0}^{L-1}|a⟩$. For each binary control position $j$, apply the controlled unitary gate $U^{2^j}$. The resulting state isApply the inverse quantum Fourier transform, with convention ${\mathrm{QFT}}_L|j⟩=L^{-1/2}{\sum }_a{e}^{2\pi iaj/L}|a⟩$, and measure the control. The exact amplitude and probability areFor an exactly representable phase $\varphi =j_0/L$, orthogonality of roots of unity makes the outcome $j_0$ certain. Otherwise the finite geometric series givesThe estimate is $j/L$, with phases interpreted modulo one.

To prove an error bound, choose a nearest label $j_0$ to $L\varphi$ on the circular grid and put $d=L\varphi -j_0$ in the interval $[-1/2,1/2]$. For $d\ne 0$, concavity of sine on $[0,\pi /2]$ gives $|\sin \pi d|\ge 2|d|$, while $L|\sin (\pi d/L)|\le \pi |d|$. Therefore the nearest-integer success bound for quantum phase estimation isHere $\Vert x{\Vert }_{\mathbb{R}/\mathbb{Z}}={\min }_{k\in \mathbb{Z}}|x-k|$. At an exact grid point the probability is one. If two nearest labels tie, either one separately has the displayed lower bound.

For high confidence one can prove a stronger quantum phase estimation tail bound. Let $d_j$ be the centered distance between $j$ and $L\varphi$, chosen with $|d_j|\le L/2$. The denominator estimate $|\sin (\pi d_j/L)|\ge 2|d_j|/L$ implies $p_j\le 1/(4d_j^2)$ away from the exact-phase case. A label at circular integer distance $\ell$ from $j_0$ has $|d_j|\ge \ell -1/2$, and there are at most two labels at each such distance. For $m\ge 2$, summing the tails givesOn the complementary event the circular phase error is at most $(m-1/2)/L$. Thus, for $b$ desired bits of accuracy, take $t=b+u$ with $u\ge 1$ and $m=2^u$ to obtainTaking $u=\lceil {\log }_2(1+1/(2\epsilon ))\rceil$ makes the right side at most $\epsilon$. This adds only $O(\log (1/\epsilon ))$ control qubits. Efficient QFT is not by itself a guarantee of efficient controlled powers of an arbitrary $U$: implementing them by repeated oracle calls uses $L-1$ calls. The modular-arithmetic application has efficient powers, as follows.

Assume $n>1$ and $\gcd (x,n)=1$, and let $r$ be the multiplicative order of $x$ modulo $n$. Define the unitary operator $U_x|y⟩=|xy\mathrm{mod}n⟩$ on $0\le y<n$, and extend it as the identity on unused computational-basis labels of the binary register. Coprimality makes multiplication a permutation, so this extension really is unitary. The orbit of $|1⟩$ consists of the $r$ distinct states $|x^j\mathrm{mod}n⟩$. Its modular multiplication eigenstates areThe last relation follows by shifting the index $j$ cyclically; orthogonality follows from the finite Fourier sum. We do not need to know $r$ to prepare one of these eigenstates: the readily prepared target obeysRunning quantum phase estimation on this state produces the mixture of the $r$ eigenphase distributions, each with weight $1/r$, because the target eigenstates are orthogonal. Thus it samples a uniformly random phase label $s$ and estimates $s/r$ with the bounds just proved. Equivalently the state before the inverse QFT is $L^{-1/2}{\sum }_a|a⟩|x^a\mathrm{mod}n⟩$, which is obtained by quantum modular exponentiation directly.

The controlled power $U_x^{2^j}$ multiplies by $x^{2^j}\mathrm{mod}n$, whose constant is computed by repeated squaring. Under the assumed efficient modular exponentiation, these controlled multiplications and the QFT use a number of gates polynomial in the register lengths. Taking $L>n^2$ requires only $O(\log n)$ phase qubits. The nearest-label event has probability at least $4/{\pi }^2$ and yields an estimate within $1/(2L)<1/(2r^2)$ of $s/r$. Since $r<n$, continued-fraction recovery in quantum order finding then identifies the reduced fraction $s/r$. The denominator is $r/\gcd (s,r)$, not necessarily $r$: when $s$ and $r$ are coprime it is the desired order, and when they are not it is only a divisor. One may test candidate denominators using modular exponentiation and repeat with fresh samples; denominators from successful samples can also be combined by a least common multiple. The probability of a nearest-label sample with $s$ coprime to $r$ is at least $(4/{\pi }^2)\phi (r)/r$. These qualifications explain exactly what the phase estimate yields without falsely assuming that the unknown order or an eigenstate was available at the start.

Write $C_U=|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes U$ for the controlled unitary gate. For a normalized eigenvector $|u⟩$, the first Hadamard gate and quantum phase kickback giveThe final Hadamard gate therefore produces the unentangled outputThe auxiliary system is unchanged, while its eigenphase becomes accessible through interference of the control qubit. The special unitary group assumption is not needed for this calculation; unitarity and the normalized eigenvector suffice.

Label the control qubits by binary weight: the bit $x_n$ contributes $2^n$ to $x={\sum }_{n=0}^{N-1}{2}^n{x}_n$. For each $n$, use that qubit as the control of the supplied controlled-$V^{2^n}$, with the same target eigenstate $|v_j⟩$. The controlled unitary gate acts bysince $V^{2^n}|v_j⟩=e^{i{2}^n{\varphi }_j}|v_j⟩$. The target remains unchanged after every application. Multiplying these factors givesThe ordering of the tensor factors is chosen to match the binary place values. Discarding the unchanged target leaves the required phase register. This uses quantum phase kickback in the phase accumulation step of quantum phase estimation.

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.

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.

Apply $V^{-1}$ to the data and phase quantum registers, leaving the flag quantum ancilla untouched. This inverse needs no extra oracle assumption: the promised dyadic eigenvalues give $U^{2^n}=I$, hence $U^{-1}=U^{2^n-1}$. The inverse of each controlled unitary gate used in $V$ can therefore be built from repeated uses of the supplied controlled-$U$, and the known Hadamard gates and quantum Fourier transform gates can be reversed. Uncomputation is necessary to erase the eigenvalue label coherently. The resulting quantum state isA quantum measurement in the computational basis of the flag followed by postselection on one yieldsThis requires $A|b⟩\ne 0$. For a normalized input and nonnegative eigenvalues, the success probability of positive quantum spectral filtering satisfies $P_{\mathrm{success}}\ge {\lambda }_{\min }^2$. In the general inequality, equality holds precisely when the input is supported on the minimum-eigenvalue eigenspace. Omitting uncomputation and discarding the phase quantum register would instead leave a mixed state with diagonal weights proportional to $|{\beta }_j{|}^2{\lambda }_j^2$, rather than the desired coherent pure state.

The printed universal nonzero-success request needs a nonkernel-input hypothesis. An $n$-qubit Hermitian operator has $2^n$ eigenvalues, counted with multiplicity. All are distinct, and the printed dyadic grid contains exactly $2^n$ possible values. They therefore occupy the entire grid, including zero: this is a multiplicity-free complete dyadic spectrum, and ${\lambda }_{\min }=0$. Taking $n=1$, $A=\mathrm{diag}(0,1/2)$, and $|b⟩=|0⟩$ satisfies every printed spectral promise but gives $A|b⟩=0$. No normalized output vector exists, so no algorithm can deliver it with nonzero probability.

For every input outside the kernel, the procedure above has $P_{\mathrm{success}}>0={\lambda }_{\min }^2$, giving the requested strict bound on the meaningful domain. The corrected result is therefore exact quantum spectral filtering conditional on $A|b⟩\ne 0$, with the boxed probability. This does not require knowing the input probability amplitudes or making extra copies of an unknown quantum state. Arbitrarily small nonzero support outside the kernel gives arbitrarily small success probability, and a failed flag measurement disturbs the input; fresh independent trials cannot be assumed when only one unknown physical input is supplied.

Use a reversible circuit $T$ to compute an $L=O(n)$-bit representation of the angle into a workspace register, with all additional work bits retained:Write that representation as ${\theta }_x={\sum }_{l=1}^L{b}_l(x){\alpha }_l$, with known binary place values ${\alpha }_l$ (including the fixed scale and any integer bit). On the target, apply a controlled unitary gate $R_y(2{\alpha }_l)$ controlled by each angle bit $b_l$. Rotations about the same axis add their angles, so their product isFinally apply $T^{†}$ to perform uncomputation. The workspace returns to zero while the control register and rotated target remain unchanged; the construction works coherently on every superposition of $x$.

A polynomial time classical calculation has a polynomial-size reversible circuit with Toffoli gates, and each Toffoli gate has a constant-size decomposition into one-qubit and two-qubit gates. The $L$ controlled rotations are themselves two-qubit gates. Thus the total quantum circuit size is $\mathrm{poly}(n)$. This is the binary-angle implementation of a quantum variable rotation; the stipulated angle precision is understood.

After the first Hadamard gate and the controlled unitary gate, the state isThe final Hadamard gate givesHence the Hadamard test returns one with probabilityIf $U|\psi ⟩=|\psi ⟩$, then $\theta =0$ and the outcome is zero with certainty. If $U|\psi ⟩=-|\psi ⟩$, then $\theta =\pi$ modulo $2\pi$ and the outcome is one with certainty. The single measurement therefore distinguishes the two promised cases exactly.

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}$.

Choose the Pauli matrices with ${\sigma }_z=\mathrm{diag}(1,-1)$, and let $\omega >0$ be an angular frequency. The computational basis is an orthonormal basis of energy eigenstates for the qubit Hamiltonian operatorIn this convention $|1⟩$ is the lower energy eigenstate; the labels describe a basis choice, not a universal ground state/excited state ordering. Start in the Hadamard basis pure state $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$. ThenThe first factor in the second expression is a global phase. The ratio of the two probability amplitudes has relative quantum phase $\omega t$, so its sign follows directly from $E_1-E_0=-\hslash \omega$.

Multiplying this density matrix by each Pauli matrix and taking its trace gives the Bloch vector:The Bloch vector travels counterclockwise around the equator of the Bloch sphere, from $+x$ toward $+y$ when viewed from $+z$. A computational-basis measurement always has $P_Z(0)=P_Z(1)=1/2$, while the Hadamard basis and ${\sigma }_y$ eigenbasis measurements giveAt $\omega t=\pi /2$, the quantum state is $|+i⟩=(|0⟩+i|1⟩)/\sqrt{2}$ up to a global phase, giving $P_Y(+)=1$. At $\omega t=\pi$, it is $|-⟩$ up to a global phase, giving $P_X(+)=0$. Both retain equal energy measurement probabilities.

At $t=2\pi /\omega$, the time-evolution operator is $U(t)=-I$, so $|\psi (t)⟩=-|+⟩$. The physical quantum state ray, its density operator, and every measurement's probabilities have returned. The representative vector returns exactly only at $t=4\pi /\omega$, when $U(t)=I$. The minus sign is a global phase for this isolated evolution; comparing an evolved branch with an unevolved branch through a controlled unitary gate can make it a relative quantum phase, as explained in global phase of an uncontrolled quantum gate is unobservable.