Inputs

Phase estimation’s signature is:

phase_est(qin, qout, cont_u)

qin and qout are both QPU registers, while cont_u should be a reference to a function performing the QPU operation we’re interested in (although in a particular way, as we’ll see shortly):

qin

An n-qubit input register prepared in the eigenstate u_j that we wish to obtain the eigenphase for.

qout

A second register of m qubits, initialized as all zeros. The primitive will ultimately use this register to return a binary representation of the desired angle θ_j corresponding to the eigenstate we input in qin. In general, the larger we make m, the greater the precision with which we obtain a representation of θ_j.

cont_u

An implementation of a controlled version of the QPU operation U that we are determining the eigenphases of. This should be passed as a function of the form cont_u(in, out), which takes a single qubit in that will control whether U is applied to the n-qubit register out.

To give a concrete example of using phase estimation, we’ll apply the primitive to find an eigenphase of HAD. We saw in Table 8-1 that one of HAD’s eigenstates has an eigenphase of 180°—let’s see whether phase_est() can reproduce this result using the sample code in Example 8-1.

We specify the eigenstate of interest with qin, and initialize qout as a four-qubit register of all zeros. When it comes to cont_u, it’s worth emphasizing that we don’t simply pass HAD, but rather a function implementing a controlled HAD operation. As we’ll see later in this chapter, the inner workings of phase estimation explicitly require this. Since generating the controlled version of any given QPU operation can be non-trivial, phase_est() leaves it up to the user to specify a function achieving this. In this specific example we make use of the controlled version of HAD built into QCEngine, called chadamard().

Figure 8-4 shows an overview in circle notation of what we can expect from running Example 8-1.

Figure 8-4. Overview of how to use phase estimation primitive

The state of the input register remains the same before and after we apply phase_est(), as expected. But what’s going on with the output register? We were expecting 180° and we got 8!

Outputs

We obtain our eigenphase by applying READ operations to the m qubits of the output register. An important point to note is that the inner workings of phase estimation end up expressing θ_j as a fraction of 360°, which is encoded in the output register as a fraction of its size. In other words, if the output eigenphase was 90°, which is one quarter of a full rotation, then we would expect a three-qubit output register to yield the binary value for 2, which is also a quarter of the 2³ = 8 possible values of the register. For the case in Figure 8-4, we were expecting a phase of 180°, which is half of a full rotation. Therefore, in a four-qubit output register with 2⁴ = 16 values, we expect the value 8, since that is exactly half the register size. The simple formula that relates the eigenphase (θ_j) with the register value we will read out (R), as a function of the size of the register, is given by Equation 8-1.

Choosing the Size of the Output Register

In Example 8-1 the eigenphase we sought to reveal could be expressed perfectly in a four-qubit representation. In general, however, the precision with which we can determine an eigenphase will depend on the output register size. For example, with a three-qubit output register we can precisely represent the following angles:

If we were attempting to use this three-qubit output register to determine an eigenphase that had a value of 150°, the register’s resolution would be insufficient. Fully representing 150° would require increasing the number of qubits in the output register.

Of course, endlessly increasing the size of our output register is undesirable. In cases where an output register has insufficient resolution we find that it ends up in a superposition centered around the closest possible values. Because of this superposition, we return the best lower-resolution estimate of our phase only with some probability. For example, Figure 8-5 shows the actual output state we obtain when running phase estimation to determine an eigenphase of 150° with an output register having only three qubits. This complete example can be run online at http://oreilly-qc.github.io?p=8-2.

Figure 8-5. Estimating phases beyond the resolution of the output register

The probability of obtaining the best estimate is always greater than about 40%, and we can of course improve this probability by increasing the output register size.

If we want to determine the eigenphase to p bits of accuracy, and we want a probability of error (i.e., not receiving the best possible estimate) of no more than $ϵ$, then we can calculate the size of output register that we should employ, m, as:

Complexity

The complexity of the phase estimation primitive (in terms of number of operations needed) depends on the number of qubits, m, that we use in our output register, and is given by O(m²). Clearly, the more precision we require, the more QPU operations are needed. We’ll see in “Inside the QPU” that this dependence is primarily due to phase estimation’s reliance on the invQFT primitive.

Conditional Operations

Perhaps the biggest caveat associated with phase estimation is the assumption that we can access a subroutine implementing a controlled version of the QPU operation we want to find the eigenphases of. Since the phase estimation primitive calls this subroutine multiple times, it’s critical that it can be performed efficiently. How efficiently depends on the requirements of the particular application making use of phase estimation. In general, if our cont_u subroutine has a complexity higher than O(m²), the overall efficiency of the phase estimation primitive will be eroded. The difficulty of finding such efficient subroutines depends on the particular QPU operation in question.

The Intuition

Getting eigenphases from a QPU operation sounds pretty simple. Since phase_est() has access to the QPU operation under scrutiny and one (or more) of its eigenstates, why not simply act the QPU operation on the eigenstate, as shown in Figure 8-7?

