iTranslated by AI

The content below is an AI-generated translation. This is an experimental feature, and may contain errors. View original article
🪐

Playing with Qiskit (13) — Quantum Phase Estimation

に公開
2023/05/28

Purpose

I touched upon the Quantum Fourier Transform in Looking at the Quantum Fourier Transform, so as an application, I would like to summarize Quantum Phase Estimation here.

I want to perform simple approximate calculations on a CPU and then try more precise approximations on a GPU.

What is Quantum Phase Estimation?

Detailed explanations can be found in Quantum Phase Estimation, so this might be redundant, but it is an "algorithm for finding the corresponding eigenvalue when only a given unitary matrix U and its (normalized) eigenvector \ket{\psi} are known." One might wonder, "Why is it a phase if it's an eigenvalue?", but in the case of a unitary matrix, the absolute value of the eigenvalue is 1[1], so all eigenvalues can be written in the form \exp(2 \pi i \theta). This algorithm is for estimating the phase \theta part.

Review of Quantum Fourier Transform

Since the Quantum Fourier Transform (QFT) will be used as a module, let's review it here.

I omitted this in Looking at the Quantum Fourier Transform, but looking at the Quantum Fourier Transform in the Qiskit textbook, "4. The Quantum Fourier Transform" lists the specific tensor product decomposition formula for the QFT. Note that the rightmost qubit is the 0th and the leftmost is the n-1-th. Based on this formula, considering an n-digit binary expansion for an input non-negative integer x, the QFT formula can be written as follows:

\begin{align*} \operatorname{QFT}(\ket{x}) &= \frac{1}{\sqrt{N}} (\ket{0} + e^{\frac{2\pi i}{2^1} x} \ket{1}) \otimes (\ket{0} + e^{\frac{2\pi i}{2^2} x} \ket{1}) \otimes \cdots \otimes (\ket{0} + e^{\frac{2\pi i}{2^n} x} \ket{1}) \\ &= \bigotimes_{k=1}^n \frac{1}{\sqrt{2}} (\ket{0} + e^{\frac{2\pi i}{2^k} x} \ket{1}) \\ &= \bigotimes_{k=1}^n P_{n-k} \left( \frac{2\pi}{2^k} x \right) \ket{+}^{\otimes n} \tag{1} \end{align*}

Here P is a phase gate, and P_i\ (0 \leq i < n) acts on the i-th qubit.

Objective (Outline of the Quantum Phase Estimation Algorithm)

One of the key techniques in Quantum Phase Estimation is phase kickback. By preparing a qubit q and an ancillary qubit as the eigenvector \ket{\psi} of a unitary U, and applying a controlled-unitary gate between them, the information of the phase \theta of the eigenvalue appears on the q side in the form of phase kickback:

\begin{align*} P_{n-k} \left( \frac{2 \pi}{2^k} \ket{\theta} \right) \ket{+} \tag{2} \end{align*}

This is almost the entire point.


Comparing Equation (2) with Equation (1), we can see that it is part of what appears in the QFT. Therefore, by performing the same operation with n qubits and taking the tensor product, a state equivalent to QFT(\theta) can be generated. After that, \theta can be found by applying an inverse QFT circuit.

In summary:

  1. Create a circuit that outputs P_{n-k} \left( \frac{2\pi}{2^k} \theta \right) \ket{+} using phase kickback.
  2. Arrange n of these circuits in parallel to form a circuit that outputs the tensor product \bigotimes_{k=1}^n P_{n-k} \left( \frac{2\pi}{2^k} \theta \right) \ket{+}^{\otimes n}.
  3. Apply the inverse Quantum Fourier Transform \operatorname{QFT}^\dagger and measure \ket{\theta}.

In reality, this is slightly incorrect; instead of \theta itself, the integer value 2^n \theta will be obtained. By dividing this by 2^n, \theta is estimated in the form of a finite binary fraction 0.b_{n-1} b_{n-2} \cdots b_1 b_0\ {}_\text{(bin)}. To increase the estimation precision by one digit in binary, one additional qubit is required.

