Phase Estimation

In this lecture we will describe Kitaev’s phase estimation algorithm, and use it to obtain an alternate derivation of a quantum factoring algorithm. We will also use this technique to design quantum circuits for computing the Quantum Fourier Transform modulo an arbitrary positive integer.

0.1 Phase Estimation Technique

In this section, we define the phase estimation problem and describe an efficient quantum circuit for it.

Let U be a N × N unitary transformation. U has an orthonormal basis of eigenvectors |ψ_{1}⟩,|ψ_{2}⟩,...,|ψ_{N}⟩ with eigenvalues λ_{1},λ_{2},...,λ_{N}, where λ_{j} = e^{2πiθ_{j}} for some θ_{j}.

Proof: U, being unitary, maps unit vectors to unit vectors and hence all the eigenvalues have unit magnitude, i.e. they are of the form e^{2πiθ} for some θ. Let |ψ_{j}⟩ and |ψ_{k}⟩ be two distinct eigenvectors with distinct eigenvalues λ_{j} and λ_{k}. We have that λ_{j}⟨ψ_{j},ψ_{k}⟩ = ⟨λ_{j}ψ_{j},ψ_{k}⟩ = ⟨Uψ_{j},ψ_{k}⟩ = ⟨ψ_{j},Uψ_{k}⟩ = ⟨ψ_{j},λψ_{k}⟩ = λ_{k}⟨ψ_{j},ψ_{k}⟩. Since λ_{j} ≠ λ_{k}, the inner product ⟨ψ_{j},ψ_{k}⟩ is 0, i.e. the eigenvectors |ψ_{j}⟩ and |ψ_{k}⟩ are orthonormal.

Given a unitary transformation U, and one of its eigenvector |ψ_{j}⟩, we want to figure out the corresponding eigenvalue λ_{j} (or, equivalently, θ_{j}). This is the phase estimation problem.

For any unitary transformation U, let C-U stand for a “controlled U” circuit which conditionally transforms |ψ⟩ to U|ψ⟩ as shown in Figure ??.

|ψ⟩  U  |ψ′⟩ bif b = 0 then |ψ′⟩ = |ψ⟩ else if b = 1 then |ψ′⟩ = U|ψ⟩

Figure 0.1: Controlled U Circuit

Assume that we have a circuit which implements the controlled U transformation (We will see later in the course how to construct a circuit that implements a controlled U transformation given a circuit that implements U). The phase estimation circuit in Figure ?? can be used to estimate the value of θ.

The phase estimation circuit performs the following sequence of transformations:

|0⟩|ψ⟩ −→^{H} s.t. (|0⟩ + |1⟩)|ψ⟩
−→^{C-U} s.t. |0⟩|ψ⟩ + s.t. |1⟩λ|ψ⟩
= ( s.t. |0⟩ + \frac{λ}{\sqrt{2}}|1⟩) ⊗ |ψ⟩

|ψ⟩  U |0⟩  Measure H  H

Figure 0.2: Phase Estimation Circuit

Note that after the C-U transformation, the eigenvector remains unchanged while we have been able to put λ into the phase of the first qubit. A Hadamard transform on the first qubit will transform this information into the amplitude which we will be able to measure.

−→^{H}  \frac{1 + λ}{\sqrt{2}} |0⟩ + \frac{1 − λ}{\sqrt{2}} |1⟩

Let P(0) and P(1) be the probability of seeing a zero and one respectively on measuring the first qubit. If we write λ = e^{2πiθ}, we have:

P(0) = | \frac{1 + cos2πθ + isin2πθ}{\sqrt{2}} |^{2} = \frac{1 + cos2πθ}{2}

P(1) = | \frac{1 − cos2πθ − isin2πθ}{\sqrt{2}} |^{2} = \frac{1 − cos2πθ}{2}

