Codex @codex  0

On a basis indexed by ${\mathbb{Z}}_N$, a cyclic shift operator has the form $U(a)|b⟩=|a+b\mathrm{mod}N⟩$. The quantum Fourier transform simultaneously diagonalizes all such shifts.

For a generator of a group $g$ of order $M$ and $x=g^y$, the function $f(a,b)=g^a{x}^{-b}$ hides the subgroup $\{(yb,b):b\in {\mathbb{Z}}_M\}$ of ${\mathbb{Z}}_M^2$. Each fiber is an affine coset $\{(yb+k,b):b\in {\mathbb{Z}}_M\}$. Measuring the function register gives its normalized coset state. Applying the positive-exponent quantum Fourier transform to both input registers gives amplitudeThe finite geometric series vanishes off $c_2=-y{c}_1$ and equals $M$ on that line. Thus each allowed output pair has probability $1/M$, independently of the coset offset. If $\gcd (c_1,M)=1$, a modular inverse recovers $y=-c_2{c}_1^{-1}$.

For the phase gate $R_a=\mathrm{diag}(1,e^{2\pi ia/2^n})$, apply powers $R_a^{2^{n-1}},\dots ,R_a$ to a uniform quantum superposition on $n$ qubits. Binary positional weights multiply the phases into $e^{2\pi iax/2^n}$ on basis vector $|x⟩$. The inverse quantum Fourier transform returns $|a⟩$ exactly, by orthogonality of roots of unity. Preparing the powers by repeated applications uses $2^n-1$ copies of $R_a$; this does not claim a number of gate calls polynomial in $n$. If $a$ is odd, its powers generate the entire set of dyadic phase gates because $a$ has a modular inverse modulo $2^n$.

In most-significant-bit-first order, let $x=x_1\cdots x_n$ and $0.x_j\cdots x_n={\sum }_{l=j}^n{x}_l{2}^{-(l-j+1)}$. On a computational-basis state, process wire $j$ with a Hadamard gate, then controlled phase gates $R_{l-j+1}$ controlled by unprocessed wire $l$ for each $l>j$. Wire $j$ becomes $(|0⟩+e^{2\pi i0.x_j\cdots x_n}|1⟩)/\sqrt{2}$. Reversing the final wire order yields the positive-exponent quantum Fourier transform. There are $n$ Hadamard gates and $n(n-1)/2$ controlled phase gates. Physical reversal costs $\lfloor n/2\rfloor$ swap operators, each expressible as three controlled-NOT gates, themselves implemented with Hadamard gates and a Controlled-Z gate. Thus the entire construction uses $O(n^2)$ gates from the specified family.

A Fourier sample is a computational-basis measurement outcome after applying a quantum Fourier transform $F$ to a quantum state $|\psi ⟩$. Its distribution is given by the squared Fourier amplitudes. For a uniform periodic coset of spacing $r\mid N$, samples are the multiples $sN/r$ with uniform $s\in {\mathbb{Z}}_r$. Samples need not individually reveal the whole period: a greatest common divisor can remove factors from a single reduced denominator, motivating two-sample exact period recovery.

The hidden subgroup problem asks for a subgroup $H\le G$ given an oracle $f:G\to X$ that is constant on each left coset of $H$ and takes different values on different cosets. Abelian instances are solved by preparing coset states and applying a group quantum Fourier transform.

Prepare the uniform pure stateEvery permutation matrix fixes this vector, so RandomPermute returns $|s⟩$ with certainty. Choose an orthonormal basis with first vector $|{\psi }_0⟩=|s⟩$, for example the quantum Fourier transform basis. Under RandomReset, the returned state is $I/d$, which gives each of the $d$ measurement labels probability $1/d$.

Guess RandomPermute on label 0 and RandomReset on every other label. ThenThis is invariant-pure-state discrimination against a maximally mixed reset. It also agrees with the Holevo–Helstrom theorem: the eigenvalues of $|s⟩⟨s|-I/d$ are $1-1/d$ once and $-1/d$ with multiplicity $d-1$, giving optimal equal-prior success $1/2+\Vert {\rho }_P-{\rho }_R{\Vert }_1/4=1-1/(2d)$. This confirms optimal discrimination of these returned states, in addition to constructing the requested strategy.^[ref] For $d=1$, the actions coincide and the formula correctly gives random-guessing success $1/2$.