Note that since the number of gates required relative to the number of qubits is roughly \mathcal{O}(2^n) + the length of the inverse QFT circuit, care must be taken regarding the circuit depth.

Try it out (Equations)

First, let's follow the logic using equations. Out of the blue, let's consider applying a controlled-U gate to \ket{+}\ket{\psi}:

\begin{align*} CU \ket{+}\ket{\psi} &= \frac{1}{\sqrt{2}} (\ket{0}\ket{\psi} + \ket{1} U\ket{\psi}) \\ & = \frac{1}{\sqrt{2}}(\ket{0}\ket{\psi} + \ket{1} e^{2 \pi i \theta} \ket{\psi}) = (P \left( 2 \pi \theta \right) \ket{+}) \ket{\psi} \end{align*}

As a result, it appears as if the phase gate was applied to \ket{+} (phase kickback).

If we repeat this j times:

\begin{align*} (CU)^j \ket{+}\ket{\psi} = CU^j \ket{+}\ket{\psi} = (P \left( 2 \pi j \theta \right) \ket{+}) \ket{\psi} \tag{3} \end{align*}

Comparing this with Equation (1), we realize that it would be great if it were \frac{2 \pi}{2^k} \theta instead of 2 \pi j \theta... So, let's perform a variable transformation.

\begin{align*} 2 \pi j \theta = \frac{2 \pi}{2^n} j 2^n \theta = \frac{2 \pi}{2^k} \varphi \end{align*}

Here, we set j = 2^{n-k} and \varphi = 2^n \theta.

Rewriting Equation (3) based on this variable transformation:

\begin{align*} (CU)^{2^{n-k}} \ket{+}\ket{\psi} = \left( P \left( \frac{2 \pi}{2^k} \varphi \right) \ket{+} \right) \ket{\psi} \quad (1 \leq k \leq n) \tag{3'} \end{align*}

We have now obtained a form that is almost identical to the QFT.


Comparing Equation (1) and Equation (3'), we can see that we should arrange n qubits and apply \bigotimes_{k=1}^n. That is, assuming \ket{\psi} is prepared in q_n:

\begin{align*} \bigotimes_{k=1}^n (CU_{n-k,n})^{2^{n-k}} \ket{+}^{\otimes n} \ket{\psi} &= \bigotimes_{k=1}^n P_{n-k} \left( \frac{2 \pi}{2^k} \varphi \right) \ket{+}^{\otimes n} \ket{\psi} \\ &= \operatorname{QFT} (\varphi) \ket{\psi} \tag{4} \end{align*}

By applying the inverse QFT to Equation (4) and measuring in the computational basis, we obtain \sum_{\ell=0}^{n-1} 2^\ell b_\ell as an approximation of \varphi. Here, b_\ell \in \{0, 1\}. Conceptually, since this is \varphi:

\begin{align*} 2^n \theta = \varphi \approx \sum_{\ell=0}^{n-1} 2^\ell b_\ell \end{align*}

Dividing both sides by 2^n:

\begin{align*} \theta = \frac{\varphi}{2^n} \approx \sum_{\ell=0}^{n-1} \frac{b_\ell}{2^{n-\ell}} = 0.b_{n-1} b_{n-2} \cdots b_1 b_0 \ {}_\text{(bin)} \end{align*}

This yields an approximate binary expansion of \theta.

That concludes the explanation of Quantum Phase Estimation using equations.

Let's try it (Implementation)

The implementation is complete by implementing Equation (4) and connecting the inverse QFT circuit. Specifically, you can do the following:

from qiskit import QuantumCircuit
import qiskit.quantum_info as qi
from qiskit.circuit.library import QFT
from qiskit.extensions import UnitaryGate
from qiskit_aer import AerSimulator

# Randomly create a unitary matrix U as described in the equations.
unitary = qi.random_unitary(2, seed=1234)
unitary

Operator([[-0.65182701+0.35104045j, -0.06872086+0.66870741j],
[ 0.30111103-0.60101938j, 0.3613751 +0.64615469j]],
input_dims=(2,), output_dims=(2,))

A random unitary matrix was created with a fixed seed for reproducibility. Continuing:

# Obtain the eigenvalues and eigenvectors of U.
w, vec = np.linalg.eig(unitary.data)
w = w[0]
vec = vec[:, 0]
# np.allclose(unitary.data @ vec, w * vec) # => True

arg = np.log(w)
arg = arg.imag * 1.j
print(arg)
theta = (arg / (2*np.pi) * (-1j)).real
assert 0 <= theta < 1
print(theta)

2.878968619668155j
0.4582020868266377

Ultimately, Quantum Phase Estimation will find an approximate value of the latter 0.4582020868266377.

# Convert the unitary matrix into a gate.
unitary_gate = UnitaryGate(unitary, label='random_unitary')
unitary_gate.name = 'random_unitary'
%%time

n_qubits = 4

qc = QuantumCircuit(n_qubits + 1, n_qubits)
for i in range(n_qubits):
    qc.h(i)

# Prepare the eigenvector in the ancillary qubit part.
qc.initialize(vec, n_qubits)

for i in range(n_qubits):
    for _ in range(2**i):
        # Add the unitary gate to the circuit as a controlled-unitary gate.
        qc.append(unitary_gate.control(), [i, n_qubits])
    qc.barrier()

iqft_circuit = QFT(n_qubits).inverse()
qc = qc.compose(iqft_circuit, list(range(n_qubits)))
for i in range(n_qubits):
    qc.measure(i, i)
qc.draw(scale=0.4, fold=75)

This completes the implementation of the quantum circuit. As mentioned earlier, the circuit depth is roughly 2^{\text{n\_qubits}} + the depth of the inverse QFT circuit.


Let's perform the measurement and estimate \varphi.

First, we apply .decompose() until the gates are in a form that the simulator can interpret. I'm not exactly sure how many times are needed, but in this case, it was 6 times.

%%time

qc1 = qc.decompose().decompose().decompose().decompose().decompose().decompose()

Perform the "measurement" and retrieve the most frequently observed result:

%%time

sim = AerSimulator()
counts = sim.run(qc1).result().get_counts()

counts_items = sorted(counts.items(), key=lambda k_v: -k_v[1])
print(counts_items)

[('0111', 710), ('1000', 169), ('0110', 48), ('1001', 32), ('0101', 14), ('1010', 12), ('1011', 10), ('0011', 9), ('0100', 5), ('1110', 3), ('0010', 2), ('0000', 2), ('1101', 2), ('1111', 2), ('0001', 2), ('1100', 2)]

The answer is obtained with a decent frequency, but it would be a bit worrisome if there were noise.

state, count = counts_items[0]

estimated_theta = int(state, 2) / (2**n_qubits)
print(f'estimated={estimated_theta}, real theta={theta}')

estimated=0.4375, real theta=0.4582020868266377

Don't you think we've obtained an approximate value for \theta with fairly good precision?

Let's try to increase the precision a little more

So far, the calculations have been on the CPU and completed relatively quickly. However, I think there might still be some dissatisfaction regarding precision. So, let's increase the precision and try a simulation with 12 qubits. At this scale, it's likely to be tough for a CPU, but let's give it a try.

Here are the execution times for selected cells:

...

%%time

n_qubits = 12

qc = QuantumCircuit(n_qubits + 1)
for i in range(n_qubits):
    qc.h(i)
qc.initialize(vec, n_qubits)

for i in range(n_qubits):
    for _ in range(2**i):
        qc.append(unitary_gate.control(), [i, n_qubits])
    qc.barrier()
    print(i)

iqft_circuit = QFT(n_qubits).inverse()
qc = qc.compose(iqft_circuit, list(range(n_qubits)))
for i in range(n_qubits):
    qc.measure(i, i)
print(len(qc))

4133
CPU times: user 54.5 s, sys: 463 ms, total: 55 s
Wall time: 55.3 s

%%time

qc1 = qc.decompose().decompose().decompose().decompose().decompose().decompose()
print(len(qc1))

57729
CPU times: user 1min 30s, sys: 434 ms, total: 1min 30s
Wall time: 1min 31s

It is quite painful that the depth, which was 4233 before .decompose, has increased to 57729. In other words, even if the depth is theoretically \mathcal{O}(2^n), it can be much deeper when transpiled and decomposed into gates that can actually be executed on a simulator or real machine. Also, since the gate depth increases exponentially, the time to construct the quantum circuit might double for every additional qubit.

Now, let's first try it on the CPU:

%%time

sim = AerSimulator(method='statevector')
counts = sim.run(qc1).result().get_counts()

counts_items = sorted(counts.items(), key=lambda k_v: -k_v[1])
print(counts_items[:5])

When I executed this, it didn't complete even after 16 minutes, so I gave up.

Let's try rewriting it slightly as follows. I'm not sure if the GPU will be used effectively, but I'll give it a shot. Regarding GPU usage, you can run GPU-enabled Qiskit Aer on Colab by following the steps described in Playing with Qiskit (7) — Qiskit Aer GPU. Note that as of now, that article is outdated, so please interpret it appropriately.

%%time

sim = AerSimulator(method='statevector', device='GPU')
counts = sim.run(qc1).result().get_counts()

counts_items = sorted(counts.items(), key=lambda k_v: -k_v[1])
print(counts_items[:5])

This also didn't complete after more than 20 minutes, so I gave up. I'm not sure about the reason, but the following finished relatively quickly, although it still took a fair amount of time:

%%time

sim = AerSimulator(method='statevector', device='GPU', cuStateVec_enable=True)
counts = sim.run(qc1).result().get_counts()

counts_items = sorted(counts.items(), key=lambda k_v: -k_v[1])
print(counts_items[:5])

[('011101010101', 882), ('011101010100', 53), ('011101010110', 30), ('011101010011', 14), ('011101010111', 9)]
CPU times: user 11min 8s, sys: 3.03 s, total: 11min 11s
Wall time: 11min

state, count = counts_items[0]

estimated_theta = int(state, 2) / (2**n_qubits)
print(f'estimated={estimated_theta}, real theta={theta}')

estimated=0.458251953125, real theta=0.4582020868266377

I was able to estimate with much better accuracy than when using 4 qubits. However, it's worth noting that increasing the number of qubits only improves the precision in terms of binary digits, so the improvement in precision is gradual compared to decimal fractions.

Roughly speaking, the calculation with 12 qubits took about 15 minutes; I wonder if 13 qubits would take 30 minutes and 14 qubits would take about an hour?

Trying Another Method (GPU Calculation)

While it becomes difficult with a large number of qubits, another approach is to calculate the statevector directly. In this case, because a huge unitary matrix is repeatedly applied to the statevector internally, it usually consumes a large amount of memory and is computationally heavy. However, since this is an area where GPUs excel, it might be possible to achieve higher speeds.

Perhaps because measurement is a Hermitian operation and not a unitary one, it is unsupported in this context, so we remove the measurement operations:

for i in range(n_qubits):
    qc.measure(i, i)

After doing that and transpiling, perform the following:

from qiskit_aer.quantum_info import AerStatevector as Statevector
%%time

sv = Statevector(qc1, device='GPU', cuStateVec_enable=True)

As expected, it is dramatically fast on the GPU. It was almost instantaneous.

state, _ = sorted(sv.probabilities_dict().items(), key=lambda k_v: -k_v[1])[0]
estimated_theta = int(state, 2) / (2**n_qubits)
print(f'estimated={estimated_theta}, real theta={theta}')

The result is the same as that obtained through measurement, and since we are calculating the statevector itself, it produces the theoretical result.

Summary

We have looked at Quantum Phase Estimation as an algorithm that applies the Quantum Fourier Transform. While there are advantages over classical computation in terms of quantum computational complexity, the construction of the quantum circuits themselves consumes a significant amount of resources. I feel that continuing with Python for this part might become challenging in the future. I wonder if this will improve when we can write in languages like Mojo?

脚注
  1. Since U \ket{\psi} = \lambda \ket{\psi}, we have \bra{\psi} U^\dagger = \lambda^* \bra{\psi}. Taking the product yields 1 = \braket{\psi | U^\dagger U | \psi} = |\lambda|^2 \braket{\psi | \psi}, so |\lambda| = 1. ↩︎

GitHubで編集を提案

Discussion