There is a bias of \frac{1}{2} cos2πθ in the probability of seeing a 0 or 1 upon measurement. Hence, we can hope to estimate θ by performing the measurement several times. However, to estimate cos2πθ within m bits of accuracy, we need to perform Ω(2^{m}) measurements. This follows from the fact that estimating the bias of a coin to within ϵ with probability at least 1 − δ requires Θ(\frac{log(1/δ)}{ϵ^{2}}) samples.

We will now see how to estimate θ efficiently. Suppose we can implement the C_{m}-U transformation as defined below.

For any unitary transformation U, let C_{k}-U stand for a “k-controlled U” circuit which implements the transformation |k⟩ ⊗ |ψ⟩ −→ |k⟩ ⊗ U^{k}|ψ⟩ as shown in Figure ??.

|ψ⟩  U  U^{k}(|ψ⟩) k (m bits) k ∈ {0,1,...,2^{m}− 1}

Figure 0.3: m-Controlled U Circuit

|ψ⟩  U |0^{m}⟩  |j⟩ QF T_{M}^{−1} H^{⊗m}

Figure 0.4: Efficient Phase Estimation Circuit

Estimating θ within m bits of accuracy is equivalent to estimating integer j, where \frac{j}{2^{m}} is the closest approximation to θ. Let M = 2^{m} and w_{M} = e^{\frac{2πi}{M}}.

The circuit in Figure ?? performs the following sequence of transformations:

|0^{m}⟩|ψ⟩ −→^{H^{⊗m}} ( \frac{1}{\sqrt{M}} ∑_{k=0}^{M−1} |k⟩) ⊗ |ψ⟩

−→^{C_{m}-U} ( \frac{1}{\sqrt{M}} ∑_{k=0}^{M−1} λ^{k}|k⟩) ⊗ |ψ⟩

= ( \frac{1}{\sqrt{M}} ∑_{k=0}^{M−1} ω_{m}^{jk}|k⟩) ⊗ |ψ⟩

Note that the first register now contains the Fourier Transform mod M of j and if we apply the reverse of the Fourier Transform mod M (note that quantum circuits are reversible), we will get back j.

−→^{QF T_{M}^{−1}} |j⟩ ⊗ |ψ⟩

If θ = \frac{j}{2^{m}}, then clearly the circuit outputs j. If θ ≈ \frac{j}{2^{m}}, then the circuit outputs j with high probability (Exercise!).

0.2 Kitaev’s Factoring Algorithm

In this section, we will see how to use the phase estimation circuit to factor a number.

Recall that the problem of factoring reduces to the problem of order finding. To factor N, it is sufficient to pick a random number a and compute the minimum positive r such that a^{r} ≡ 1 mod N. With reasonable probability, r is even and a^{r/2} ≢ ± mod N and hence N | a^{r}−1, i.e. N | (a^{r/2}+1)(a^{r/2}−1). Since N does not divide a^{r/2}±1, it must be the case that a part of it divides a^{r/2}+ 1 and hence gcd(N,a^{r/2}+ 1) is a non-trivial factor of N.

We now reduce the problem of order finding to the phase estimation problem. Consider the unitary transformation

|1⟩  M_{a} |0^{m}⟩  |j⟩ QF T_{M}^{−1} H^{⊗m}

Figure 0.5: Order Finding Circuit (Kitaev’s)

M_{a} : |x⟩ → |xa mod N⟩. Its eigenvectors are |ψ_{k}⟩ = \frac{1}{\sqrt{r}} ( |1⟩ + ω^{−k} |a⟩ + ...+ ω^{−k(r−1)} |a^{r−1} ⟩) , where ω = e^{2πi/r}:

M_{a}|ψ_{k}⟩ = \frac{1}{\sqrt{r}} ( |a⟩ + ω^{−k} |a^{2}⟩ + ...+ ω^{−k(r−1)} |a^{r}⟩)
= ω^{k} \frac{1}{\sqrt{r}} ( |1⟩ + ω^{−k} |a⟩ + ...+ ω^{−k(r−1)} |a^{r−1} ⟩)
= ω^{k}|ψ_{k}⟩