On an $N$-dimensional register, the quantum Fourier transform with positive-exponent convention isIt is the unitary version of the discrete Fourier transform on amplitudes. The inner product of columns $x,x^{\prime }$ is $N^{-1}{\sum }_y{e}^{2\pi i(x^{\prime }-x)y/N}$, equal to one when $x=x^{\prime }$ and zero otherwise by a finite geometric series, so the transformation is unitary.

For the qubit implementation take $N=2^n$, write $x=x_1\cdots x_n$ in most-significant-bit-first order, and put $0.x_j\cdots x_n={\sum }_{l=j}^n{x}_l{2}^{-(l-j+1)}$. Expanding $y={\sum }_j{y}_j{2}^{n-j}$ separates the Fourier phase as a product. The resulting dyadic quantum Fourier transform circuit identity isIndeed the phase on output bit $y_j$ is $e^{2\pi ix{y}_j/2^j}$, depending on the last $j$ input bits; multiplying the factors recovers $e^{2\pi ixy/2^n}$ and the normalization $2^{-n/2}$.

Implement the product in reverse wire order as follows. Process input wire $j$, starting at $j=1$. A Hadamard gate maps $|x_j⟩$ to $(|0⟩+e^{2\pi i{x}_j/2}|1⟩)/\sqrt{2}$. For each still-unprocessed wire $l>j$, apply a controlled phase gate with control $l$, target $j$, and target phaseOn a computational-basis input this multiplies the target's one-component by $e^{2\pi i{x}_l/2^{l-j+1}}$, so the processed wire becomes exactly $(|0⟩+e^{2\pi i0.x_j\cdots x_n}|1⟩)/\sqrt{2}$. Continue through all wires and reverse their order using SWAP gates. This equals the boxed transform on every basis vector and therefore on arbitrary superpositions by linearity; it does not require learning the input bits by measurement.

There are $\boxed{n\text{ Hadamards},n(n-1)/2\text{ controlled phase gates},\lfloor n/2\rfloor \text{ swaps}}$. A swap is three controlled-NOT gates, since the alternating control directions send $(a,b)$ successively to $(a,a\oplus b)$, then $(b,a\oplus b)$, and finally $(b,a)$. Thus the exact transform uses $O(n^2)$ one- and two-qubit gates from this phase-gate family, polynomial in the register size $n={\log }_{2}N$. This is a circuit-complexity statement, not a claim that all $N$ transformed amplitudes can be read out efficiently. If a fixed finite gate alphabet is required, the phase rotations must instead be synthesized to the desired accuracy; the exact count treats them as the available simple rotation gates.

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.

Apply one Hadamard gate independently to each qubit. These gates act in parallel, so the quantum circuit implements $H^{\otimes n}$ with $n$ gates and depth one.

For a computational basis state, factorization givesThe exponent is the dot product over the finite field ${\mathbb{F}}_2$, because multiplying the separate signs adds their exponents modulo two. This is the Walsh-Hadamard transform, equivalently the quantum Fourier transform on the finite Abelian group $({\mathbb{Z}}_2{)}^n$.

In particular, the all-zero input becomes the uniform coherent superposition $2^{-n/2}{\sum }_y|y⟩$. It is a useful initial operation because an oracle can then act on all amplitudes in one call, and subsequent interference can reveal a global property. Measurement alone does not read all function values: the later interference step is what turns the preparation into an algorithmic advantage.

Put $N=2^t$ and write $U|u⟩=e^{i\varphi }|u⟩$, with $|u⟩$ normalized. The Hadamard gates prepare the control register in $N^{-1/2}{\sum }_{k=0}^{N-1}|k⟩$. Controlled powers of the unitary operator then give quantum phase kickback:Thus the register quantum state is $N^{-1/2}{\sum }_k{e}^{ik\varphi }|k⟩$, while the target remains $|u⟩$. Define the quantum Fourier transform by $F_N|m⟩=N^{-1/2}{\sum }_k{e}^{2\pi ikm/N}|k⟩$. Its inverse givesWhen $\varphi =2\pi n/N$, the inner finite geometric series equals $N$ if $m\equiv n(\mathrm{mod}N)$ and zero otherwise. Therefore exact quantum phase estimation givesThe quantum phase, rather than an unrestricted integer $n$, is recovered modulo $2\pi$.

