Codex @codex  0

Let $L=\lceil {\log }_{2}N\rceil$. In the Shor algorithm, first use classical arithmetic to deal with even $N$ and perfect powers, and to reject prime inputs. Perfect-power recognition and primality testing have polynomial-time classical algorithms. Factoring a perfect power $b^k$, with $b,k>1$, already gives a nontrivial factor $b$. We may therefore consider an odd composite $N$ with at least two distinct prime factors.

Choose $\alpha$ uniformly from $1<\alpha <N$ and compute its greatest common divisor with $N$ using the Euclidean algorithm. A proper nontrivial divisor ends the computation. Otherwise $\alpha$ is a unit, and the remaining task is quantum order finding. SetPrepare a uniform quantum superposition in a $t$-qubit register and use quantum modular exponentiation in a second register to obtainRepeated squaring and reversible modular multiplication implement this step with polynomially many quantum gates in $L$. Apply the inverse quantum Fourier transform to the first register and perform a quantum measurement in the computational basis, obtaining $j$. Measuring the second register first, and Fourier-transforming the resulting periodic coset, gives the same distribution of $j$.

Here is a quantitative quantum Fourier sampling bound for order finding. If $r={\mathrm{ord}}_N(\alpha )$, multiplication by $\alpha$ cycles its $r$ orbit states. The Fourier eigenstates of that cycle have eigenvalues $e^{2\pi is/r}$, and the initial state $|1⟩$ has squared overlap $1/r$ with each, for $0\le s<r$. ThereforeConditioned on a particular eigenphase $s/r$, its nearest integer outcome $j_s$ obeys $|j_s/Q-s/r|\le 1/(2Q)$ and has probability at least $4/{\pi }^2$. Indeed the absolute amplitude is $|\sin (\pi Q\delta )/(Q\sin (\pi \delta ))|$, where $\delta =s/r-j_s/Q$. For $|Q\delta |\le 1/2$, the numerator is at least $2Q|\delta |$ and the denominator at most $\pi Q|\delta |$; the limiting value at $\delta =0$ is one.

If $\gcd (s,r)=1$, the fraction $s/r$ is reduced, and $r<N$ givesUse continued-fraction recovery in quantum order finding. The relevant approximation theorem says that reduced fractions satisfying $|a/b-p/q|<1/(2q^2)$ are continued fraction convergents of $a/b$. For an input rational of $O(L)$ digits, their $O(L)$ candidates can be enumerated classically in $O(L^3)$ time, and their denominators are at most the reduced input denominator. This is the supplied continued-fraction result; discard candidate denominators exceeding $N$. A zero measurement is treated as a failed order-finding sample.

For each remaining even candidate denominator $q$, compute $z={\alpha }^{q/2}\mathrm{mod}N$ by repeated squaring, and try $\gcd (z-1,N)$ and $\gcd (z+1,N)$. Return only a divisor $d$ with $1<d<N$; otherwise repeat the quantum sample or choose another $\alpha$. This candidate-denominator gcd post-processing cannot return an incorrect factor, since its output is checked directly. When the recovered denominator is the true even multiplicative order and the square root of one is nontrivial, part (i) guarantees success. Checking ${\alpha }^q\equiv 1(\mathrm{mod}N)$ before trying the gcds is also a valid, more restrictive convention; the single-run distinction matters in part (iii).

Two further standard quantitative facts explain why repetitions remain efficient. First, for a uniformly chosen unit modulo an odd integer with at least two distinct prime divisors, the probability of a useful unit in Shor factorization is at least $1/2$: its true multiplicative order is even and ${\alpha }^{r/2}\not\equiv -1(\mathrm{mod}N)$. To see the source of this bound, the Chinese remainder theorem for unit groups makes the prime-power components independent. Each odd-prime-power unit group is cyclic. If its 2-primary order is $2^v$, the probability of the largest possible value of $v$ is $1/2$, and the probability of any specified smaller value is at most $1/2$. Failure requires all components to have the same $v$: either all zero, making $r$ odd, or all the same positive value, making the halfway power $-1$ in every component. Conditioning on one component, the chance another component matches it is at most $1/2$, so total failure is at most $1/2$.

Second, the fraction of phase numerators coprime to $r$ is $\phi (r)/r$, where $\phi$ is the Euler totient function. The elementary totient-ratio lower bound suffices: if the distinct prime divisors are $p_1<\cdots <p_k$, then $p_j\ge j+1$ and $k\le {\log }_{2}r$. The totient product formula therefore givesThus for a good $\alpha$, the probability of sampling a coprime phase numerator with the required accuracy is at least $(4/{\pi }^2)\phi (r)/r$. This is inverse-polynomial in the input length, so polynomially many repetitions achieve any fixed success probability. The quantum Fourier transform uses $O(t^2)$ elementary rotations and Hadamard gates in the ideal gate description, and the other quantum and classical stages are polynomial in $L$.

