{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Quantum Phase Estimation Algorithm\n",
"\n",
"Translator: [unseenme](https://gitee.com/unseenme)\n",
"\n",
"[](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/notebook/r2.7.0rc1/mindquantum/en/case_library/mindspore_quantum_phase_estimation.ipynb) \n",
"[](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/notebook/r2.7.0rc1/mindquantum/en/case_library/mindspore_quantum_phase_estimation.py) \n",
"[](https://gitee.com/mindspore/docs/blob/r2.7.0rc1/docs/mindquantum/docs/source_en/case_library/quantum_phase_estimation.ipynb)\n",
"\n",
"## Overview\n",
"\n",
"Quantum Phase Estimation Algorithm, or QPE for short, is the key to many quantum algorithms. Suppose a unitary operator $U$, which acts on its eigenstate $|u\\rangle$ will have a phase $e^{2\\pi i \\varphi}$, now we assume that the eigenvalue of the $U$ operator is unknown, that is, $\\varphi$ is unknown, but the $U$ operator and the eigenstate $|u\\rangle$ are known, The role of the phase estimation algorithm is to estimate this phase $\\varphi$.\n",
"\n",
"\n",
"\n",
"## Algorithm Analysis\n",
"\n",
"The implementation of the quantum phase estimation algorithm requires two registers, the first register contains $t$ qubits initially at $|0\\rangle$, the number of bits is related to the accuracy of the final phase estimation result and the success probability of the algorithm; the second register is initialized on the eigenstate $|u\\rangle$ of the unitary operator $U$. The phase estimation algorithm is mainly divided into three steps:\n",
"\n",
"### Step One\n",
"\n",
"Perform [Hadamard](https://www.mindspore.cn/mindquantum/docs/en/r0.11/core/gates/mindquantum.core.gates.HGate.html) gate operations on all qubits in the first register, and continuously perform `control U` gate operations on the second register, where the powers of $U$ gates are $2^0, 2^1,...,2^{t-1}$, and the control qubits are $q_{t-1}, q_{t-2},..., q_{1}, q_{0}$. Then the state in the first register will change to:\n",
"\n",
"$$\n",
"|\\psi_1\\rangle=\\frac{1}{2^{t/2}}\\left(|0\\rangle+e^{i2\\pi 2^{t-1}\\varphi}|1\\rangle\\right)\\left(|0\\rangle+e^{i2\\pi2^{t-2}\\varphi}|1\\rangle\\right)...\\left(|0\\rangle+e^{i2\\pi 2^{0}\\varphi}|1\\rangle\\right) = \\frac{1}{2^{t/2}}\\sum_{k=0}^{2^t-1}e^{i2\\pi\\varphi k}|k\\rangle\n",
"$$\n",
"\n",
"where $k$ is the decimal representation of the direct product state, for example, $k=0$ means that all t qubits in the first register are in the ground state $|00...00\\rangle$, $k=2$ means $|00...10\\rangle$, and so on.\n",
"\n",
"### Step Two\n",
"\n",
"Perform the inverse quantum Fourier transform on the first register, which is expressed as $QFT^\\dagger$ in the circuit, and perform the inverse quantum Fourier transform on $|\\psi_1\\rangle$ to obtain\n",
"\n",
"$$\n",
"|\\psi_2\\rangle=QFT^\\dagger|\\psi_1\\rangle =\\frac{1}{2^t}\\sum_{x=0}^{2^t-1}a_x|x\\rangle\n",
"$$\n",
"\n",
"where\n",
"\n",
"$$\n",
"a_x=\\sum_{k=0}^{2^t-1}e^{2\\pi i k(\\varphi-x/2^t)}\n",
"$$\n",
"\n",
"is the probability amplitude corresponding to the eigenbasis vector $|x\\rangle$ ($x=0.1,...,2^t$).\n",
"It can be obtained from the above formula that when $2^t\\varphi$ is an integer and $x=2^t\\varphi$ is satisfied, the probability amplitude takes the maximum value of 1, at this time, the last state of the first register can accurately reflect $\\varphi$; when $2^t\\varphi$ is not an integer, $x$ is the estimate of $\\varphi$, and the larger $t$, the higher the estimation accuracy.\n",
"\n",
"### Step Three\n",
"\n",
"Measure the qubits of the first register to obtain the final state of the first register $f=\\sum_{x}^{2^t-1}a_x|x\\rangle$, $x=0,1,...,2^t$, and find the maximum amplitude $a_{max}$ from it, then the $x$ in the corresponding eigenvector $|x\\rangle$ divided by $2^t$ is the estimated value of phase.\n",
"\n",
"## QPE Code Implementation\n",
"\n",
"The following is an example to demonstrate how to implement the quantum phase estimation algorithm in MindSpore Quantum. The [T](https://www.mindspore.cn/mindquantum/docs/en/r0.11/core/gates/mindquantum.core.gates.TGate.html) gate is selected as the unitary operator for estimation, from the definition of\n",
"\n",
"$$T|1\\rangle=e^{i\\pi/4}|1\\rangle$$\n",
"\n",
"it can be known that the phase angle to be estimated is $\\varphi=\\frac{1}{8}$.\n",
"\n",
"Now suppose we don't know the phase information of the [T](https://www.mindspore.cn/mindquantum/docs/en/r0.11/core/gates/mindquantum.core.gates.TGate.html) gate, but only know that the unitary operator $U$ is a [T](https://www.mindspore.cn/mindquantum/docs/en/r0.11/core/gates/mindquantum.core.gates.TGate.html) gate and the eigenstate is $|1\\rangle$ , then we need to use the quantum phase estimation algorithm to find its corresponding eigenvalue, that is, we need to estimate the phase angle on the eigenvalue index.\n",
"\n",
"First import the relevant dependencies."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from mindquantum.core.gates import T, H, X, Power, BARRIER\n",
"from mindquantum.core.circuit import Circuit, UN\n",
"from mindquantum.simulator import Simulator\n",
"from mindquantum.algorithm.library import qft\n",
"import numpy as np"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[UN](https://www.mindspore.cn/mindquantum/docs/en/r0.11/core/circuit/mindquantum.core.circuit.UN.html) can specify quantum gates, target bits and control bits to build gate operations in the circuit; [Power](https://www.mindspore.cn/mindquantum/docs/en/r0.11/core/gates/mindquantum.core.gates.Power.html) can get the exponential form of the specified quantum gate. Because we know that the eigenstate of the [T](https://www.mindspore.cn/mindquantum/docs/en/r0.11/core/gates/mindquantum.core.gates.TGate.html) gate is $|1\\rangle$, the second register only needs 1 bit, and the more bits in the first register, the more accurate the result, here we use 4 bits.\n",
"\n",
"So we need to build a 5-bit circuit, $q_0, q_1, q_2, q_3$ bits are used for estimation, belong to the first register, and $q_4$ belong to the second register to pass in the eigenstate of the $T$ operator.\n",
"\n",
"Use [UN](https://www.mindspore.cn/mindquantum/docs/en/r0.11/core/circuit/mindquantum.core.circuit.UN.html) to perform [Hadamard](https://www.mindspore.cn/mindquantum/docs/en/r0.11/core/gates/mindquantum.core.gates.HGate.html) gate operation on $q_0, q_1, q_2, q_3$, and use [X](https://www.mindspore.cn/mindquantum/docs/en/r0.11/core/gates/mindquantum.core.gates.XGate.html) gate to flip $q_4$ to obtain the eigenstate $|1\\rangle$ of [T](https://www.mindspore.cn/mindquantum/docs/en/r0.11/core/gates/mindquantum.core.gates.TGate.html) gate."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"n = 4\n",
"circ = Circuit()\n",
"circ += UN(H, n) # Act h gate on the first 4 bits\n",
"circ += X.on(n) # Act X gate on q4\n",
"circ.svg()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With $q_4$ as the target bit, add the control $T^{2^i}$ gate."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"for i in range(n):\n",
" circ += Power(T, 2**i).on(n, n - i - 1) # Add T^2^i gate, where q4 is the target bit and n-i-1 is the control bit\n",
"circ.svg()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Perform an inverse quantum Fourier transform on the bits in the first register."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"circ += BARRIER\n",
"circ += qft(range(n)).hermitian() # Inverse transform of quantum Fourier transform applied to the first 4 bits\n",
"circ.svg()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Select the backend, pass in the total number of bits to create a simulator, evolve the quantum circuit, and get the final state."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"from mindquantum.core.gates import Measure\n",
"sim = Simulator('mqvector', circ.n_qubits) # Create an emulator\n",
"sim.apply_circuit(circ) # Evolving the circuit with the simulator\n",
"qs = sim.get_qs() # Obtain the evolved quantum state\n",
"res = sim.sampling(UN(Measure(), circ.n_qubits - 1), shots=100) # Add a measurement gate to register 1 and sample the circuit 100 times to obtain statistical results\n",
"res.svg()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It should be noted that the reading order of the measurement result as a binary string should be $|q_0q_1q_2q_3\\rangle$, so we get that the measurement result of register 1 is `0010`, the probability amplitude is 1, and the final state can accurately reflect the phase $\\varphi$. But `0010` is a binary result, so we convert it back to decimal and divide by $2^n$ to get our final estimate: $\\varphi=\\frac{2}{2^4}=\\frac{1}{8}$.\n",
"\n",
"We can also find out the position of the amplitude maximum $a_{max}$ in the first register by the quantum state `qs` obtained from the circuit evolution, and then obtain the corresponding eigenbasis vector $|x\\rangle$, where $x$ is divided by $2^t$ to be the estimated value of the phase."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10100\n"
]
}
],
"source": [
"index = np.argmax(np.abs(qs))\n",
"print(bin(index)[2:])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It should be noted that `qs` corresponds to the final state of the entire quantum circuit, so the obtained `index` also includes the bits in the second register, and the $|x\\rangle$ corresponding to $a_{max}$ in the final state of the first register cannot be directly obtained, and it is necessary to convert the `index` into binary and remove the bits corresponding to $q4$, and then the $|x\\rangle$ of the first register is obtained."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0010\n"
]
}
],
"source": [
"bit_string = bin(index)[2:].zfill(circ.n_qubits)[1:] # Convert index to 01 string and remove q4\n",
"bit_string = bit_string[::-1] # Adjust the bit string order to q0q1q2q3\n",
"print(bit_string)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Convert binary back to decimal again to get our final estimate."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.125"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"theta_exp = int(bit_string, 2) / 2**n\n",
"theta_exp"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It can be seen that the estimated phase obtained is approximately equal to $\\varphi$."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"