The normalized input density operator is
A quantum measurement in the computational basis has projectors . Discarding its recorded outcome gives the dephasing channel
The original off-diagonal coherence disappears. If the outcome is retained instead, the conditional state is or and the record carries information about which occurred. Thus discarding the record is an essential part of this channel specification.
With the negative exponential convention of the specified quantum Fourier transform, the amplitude of computational outcome is
If , every summand is one. Otherwise this finite geometric series has ratio with , so it equals . Thus
The Born rule gives outcome with probability one when performing a quantum measurement in the computational basis. Recover the promised phase as modulo . Using the opposite Fourier sign would instead return the label , so the sign convention matters.
When , the first two qubits after the Boolean quantum oracle are . The Hadamard gate obeys for . Applying the Walsh-Hadamard transform therefore gives
Consequently the quantum measurement in the computational basis has the deterministic outcomes
These four distinct answers identify the four promised Boolean quantum oracles with one query and certainty. The constant term does not affect the measurement in quantum mechanics, because a global phase does not change its probabilities.
All four promised functions have . Use quadratic Boolean phase cancellation: apply a Controlled-Z gate to remove the phase , then apply the Walsh-Hadamard transform. With the rightmost gate acting first, choose
Because and the Controlled-Z gate commutes with the Pauli Z gates,
The quantum measurement in the computational basis consequently produces
Each answer occurs with probability one for its promised Boolean quantum oracle.
In the ordered computational basis , the first two qubits of have amplitudes , while those of have amplitudes . Both have the same normalized answer qubit . Their inner product is therefore
A common unitary operator preserves this nonzero inner product. To distinguish the alternatives with certainty using the prescribed quantum measurement in the computational basis, their first-register outcome supports would have to be disjoint: every outcome possible under one alternative must be impossible under the other. Vectors with disjoint computational basis supports have zero inner product, contradicting its preservation. Thus no such exists. This is also an instance of perfect discrimination of pure states requires orthogonality; allowing a more general measurement in quantum mechanics would not rescue this pair of states. The obstruction concerns these prepared oracle-output states, rather than every conceivable oracle-query procedure.
For , induction using the Grover rotation angle gives
The quantum measurement in the computational basis therefore returns with probability . Since , the first angle interval attaining the required success is
The first successful Grover iterate is consequently
Indeed, this is the first integer at or above the lower endpoint requirement . The inequality also implies , so this iterate cannot overshoot the first success interval. Every smaller nonnegative integer lies before that interval and fails the threshold. Finally, for , so
For the singleton case , measuring the initial state already returns with certainty, and . For , the requested threshold is only , so zero iterations already suffice. These boundary cases agree with the search guarantee.
Write and . The initial Hadamard gates prepare in the search register and in the final quantum ancilla. Since the Pauli X gate satisfies , the Boolean quantum oracle acts by quantum phase kickback:
For a single marked entry this is the marked-state phase oracle on the search register. The ancilla stays separate and unchanged throughout.
The Grover diffusion operator is , because . The PDF circuit places one diffusion after each oracle call, so the state before measurement is
In the supplied amplitude amplification theorem, take and . Their overlap has modulus , so the Grover rotation angle is . A quantum measurement in the computational basis therefore gives
The inverse sine here is applied to the overlap of the two different states. The converted TeX's self-overlap in the angle definition is a transcription error; the original PDF has .
First expand the result of the first gate in the computational basis:
Using and , this becomes
Apply and to obtain
For example, its quantum measurement in the computational basis has probabilities and , obtained by squaring the two basis amplitudes.
The inverse quantum Fourier transform in the original PDF has matrix elements multiplying . The converted TeX incorrectly repeats in the bra; using the actual PDF operator,
If , every summand of the inner sum is one, so it equals . If , let . Then and , and the finite geometric series gives . This is orthogonality of roots of unity. Hence
A quantum measurement in the computational basis consequently returns the integer with probability one.
Let . In the Shor algorithm, first use classical arithmetic to deal with even and perfect powers, and to reject prime inputs. Perfect-power recognition and primality testing have polynomial-time classical algorithms. Factoring a perfect power , with , already gives a nontrivial factor . We may therefore consider an odd composite with at least two distinct prime factors.
Choose uniformly from and compute its greatest common divisor with using the Euclidean algorithm. A proper nontrivial divisor ends the computation. Otherwise is a unit, and the remaining task is quantum order finding. Set
Prepare a uniform quantum superposition in a -qubit register and use quantum modular exponentiation in a second register to obtain
Repeated squaring and reversible modular multiplication implement this step with polynomially many quantum gates in . Apply the inverse quantum Fourier transform to the first register and perform a quantum measurement in the computational basis, obtaining . Measuring the second register first, and Fourier-transforming the resulting periodic coset, gives the same distribution of .
Here is a quantitative quantum Fourier sampling bound for order finding. If , multiplication by cycles its orbit states. The Fourier eigenstates of that cycle have eigenvalues , and the initial state has squared overlap with each, for . Therefore
Conditioned on a particular eigenphase , its nearest integer outcome obeys and has probability at least . Indeed the absolute amplitude is , where . For , the numerator is at least and the denominator at most ; the limiting value at is one.
If , the fraction is reduced, and gives
Use continued-fraction recovery in quantum order finding. The relevant approximation theorem says that reduced fractions satisfying are continued fraction convergents of . For an input rational of digits, their candidates can be enumerated classically in time, and their denominators are at most the reduced input denominator. This is the supplied continued-fraction result; discard candidate denominators exceeding . A zero measurement is treated as a failed order-finding sample.
For each remaining even candidate denominator , compute by repeated squaring, and try and . Return only a divisor with ; otherwise repeat the quantum sample or choose another . 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 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 : its true multiplicative order is even and . 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 , the probability of the largest possible value of is , and the probability of any specified smaller value is at most . Failure requires all components to have the same : either all zero, making odd, or all the same positive value, making the halfway power in every component. Conditioning on one component, the chance another component matches it is at most , so total failure is at most .
Second, the fraction of phase numerators coprime to is , where is the Euler totient function. The elementary totient-ratio lower bound suffices: if the distinct prime divisors are , then and . The totient product formula therefore gives
Thus for a good , the probability of sampling a coprime phase numerator with the required accuracy is at least . This is inverse-polynomial in the input length, so polynomially many repetitions achieve any fixed success probability. The quantum Fourier transform uses elementary rotations and Hadamard gates in the ideal gate description, and the other quantum and classical stages are polynomial in .
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 . The period of a function here is the least positive translation leaving the function unchanged on the cyclic group . The injective promise means exactly when . In particular : the subgroup of period translations is generated by , and wrapping the argument by 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 , 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 . On those labels its normalized amplitude is . Thus has the uniform distribution on a finite set on , irrespective of .
Compute the greatest common divisor by the Euclidean algorithm, and set , with . Since ,
The exact period recovery from a Fourier sample is therefore certified by testing . Every candidate divides and lies between and , so the injective promise makes that equality equivalent to . This includes , where the test uses input , and , 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 is
Here is the Euler totient function, with . The totient lower bound from the Mertens product gives for . Each trial uses polynomial time quantum Fourier transforms, function evaluations and Euclidean algorithm arithmetic in . Repeating 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 , , not . Likewise the single-trial success need not be , since it tends to one for 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 ; this discards useful successes and is unnecessary for efficient recovery.
Assume first . Define the orthonormal quantum states
and by . The relevant invariant subspace is the two-dimensional span of these quantum states, not the entire Hilbert space. The uniform quantum superposition is .
In the ordered orthonormal basis , the marked-state phase oracle is the reflection operator . Since , conjugation by the Walsh-Hadamard transform gives the Grover diffusion operator
It is the reflection in the line through . The product of these two reflection operators is a rotation matrix by toward the marked quantum state:
Thus the Born rule gives . Choose a nonnegative integer nearest to . Rounding changes the angle from by at most , so
Each 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 . This uses the supplied marked count to select the stopping time; an unknown needs an additional search schedule or counting procedure. If , no oracle query is needed; if , no marked item exists, so a successful search is impossible.
Use exact quantum phase estimation with control qubits initially and one target quantum register prepared in the given eigenvector . Apply Hadamard gates to the control qubits. If control bit has significance , apply a controlled unitary gate from that qubit to the target. The target stays in , while quantum phase kickback produces
Since , this is . The inverse quantum Fourier transform on the control quantum register therefore gives . The quantum measurement in the computational basis returns with certainty, so
The quantum circuit below reads left to right. The upper wires are control qubits, with 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- can implement controlled- by repetitions with the same control. Hence this exact quantum circuit uses calls to the supplied controlled-, unless controlled powers are additionally available cheaply. The cost of exact phase estimation on a dyadic spectrum is not automatically polynomial in ; 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 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 , hence . The inverse of each controlled unitary gate used in can therefore be built from repeated uses of the supplied controlled-, 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 is
A quantum measurement in the computational basis of the flag followed by postselection on one yields
This requires . For a normalized input and nonnegative eigenvalues, the success probability of positive quantum spectral filtering satisfies . 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 , rather than the desired coherent pure state.
The printed universal nonzero-success request needs a nonkernel-input hypothesis. An -qubit Hermitian operator has eigenvalues, counted with multiplicity. All are distinct, and the printed dyadic grid contains exactly possible values. They therefore occupy the entire grid, including zero: this is a multiplicity-free complete dyadic spectrum, and . Taking , , and satisfies every printed spectral promise but gives . No normalized output vector exists, so no algorithm can deliver it with nonzero probability.
For every input outside the kernel, the procedure above has , giving the requested strict bound on the meaningful domain. The corrected result is therefore exact quantum spectral filtering conditional on , 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 be
The PDF places 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 of the square in the computational basis, obtaining , then vertex of the surviving path in the fixed equatorial qubit measurement basis at angle , obtaining . Put . The previous part gives .
Commute its Pauli frame through the Controlled-Z gate. Since and commutes with , the actual output is
Finally measure vertices in the computational basis, with raw results . A Pauli X gate flips a computational basis result, whereas a Pauli Z gate changes only its phase. Thus the purely classical correction is
This 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 for and for , independently of . The measurement procedure gives exactly these probabilities after its classical relabelling.
If , then
so
In either promised case, construct by the one-query procedure in part (a), apply the Walsh-Hadamard transform to its two qubits, and perform a quantum measurement in the computational basis. The outcome is certainly for case (i) and certainly for case (ii). Therefore
This 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 . Since that amplitude in is ,
Also,
It follows that and , so
The global minus sign has no observable effect. Prepare , query once, apply the fixed operator , and perform a quantum measurement in the computational basis. The outcome is with probability one. This is exact Grover search on four entries.
Apply a Hadamard gate to every qubit. The amplitude of becomes
It equals in case (I) and in case (II). A computational-basis measurement therefore returns with certainty in case (I) and never returns it in case (II). This is the Deutsch-Jozsa algorithm.
For the distributed problem, Alice prepares
using one query to her quantum oracle, and sends these qubits to Bob. Bob applies his phase oracle, producing
The function is constant zero in case (1) and balanced in case (2). Bob applies and measures as above: outcome identifies case (1), while every other outcome identifies case (2), with certainty.
The two registers start in . A quantum Fourier transform on the first and evaluation of give
The first measurement, on the function register, returns . The compatible inputs are , so the normalized state becomes
Apply to the first register and put . Its state is
The geometric sum vanishes unless . Thus this is
up to the unchanged second register. The outcomes each have probability , in accordance with the quantum Fourier transform of a periodic coset state.
For the stated second outcome,
The continued-fraction algorithm therefore returns denominator . Since the numerator is coprime to the true period, exact period recovery from a Fourier sample succeeds, and direct evaluation confirms that the least period is