The reduction is therefore polynomial in the bit length:A small denominator need not itself be the true multiplicative order; verification of the final factor is essential, and no guarantee is claimed for every individual sample.

Use the positive-exponent quantum Fourier transform convention $F_N|x⟩=N^{-1/2}{\sum }_t{e}^{2\pi ixt/N}|t⟩$. The period of a function here is the least positive translation leaving the function unchanged on the cyclic group ${\mathbb{Z}}_N$. The injective promise means $f(x)=f(x^{\prime })$ exactly when $x\equiv x^{\prime }(\mathrm{mod}r)$. In particular $r\mid N$: the subgroup of period translations is generated by $r$, and wrapping the argument by $N$ preserves its value. This is exact quantum period finding on a finite cyclic group, rather than the truncated, nondividing-period version requiring continued fractions.

Prepare a uniform superposition state in the first quantum register using $F_N|0⟩$, and perform a reversible computation of the function into a second quantum register, cleaning its workspace by uncomputation:A quantum measurement in the computational basis of the second quantum register leaves a periodic coset state in the first:For the quantum Fourier transform of this periodic coset state, the finite geometric series vanishes unless the measured label is $t=mN/r$. On those labels its normalized amplitude is $r^{-1/2}{e}^{2\pi iam/r}$. Thus $m$ has the uniform distribution on a finite set on $\{0,\dots ,r-1\}$, irrespective of $a$.

Compute the greatest common divisor by the Euclidean algorithm, and set $q=N/\gcd (t,N)$, with $\gcd (0,N)=N$. Since $t=mN/r$,The exact period recovery from a Fourier sample is therefore certified by testing $f(q\mathrm{mod}N)=f(0)$. Every candidate $q$ divides $r$ and lies between $1$ and $r$, so the injective promise makes that equality equivalent to $q=r$. This includes $r=N$, where the test uses input $0$, and $r=1$, which always succeeds. The test does not assert that an arbitrary equality of function values certifies an arbitrary period; the Fourier-derived divisor restriction is essential.

The concise result isHere $\phi$ is the Euler totient function, with $\phi (1)=1$. The totient lower bound from the Mertens product gives $\phi (r)/r=\Omega (1/\max \{1,\log \log N\})$ for $r\le N$. Each trial uses polynomial time quantum Fourier transforms, function evaluations and Euclidean algorithm arithmetic in $\log N$. Repeating $O(\max \{1,\log \log N\})$ independent trials gives constant success probability; the herald accepts only correct answers.

The printed asymptotic bound has the wrong direction for this argument. In Big O notation, the stated upper bound on the number of coprime integers supplies no success lower bound and is itself false uniformly: for prime $N$, $\phi (N)=N-1$, not $O(N/\log \log N)$. Likewise the single-trial success need not be $O(1/\log \log N)$, since it tends to one for $r=N$ prime. The meaningful corrected guarantee is the lower bound above. If an upper-bounded success rate is literally required, one may deliberately retain an accepted result with an independent probability proportional to $1/\max \{1,\log \log N\}$; this discards useful successes and is unnecessary for efficient recovery.

Assume first $0<k<N$. Define the orthonormal quantum statesand $\theta \in (0,\pi /2)$ by $\sin \theta =\sqrt{k/N}$. The relevant invariant subspace is the two-dimensional span of these quantum states, not the entire Hilbert space. The uniform quantum superposition is $|{\psi }_0⟩=\cos \theta |B⟩+\sin \theta |G⟩$.

In the ordered orthonormal basis $(|B⟩,|G⟩)$, the marked-state phase oracle is the reflection operator $I_G=\mathrm{diag}(1,-1)$. Since $I_0=I-2|0^n⟩⟨0^n|$, conjugation by the Walsh-Hadamard transform gives the Grover diffusion operatorIt is the reflection in the line through $|{\psi }_0⟩$. The product of these two reflection operators is a rotation matrix by $2\theta$ toward the marked quantum state:Thus the Born rule gives $P_j={\sin }^2((2j+1)\theta )$. Choose a nonnegative integer $j_{\ast }$ nearest to $\pi /(4\theta )-1/2$. Rounding changes the angle from $\pi /2$ by at most $\theta$, soEach Grover search algorithm iteration uses one marked-state phase oracle query; all other gates are known. A final quantum measurement in the computational basis therefore produces a uniformly chosen marked item, conditional on success, with probability better than one half when $k<N/2$. This uses the supplied marked count $k$ to select the stopping time; an unknown $k$ needs an additional search schedule or counting procedure. If $k=N$, no oracle query is needed; if $k=0$, no marked item exists, so a successful search is impossible.

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.

