bernstein-vazirani.ipynb

Kernel: Python 3

ベルンシュタイン・ヴァジラニ アルゴリズム

本節では、まず、ベルンシュタイン・ヴァジラニ問題と、それを解くための古典的アルゴリズムと量子アルゴリズムを紹介します。次に、Qiskitを用いて量子アルゴリズムを実装し、シミュレーターと実デバイス上でそれぞれ実行します。

1. ベルンシュタイン・ヴァジラニ アルゴリズム

参考文献[1]で最初に紹介されたベルンシュタイン・ヴァジラニ アルゴリズムは、前節で取り上げたドイチ・ジョザ アルゴリズムの拡張として見ることができます。このアルゴリズムは、ドイチ・ジョザ問題と比較して、より複雑な問題の計算ツールとして量子コンピューターを使用することに利点があることを示しました。

1.1 ベルンシュタイン・ヴァジラニ問題

我々は再び、以下のような隠されたブール関数$f$を与えられます。この関数は、ビットの文字列 ($x$) を入力として受け取り、$0$か$1$のどちらかを返します。
$$f({x_0,x_1,x_2,...}) \rightarrow 0 \textrm{ or } 1 \textrm{ where } x_n \textrm{ is }0 \textrm{ or } 1$$

ドイチ・ジョザ問題のように、均等(balanced)または一定(constant)な関数のどちらかになるのではなく、この関数は入力xと文字列sのビットごとの内積を返すことが保証されています。つまり、入力$x$について$f(x) = s \cdot x , \text{(mod 2)}$を満たす関数です。我々は、そのときの$s$を見つけることを期待されています。リバーシブルな古典回路としてのベルンシュタイン・ヴァジラニのオラクルは以下のようにかけます。

1.2 古典的な解法

古典的には、オラクルは入力$x$に対して $$f_s(x) = s \cdot x \mod 2$$ を返します。隠れたビット文字列 $s$ の各ビットは以下の入力のシーケンスをオラクルに問合せすることで洗い出されます。

Input(x) :-: 100...0 010...0 001...0 000...1

例えば、x = 1000...0 により $s$ (ビット $s_i$)の一番小さい桁のビットをみつけることができます。x = 0100...0 により $s$ の二番目に小さい桁のビットをみつけることができます。つまり、関数$f_s(x)$を $n$ 回呼び出す必要があります

1.3 量子的な解法

量子コンピューターを使うと、関数 $f(x)$を1回呼び出すだけで、この問題を100%の確度で解くことができます。隠れたビット文字列を見つける量子ベルンシュタイン・ヴァジラニ アルゴリズムは非常にシンプルです。

1. 入力量子ビットを$|0\rangle^{\otimes n}$ に、出力量子ビットを$|{-}\rangle$状態に初期化

2. アダマールゲートを入力量子ビットに適用

3. オラクルをクエリ

4. 入力レジスタにアダマールゲートを適用

5. 測定

アルゴリズムを説明するために、各量子ビットにアダマールゲートを適用したときに何が起きるのかをみてみましょう。$n$量子ビットの量子状態$|a\rangle$ にアダマールゲートを適用すると以下の変換をみることができます。

$$|a\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in {0,1}^n} (-1)^{a\cdot x}|x\rangle.$$

式を説明する (クリックして開く)

アダマールゲートは1つの量子ビットに対して次のような変換を行うことを思い出しましょう。

$$H|0\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$$

総和記号を使うことで、以下のように書き換えられます。

$$H|a\rangle = \frac{1}{\sqrt{2}}\sum_{x\in {0,1}} (-1)^{a\cdot x}|x\rangle.$$

2つの量子ビットに対して、それぞれにアダマールゲートを適用すると、次のような変換が行われます。

$$H^{\otimes 2}|00\rangle = \tfrac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$$

総和記号で、以下のようにまとめて表現することができます。

$$H^{\otimes 2}|a\rangle = \frac{1}{2}\sum_{x\in {0,1}^2} (-1)^{a\cdot x}|x\rangle$$

最初の式にたどり着く方法がこれで理解できるかと思います。

特に、$|00\dots 0\rangle$に初期化された量子レジスタから始めて、 $n$個のアダマールゲートをかけると、おなじみの量子重ね合わせができます。

$$|00\dots 0\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in {0,1}^n} |x\rangle$$

この場合、$a=0$により$(-1)^{a\cdot x} = 1$ となることから、位相$(-1)^{a\cdot x}$ が消えます。

