Phase Encoding

The \(\ket-\) target worked because flipping it only multiplied it by \(-1\). Look for the same property in any unitary \(V\): a state \(\ket u\) that \(V\) changes only by a phase,

\[V\ket u=e^{i\phi}\ket u.\]

Such a state is an eigenstate of \(V\), and \(e^{i\phi}\) is its eigenvalue. Because \(V\) is unitary, it preserves lengths, so the eigenvalue has magnitude one: it is a pure phase. For \(V=X\), the eigenstates are \(\ket+\) with eigenvalue \(1\) and \(\ket-\) with eigenvalue \(-1\).

Now control \(V\) with a qubit in \(\ket+\):

\[\mathrm{C}V\,\frac{\ket0+\ket1}{\sqrt2}\ket u=\frac{\ket0\ket u+\ket1\,e^{i\phi}\ket u}{\sqrt2}=\frac{\ket0+e^{i\phi}\ket1}{\sqrt2}\otimes\ket u.\]

The target is untouched and factors out. The phase \(e^{i\phi}\), which was a global phase of \(V\ket u\) and therefore unobservable, is now a relative phase between the control branches. This is phase kickback in its general form. Applying \(V\) again multiplies \(\ket u\) by \(e^{i\phi}\) again, so \(V^k\ket u=e^{ik\phi}\ket u\), and controlled-\(V^k\) kicks back \(e^{ik\phi}\). Kickback needs three things: a target prepared in an eigenstate, controlled access to \(V\), and the eigenvalue being the information we want.

All three are real requirements. If \(\ket u\) is not an eigenstate, the target becomes entangled with the control and the clean factorization fails. If only an uncontrolled \(V\) is available, the phase stays global. And if many eigenstates are present at once, each contributes its own phase on its own branch. We will find, with phase estimation, that this produces a random sample of the eigenvalues rather than all of them.

A phase on the control is still a relative phase, which no computational-basis measurement sees. How do we turn it into a probability? A Hadamard does it. Apply \(H\) to \((\ket0+e^{i\phi}\ket1)/\sqrt2\):

\[\frac{1+e^{i\phi}}{2}\ket0+\frac{1-e^{i\phi}}{2}\ket1,\qquad \Pr[0]=\left|\frac{1+e^{i\phi}}{2}\right|^2=\frac{1+\cos\phi}{2}.\]

So measuring the control is a coin whose bias reveals \(\cos\phi\). This circuit, \(H\), controlled-\(U\), \(H\), measure, is the Hadamard test. It works even when the target is not an eigenstate. For a general state \(\ket\psi\), the same calculation gives

\[\Pr[0]=\frac{1+\operatorname{Re}\bra\psi U\ket\psi}{2}.\]

To see this, write the state before the final Hadamard as \(\frac{1}{\sqrt2}(\ket0\ket\psi+\ket1U\ket\psi)\). The Hadamard puts amplitude \(\frac12(\ket\psi+U\ket\psi)\) on control outcome \(0\), whose squared length is \(\frac14(2+\bra\psi U\ket\psi+\bra\psi U^\dagger\ket\psi)=\frac12(1+\operatorname{Re}\bra\psi U\ket\psi)\). Inserting \(S^\dagger\) on the control before the final Hadamard gives \(\frac12(1+\operatorname{Im}\bra\psi U\ket\psi)\) instead.

How well does the Hadamard test read a phase? One run gives one bit. To estimate \(\cos\phi\) to precision \(\epsilon\) we need on the order of \(1/\epsilon^2\) runs, by Chebyshev’s inequality for averaged bits. And \(\cos\phi\) does not distinguish \(\phi\) from \(-\phi\). Phase estimation, and its iterative version with one control qubit, do better by combining such tests with controlled powers.

Two forms of Boolean oracle appear in the literature: the bit oracle \(U_f\ket x\ket y=\ket x\ket{y\oplus f(x)}\) and the phase oracle \(O_f\ket x=(-1)^{f(x)}\ket x\). How do they relate?

From a bit oracle to a phase oracle is one query: put the target in \(\ket-\), as in Deutsch’s circuit. Or, if \(U_f\) is built by compute–copy–uncompute, replace the copy by a \(Z\) gate and save the target entirely.

The other direction is subtler. A phase oracle \(O_f\) cannot distinguish \(f\) from \(1\oplus f\): their phase oracles differ by the global factor \(-1\). A bit oracle can, since \(U_f\ket x\ket0\) and \(U_{1\oplus f}\ket x\ket0\) give different target values. So an uncontrolled phase oracle alone cannot implement a bit oracle. With a controlled phase oracle it can. Apply \(H\) to the target \(\ket y\), use the target as the control of \(O_f\), and apply \(H\) again:

\[\ket x\ket y\xrightarrow{H}\ket x\tfrac{1}{\sqrt2}\textstyle\sum_b(-1)^{yb}\ket b\xrightarrow{\mathrm{C}O_f}\ket x\tfrac{1}{\sqrt2}\sum_b(-1)^{b(y\oplus f(x))}\ket b\xrightarrow{H}\ket x\ket{y\oplus f(x)}.\]

The controlled version fixes the global phase: the control-\(0\) branch gets no sign at all, so \(f\) and \(1\oplus f\) become distinguishable. This is a specific case of a general fact about controlled access: control turns a global phase into a relative one. When a paper says “given a phase oracle”, check whether controlled access is assumed.

What does a layer of Hadamards do to a basis state of \(n\) qubits? On one qubit, \[H\ket x=\frac{1}{\sqrt2}\big(\ket0+(-1)^x\ket1\big)=\frac{1}{\sqrt2}\sum_{z\in\{0,1\}}(-1)^{xz}\ket z\]. On \(n\) qubits, apply \(H\) to each and multiply out:

\[H^{\otimes n}\ket x=\bigotimes_{j=1}^n\frac{1}{\sqrt2}\sum_{z_j}(-1)^{x_jz_j}\ket{z_j}=\frac{1}{\sqrt{2^n}}\sum_{z\in\{0,1\}^n}(-1)^{x\cdot z}\ket z,\]

where \(x\cdot z=x_1z_1\oplus\cdots\oplus x_nz_n\) is the bitwise inner product modulo two. The sign of each term is the parity of the positions where both strings have a \(1\). This is the Hadamard transform.

Two consequences follow. First, \(H^{\otimes n}\ket{0^n}\) is the uniform superposition, since \(0\cdot z=0\) for every \(z\). Second, \(H^{\otimes n}\) is its own inverse, because each \(H\) is. So if a state has the form \(2^{-n/2}\sum_x(-1)^{s\cdot x}\ket x\) for some string \(s\), then \(H^{\otimes n}\) maps it exactly to \(\ket s\). Sign patterns of this special “linear” form are read perfectly by one layer of Hadamards.