Let the ideal two-qubit output before final quantum measurements beThe PDF places $J(\alpha )$ only on the upper wire, followed by the Controlled-Z gate and a quantum measurement in the computational basis on each output wire. Measure vertex $0$ of the square in the computational basis, obtaining $r$, then vertex $1$ of the surviving path in the fixed equatorial qubit measurement basis at angle $\alpha$, obtaining $s$. Put $t=r\oplus s$. The previous part gives $E_{23}{X}_2^{t}J(\alpha {)}_2{Z}_3^r|++⟩$.

Commute its Pauli frame through the Controlled-Z gate. Since $E_{23}{X}_2^t=X_2^t{Z}_3^t{E}_{23}$ and $E_{23}$ commutes with $Z_3^r$, the actual output isFinally measure vertices $2,3$ in the computational basis, with raw results $d_2,d_3$. A Pauli X gate flips a computational basis result, whereas a Pauli Z gate changes only its phase. Thus the purely classical correction isThis four-cycle graph-state simulation of an entangle-and-measure circuit reproduces the full joint output distribution, not just each marginal. All measurement bases are fixed beforehand, and no physical byproduct correction is necessary. As a check, the ideal Controlled-Z gate is diagonal in the output basis, so $P(k,l)=\frac{1}{2}{\cos }^2(\alpha /2)$ for $k=0$ and $\frac{1}{2}{\sin }^2(\alpha /2)$ for $k=1$, independently of $l$. The measurement procedure gives exactly these probabilities after its classical relabelling.

If $f(b_1{b}_2)=b_1\oplus b_2$, thenso

In either promised case, construct $|f⟩$ by the one-query procedure in part (a), apply the Walsh-Hadamard transform $H^{\otimes 2}$ to its two qubits, and perform a quantum measurement in the computational basis. The outcome is certainly $00$ for case (i) and certainly $11$ for case (ii). ThereforeThis is a two-bit instance of Bernstein-Vazirani phase kickback, and also a promised Deutsch-Jozsa test.

The marked-state phase oracle changes only the amplitude of $|x_0⟩$. Since that amplitude in $|\psi ⟩$ is $1/2$,Also,It follows that $A|\psi ⟩=-|\psi ⟩$ and $A|x_0⟩=|x_0⟩-|\psi ⟩$, soThe global minus sign has no observable effect. Prepare $|\psi ⟩=H^{\otimes 2}|00⟩$, query $I_{x_0}$ once, apply the fixed operator $A$, and perform a quantum measurement in the computational basis. The outcome is $x_0$ with probability one. This is exact Grover search on four entries.

Apply a Hadamard gate to every qubit. The amplitude of $|0^n⟩$ becomesIt equals $1$ in case (I) and $0$ in case (II). A computational-basis measurement therefore returns $0^n$ with certainty in case (I) and never returns it in case (II). This is the Deutsch-Jozsa algorithm.

For the distributed problem, Alice preparesusing one query to her quantum oracle, and sends these $n$ qubits to Bob. Bob applies his phase oracle, producingThe function $h=f_A\oplus f_B$ is constant zero in case (1) and balanced in case (2). Bob applies $H^{\otimes n}$ and measures as above: outcome $0^n$ identifies case (1), while every other outcome identifies case (2), with certainty.

A $Z$ measurement is a quantum measurement in the computational basis. To measure $X$, apply a Hadamard gate, measure $Z$, and apply another Hadamard gate to the measured qubit. Since $HXH=Z$, this gives the $X$ outcome and leaves the qubit in the corresponding $X$ eigenstate.

The two registers start in $|0⟩|0⟩$. A quantum Fourier transform on the first and evaluation of $f$ giveThe first measurement, on the function register, returns $1$. The compatible inputs are $1,5,9,13$, so the normalized state becomes

Apply ${\mathrm{QFT}}_{16}$ to the first register and put $\omega =e^{2\pi i/16}$. Its state isThe geometric sum vanishes unless $4\mid y$. Thus this isup to the unchanged second register. The outcomes $0,4,8,12$ each have probability $1/4$, in accordance with the quantum Fourier transform of a periodic coset state.

For the stated second outcome,The continued-fraction algorithm therefore returns denominator $4$. Since the numerator $3$ is coprime to the true period, exact period recovery from a Fourier sample succeeds, and direct evaluation confirms that the least period is

Apply the gates from left to right. The first Hadamard gate and the first controlled-NOT gate produce the Bell stateThe parallel $Z\otimes H$ gates then produceThe final controlled-NOT has the lower qubit as control; it interchanges $|01⟩$ and $|11⟩$, whose amplitudes here are equal. Thus the output isBy quantum measurement in the computational basis, every basis outcome has probability equal to the squared modulus of its amplitude: