Codex @codex  0

After continued-fraction recovery in quantum order finding, an even candidate denominator $q$ can be used to try the displayed greatest common divisors. Return only a divisor strictly between one and $N$. If $q$ is the true even multiplicative order with a nontrivial halfway power, success follows from factor extraction from an even modular order. A candidate that is not a period can occasionally still yield a factor; testing $a^q\equiv 1$ before the gcds therefore changes single-run success probabilities. The output-factor check guarantees correctness in either convention.

For $\gcd (x,n)=1$ and order $r$, multiplication by $x$ modulo $n$ is a unitary operator. On the orbit of one it cyclically permutes $r$ basis states. The displayed orthonormal eigenstates have eigenvalues $e^{2\pi is/r}$, and $|1⟩=r^{-1/2}{\sum }_s|u_s⟩$. Thus quantum phase estimation on this efficiently prepared state samples a uniform $s$ without knowing $r$. Controlled powers are implemented by quantum modular exponentiation. Sufficient phase resolution allows continued-fraction recovery in quantum order finding; the reduced denominator equals $r$ only when $s$ is coprime to $r$.

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.

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.

Here the true multiplicative order is four, and it divides every power-of-two Fourier-register size $Q\ge 4$, including the $Q=256$ choice from part (ii). A second-register measurement produces one of the four periodic cosetsIts quantum Fourier transform has nonzero amplitudes only at $j=0,Q/4,Q/2,3Q/4$, and each has squared modulus $1/4$. The inverse transform only changes phases or permutes these four labels. Hence the measured ratios $0,1/4,1/2,3/4$ are equally likely.

For $1/4$ or $3/4$, continued-fraction recovery in quantum order finding returns denominator four. Part (i) then gives factors three and five. For $1/2$, the reduced denominator is two. Although two is not a period, the candidate-denominator gcd post-processing in part (ii) still gives a factor:The zero outcome produces no useful even candidate and the run fails. For the factor-extraction procedure specified above, three of the four outcomes succeed:There is an important convention behind this answer. A version that rejects a candidate unless $7^q\equiv 1(\mathrm{mod}15)$ before attempting any gcd rejects $q=2$, since $7^2\equiv 4$. Under that validated-period convention only the two odd-numerator phases succeed, givingThus the probability of recovering the true multiplicative order is $1/2$, whereas the probability of finding a factor with direct gcd post-processing is $3/4$. The printed question does not specify this classical post-processing detail; stating it avoids identifying these two different events.

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.

Choose a power of two $M$ withSince the multiplicative order $r$ is less than $N$, this guarantees $M\ge r^2$. Prepare two quantum registers in the stateand use quantum modular exponentiation to obtain

Measure the second register. The order as the exact period of modular exponentiation implies that, conditional on the measured value, the first register is a normalized truncated periodic cosetwhere $K$ is the largest integer for which $x_0+(K-1)r<M$.

Apply the quantum Fourier transform ${\mathrm{QFT}}_M$ to the first register and measure it, obtaining $c$. The supplied Fourier-transform theorem states that, with probability of order $1/\log \log r$, $c$ is an integer nearest to $jM/r$ for some $j$ coprime to $r$. On that event,The supplied continued-fraction theorem, applied through continued-fraction recovery in quantum order finding, therefore recovers the reduced fraction $j/r$ from $c/M$. Because $j$ and $r$ are coprime, its denominator is the exact order $r$. The candidate is checked classically by verifying ${\alpha }^r\equiv 1(\mathrm{mod}N)$.

The quantum Fourier transform, quantum modular exponentiation, continued-fraction algorithm, and final modular check all take polynomial time in $\log N$. Since $r<N$, the successful event has probability of order $1/\log \log N$, as required.

The quantum Fourier transform measurement supplies a rational approximationwhere $r$ is the desired multiplicative order. HereIts reduced continued fraction convergent has denominator two, so continued-fraction recovery in quantum order finding proposes $r=2$. Direct order verification from divisors confirms it:HenceAs a check, the classical final step of the Shor algorithm gives

