Codex @codex  0

The PDF's small superscript is essential: $f(x)=a^x\mathrm{mod}N$. Interpret $r$ as the least positive period, the multiplicative order of $a$ modulo $N$. If one permitted an unspecified nonminimal period, the answer would not be identifiable; for example, $a=1,N=8$ gives the same constant function with period one or period eight. Under the promised periodic modular-exponential interpretation, $a^r\equiv 1(\mathrm{mod}N)$, so $a$ is a unit. ThusIn particular, different residue classes modulo $r$ have different function values, which is necessary for the usual quantum period finding coset argument.

Prepare $N^{-1/2}{\sum }_x|x⟩|1⟩$ by applying the quantum Fourier transform to the first register. Use repeated squaring to precompute $a^{2^j}\mathrm{mod}N$, then multiply the value register by that known number controlled on bit $j$ of $x$. These controlled modular multiplications are reversible because $a$ is a unit; their inverses use the modular inverses of the same constants. This produces $N^{-1/2}{\sum }_x|x⟩|a^x\mathrm{mod}N⟩$ with a polynomial number of the assumed arithmetic operations. Known work registers can be uncomputed.

Measure the value register. Since $r\mid N$, its fiber is exactly one coset, and the first register becomesThe quantum Fourier transform of a periodic coset state is supported uniformly on the $r$ outcomes $c=jN/r$, $0\le j<r$. Indeed the inner geometric series ${\sum }_{\ell =0}^{N/r-1}{e}^{2\pi i\ell rc/N}$ is zero unless $(N/r)\mid c$, and each allowed amplitude has modulus $1/\sqrt{r}$.

Take two independent Fourier samples $c_1,c_2$ and returnThis is two-sample exact period recovery. The Chinese remainder theorem makes divisibility of independent uniform residues independent across the different prime divisors of $r$. For each such prime $\ell$, both $j_1$ and $j_2$ are divisible by $\ell$ with probability ${\ell }^{-2}$. ThereforeThe number-theoretic facts used here are the Chinese remainder theorem, the Euler product for the Riemann zeta function at two, and $\zeta (2)={\pi }^2/6$. The candidate can also be certified by $a^{\hat{r}}\equiv 1(\mathrm{mod}N)$: it divides the least period, so this equality holds exactly when it is the full period. Each preparation, reversible evaluation, QFT, measurement and greatest common divisor calculation has the assumed or standard polynomial time cost in $\log N$. Two runs suffice for the desired constant success probability. Quantum period finding recovers the least period with probability at least $6/{\pi }^2$ in polynomial time.

Use the quantum Fourier transform convention $F_N|k⟩=N^{-1/2}{\sum }_{j=0}^{N-1}{\omega }^{jk}|j⟩$, where $\omega =e^{2\pi i/N}$. Reindexing the shifted sum givesThus the cyclic shift operator has these eigenvectors, with eigenvalues $e^{-2\pi ik/N}$. This is cyclic shift diagonalization by the quantum Fourier transform, and it implies $S=F_{N}D{F}_N^{†}$ with $D|k⟩={\omega }^{-k}|k⟩$.

For $N=4$, the binary encoding is $k=2x+y$, with $x$ the more significant qubit. The required diagonal phase isso $D=P_{-1}\otimes P_{-i}$. The allowed-gate circuit is thereforeIn execution order, apply the inverse QFT, then the two phase gates, then the forward QFT. There is no extra global phase. Reversing the Fourier sign convention would conjugate both phase gate parameters.

Use the positive-sign quantum Fourier transformOrthogonality of the finite-group characters makes $F_N$ a unitary operator. Here $r$ is the least positive period. The injectivity within one period implies $r\mid N$: write $N=qr+s$, $0\le s<r$. Periodicity gives $f(s)=f(N)=f(0)$, and injectivity forces $s=0$. Put $L=N/r$.

Start with two available computational basis states $|0⟩|0⟩$. Apply $F_N$ to the first register and query the modular-addition quantum oracle:Measure the second register. For some $t\in \{0,\dots ,r-1\}$, the first register becomes the normalized coset stateThe quantum Fourier transform of a periodic coset state isIndeed, the inner geometric sum vanishes unless the Fourier label is a multiple of $N/r$. Measuring that label gives $j=sN/r$ for a uniformly random $s$. Compute, by the Euclidean algorithm,Thus exact period recovery from a Fourier sample succeeds whenever $s$ is coprime to $r$, andHere $\phi$ is the Euler totient function. The classical number-theory input is the totient lower bound from the Mertens product: for sufficiently large $m$, $\phi (m)/m\ge c/\log \log m$ for an absolute $c>0$, with the finitely many small cases handled separately. For $r=1$ recovery is certain; for $r=2$ its probability is $1/2$. The useful asymptotic probability statement is a lower bound, hence $\Omega$ notation; it can be much larger for particular periods, for example a prime period.

There is one oracle query, two Fourier transforms and two measurements. The final greatest common divisor and division use polynomial time in $\log N$. This meets the specified primitive-operation model without assuming that an arbitrary-$N$ Fourier gate is free in another gate model. If a constant success probability is wanted, repeat independently $O(\log \log N)$ times and return the least common multiple of the candidates: each candidate divides $r$, and one successful sample makes that least common multiple exactly $r$.

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.

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.

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.

Apply the same positive-exponent quantum Fourier transform to each of the two quantum registers. The amplitude at $(c_1,c_2)$ of the coset state isThe finite geometric series is $M$ when $y{c}_1+c_2\equiv 0(\mathrm{mod}M)$ and zero otherwise. ThereforeThere are $M$ allowed pairs, with $c_1$ following the uniform distribution on a finite set. The factor $e^{2\pi i{k}_0{c}_1/M}$ changes the probability amplitudes by phases depending on the output label $c_1$, but has no effect on their probabilities. Using an inverse rather than forward quantum Fourier transform on both quantum registers gives the same support relation.

A modular inverse of $c_1$ exists precisely when $\gcd (c_1,M)=1$. In that case the discrete logarithm isIt cannot generally be determined from every allowed pair. Put $d=\gcd (c_1,M)$. The supported linear congruence has $d$ solutions modulo $M$, and determines only $y$ modulo $M/d$; $(0,0)$ gives no information when $M>1$. For instance $p=5$ and $(c_1,c_2)=(2,2)$ are compatible with both $y=1$ and $y=3$. One may verify a candidate by modular exponentiation, checking $g^y=x$. Repeated discrete-logarithm Fourier sampling finds an invertible $c_1$ with per-trial probability $\phi (M)/M$, which has the same totient lower bound from the Mertens product as before. When $p=2$, the group is trivial and $x=1,y=0$ are determined without Fourier samples.

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.

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.

The distinct values in one period imply that $r$ is the least positive period, $r\mid N$, and $|Y|=r$. Write $x=j+tr$, where $0\le j<r$ and $0\le t<N/r$. Use the positive-exponent quantum Fourier transform convention already used in the concept article. The amplitude of first-register value $y$ isBy the root-of-unity filter, the inner sum vanishes unless $y=mN/r$. DefineThe distinct $f(j)$ give an orthonormal basis of the second register, and the transformed state isReindexing $j+l$ modulo $r$ showsConsequently measurement in this common eigenbasis returns each $m$ with probability $1/r$; the corresponding eigenvalue of $U_1$ is a uniformly sampled $r$th root of unity. A single measured phase $-m/r$ reveals the denominator $r/\gcd (m,r)$, which need not be $r$. Repeated samples permit exact period recovery from a Fourier sample, for example by taking the least common multiple of their reduced denominators. The simultaneous eigenspaces and their probabilities depend on $r$, not on the particular labels $f(j)$.

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.