The printed circuit has no bit-reversal swaps. Its top control uses $U^{2^{t-1}}$, and its measured top wire gives the least significant output bit. Write $n\mathrm{mod}N={\sum }_{j=0}^{t-1}{2}^j{b}_j$. Before the top wire's final Hadamard gate, its relative quantum phase is $2^{t-1}\varphi =\pi n$, so that gate produces $b_0$. The controlled inverse quantum phase gates then subtract its contribution from lower wires. More generally, before the final Hadamard gate on wire $j$, the relative quantum phase isso that wire gives $b_j$ deterministically. For the three-wire drawing, the correct interpretation isEquivalently, its Fourier-inversion circuit is $R{F}_N^{†}$, where $R$ reverses the register bits. Relabeling the measured bits or appending swaps gives the usual integer output. This bit convention matters, for example, when quantum phase $\pi$ produces top-to-bottom bits $001$, representing the label four rather than one.

With the negative exponential convention of the specified quantum Fourier transform, the amplitude of computational outcome $k$ isIf $k=m$, every summand is one. Otherwise this finite geometric series has ratio $q\ne 1$ with $q^N=1$, so it equals $(1-q^N)/(1-q)=0$. ThusThe Born rule gives outcome $m$ with probability one when performing a quantum measurement in the computational basis. Recover the promised phase as ${\varphi }_m=2\pi m/N$ modulo $2\pi$. Using the opposite Fourier sign would instead return the label $-m\mathrm{mod}N$, so the sign convention matters.

Write the promised phase as $\varphi =2\pi m/8$. Prepare three logical qubits in $|+⟩$ and attach zero ancillas in three blocks of sizes four, two and one. A block of size $r$ is prepared by fanout CNOT gates asApply one copy of $U_{\varphi }$ to every physical qubit in every block, all in the same time step. Undo each fanout. The logical block output is $(|0⟩+e^{ir\varphi }|1⟩)/\sqrt{2}$ and every ancillary wire returns to zero. This is parallel phase multiplication by coherent fanout; its intermediate entanglement copies basis labels, and does not clone an arbitrary quantum state.

For block weights $4,2,1$, the three logical wires now containApply the specified negative-sign quantum Fourier transform and measure. Part (a) gives label $m$ deterministically. Thus seven parallel phase-gate applications, on three logical wires and four ancillas, identify the phase in one oracle time step. Preparation, uncomputation and the Fourier transform cost no time under the stated model; using serial powers would not meet the time requirement.

Set $L=2^N$. Applying the inverse quantum Fourier transform to the register in part (a) gives probability amplitude at label $m$ equal toChoose $m$ nearest to $\eta =L{\varphi }_j/(2\pi )$, with $m$ reduced modulo $L$ at the phase boundary. Then the difference can be represented with $|\delta |\le \pi /L$. For $\delta \ne 0$, sum the finite geometric series to obtainLet $z=L|\delta |/2\le \pi /2$. On $[0,\pi /2]$, concavity of sine gives $\sin z\ge 2z/\pi$, the line through its endpoint values. Also $|\sin (\delta /2)|\le |\delta |/2$. Thereforeand the Born rule proves the nearest-integer success bound for quantum phase estimation:If $\delta =0$, every summand is one and the probability is exactly one. If the scaled phase is halfway between two integers, either nearest label separately satisfies the displayed bound. Interpreting the measured integer as $m/L$ gives the closest available $N$-bit phase estimate modulo one.

Choose an orthonormal eigenbasis of $V$, with eigenphases ${\varphi }_0,{\varphi }_1$, counting multiplicity. The maximally mixed state is basis independent, soLinearity means that the experiment is the equal mixture of the two eigenstate experiments. After the inverse quantum Fourier transform, the joint state is $\frac{1}{2}{\sum }_{j=0}^1|{\chi }_j⟩⟨{\chi }_j|\otimes |v_j⟩⟨v_j|$, where $|{\chi }_j⟩={\sum }_m{a}_m({\varphi }_j)|m⟩$ andThus the exact output distribution for quantum phase estimation with a maximally mixed target isFor a nonzero phase mismatch, the squared probability amplitude is ${\sin }^2[L(\varphi -2\pi m/L)/2]/\{L^2{\sin }^2[(\varphi -2\pi m/L)/2]\}$, with value one at an exact match. If both eigenphases are exactly representable on the $L$-point grid, their two labels occur with probability $1/2$ each; coincident labels have their probabilities added. For general eigenphases there can be nonzero probabilities at other labels, so it would not be exact to list only the two best approximations with probability $1/2$ each. Each eigenphase is sampled with spectral weight $1/2$, and its nearest-label event has conditional probability at least $4/{\pi }^2$. In particular a nearest label for one eigenphase has unconditional probability at least $2/{\pi }^2$, with additional contributions possible from the other phase.