さて、古典のオラクル $f_s$ は、$s \cdot x\mod 2 = 1$を満たす任意の入力 $x$ に対して $1$を、それ以外のときは $0$ を返します。ドイチ・ジョザでも用いた$|{-}\rangle$に対する位相キックバックのテクニックを利用することで、以下の変換を得られます。

$$|x \rangle \xrightarrow{f_s} (-1)^{s\cdot x} |x \rangle$$

隠れた文字列を明らかにするアルゴリズムは、$|00\dots 0\rangle$のアダマール変換から得られた量子的な重ね合わせで、量子オラクル$f_s$を問い合わせることで、自然に次のようになります。

$$|00\dots 0\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in {0,1}^n} |x\rangle \xrightarrow{f_a} \frac{1}{\sqrt{2^n}} \sum_{x\in {0,1}^n} (-1)^{a\cdot x}|x\rangle$$

$n$ 個のアダマールゲートの逆行列は、再び $n$ 個のアダマールゲートなので、次のようにして $a$ を求めることができます。

$$\frac{1}{\sqrt{2^n}} \sum_{x\in {0,1}^n} (-1)^{a\cdot x}|x\rangle \xrightarrow{H^{\otimes n}} |a\rangle$$

2. 具体例

$n=2$ の量子ビットと秘密の文字列 $s=11$ で具体的な例を見てみましょう。ここでは、参考文献 [2] の定式に従って、1つのレジスタだけを使ってベルンシュタイン・ヴァジラニ量子オラクルのための回路を生成していることに注意してください。

1. 2つの量子ビットのレジスタは0に初期化されています。

$$\lvert \psi_0 \rangle = \lvert 0 0 \rangle$$

両方の量子ビットにアダマールゲートを適用します。

$$\lvert \psi_1 \rangle = \frac{1}{2} \left( \lvert 0 0 \rangle + \lvert 0 1 \rangle + \lvert 1 0 \rangle + \lvert 1 1 \rangle \right)$$

文字列 $s=11$ に対して、量子オラクルは以下の演算を行います。
$$|x \rangle \xrightarrow{f_s} (-1)^{x\cdot 11} |x \rangle.$$

$$\lvert \psi_2 \rangle = \frac{1}{2} \left( (-1)^{00\cdot 11}|00\rangle + (-1)^{01\cdot 11}|01\rangle + (-1)^{10\cdot 11}|10\rangle + (-1)^{11\cdot 11}|11\rangle \right)$$$$\lvert \psi_2 \rangle = \frac{1}{2} \left( \lvert 0 0 \rangle - \lvert 0 1 \rangle - \lvert 1 0 \rangle + \lvert 1 1 \rangle \right)$$

両方の量子ビットにアダマールゲートを適用します。

$$\lvert \psi_3 \rangle = \lvert 1 1 \rangle$$

秘密の文字列$s=11$ を見つけるために測定します。

以下のウィジェット bv_widget を活用してください。ボタンを押してそれぞれのステップを適用し、アルゴリズムを実行してみてください。最初の2つの位置引数によって、入力量子ビットの数と秘密の文字列の値を変更することができます。

from qiskit_textbook.widgets import bv_widget
bv_widget(2, "11")

