Dioichi-Josa’s algorithm
I will be using 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 deepen my understanding of the Doichi-Josa algorithm by following the formulas.
It is my lack of study, but when I studied quantum information as a student, I did not know about the Doychi-Josa algorithm. It may not be as famous as Shore’s algorithm, but according to the qiskit website, it was the first quantum algorithm that was announced to have better performance than the classical algorithm, so I think it is essential to understand.
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 Dichi-Josa problem is to determine which type of function should be used, if the function is limited to constant or distributed types. In the case of the constant type, any input will return either 0 or 1. In the case of the distributed type, half the inputs will return 0, and the other half will return 1.
To think of it simply, if the first trial returns 0 and the second trial returns 1, we know it is a distributed type, but if the second trial is also 0, we cannot make a decision and have to repeat the trial again.
However, if the second attempt is also zero, the decision cannot be made and another attempt must be made. Using a quantum computer and applying the Doyich-Josa algorithm, it is possible to determine which type is which just by running $f(x)$ once.
I’m going to try my hand at this too, following the qiskit website .
The flow of the algorithm is as follows. This is also just a transcription of the above site.
1. Prepare the quantum bits.
Prepare $N$ qubits initialized to $|0\rangle$ and one qubit initialized to $|1\rangle$.
$$ \left|\psi_{0}\right\rangle=|0\rangle^{\otimes n}|1\rangle $$
2. Apply the Adamant Gate
Apply an adamantine gate to all qubits.
$$ \left|\psi_{1}\right\rangle=\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^{n}-1}|x\rangle(|0\rangle-|1\rangle) $$
Use the following formula.
$$ \begin{aligned} &|0\rangle \stackrel{H}{\longrightarrow} \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \\ &|1\rangle \stackrel{H}{\longrightarrow}\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{aligned} $$
Here, $|x\rangle$ represents the following state in 2-bit notation. $x_k$ is 0 or 1. A detailed example is [here](#bit notation).
$$ |x\rangle=\left|x_{n} x_{n-1} \cdots x_{2} x_{1} x_{0}\right\rangle $$
3. Applying the quantum oracle
Applying the quantum oracle that converts $|x\rangle|y\rangle=|x_{n} x_{n-1}\cdots x_{2} x_{1} x_{0}\rangle|y\rangle$ to $|x\rangle|y\oplus f(x)\rangle$, the $f(x)$ part is We can go out to the coefficients (global phase).
$$ \begin{aligned} \left|\psi_{2}\right\rangle &=\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^{n}-1}|x\rangle(|f(x)\rangle-|1 \oplus f(x)\rangle) \\ &=\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle(|0\rangle-|1\rangle) \end{aligned} $$
4. Apply the Adamant gate to the first n qubits
Now, if we ignore the last qubit $\displaystyle \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$.
$$ \begin{aligned} \left|\psi_{3}\right\rangle &=\frac{1}{2^{n}}\sum_{x=0}^{2^{n}-1}(-1)^{f(x)}\left[\sum_{y=0}^{2^{n}-1}(-1)^{x \cdot y}|y\rangle\right ] \\ &=\frac{1}{2^{n}}\sum_{y=0}^{2^{n}-1}\left[\sum_{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x \cdot y}\right]|y\rangle \end{aligned} $$
It becomes. $x \cdot y=x_{0} y_{0} \oplus x_{1} y_{1} \oplus \ldots \oplus x_{n-1} y_{n-1}$$ is the sum of bitwise products.
5. Measure the first N bits
Calculate the amplitude probability of $\displaystyle |0\rangle^{\otimes n}$ for the first N bits.
$$ \left|\frac{1}{2^{n}} \sum_{x=0}^{2^{n}-1}(-1)^{f(x)}\right|^{2} $$
The result is 1 if $f(x)$ is of constant type, and 0 if $f(x)$ is of distributed type.
Example of a 2-bit distributed function.
This is a copy of the site, but we’ll go over it a little bit as we understand it.
1. Initialize the qubit.
$$ \left|\psi_{0}\right\rangle=|00\rangle_{12}\otimes|1\rangle_{3} $$
2. Apply the Adamant gate to all qubits.
$$ \left|\psi_{1}\right\rangle=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle){12} \otimes \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle){3} $$
3. Implementing oracle functions
For distributed functions, oracle functions can be implemented with CX gates by using phase kickback. Since the operation is to do nothing if the control bit is 0, and to reverse the phase if it is 1, CX gates can be used.
$$ \begin{aligned} \left|\psi_{2}\right\rangle &=\frac{1}{\sqrt{2^{n+1}}} \sum_{x=0}^{2^{n}-1}|x\rangle(|f(x)\rangle-|1 \oplus f(x)\rangle) \\ &=\frac{1}{\sqrt{2^{n+1}}} \sum_{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle(|0\rangle-|1\rangle) \end{aligned} $$
4. Organize the expression
$$ \begin{aligned} \left|\psi_{2}\right\rangle &=\frac{1}{2 \sqrt{2}}\left[|00\rangle_{12} \otimes(|0\rangle-|1\rangle){3}-|01\rangle{12} \otimes(|0\ rangle-|1\rangle){3}-|10\rangle{12}\otimes(|0\rangle-|1\rangle){3}+|11\rangle{12}\otimes(|0\rangle-|1\rangle){3}\right] \\ &=\frac{1}{2}(|00\rangle-|01\rangle-|10\rangle+|11\rangle){12}\otimes \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle){3} \\ &=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle){1}\otimes\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle){2}\otimes\frac{1}{\sqrt{2}}(|0\rangle -|1\rangle){3} \end{aligned} $$
It’s very simple.
5. Apply the Adamant gate to the first qubit.
$$ \left|\psi_{3}\right\rangle=|1\rangle_{1}\otimes|1\rangle_{2}\otimes(|0\rangle-|1\rangle)_{3} $$
6. Measure the first two qubits
If we measure the first two qubits, we get $|11\rangle$, indicating that the distribution is a function.
Notation for applying an Adamant gate to multiple qubits.
Now that we have a quick look at the formula for the operation of an adamantine gate to multiple qubits, let’s check it out by doing a quick calculation.
$$ \left|x\right\rangle \stackrel{H}{\rightarrow}\frac{1}{\sqrt{2^n}}\left(\sum_{y=0}^{2^{n}-1}(-1)^{x \cdot y}|y\rangle\right) $$
However, $x \cdot y$ is the sum of bitwise products.
$$ x \cdot y=x_{0} y_{0} \oplus x_{1} y_{1} \oplus \ldots \oplus x_{n-1} y_{n-1} $$
Bit notation
Often, when we see a sigma symbol like the following, we see $|3\rangle$, which we need to convert in our mind to bit notation.
$$ \sum_{y=0}^{2^{n}-1}(-1)^{x \cdot y}|y\rangle $$
If $x$ is included in the bla symbol, it means a quantum state like the following.
$$ |x\rangle = |x_nx_{n-1}\cdots x_2x_1x_0\rangle $$
The specific notation for three qubits is as follows: $$ x_k$ can only be 0 or 1.
$$ \begin{aligned} &|0\rangle=|000\rangle \\ &|1\rangle=|001\rangle \\ &|2\rangle=|010\rangle \\ &|3\rangle=|011\rangle \\ &|4\rangle=|100\rangle \\ &|5\rangle=|101\rangle \\ &|6\rangle=|110\rangle \\ &|7\rangle=|111\rangle \end{aligned} $$
Check.
Start with the first bit.
$$ \begin{aligned} &|0\rangle \stackrel{H}{\rightarrow}\frac{1}{\sqrt{2}}\sum_{y=0}^{1}(-1)^{0 \cdot y}|y\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \\ &|1\rangle\stackrel{H}{\rightarrow}\frac{1}{\sqrt{2}}\sum_{y=0}^{1}(-1)^{1\cdot y}|y\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{aligned} $$
One bit is easy to understand, so let’s calculate two bits by hand. We will also use qiskit to check the answer.
Let’s start with $|00\rangle$.
qc = QuantumCircuit(2)
qc.h(0)
qc.h(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}{2} \\ \tfrac{1}{2} \\ \tfrac{1}{2} \\ \tfrac{1}{2} \end{bmatrix} $
Let’s calculate it by hand.
$$ \begin{aligned} \mid 00) &\stackrel{H}{\rightarrow} \frac{1}{\sqrt{2^2}} \sum_{y=0}^{3}(-1)^{x \cdot y}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\sum_{y=0}^{3}(-1)^{x_{0} y_{0}+x_{1}, y_{1}}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\sum_{y=0}^{3}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right) \end{aligned} $$
and we see that they match.
$|01\rangle$.
qc = QuantumCircuit(2)
qc.x(0)
qc.h(0)
# qc.x(1)
qc.h(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}{2} \\ -\tfrac{1}{2} \\ \tfrac{1}{2} \\ -\frac{1}{2} \end{bmatrix} $
$$ \begin{aligned} \mid 01) &\stackrel{H}{\rightarrow}\frac{1}{\sqrt{2^2}}\sum_{y=0}^{3}(-1)^{x \cdot y}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\sum_{y=0}^{3}(-1)^{x_{0} y_{0}+x_{1}, y_{1}}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\sum_{y=0}^{3}(-1)^{y_{0}}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right) \end{aligned} $$ and this is also consistent.
$|10\rangle$.
qc = QuantumCircuit(2)
qc.x(1)
qc.h(0)
qc.h(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}{2} \\ \tfrac{1}{2} \\ -\tfrac{1}{2} \\ \frac{1}{2} \end{bmatrix} $
$$ \begin{aligned} \mid 10) &\stackrel{H}{\rightarrow}\frac{1}{\sqrt{2^2}}\sum_{y=0}^{3}(-1)^{x \cdot y}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\sum_{y=0}^{3}(-1)^{x_{0} y_{0}+x_{1}, y_{1}}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\sum_{y=0}^{3}(-1)^{y_{1}}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right) \end{aligned} $$
$|11\rangle$.
qc = QuantumCircuit(2)
qc.x(0)
qc.h(0)
qc.x(1)
qc.h(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}{2} \\ -\tfrac{1}{2} \\ -\tfrac{1}{2} \\ \tfrac{1}{2} \end{bmatrix} $
$$ \begin{aligned} \mid 11) &\stackrel{H}{\rightarrow}\frac{1}{\sqrt{2^2}}\sum_{y=0}^{3}(-1)^{x \cdot y}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\sum_{y=0}^{3}(-1)^{x_{0} y_{0}+x_{1}, y_{1}}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\sum_{y=0}^{3}(-1)^{y_{0} + y_{1}}|y\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned} $$
This is also a match. It’s easy, but it’s a little complicated with the bit notation in bra, but once you get used to it, it’s not so complicated.
Creating a quantum oracle
This section explains how to create a quantum oracle as an actual quantum circuit.
The quantum oracle $f(x)$ looks like the following circuit.
$$ |x\rangle|y\rangle \rightarrow |x\rangle|y\oplus f(x)\rangle $$
Therefore, if $f(x)$ is divided by constant type or distributed type, it can be easily written.
For constant type functions
- if $f(x)=0$, from $|x\rangle|y \oplus f(x)\rangle$, there is no need to do anything to the qubit in register 2, so apply the $I$ gate. 2.
In the case of $f(x)=1$, we only need to apply the $X$ gate.
In the case of distributive type
As mentioned above, each qubit in register 1 is the control bit, and the qubit in register 2 is the target, so we can apply the CX gate.
It is amazing that people can think of such an algorithm. I’m going to study Simon’s algorithm next.