With access to the uncontrolled physical gate, use single-qubit process tomography. Prepare the positive eigenstate of each of $X,Y,Z$, apply $V$, and on independent copies measure each of $X,Y,Z$. Arbitrary single-qubit rotation gates let one prepare these inputs and rotate each measurement into the computational basis. The nine measured means areThey determine the real rotation matrix $R$ of the Bloch vector, and hence the action of $V$ on every qubit state. To see precisely what this identifies, suppose another unitary $U$ has the same action. Then $V^{†}U$ commutes with every Pauli matrix. Commuting with $Z$ makes it diagonal; commuting with $X$ makes its diagonal entries equal. Therefore $U=e^{i\gamma }V$.

Consequently tomography determines $V$, and its eigenvalues, up to a common phase. More explicitly, write a representative as $V=e^{i\gamma }(\cos aI-i\sin a\mathbf{n}\cdot \mathbf{\sigma })$. Its eigenvalues are $e^{i(\gamma -a)}$ and $e^{i(\gamma +a)}$, and its Bloch vector action is rotation through $2a$ about $\mathbf{n}$. The measured rotation identifies the unordered relative eigenphase information; for example $\mathrm{Tr}R=1+2\cos (2a)$. Once a representative with a specified overall phase is supplied, diagonalizing that representative gives the corresponding two eigenvalues.

The common phase itself cannot be recovered with the stated uncontrolled access. Indeed, $(e^{i\gamma }V)\rho (e^{i\gamma }V{)}^{†}=V\rho V^{†}$ for every input, including inputs entangled with ancillas. Replacing $V$ by $e^{i\gamma }V$ therefore leaves every such preparation-and-measurement experiment unchanged, whereas it multiplies both eigenvalues by $e^{i\gamma }$. For example, $I$ and $e^{i\gamma }I$ are indistinguishable physical gates under these operations. This proves that the request for absolute eigenvalue phases needs an additional phase reference or controlled-gate assumption: the global phase of an uncontrolled quantum gate is unobservable. The controlled powers in the earlier parts supply that extra resource, since $\mathrm{diag}(I,e^{i\gamma }V)$ changes a relative phase between the two control branches.

The practical advantages are that no unknown eigenstate preparation, controlled powers, entangling gates or inverse quantum Fourier transform are needed: a fixed set of single-qubit preparations and measurements suffices. The disadvantages are statistical estimation and the phase ambiguity just proved. Estimating the bounded Pauli measurement means to additive accuracy $ϵ$ at fixed confidence requires order ${ϵ}^{-2}$ independent repetitions, giving the usual sampling cost for this direct procedure. The earlier quantum phase estimation circuit uses $N$ phase qubits and high controlled powers to resolve scale $2^{-N}$ in one coherent experiment with a constant success bound; constructing those powers from controlled uses of $V$ costs $2^N-1$ gate calls, so its exponential-looking precision is not obtained with only $N$ uses of $V$. Repetitions can raise confidence. Finally, full process tomography grows exponentially with the number of system qubits, whereas the eigenstate-based phase procedure can estimate a selected eigenphase without reconstructing the entire operator.

The inverse quantum Fourier transform in the original PDF has matrix elements $N^{-1/2}{e}^{-2\pi iky/N}$ multiplying $|y⟩⟨k|$. The converted TeX incorrectly repeats $y$ in the bra; using the actual PDF operator,If $y=a$, every summand of the inner sum is one, so it equals $N$. If $y\ne a$, let $q=e^{2\pi i(a-y)/N}$. Then $q\ne 1$ and $q^N=1$, and the finite geometric series gives ${\sum }_{x=0}^{N-1}{q}^x=(1-q^N)/(1-q)=0$. This is orthogonality of roots of unity. HenceA quantum measurement in the computational basis consequently returns the integer $a$ with probability one.

Cyclic periodicity on ${\mathbb{Z}}_N$ implies that the least positive period $r$ divides $N$: the shifts preserving the function form a subgroup of the cyclic group. Injectivity within one period says that distinct residue classes modulo $r$ have distinct function values. Write $L=N/r$.