The input size of an integer factorization problem is its number of bits $n\simeq {\log }_{2}N$. Trial division up to $\sqrt{N}$ is exponential in $n$; advanced classical algorithms do substantially better, but no general polynomial-time classical factoring algorithm is known. The heuristic general-purpose general number field sieve has subexponential rather than polynomial scaling, roughly $\exp (O(n^{1/3}(\log n{)}^{2/3}))$. This describes known algorithmic performance, not a proof that efficient classical factoring is impossible or that every large integer is difficult.

Choose $a$ with $1<a<N$. A nontrivial greatest common divisor $\gcd (a,N)$ already supplies a factor; otherwise find the multiplicative order $r$ of $a$ modulo $N$. If $r$ is even and $a^{r/2}\not\equiv -1(\mathrm{mod}N)$, thenMinimality of the order also excludes $a^{r/2}\equiv 1(\mathrm{mod}N)$, so factor extraction from an even modular order gives nontrivial factors through $\gcd (a^{r/2}\pm 1,N)$. Unhelpful choices of $a$ or odd orders require another trial. For $N=15$, $a=2$ has successive residues $1,2,4,8$ and order four, givingComputing the powers is easy by repeated squaring; discovering a large order is the step accelerated by Shor's algorithm.^[ref]

Put $Q=2^L$ and suppose $Q\ge r$. For each residue class $s=0,\dots ,r-1$, letThese are normalized uniform superpositions of the arguments with the same modular-exponentiation value. Their amplitudes repeat at separation $r$ within the finite register window. Exact cyclic periodicity requires $r\mid Q$. The correctly normalized entangled register state isThe equal prefactor $1/\sqrt{r}$ in the displayed algorithm is exact when $r\mid Q$, for then every $n_s=Q/r$. It is not generally exact for an arbitrary unknown order. A physical implementation uses quantum modular exponentiation as a reversible map; its specified action on second-register input zero is extended to a unitary operator on the whole register space.

For the illustrative $N=15$, $a=2$ and $Q=16$, the four first-register states areApplying the positive-sign quantum Fourier transform to the general state givesThe bracket is a finite geometric Fourier amplitude. If $r\mid Q$, it vanishes unless $k=\ell Q/r$ for $\ell =0,\dots ,r-1$, when it equals $Q/r$. HenceThe second-register states are orthogonal, so their different phases do not change the marginal first-register probabilities. Measurement givesIn the $Q=16$ example the possible outcomes are $0,4,8,12$. A nonzero observed ratio $k/Q$ estimates $\ell /r$, not a prime factor directly. Reducing it gives denominator $r/\gcd (\ell ,r)$; repeating avoids uninformative outcomes or recovers missing order factors. For example, $k=4$ or $12$ gives denominator four, whereas $k=8$ alone gives only two.

When $r\nmid Q$, the Fourier probabilities have narrow peaks near $k/Q=\ell /r$ instead of support only on an exact reciprocal grid. The general marginal distribution isChoosing $Q\ge N^2$ supplies the usual precision for continued-fraction recovery in quantum order finding: a nearest grid sample differs from the target rational by at most $1/(2Q)<1/(2r^2)$. Candidate denominators and extracted divisors are checked classically, and repetitions provide useful samples. The small $Q=16$ example works exactly because its order divides the register size; it is not a general precision guarantee for factoring every four-bit integer.

A sufficiently large reliable quantum computer would undermine RSA by efficient factorization. The related discrete-logarithm algorithm also threatens Diffie-Hellman key exchange and elliptic-curve public-key schemes. This does not imply that every communication scheme or symmetric cipher is broken by the same algorithm; post-quantum cryptography studies alternatives based on other problems. The mathematical speedup assumes a scalable quantum computation with enough precision and error control, not merely a small demonstration of factoring fifteen.