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

• 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}$$