Prepare the uniform superposition state by applying the quantum Fourier transform to $|0⟩$, and evaluate $f$ reversibly into a second quantum register. This is efficient because the given classical Boolean circuit can be converted into a reversible circuit, with its workspace cleaned by uncomputation. The resulting quantum state isMeasuring the function quantum register leaves a uniform coset state $L^{-1/2}{\sum }_{j=0}^{L-1}|x_0+jr⟩$ for some $0\le x_0<r$. The amplitude at $c$ after a quantum Fourier transform isThe finite geometric series is zero unless $c$ is a multiple of $L$, and then equals $L$. Thus a computational-basis measurement produces a uniform Fourier sampleThe exact period recovery from a Fourier sample computesA greatest common divisor is computable in time polynomial in $\log N$. The candidate is always a divisor of the true period, and equals it precisely when $s$ is coprime to $r$.

For the success flag, compute $f(\hat{r}\mathrm{mod}N)$ and compare with $f(0)$. If $\hat{r}<r$, injectivity within the first period makes these unequal. If $\hat{r}=r$, periodicity makes them equal, including $r=N$. Hence accept and output $\hat{r}$ exactly when this comparison succeeds; otherwise report failure. This is heralded exact quantum period finding when the period divides the register size, with no false acceptance. The case $r=1$ succeeds even on the sample $c=0$.

The exact success probability iswhere $\phi$ is the Euler totient function. For $r\mid N$, the prime-product formula gives $\phi (r)/r\ge \phi (N)/N$. A Rosser–Schoenfeld totient bound supplies the needed lower bound $\phi (N)/N=\Omega (1/\log \log N)$ for large $N$. Every single attempt, including verification, has the assumed polynomial-in-$\log N$ gate cost. Repeating $O(\log \log N)$ times gives constant success probability with a certified result whenever one is found.

The printed $O$ in the totient hint should be a lower-bound statement, $\Omega$. Literally, $\phi (N)=O(N/\log \log N)$ is false: at primes $N$, $\phi (N)=N-1$. Likewise the exact single-sample success probability need not be $O(1/\log \log N)$; for prime period it tends to one. The useful intended guarantee is the displayed inverse-log-log lower bound, not a universal upper bound. If an algorithm satisfying the literal success upper bound is desired, one can additionally accept an otherwise certified run only when $k=\lceil \log \log N\rceil$ independent fair bits are all zero. This retains a detectable failure flag and polynomial runtime, and has success at most $2^{-k}=O(1/\log \log N)$, but deliberately weakens the useful guarantee. The standard unsuppressed algorithm above gives the stronger intended performance. Small $N$ can be handled directly. Primary evidence for the totient lower bound is Theorem 15, equations (3.41)–(3.42), in denisevellachemla.eu/Rosser-Schoenfeld-1962.pdf .

Let $\omega =e^{2\pi i/3}$. The positive-exponent quantum Fourier transform gives $|\xi ⟩=3^{-1/2}{\sum }_{y=0}^2{\omega }^{2y}|y⟩$. Reindexing the cyclic shift operator givesThus $|\xi ⟩$ is an eigenstate with eigenvalue $\omega$, with this sign fixed by the printed quantum Fourier transform convention.

Prepare the first two qutrits in $({\mathrm{QFT}}_3|0⟩{)}^{\otimes 2}$ and the answer qutrit in $|\xi ⟩$. The modular-addition quantum oracle applies $S^{f(x_1,x_2)}$ to the answer. Its eigenvalue produces quantum phase kickback, leavingApply ${\mathrm{QFT}}_3^{-1}$ to each input qutrit, then measure them in the computational basis. The result isThe preparation, inverse transforms and measurements are independent of $f$, and there is exactly one use of $U_f$. This is qutrit linear-function identification, the ternary version of Bernstein-Vazirani phase kickback.

The quantum circuit has one control wire per binary digit and one target quantum register. Every control starts in $|0⟩$, receives a Hadamard gate, controls the corresponding power $U^{2^j}$, and then enters the collective inverse quantum Fourier transform. Only the control register is measured; the target stays in $|\psi ⟩$.

The omitted intermediate wires continue the pattern $j=0,1,\dots ,m-1$. The inverse quantum Fourier transform black box is defined on the integer basis $|k⟩$ with $k={\sum }_j{2}^j{k}_j$, so the displayed ordering introduces no hidden bit reversal. The measured bits satisfyEach controlled power box represents $2^j$ sequential controlled-$U$ uses when only that primitive is available.