Figure 8-7. Simple suggestion for phase estimation

Thanks to the very definition of eigenstates and eigenphases, this simple program results in our output register being the same input eigenstate, but with the eigenphase applied to it as a global phase. Although this approach does represent the eigenphase θ in the output register, we already reminded ourselves earlier that a global phase cannot be READ out. So this simple idea falls foul of the all-too-familiar problem of having the information we want trapped inside the phases of a QPU register.

What we need is some way of tweaking Figure 8-7 to get the desired eigenphase in a more READable property of our register. Looking back through our growing toolbox of primitives, the QFT offers some promise.

Recall that the QFT transforms periodic phase differences into amplitudes that can be read out. So if we can find a way to cause the relative phases in our output register to vary periodically with a frequency determined by our eigenphase, we’re home free—we simply apply the inverse QFT to read out our eigenphase.

Using two explicit eigenphase angles as examples, Figure 8-8 shows what we’re after.

Figure 8-8. Two examples of representing eigenphases in register frequencies

We want to fill in the question marks with a set of QPU operations that produce these results. Say we’re trying to determine an eigenphase of 90° (the first example in Figure 8-8), and we want to encode this in our register by having the register’s relative phases rotate with a frequency of $\frac{90}{360}=\frac{1}{4}$. Since we have 2³ = 8 possible states in our register, this means we want the register to perform two full rotations across its length to give a frequency of $\frac{2}{8}=\frac{1}{4}$. When we perform the invQFT operation on this we, of course, read out a value of 2. From this we could successfully infer the eigenphase: $\frac{2}{8}=\frac{\theta }{{360}^{\circ }}\Rightarrow \theta ={90}^{\circ }$.

After ruminating on Figure 8-8, one realizes that we can get the states we need with a few carefully chosen conditional rotations. We simply take an equal superposition of all possible register states and rotate the k^th state by k times whatever frequency is desired. That is, if we wanted to encode an eigenphase of θ, we would rotate the k^th state by kθ.

This gives just the results we wanted in Figure 8-8, as we show explicitly in Figure 8-9 for the example of wanting to encode a 90° eigenphase in the eight states of a three-qubit register.

Figure 8-9. How to encode a value in the frequency of a register through conditional rotations

So, we’ve managed to reframe our problem as follows: if we can rotate the k^th state of a register by k times the eigenphase we’re after, then (via the inverse QFT) we’ll be able to read it out.

Operation by Operation

As we’ll now see, we can build up a circuit to achieve this kind of conditional rotation by combining the cont_u subroutine (providing conditional access to U) with the phase-kickback trick that we introduced in Chapter 3.

Every time we act our QPU operation U on its eigenstate we produce a global rotation by its eigenphase. Global phases aren’t much good to us as they stand, but we can extend this idea and apply a global phase that is rotated by any integer multiple k (specified in another QPU register) of an eigenphase angle. The circuit shown in Figure 8-10 achieves this.

Figure 8-10. Rotating by a specified number of eigenphases

Every time we apply U to the eigenstate in the bottom register we rotate by the eigenphase θ. The choice of conditional operations simply performs the number of rotations required by each bit in the binary representation of k—resulting in us applying U a total of k times on our bottom eigenstate register—thus rotating it by kθ.

This circuit allows us to implement just one global phase, for some single value of k. To perform the trick that we’re asking for in Figure 8-9 we really want to implement such a rotation for all values of k in the register in superposition. Instead of specifying a single k value in the top register, let’s use a uniform superposition of all 2ⁿ possible values, as shown in Figure 8-11.

Figure 8-11. Conditionally rotating all states in a register at once

The result of this circuit on the second register is that if the first register was in state ∣0⟩, then the second register would have its global phase rotated by 0 × θ = 0°, whereas if the first register was in state ∣1⟩, the second would be rotated by 1 × θ = θ, etc. But after all this, it still seems like we’ve only ended up with pretty useless (conditional) global phases in our second register.

What can we say about the state of the first register that initially held a superposition of k values? Recall from “QPU Trick: Phase Kickback” that at the end of this circuit we can equally think of each state in the first register having its relative phase rotated by the specified amount. In other words, the ∣0⟩ state acquires a relative phase of 0°, the ∣1⟩ state acquires a relative phase of 90°, etc., which is exactly the state we wanted in Figure 8-9. Bingo!

It might take a few runs through the preceding argument to see how we’ve used cont_u and phase kickback to extract the eigenphase into the first register’s frequency. But once we’ve done this, all we need to do is apply invQFT to the register and READ it to acquire the eigenphase we’re after. Hence, the full circuit for implementing phase estimation is as shown in Figure 8-12.

Figure 8-12. Full circuit for implementing phase estimation

We now see why we needed to be able to provide a subroutine for performing a conditional version of our QPU operation. Note also that the bottom register will remain in the same eigenstate at the end of the primitive. It’s hopefully also now clear why (thanks to invQFT) the size of the upper output register limits the precision of the primitive.