Simon’s algorithm
I’m going to use qiskit to study quantum algorithms in my own way. Since this is a record of my personal study, I may have left out a lot of explanations.
I am following the qiskit website.
In this article, I will try to understand Simon’s algorithm by following the formula.
The difference is that Simon’s algorithm determines whether the function $f(x)$ is a 1:1 function or a 2:1 function. The difference is that Simon’s algorithm sets up the problem to determine whether it is a 1:1 function or a 2:1 function, and then determines the period of the 2:1 function.
github
- The file in jupyter notebook format is here
google colaboratory
- If you want to run it in google colaboratory here
Author’s environment
!sw_vers
ProductName: Mac OS X
ProductVersion: 10.14.6
BuildVersion: 18G103
Python -V
Python 3.8.5
Import the basic libraries and check their versions.
%matplotlib inline
%config InlineBackend.figure_format = 'svg'
import matplotlib
import matplotlib.pyplot as plt
import scipy
import numpy as np
import pandas as pd
print('matplotlib version :', matplotlib.__version__)
print('scipy version :', scipy.__version__)
print('numpy version :', np.__version__)
print('pandas version :', pd.__version__)
matplotlib version : 3.3.2
scipy version : 1.5.2
numpy version : 1.19.2
pandas version : 1.1.3
import qiskit
import json
dict(qiskit.__qiskit_version__)
{'qiskit-terra': '0.17.4',
'qiskit-aer': '0.8.2',
'qiskit-ignis': '0.6.0',
'qiskit-ibmq-provider': '0.13.1',
'qiskit-aqua': '0.9.1',
'qiskit': '0.26.2',
'qiskit-nature': None,
'qiskit-finance': None,
'qiskit-optimization': None,
'qiskit-machine-learning': None}
from qiskit import IBMQ, Aer, execute
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, assemble, transpile
from qiskit.visualization import plot_histogram
from qiskit_textbook.tools import array_to_latex
Problem Setup
The problem is to determine whether the function $f(x)$ is a 1:1 function or a 2:1 function. 1:1 functions can be thought of as simple all-singular functions, such as $y=x$.
$$ \begin{aligned} &|00\rangle \stackrel{f}{\longrightarrow}| 00\rangle \\ &|01\rangle \stackrel{f}{\longrightarrow}| 01\rangle \\ &|10\rangle\stackrel{f}{\longrightarrow}| 10\rangle \\ &|11\rangle\stackrel{f}{\longrightarrow}| 11\rangle \end{aligned} $$
A 2:1 function is a function from N bits to N-1 bits, as shown below. Two input values correspond to one output value, and since it is 2:1, the number of bits is reduced by one.
$$ f:\lbrace 0,1 \rbrace^{n} \rightarrow \lbrace 0,1 \rbrace^{n-1} $$ $$ x\in{0,1}^{n} $$
A concrete example in two bits is as follows.
$$ \begin{aligned} &|00>\stackrel{f}{\longrightarrow}| 0\rangle \\ &|01>\stackrel{f}{\longrightarrow}| 1\rangle \\ &|10>\stackrel{f}{\longrightarrow}| 1\rangle \\ &|11>\stackrel{f}{\longrightarrow}| 0\rangle \end{aligned} $$
Since it is a 2:1 function, there is an N-bit array $a (a\ne |00\cdots\rangle)$ and
$$ f(x \oplus a)=f(x) $$
is satisfied.
To find out which function is which, we need to run the function at most, $2^{n-1}+1$ times. If you are lucky enough to get the same output twice in a row for different inputs, you will know that it is a 2:1 type function.
There are known algorithms on classical computers where the lower bound on the number of times is $\Omega\left(2^{n / 2}\right)$, but it still increases exponentially with $n$.
1. Initialize the input resistance of the two n qubits to 0
$$ \left|\psi_{1}\right\rangle=|0\rangle^{\otimes n}|0\rangle^{\otimes n} $$
2. Apply the adamantine gate to the first register as well
$$ \left|\psi_{2}\right\rangle=\frac{1}{\sqrt{2^{n}}} \sum_{x \in{0,1}^{n}}|x\rangle|0\rangle^{\otimes n} $$
The application of the adamantine gate to the qubit of $|0\rangle^{\otimes n} $$ is equivalent to the above, although it looks like this.
$$ |0\rangle^{\otimes n}\longmapsto \frac{1}{\sqrt{2}^{n}}\sum_{k=0}^{2^n-1}|k\rangle $$
3. Execute the query function to oracle
$$ \left|\psi_{3}\right\rangle=\frac{1}{\sqrt{2^{n}}} \sum_{x \in{0,1}^{n}}|x\rangle|f(x)\rangle $$
The quantum oracle stores the result of the function $f(x)$ in the second register. The above oracle is equivalent to the following oracle.
$$ \begin{aligned} \frac{1}{\sqrt{2}^{n}}\sum_{k=0}^{2^n-1}|k\rangle \otimes|0\rangle \longmapsto \frac{1}{\sqrt{2^{n}}}\displaystyle \sum_{k=0}^{2^n-1}| k\rangle \otimes|f(k)\rangle \end{aligned} $$
4. Measure the second quantum register
From the problem setup, the input $x$ of the function $f(x)$ can be mapped to two qubits.
For a given $x$, the XOR of that $x$ and the qubit $b$, $y=x \oplus b$, will be. If $b=|00\cdots 0\rangle$, it is a 1:1 function, and if it is non-zero, it is a 2:1 function. By using $x$ and $y$, the value of the first register will be as follows.
$$ \left|\psi_{4}\right\rangle=\frac{1}{\sqrt{2}}(|x\rangle+|y\rangle) $$
Correspondence table
The correspondence table between $x$ and $y=x \oplus b$ is as follows. $f(x)$ is a 2:1 functional type.
- If $b=|11\rangle$ and $n=2$.
$$ \begin{array}{|r|r|r|r|} \hline \mathrm{x} & \mathrm{f}(\mathrm{x}) & \mathrm{y}(=\mathrm{x} \oplus \mathrm{b}) & \mathrm{x} \cdot \mathrm{b} (\text{mod 2})\\ \hline 00 & 00 & 11 & 0 \\ 01 & 10 & 10 & 1 \\ 10 & 10 & 01 & 1 \\ 11 & 00 & 00 & 0 \\ \hline \end{array} $$
- For $b=|110\rangle$ and $n=3$
$$ \begin{array}{|r|r|r|r|} \hline \mathrm{x} & \mathrm{f}(\mathrm{x}) & \mathrm{y}(=\mathrm{x} \oplus \mathrm{b}) & \mathrm{x} \cdot \mathrm{b}(\text{mod 2}) \\ \hline 000 & 000 & 110 & 0 \\ 001 & 001 & 111 & 0 \\ 010 & 100 & 100 & 1 \\ 011 & 101 & 101 & 1 \\ 100 & 100 & 010 & 1 \\ 101 & 101 & 011 & 1 \\ 110 & 000 & 000 & 0 \\ 111 & 001 & 001 & 0 \\ \hline \end{array} $$
5. Apply the Adamant gate to the first register
Applying the adamantine gate to the $|\psi_4\rangle$ obtained in 4, we get the following.
$$ \left|\psi_{5}\right\rangle=\frac{1}{\sqrt{2^{n+1}}} \sum_{z \in{0,1}^{n}}\left[(-1)^{x \cdot z}+(-1)^{y-z}\right]|z\rangle $$
Formulas for Adamant Gates
Since the formula after the adamant transformation was mentioned in STEP 5, let’s calculate why it is so with a review.
$$ \left|\psi_{5}\right\rangle=\frac{1}{\sqrt{2^{n+1}}}\sum_{z \in\lbrace0,1\rbrace^{n}}\left[(-1)^{x \cdot z}+(-1)^{y \cdot z}\right]|z\ rangle $$
Express $|b\rangle$ in binary notation as follows. $b_{k}\in\lbrace0,1\rbrace^{n}$
$$ |b\rangle=\left|b_{n} b_{n-1} \cdots b_{1} b_{0}\right\rangle $$
Apply the adamantine gate to this $|b\rangle$
$$ \begin{aligned} H^{\otimes n}|b\rangle&=H^{\otimes n}\left|b_{n} b_{n-1} \cdots b_1 \right\rangle \\ &=\frac{1}{\sqrt{2^{n}}}\left(|0\rangle+(-1)^{b_n}|1\rangle\right)\otimes\left(|0\rangle+(-1)^{b_{n-1}}|1\rangle\right)\otimes \cdots \\ &=\frac{1}{\sqrt{2^{n}}}(\mid 00 \ldots 0\rangle+(-1)^{b_{1}}|00 \cdots 01\rangle \\ &\qquad \left.+(-1)^{b_{1}}|00 \cdots 01 0\right\rangle \left.+(-1)^{b_{2}+b_{1}}|00 \cdots 011\right\rangle \\ &\qquad \qquad \cdots \left.+(-1)^{b_{n}+b_{n-1}+\cdots+b_{2}+b_{1}}|11 \cdots 1)\right\rangle \\ &=\frac{1}{\sqrt{2^{n}}} \sum_{z \in\lbrace 0,1 \rbrace^n }(-1)^{b_{n} z_{n}+b_{n-1} z_{n-1}+\cdots+b_{1} z_{1}}|z\rangle \\ &=\frac{1}{\sqrt{2^{n}}} \sum_{z \in\lbrace0,1\rbrace^n}(-1)^{b \cdot z}|z\rangle \end{aligned} $$
This change is often seen in qiskit explanations, but it can be a stumbling block if you are not familiar with it as you follow the equation.
6. Measurement
When measuring the above $|\psi_5\rangle$, only $z$ that satisfies $(-1)^{x \cdot z}=(-1)^{y \cdot z}$ is measured. All other elements are zero.
$$ \begin{aligned} & x \cdot z=y \cdot z \\ & x \cdot z=(x \oplus b) \cdot z \\ & x \cdot z=x \cdot z \oplus b \cdot z \\ & b \cdot z=0(\bmod 2) \end{aligned} $$
Thus, the $z$ whose inner product with $b$ is zero is measured. By performing the measurement multiple times, we can obtain the following simultaneous linear equations, which can be solved using a classical computer to obtain the qubit $b$.
$$ \begin{array}{c} b \cdot z_{1}=0 \\ b \cdot z_{2}=0 \\ \vdots \\ b \cdot z_{n}=0 \end{array} $$
Solving this simultaneous linear equation identifies $b$, and if $b=|00 \cdots 0\rangle$, then it is a 1:1 function, otherwise it is a 2:1 function.
Normally, this would require an exponential amount of computation, but we can find the answer to the problem by taking roughly $n$ measurements and solving a simultaneous linear equation.
Review of phase kickback.
A note on phase kickback. If the unitary matrix on which the target bit acts is $U$ and its eigenvalue is $e^{i \phi}$, then the eigenvalue appears in the coefficient of $|1\rangle$ of the control bit. I think it means that it is kicked back to the control bit, not to the target bit.
$$ \begin{aligned} &\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \otimes|\psi\rangle \\ & \longrightarrow \frac{1}{\sqrt{2}}(|0\rangle \otimes|\psi\rangle+|1\rangle \otimes U|\psi\rangle) \\ &=\frac{1}{\sqrt{2}}\left(|0\rangle \otimes|\psi\rangle+e^{i \phi}|1\rangle \otimes|\psi\rangle\right) \\ &=\frac{1}{\sqrt{2}}\left(|0\rangle+e^{i \phi}|1\rangle\right) \otimes|\psi\rangle \end{aligned} $$
Example of unitary operators in qiskit with CNOT gates.
qc = QuantumCircuit(2)
qc.h(0)
qc.cx(0,1)
qc.draw('mpl')
backend = Aer.get_backend('statevector_simulator')
final_state = execute(qc,backend).result().get_statevector()
array_to_latex(final_state, pretext="\\\\\\\\text{Statevector} = ")
$\displaystyle \\text{Statevector} = \begin{bmatrix} \tfrac{1}{\sqrt{2}} \\ 0 \\ 0 \\ \tfrac{1}{\sqrt{2}} \end{bmatrix} $
CNOT gates and XOR
This one is just a note, but the CNOT gate is equivalent to replacing the target bit with an XOR of the control bit and the target bit. I’ll have to remember that.
$$ |i j\rangle \stackrel{\mathrm{CX}}{\longrightarrow}|i(i \mathrm{XOR} j)\rangle $$