It follows that |ψ_{k}⟩ is an eigenvector of M_{a} with eigenvalue ω^{k}. Hence, if we can implement the C_{m}-M_{a} transformation and construct the eigenvector ψ_{k}for some suitable k, we can use the phase estimation circuit to obtain an approximation to the eigenvalue w^{k} and therefore reconstruct r as follows: w^{k} = e^{2πiθ} for θ = k/r. Recall that phase estimation reconstructs θ ≈ \frac{j}{2^{m}} where j is the output of the phase estimation procedure carried out to m bits of precision. Thus with high probability \frac{j}{2^{m}} is a very close approximation to \frac{k}{r}. Assuming that k is relatively prime to r (which we will ensure with high probability) we can estimate r using the method of continued fractions if we choose M ≈ N^{2}.

Lets look carefully at the C_{m}-M_{a} transformation. It transforms |k⟩|x⟩ → |xa^{k} mod N⟩. But this is precisely the transformation that does modular exponentiation. There exists a classical circuit that performs this transformation in O(|x|^{2}|k|) time, and thus we can construct a quantum circuit that implements the C_{m}-M_{a} transformation.

It is not obvious how to obtain an eigenvector |ψ_{k}⟩ for some k, but it is easy to obtain the uniform superposition of

the eigenvectors |ψ_{0}⟩,|ψ_{1}⟩...|ψ_{r−1} ⟩. Note that \frac{1}{\sqrt{r}} ∑_{k=0}^{r−1} |ψ_{k}⟩ = |1⟩. Hence, if we use |1⟩ as the second input to the

phase estimation circuit, then we will be able to measure a random eigenvalue w^{k}, where k is chosen u.a.r. from the set {0,...,r − 1}. Note that k = 0 is completely useless for our purposes. But k will be relatively prime to r with reasonable probability.

With these observations, it is easy to see that the circuit in Figure ?? outputs |j⟩ with high probability, where \frac{j}{2^{m}} is the closest approximation to \frac{k}{r} for some random k. Note that with reasonable probability, k is relatively prime to r and if that be the case, then we can estimate r using the method of continued fractions if we choose M ≈ N^{2}.

Though the thinking and the analysis behind the Kitaev’s and Shor’s order-finding algorithm are different, it is interesting to note that the two circuits are almost identical. Figure ?? describes the Shor’s circuit with QF T_{Q} transformation replaced by H^{⊗q} since both act in an identical manner on |0^{q}⟩. The quantities q, Q and x in the Shor’s algorithm correspond to m, M and a in the Kitaev’s algorithm. Also, note that raising a to some power is same as performing controlled multiplication.

x  x^{k}( mod N) |0^{q}⟩  measure QF T_{Q} H^{⊗q}

Figure 0.6: Order Finding Circuit (Shor’s)

0.3 QFT mod Q

In this section, we will present Kitaev’s quantum circuit for computing Fourier Transform over an arbitrary positive integer Q, not necessarily a power of 2. Let m be such that 2^{m−1} < Q ≤ 2^{m} and let M = 2^{m}.

Recall that the Fourier Transform mod Q sends

|a mod Q⟩ −→ \frac{1}{\sqrt{Q}} ∑_{b=0}^{Q−1} ω^{ab}|b⟩ =^{let} |χ_{a}⟩

where ω = e^{2πi/Q}. Note that {|χ_{a}⟩ | a = 0,1,...,Q − 1} forms an orthonormal basis, so we may regard the Fourier Transform as a change of basis.

Consider the following sequence of transformations, which computes something close to the Fourier Transform mod Q:

|a⟩|0⟩ −→ |a⟩ ⊗ \frac{1}{\sqrt{Q}} ∑_{b=0}^{Q−1} |b⟩ −→ |a⟩ ⊗ \frac{1}{\sqrt{Q}} ∑_{b=0}^{Q−1} ω^{ab}|b⟩ = |a⟩ ⊗ |χ_{a}⟩