HBox(children=(Button(description='H⊗ⁿ', style=ButtonStyle()), Button(description='Oracle', style=ButtonStyle(…

HTMLMath(value='$$ |00\\rangle = |00\\rangle $$')

Image(value=b'\x89PNG\r\n\x1a\n\x00\x00\x00\rIHDR\x00\x00\x00\xce\x00\x00\x00\xcc\x08\x06\x00\x00\x00;\xd7\x9c…

3. Qiskitを用いた実装

ここで、$s=011$の3量子ビットの関数について、Qiskitでのベルンシュタイン・ヴァジラニ アルゴリズムの実装を見ていきましょう。

# initialization
import matplotlib.pyplot as plt
import numpy as np

# importing Qiskit
from qiskit import IBMQ, Aer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, transpile

# import basic plot tools
from qiskit.visualization import plot_histogram

まず、実験で使用する量子ビット数と、アルゴリズムが求める隠れたビット文字列 $s$を設定します。隠れたビット文字列 $s$ は、量子オラクルの回路を決定します。

n = 3 # number of qubits used to represent s
s = '011'   # the hidden binary string

その後、Qiskitを使用してベルンシュタイン・ヴァジラニ アルゴリズムをプログラムします。

# We need a circuit with n qubits, plus one auxiliary qubit
# Also need n classical bits to write the output to
bv_circuit = QuantumCircuit(n+1, n)

# put auxiliary in state |->
bv_circuit.h(n)
bv_circuit.z(n)

# Apply Hadamard gates before querying the oracle
for i in range(n):
    bv_circuit.h(i)
    
# Apply barrier 
bv_circuit.barrier()

# Apply the inner-product oracle
s = s[::-1] # reverse s to fit qiskit's qubit ordering
for q in range(n):
    if s[q] == '0':
        bv_circuit.i(q)
    else:
        bv_circuit.cx(q, n)
        
# Apply barrier 
bv_circuit.barrier()

#Apply Hadamard gates after querying the oracle
for i in range(n):
    bv_circuit.h(i)

# Measurement
for i in range(n):
    bv_circuit.measure(i, i)

bv_circuit.draw()

3a. シミュレーターでの実験

上記の回路をシミュレーター上で実行できます。

# use local simulator
aer_sim = Aer.get_backend('aer_simulator')
shots = 1024
results = aer_sim.run(bv_circuit).result()
answer = results.get_counts()

plot_histogram(answer)

測定の結果が隠された文字列 011 であることが分かります。

3b. 実デバイスでの実験

以下のように実デバイス上で回路を動作させることができます。

# Load our saved IBMQ accounts and get the least busy backend device with less than or equal to 5 qubits
IBMQ.load_account()
provider = IBMQ.get_provider(hub='ibm-q')
provider.backends()
backend = least_busy(provider.backends(filters=lambda x: x.configuration().n_qubits <= 5 and
                                   x.configuration().n_qubits >= 2 and
                                   not x.configuration().simulator and x.status().operational==True))
print("least busy backend: ", backend)

least busy backend:  ibmq_quito

# Run our circuit on the least busy backend. Monitor the execution of the job in the queue
from qiskit.tools.monitor import job_monitor

shots = 1024
transpiled_bv_circuit = transpile(bv_circuit, backend)
job = backend.run(transpiled_bv_circuit, shots=shots)

job_monitor(job, interval=2)

Job Status: job has successfully run

# Get the results from the computation
results = job.result()
answer = results.get_counts()

plot_histogram(answer)

見ての通り、ほとんどの結果は011です。他の結果は量子計算の誤差によるものです。

4. 演習

1. 以下のウィジットを使用してベルンシュタイン・ヴァジラニ アルゴリズムが異なるオラクルで動く様子を確認してください。

from qiskit_textbook.widgets import bv_widget
bv_widget(3, "011", hide_oracle=False)

HBox(children=(Button(description='H⊗ⁿ', style=ButtonStyle()), Button(description='Oracle', style=ButtonStyle(…

HTMLMath(value='$$ |000\\rangle = |000\\rangle $$')

Image(value=b'\x89PNG\r\n\x1a\n\x00\x00\x00\rIHDR\x00\x00\x00\xce\x00\x00\x01\x08\x08\x06\x00\x00\x00\x17\xd9\…

1. 上記のベルンシュタイン・ヴァジラニの 実装 は、秘密のビット文字列$s = 011$の場合のものです。秘密の文字列 $s = 1011$ の場合を実装してください。結果は期待通りでしたか？説明してみてください。

2. 上記のベルンシュタイン・ヴァジラニの 実装 は、秘密のビット文字列$s = 011$の場合のものです。秘密の文字列 $s = 11101101$ の場合を実装してください。結果は期待通りでしたか？説明してみてください。

5. 参考文献

1. Ethan Bernstein and Umesh Vazirani (1997) "Quantum Complexity Theory" SIAM Journal on Computing, Vol. 26, No. 5: 1411-1473, doi:10.1137/S0097539796300921.

2. Jiangfeng Du, Mingjun Shi, Jihui Wu, Xianyi Zhou, Yangmei Fan, BangJiao Ye, Rongdian Han (2001) "Implementation of a quantum algorithm to solve the Bernstein-Vazirani parity problem without entanglement on an ensemble quantum computer", Phys. Rev. A 64, 042306, 10.1103/PhysRevA.64.042306, arXiv:quant-ph/0012114.

import qiskit.tools.jupyter
%qiskit_version_table

/usr/local/anaconda3/envs/terra-unstable/lib/python3.9/site-packages/qiskit/aqua/__init__.py:86: DeprecationWarning: The package qiskit.aqua is deprecated. It was moved/refactored to qiskit-terra For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>
  warn_package('aqua', 'qiskit-terra')