The rows of the table are orthogonal: for \(s\neq s'\), \[\sum_x(-1)^{s\cdot x}(-1)^{s'\cdot x}=\sum_x(-1)^{(s\oplus s')\cdot x}=0\], since a nonzero string \(t=s\oplus s'\) has \(t\cdot x=1\) for exactly half the \(x\). This cancellation identity has an analogue for complex roots of unity, which will drive the Fourier transform.

Suppose \(f_s(x)=s\cdot x\) for a hidden string \(s\in\{0,1\}^n\), and we have a clean oracle for \(f_s\). The task is to find \(s\).

A classical query returns one bit, \(s\cdot x\), which is one linear equation for the unknown \(s\). Querying \(x=e_j\) (a single \(1\) in position \(j\)) returns \(s_j\), so \(n\) queries suffice. They are also necessary for any classical algorithm: there are \(2^n\) possible strings, and \(k\) queries return \(k\) bits, which can distinguish at most \(2^k\) cases.

The quantum algorithm uses one query. Prepare \(H^{\otimes n}\ket{0^n}\) and the target \(\ket-\), query, and apply \(H^{\otimes n}\):

\[\ket{0^n}\xrightarrow{H^{\otimes n}}\frac{1}{\sqrt{2^n}}\sum_x\ket x\xrightarrow{O_{f_s}}\frac{1}{\sqrt{2^n}}\sum_x(-1)^{s\cdot x}\ket x\xrightarrow{H^{\otimes n}}\ket s.\]

The last step uses the self-inverse property of the Hadamard transform: the phase pattern is a row of the Hadamard table, so the Hadamard layer maps it to the corresponding basis state. Measuring returns \(s\) with certainty.

Here is an \(n=3\) example with \(s=101\). The signs \((-1)^{s\cdot x}\) on \(x=000,001,\ldots,111\) are \(+,-,+,-,-,+,-,+\). The final amplitude of \(z\) is \(\frac18\sum_x(-1)^{(s\oplus z)\cdot x}\), which is \(1\) for \(z=101\) and \(0\) otherwise.

This is the Bernstein–Vazirani algorithm (1993/1997). Its query separation, one versus \(n\), holds for any success criterion, since the classical bound is an information count. Its cost is otherwise ordinary: \(2n+1\) Hadamards and \(n\) measurements around the oracle. And if \(f_s\) is given as a circuit we can read, \(s\) could often be found by inspecting the circuit; the speedup is relative to black-box access.

The Deutsch–Jozsa algorithm is the same circuit with a different promise. What is the final amplitude of \(\ket{0^n}\) for an arbitrary Boolean \(f\)? The row of the Hadamard table for \(z=0^n\) has every sign \(+\), since \(x\cdot0^n=0\). So the amplitude is \(\frac{1}{2^n}\sum_x(-1)^{f(x)}\), the average of the signs. Under the promise that \(f\) is constant or balanced, that average is \(\pm1\) or \(0\), so the circuit outputs \(0^n\) with certainty for constant \(f\) and never for balanced \(f\). One query decides this promise problem exactly.

What about functions outside the promise? If \(f\) takes the value \(1\) on \(k\) of the \(2^n\) inputs, the zero outcome has probability \(\big(1-2k/2^n\big)^2\). For \(n=3\):

Only \(k=0\), \(k=8\) (constant) and \(k=4\) (balanced) give certain answers. A function with \(k=3\) gives zero with probability \(1/16\). An algorithm that announced “balanced” whenever the outcome is nonzero would be making claims about inputs the problem never covered.

How hard is the promise problem classically? It depends on the success criterion. An exact deterministic algorithm needs \(2^{n-1}+1\) queries in the worst case, because \(2^{n-1}\) equal answers are still consistent with a balanced function. A randomized algorithm can query \(k\) random inputs and answer “constant” if all the values agree. It errs only on balanced functions, and then with probability \(2\cdot2^{-k}\), since all \(k\) values must land on the same side. So \(k=1+\log_2(1/\delta)\) queries give error at most \(\delta\). So Deutsch–Jozsa separates exact quantum and exact classical query complexity exponentially, but bounded-error classical algorithms close the gap. Bernstein–Vazirani’s separation is smaller (one versus \(n\)) but survives randomization. Simon’s problem, next, gives an exponential separation that survives randomization.

Can we hide a string in a function so that no single pattern reveals it? Let \(f:\{0,1\}^n\to\{0,1\}^n\) satisfy, for some hidden nonzero \(s\),

\[f(x)=f(y)\iff y=x\ \text{or}\ y=x\oplus s.\]

So \(f\) is two-to-one, and its collisions are exactly the pairs \(\{x,x\oplus s\}\). The task of Simon’s problem is to find \(s\).

Classically, the only way to learn about \(s\) is to find a collision \(f(x)=f(y)\), which reveals \(s=x\oplus y\). With \(k\) queries there are about \(k^2/2\) pairs, each colliding with probability about \(2^{-n}\), so on the order of \(2^{n/2}\) queries are needed. Simon proved this is a lower bound for any bounded-error classical algorithm.

The quantum circuit uses a clean bit oracle with an \(n\)-qubit output register. Prepare the uniform superposition, query, and measure the output register:

\[\frac{1}{\sqrt{2^n}}\sum_x\ket x\ket{f(x)}\ \xrightarrow{\text{measure output, see }f(x_0)}\ \frac{\ket{x_0}+\ket{x_0\oplus s}}{\sqrt2}.\]

The measurement leaves a superposition of the two inputs consistent with the observed value. We do not learn \(x_0\) usefully: it is random. But the difference between the two branches is \(s\), wherever they sit. Now apply \(H^{\otimes n}\). The amplitude of \(z\) is

\[\frac{1}{\sqrt{2^{n+1}}}\Big((-1)^{x_0\cdot z}+(-1)^{(x_0\oplus s)\cdot z}\Big)=\frac{(-1)^{x_0\cdot z}}{\sqrt{2^{n+1}}}\big(1+(-1)^{s\cdot z}\big).\]

It is zero whenever \(s\cdot z=1\), and has magnitude \(2/\sqrt{2^{n+1}}\) whenever \(s\cdot z=0\). The random \(x_0\) contributes only a phase. So each run returns a uniformly random \(z\) satisfying \(s\cdot z=0\).

Take \(n=3\) and \(s=110\). The collision pairs are \(\{000,110\}\), \(\{001,111\}\), \(\{010,100\}\) and \(\{011,101\}\). The condition \(s\cdot z=0\) reads \(z_1\oplus z_2=0\), so the circuit returns one of \(000\), \(001\), \(110\), \(111\), each with probability \(\tfrac14\).

Measuring the output register is not essential; leaving it unmeasured gives the same statistics for \(z\), since the output is never used again. It is a convenient way to see the state. The algorithm is due to Simon, On the Power of Quantum Computation (1994/1997).

One run gives one equation \(s\cdot z=0\) over bits. How many runs determine \(s\), and how do we combine them? These are linear equations modulo two, and solving them is linear algebra over GF(2), arithmetic in which \(1+1=0\). Collect \(n-1\) linearly independent equations; then the solution space is \(\{0^n,s\}\), and the nonzero solution is \(s\). Gaussian elimination finds it in \(O(n^3)\) classical bit operations.

Return to \(n=3\) and \(s=110\). Suppose the runs return \(z=001\) and then \(z=111\). The equations are \(s_3=0\) and \(s_1\oplus s_2\oplus s_3=0\), so \(s_1=s_2\). The nonzero solution is \(s=110\). If the second run had returned \(000\) or \(001\) again, it would add no information, and we would run again.

How many runs are needed? The samples are uniform over the \((n-1)\)-dimensional space of strings orthogonal to \(s\). If we already have \(k\) independent samples, they span \(2^k\) strings, so a new sample is dependent with probability \(2^{k}/2^{n-1}\). The expected wait for an independent one is \(1/(1-2^{k-n+1})\) runs. Writing \(j=n-1-k\) and summing over \(k=0,\ldots,n-2\),

\[\sum_{j=1}^{n-1}\frac{1}{1-2^{-j}}\le\sum_{j=1}^{n-1}\big(1+2^{1-j}\big)<(n-1)+2=n+1,\]

using \(1/(1-u)\le1+2u\) for \(0\le u\le\tfrac12\). So the expected number of runs is less than \(n+1\). A standard tail bound, which we quote, shows that \(n+O(\log(1/\delta))\) runs fail with probability below \(\delta\).

Simon’s algorithm uses \(O(n)\) queries against the classical \(\Omega(2^{n/2})\), an exponential separation for bounded-error algorithms in the black-box model.

What structure made it work, and will the same strategy work elsewhere? Three facts were used. Strings combine by XOR, and the result is again a string. The string \(0^n\) changes nothing, \(x\oplus0^n=x\). And every string undoes itself, \(x\oplus x=0^n\). A set with an operation that has these three properties (closure, an identity element, and an inverse for every element, together with the associativity that XOR has) is called a group. The integers \(\{0,1,\ldots,N-1\}\) under addition modulo \(N\) form another group, with identity \(0\) and the inverse of \(a\) equal to \(N-a\) for \(a\neq0\). In both examples the order of combination does not matter, \(x\oplus y=y\oplus x\) and \(a+b=b+a\); a group with this property is an abelian group.

The hidden pair \(\{0^n,s\}\) is itself a group under XOR, since \(s\oplus s=0^n\). A subset of a group that is a group under the same operation is a subgroup. The collision pair \(\{x_0,x_0\oplus s\}\) is the subgroup shifted by \(x_0\). A shifted copy \(x_0\oplus\{0^n,s\}\) of a subgroup is called a coset. Simon’s function is constant on each coset and takes different values on different cosets, so the measurement of \(f(x)\) collapsed the input onto a random coset.

In this language the algorithm is a template: a coherent query, a measurement that collapses onto a random coset of a hidden subgroup, a Fourier-type transform that turns the unknown shift into a harmless phase, and classical post-processing of several samples. For period finding the group of strings under XOR becomes the integers modulo \(N\) under addition, and the Hadamard transform becomes the quantum Fourier transform. Gaussian elimination is replaced by a number-theoretic method that recovers a fraction from a close approximation.

How do we turn a computed integer into a phase? Suppose a clean computation writes an \(m\)-bit integer \(v=\sum_jv_j2^j\) into a register, and we want the phase \(e^{2\pi iv/2^m}\). The exponent splits into a sum over bits, so the phase splits into a product:

\[e^{2\pi iv/2^m}=\prod_{j=0}^{m-1}e^{2\pi iv_j2^j/2^m}=\prod_{j=0}^{m-1}P\!\left(\frac{2\pi}{2^{m-j}}\right)^{v_j},\]

where \(P(\theta)=\mathrm{diag}(1,e^{i\theta})\) is the phase gate. So apply \(P(2\pi/2^{m-j})\) to bit \(j\), one gate per bit, then uncompute \(v\). The highest bit gets \(P(\pi)=Z\), the next \(P(\pi/2)=S\), then \(P(\pi/4)=T\), and so on. The quantity \(v/2^m\) is the binary fraction \(0.v_{m-1}\cdots v_0\), and each bit contributes its own share of a full turn.

For \(m=3\) and \(v=5=101_2\): \(Z\) on \(v_2=1\) gives \(-1\), \(S\) on \(v_1=0\) gives \(1\), \(T\) on \(v_0=1\) gives \(e^{i\pi/4}\). The product is \(-e^{i\pi/4}=e^{i5\pi/4}=e^{2\pi i\cdot5/8}\). Correct.

The same idea applies with a real angle: if \(\theta(x)\) is computed to \(m\) bits as an approximation, applying the phase gates gives \(e^{i\tilde\theta(x)}\) with \(\tilde\theta\) the rounded angle. The cost is \(m\) controlled rotations plus computing and uncomputing \(\tilde\theta\). Small-angle rotations are not elementary in fault-tolerant gate sets; each must itself be synthesized to some accuracy, and that error must be counted too.

Can we avoid small rotation gates altogether? There is a second way, which reuses arithmetic instead. On an \(m\)-qubit register with \(M=2^m\), prepare the state

\[\ket\chi=\frac{1}{\sqrt M}\sum_{y=0}^{M-1}e^{-2\pi iy/M}\ket y.\]

Adding an integer \(v\) modulo \(M\) to this register multiplies it by a phase. Indeed, substituting \(z=y+v\bmod M\),

\[\frac{1}{\sqrt M}\sum_ye^{-2\pi iy/M}\ket{y+v}=\frac{1}{\sqrt M}\sum_ze^{-2\pi i(z-v)/M}\ket z=e^{2\pi iv/M}\ket\chi.\]

The phase is consistent modulo \(M\) because \(e^{-2\pi iM/M}=1\). So \(\ket\chi\) is an eigenstate of “add \(v\)”, with eigenvalue \(e^{2\pi iv/M}\). Kickback then says what to do: control the addition by the input. If a clean computation produces \(v(x)\) and we add it into \(\ket\chi\), the phase \(e^{2\pi iv(x)/M}\) is kicked back onto \(\ket x\), and \(\ket\chi\) is untouched.

This construction, sometimes called the phase-gradient trick, turns an adder into a bank of phase rotations. The state \(\ket\chi\) is prepared once and reused for every query, since it is never changed. It is a Fourier state; we will see that it is the quantum Fourier transform of a basis state. The cost is a reversible adder per phase operation plus a one-time preparation.

Phases computed to finitely many bits are approximate. How much does that phase error matter? Suppose the intended phase oracle multiplies \(\ket x\) by \(e^{i\phi(x)}\), but the implementation uses \(\tilde\phi(x)\) with \(|\phi(x)-\tilde\phi(x)|\le\delta\) for every \(x\). On a basis state the error is

\[|e^{i\phi}-e^{i\tilde\phi}|=2\left|\sin\frac{\phi-\tilde\phi}{2}\right|\le|\phi-\tilde\phi|\le\delta.\]

On a normalized superposition \(\sum_x\alpha_x\ket x\), the error vector has squared length \(\sum_x|\alpha_x|^2|e^{i\phi(x)}-e^{i\tilde\phi(x)}|^2\le\delta^2\). So the state error is at most \(\delta\), for every input state. The largest such error over all normalized inputs is the operator norm of the difference of the two operations, here at most \(\delta\). Rounding \(\phi\) to the nearest multiple of \(2\pi/M\) gives \(\delta\le\pi/M\), so \(m=\log_2M\) bits give error \(O(2^{-m})\).

What happens when several approximate operations are composed? Suppose \(\|U_1-V_1\|\le\delta_1\) and \(\|U_2-V_2\|\le\delta_2\), all four unitary. Then

\[U_2U_1-V_2V_1=U_2(U_1-V_1)+(U_2-V_2)V_1.\]

Unitaries preserve lengths, so the first term has norm at most \(\delta_1\) and the second at most \(\delta_2\). The product therefore has error at most \(\delta_1+\delta_2\): an error introduced early is not amplified later. An algorithm using \(q\) approximate phase oracles therefore has total error at most \(q\delta\). To keep the total below \(\epsilon\), each oracle needs \(\delta\le\epsilon/q\), which costs only \(\log_2(q/\epsilon)\) bits of phase precision.

Precision is not the only failure mode. Both constructions compute an intermediate value \(v(x)\) and must uncompute it. If \(v\) is left in its register, the branches \(\ket x\ket{v(x)}\) carry different records, and the phases cannot interfere, however precise they are. With clean phase oracles of known precision in hand, we can ask what structured phase patterns such as \(e^{2\pi ixy/N}\) reveal.