We can implement the circuit that sends |0⟩ −→ \frac{1}{\sqrt{Q}} ∑_{b=0}^{Q−1} |b⟩ efficiently in the following two ways:

1. Perform the following sequence of transformations.

|0⟩^{m}⊗ |0⟩ −→^{H^{⊗m}} \frac{1}{M} ∑_{x=0}^{2^{m}−1} |x⟩|0⟩ −→^{x≥Q} \frac{1}{M} ∑_{x=0}^{2^{m}−1} |x⟩|x ≥ Q⟩

Note that since we can efficiently decide whether or not x ≥ Q classically, we can also do so quantum mechanically. Now take measurement on the second register. If the result is a 0, the first register contains a uniform superposition over |0⟩,...,|Q−1⟩. If not, we repeat the experiment. At each trial, we succeed with probability Q/M > 2^{m−1}/2^{m}= 1/2.

2. If we pick a number u.a.r. in the range 0 to Q − 1, the most significant bit of the number is 0 with probability 2^{m−1}/Q. We can therefore set the first bit of our output to be the superposition:

\sqrt{\frac{2^{m−1}}{Q}} |0⟩ + \sqrt{1 − \frac{2^{m−1}}{Q}} |1⟩

If the first bit is 0, then the remaining m − 1 bits may be chosen randomly and independently, which correspond to the output of H^{⊗m−1} on |0^{m−1}⟩. If the first bit is 1, we need to pick the remaining m−1 bits to correspond to a uniformly chosen random number between 0 and Q − 2^{m−1}, which we can do recursively.

The second transformation |a⟩|b⟩ → ω^{ab}|a⟩|b⟩ can be made using the controlled phase shift circuit.

This gives us an efficient quantum circuit for |a⟩|0⟩ → |a⟩|χ_{a}⟩, but what we really want is a circuit for |a⟩ → |χ_{a}⟩. In particular, for application to factoring, we need a circuit that “forgets” the input a in order to have interference in the superposition over |χ_{a}⟩.

What we would like is a quantum circuit that transforms |a⟩|χ_{a}⟩ → |0⟩|χ_{a}⟩. If we could find a unitary transformation U with eigenvector |χ_{a}⟩ and eigenvalue e^{2πia/Q}, then we could use phase estimation to implement the transformation |0⟩|χ_{a}⟩ → |a⟩|χ_{a}⟩. By reversing the quantum circuit for phase estimation (which we could do since quantum circuits are reversible), we have an efficient quantum circuit for

|a⟩|0⟩ → |a⟩|χ_{a}⟩ → |0⟩|χ_{a}⟩

which is what we need. Note that the phase estimation circuit with m bits of precision outputs j such that \frac{j}{2^{m}} ≈ \frac{a}{Q}. So if we take 2^{m}>> Q^{2}, we can use continued fractions to reconstruct a as required above.

To see that the required U exists, consider U : |x⟩ → |x − 1 mod Q⟩. Then,

U(χ_{a}) = U ( ∑_{b=0}^{Q−1} ω^{ab}|b⟩) = ∑_{b=0}^{Q−1} ω^{ab}|b − 1⟩ = ω^{a} ∑_{b=1}^{Q} ω^{a(b−1)} |b − 1⟩ = ω^{a}χ_{a}.

In addition, note that U^{k} can be efficiently computed with a classical circuit, and can therefore be both efficiently and reversibly computed with a quantum circuit. The overall circuit to compute QF T mod Q is shown in Figure ?? (The circuit should be read from right to left).

U  QF T_{M}^{−1} H^{⊗m}  H^{⊗m}  |0^{m}⟩ |a⟩ Controlled Phase Shift |a⟩ χ_{a}  ⟵

Figure 0.7: Using Reverse Phase Estimation Circuit to do QFT mod Q for arbitrary Q

0.4 Mixed Quantum State

Next, we will outline a very interesting application of phase estimation. Before we can do this, we must introduce some concepts in quantum information theory.

So far we have dealt with pure quantum states

|ψ⟩ = ∑_{x} α_{x}|x⟩.