iTranslated by AI
Playing with Qiskit (13) — Quantum Phase Estimation
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
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
Here
Objective (Outline of the Quantum Phase Estimation Algorithm)
One of the key techniques in Quantum Phase Estimation is phase kickback. By preparing a qubit
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
In summary:
- Create a circuit that outputs
using phase kickback.P_{n-k} \left( \frac{2\pi}{2^k} \theta \right) \ket{+} - Arrange
of these circuits in parallel to form a circuit that outputs the tensor productn .\bigotimes_{k=1}^n P_{n-k} \left( \frac{2\pi}{2^k} \theta \right) \ket{+}^{\otimes n} - Apply the inverse Quantum Fourier Transform
and measure\operatorname{QFT}^\dagger .\ket{\theta}
In reality, this is slightly incorrect; instead of
Note that since the number of gates required relative to the number of qubits is roughly
Try it out (Equations)
First, let's follow the logic using equations. Out of the blue, let's consider applying a controlled-
As a result, it appears as if the phase gate was applied to
If we repeat this
Comparing this with Equation (1), we realize that it would be great if it were
Here, we set
Rewriting Equation (3) based on this variable transformation:
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
By applying the inverse QFT to Equation (4) and measuring in the computational basis, we obtain
Dividing both sides by
This yields an approximate binary expansion of
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
Let's perform the measurement and estimate
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
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
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?
-
Since
, we haveU \ket{\psi} = \lambda \ket{\psi} . Taking the product yields\bra{\psi} U^\dagger = \lambda^* \bra{\psi} , so1 = \braket{\psi | U^\dagger U | \psi} = |\lambda|^2 \braket{\psi | \psi} . ↩︎|\lambda| = 1
Discussion