Skip to main content
IBM Quantum Platform

Deutsch-Jozsaアルゴリズム

Deutschのアルゴリズムは、クエリ問題では古典的なアルゴリズムよりも優れているが、その優位性は1クエリ対2クエリという極めてささやかなものである。 Deutsch-Jozsaアルゴリズムは、この利点を拡張するもので、実際、2つの異なるクエリー問題を解くのに使うことができる。

ドイチュ・ヨッサ・アルゴリズムの量子回路の説明である。 図には示されていないが、解決しようとする特定の問題によっては、さらに古典的な後処理ステップが必要になることもある。

ドイチュ・ヨッサ・アルゴリズム

もちろん、このアルゴリズムがどのような問題を解決するのかについては、実際には議論していない。

ドイッチュ＝ヨージャ問題

まず、Deutsch-Jozsaアルゴリズムが元々解こうとしていたクエリー問題（ Deutsch-Jozsa問題として知られている）から始めよう。

この問題の入力関数は、任意の正の整数 nn に対して、 f:Σn→Σf:\Sigma^n \rightarrow \Sigma という形をとる。 ドイッチュの問題と同様に、この課題は、 ff が定数である場合に 00 を出力し、 ff が平衡である場合に 11 を出力することである。これは、関数が値 00 をとる入力文字列の数が、関数が値 11 をとる入力文字列の数と等しいことを意味する。

nn が 11 より大きい場合、 f:Σn→Σf:\Sigma^n \rightarrow \Sigma という形の関数の中には、定数でもなく、平衡でもな いものがあることに注意してください。 たとえば、次のように定義された関数 f:Σ2→Σf:\Sigma^2\rightarrow\Sigma は、

f(00)=0f(01)=0f(10)=0f(11)=1\begin{aligned} f(00) & = 0 \\ f(01) & = 0 \\ f(10) & = 0 \\ f(11) & = 1 \end{aligned}

この2つのカテゴリーには当てはまらない。 Deutsch-Jozsa問題では、このような関数は気にしない。 つまり、この問題では、 ff が一定か均衡のどちらかであるという約束がある。

Deutsch-Jozsa problem

入力：関数 f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\} \ 約束： ff が一定か均衡のいずれかである。 \ 出力： ff が定数なら 00, ff が釣り合いなら 11

Deutsch-Jozsaアルゴリズムは、単一のクエリを用いて、以下の意味でこの問題を解決する。 nn の測定結果のすべてが 00 である場合、関数 ff は定数である。 それ以外の場合、すなわち測定結果のうち少なくとも1つが 11 である場合、関数 ff は平衡である。 別の言い方をすれば、上述の回路の後に、測定結果の論理和（OR）を計算して、ドイッチュ・ジョザ問題の出力ビットを生成する、古典的な後処理ステップが続くということである。

アルゴリズム分析

Deutsch-Jozsa問題に対するDeutsch-Jozsaアルゴリズムの性能を分析するためには、ハダマードゲートの単一層の作用について考えることから始めると役に立つ。 ハダマード演算は、通常の方法で行列として表すことができる、

H=(121212−12),H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix},

しかし、この操作を標準的な基底状態に対する作用という観点から表現することもできる：

H∣0⟩=12∣0⟩+12∣1⟩H∣1⟩=12∣0⟩−12∣1⟩.\begin{aligned} H \vert 0\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle\\[3mm] H \vert 1\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 \rangle. \end{aligned}

この2つの方程式は1つの式にまとめることができる、

H∣a⟩=12∣0⟩+12(−1)a∣1⟩=12∑b∈{0,1}(−1)ab∣b⟩,H \vert a \rangle = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} (-1)^a \vert 1 \rangle = \frac{1}{\sqrt{2}} \sum_{b\in\{0,1\}} (-1)^{ab} \vert b\rangle,

これは、 a∈Σa\in\Sigma のいずれの値を選んでも成り立つ。

ここで、1つの量子ビットの代わりに nn、それぞれの量子ビットに対してハダマード演算が行われたとする。 nn 量子ビットの複合演算は、テンソル積 H⊗⋯⊗HH\otimes \cdots \otimes H （ nn 回）によって記述される。ここでは簡潔かつ明瞭にするために H⊗nH^{\otimes n} と表記する。 上記の公式を使い、展開して単純化すると、 nn の標準基底状態に対するこの複合操作の作用を次のように表すことができる：

H⊗n∣xn−1⋯x1x0⟩=(H∣xn−1⟩)⊗⋯⊗(H∣x0⟩)=(12∑yn−1∈Σ(−1)xn−1yn−1∣yn−1⟩)⊗⋯⊗(12∑y0∈Σ(−1)x0y0∣y0⟩)=12n∑yn−1⋯y0∈Σn(−1)xn−1yn−1+⋯+x0y0∣yn−1⋯y0⟩.\begin{aligned} & H^{\otimes n} \vert x_{n-1} \cdots x_1 x_0 \rangle \\ & \qquad = \bigl(H \vert x_{n-1} \rangle \bigr) \otimes \cdots \otimes \bigl(H \vert x_{0} \rangle \bigr) \\ & \qquad = \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{n-1}\in\Sigma} (-1)^{x_{n-1} y_{n-1}} \vert y_{n-1} \rangle \Biggr) \otimes \cdots \otimes \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{0}\in\Sigma} (-1)^{x_{0} y_{0}} \vert y_{0} \rangle \Biggr) \\ & \qquad = \frac{1}{\sqrt{2^n}} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle. \end{aligned}

ちなみにここでは、Qiskitのインデックス表記規則に従い、長さ nn のバイナリ文字列を xn−1⋯x0x_{n-1}\cdots x_0 および yn−1⋯y0y_{n-1}\cdots y_0 と表記しています。

この式は、上記の量子回路を解析するための便利なツールを提供してくれる。 ハダマードゲートの第1層が実行された後、 n+1n+1 の量子ビット（左端/下端の量子ビットを含み、他とは別に扱われる）の状態は次のようになる

(H∣1⟩)(H⊗n∣0⋯0⟩)=∣−⟩⊗12n∑xn−1⋯x0∈Σn∣xn−1⋯x0⟩.\bigl( H \vert 1 \rangle \bigr) \bigl( H^{\otimes n} \vert 0 \cdots 0 \rangle \bigr) = \vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \vert x_{n-1} \cdots x_0 \rangle.

UfU_f、この状態は次のように変換される

∣−⟩⊗12n∑xn−1⋯x0∈Σn(−1)f(xn−1⋯x0)∣xn−1⋯x0⟩\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \vert x_{n-1} \cdots x_0 \rangle

ドイチュのアルゴリズムの分析で見られたのとまったく同じ位相キックバック現象によって。

次に、2層目のハダマードゲートが実行され、（上式によって）この状態は次のように変換される

∣−⟩⊗12n∑xn−1⋯x0∈Σn∑yn−1⋯y0∈Σn(−1)f(xn−1⋯x0)+xn−1yn−1+⋯+x0y0∣yn−1⋯y0⟩.\vert - \rangle \otimes \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0) + x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle.

この式は少々複雑に見え、関数 ff についてさらに詳しい情報がなければ、さまざまな測定結果が得られる確率についてあまり多くのことは結論づけられません。

幸いなことに、私たちが知る必要があるのは、すべての測定結果が 00 である確率だけである。それは、 ff が一定であるとアルゴリズムが判断する確率だからである。 この確率には簡単な公式がある。

∣12n∑xn−1⋯x0∈Σn(−1)f(xn−1⋯x0)∣2={1if f is constant0if f is balanced\Biggl\vert \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \Biggr\vert^2 = \begin{cases} 1 & \text{if $f$ is constant}\\[1mm] 0 & \text{if $f$ is balanced} \end{cases}

なお、これらの値は、 ∣0⊗n⟩\vert 0^{\otimes n} \rangle という状態が観測される確率に対応するものであり、 ドイッチュ・ジョザ問題の最終的な古典的な出力ビットに直接対応するものではないことに注意してください。 このアルゴリズムは、すべての測定結果が 00（ffが定数であることを示す）である場合に00を出力し、それ以外の場合は 11を出力する （ffが平衡状態にあることを示す）。

より詳しく説明すると、 ff が定数である場合、すべての文字列 xn−1⋯x0x_{n-1}\cdots x_0 に対して f(xn−1⋯x0)=0f(x_{n-1}\cdots x_0) = 0 が成り立つか、 その場合は和の値は 2n2^n となるか、あるいはすべての文字列 xn−1⋯x0x_{n-1}\cdots x_0 に対して f(xn−1⋯x0)=1f(x_{n-1}\cdots x_0) = 1 が成り立つか、 その場合は和の値は −2n-2^n となる。 これを 2n2^n で割り、絶対値の二乗をとると、 11 となる。

一方、 ff が平衡である場合、 ff は、文字列 xn−1⋯x0x_{n-1}\cdots x_0 の半分については 00 という値を取り、残りの半分については 11 という値を取る。したがって、和に含まれる +1+1 という項と −1-1 という項は相殺され、最終的に 00 という値が残る。

約束が果たされる限り、アルゴリズムは正しく動作すると結論づける。

古典的難度

Deutsch-Jozsaアルゴリズムは毎回機能し、約束が守られれば常に正しい答えを出し、クエリーは1回で済む。 Deutsch-Jozsa問題に対する古典的なクエリーアルゴリズムと比較してどうか？

まず、Deutsch-Jozsa問題を正しく解く決定論的古典アルゴリズムは、指数関数的に多くの問い合わせを行わなければならない： 2n−1+12^{n-1} + 1 最悪の場合、クエリーは指数関数的に多くなる。 その理由は、もし決定論的アルゴリズムが ff、 2n−12^{n-1} 以下の異なる文字列を問い合わせ、毎回同じ関数値を得るなら、両方の答えが可能であるということだ。 関数は一定かもしれないし、バランスが取れているかもしれないが、運が悪いことにクエリーはすべて同じ関数値を返す。

しかし、決定論的アルゴリズムにはランダム性や不確実性がないため、特定の関数でシステマティックに失敗することになる。 従って、この点では古典的アルゴリズムよりも量子の方が大きな利点がある。

しかし、 確率的な古典的アルゴリズムは、わずか数回のクエリーで非常に高い確率でDeutsch-Jozsa問題を解くことができるというキャッチがある。 特に、長さ nn の数種類の文字列をランダムに選び、それらの文字列に対して ff 問い合わせた場合、 ff のバランスが取れたときに、すべての文字列に対して同じ関数値が得られる可能性は低い。

具体的には、 kk の入力文字列 x1,…,xk∈Σnx^1,\ldots,x^k \in \Sigma^n を一様確率でランダムに選び、 f(x1),…,f(xk)f(x^1),\ldots,f(x^k) を評価し、関数の値がすべて同じ場合は 00 と答え、そうでない場合は 11 と答えるようにすると、 ff が定数である場合は常に正解となり、 ff が均衡状態にある場合には、確率 2−k+12^{-k + 1} で誤答することになる。 例えば、 k=11k = 11 の場合、このアルゴリズムは確率 99.999.9 ％を超えて正解する。

このような理由から、古典的アルゴリズムに対する量子の利点はまだ控えめであるが、それでもドイチュのアルゴリズムに対する改善を示す定量的な利点である。

Deutsch-Jozsa with Qiskit

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

QiskitでDeutsch-Jozsaアルゴリズムを実装するために、まずDeutsch-Jozsa問題の約束を満たす関数をランダムに選び、クエリーゲートを実装した量子回路を生成する関数 dj_query 。 50％の確率で機能は一定であり、50％の変化で機能は均衡する。 この2つの可能性のそれぞれについて、そのタイプの関数から一様に関数が選択される。 引数は関数の入力ビット数。

def dj_query(num_qubits):
    # Create a circuit implementing for a query gate for a random function
    # satisfying the promise for the Deutsch-Jozsa problem.

    qc = QuantumCircuit(num_qubits + 1)

    if np.random.randint(0, 2):
        # Flip output qubit with 50% chance
        qc.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance
        return qc

    # Choose half the possible input strings
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc.x(qubit)
        return qc

    for state in on_states:
        qc.barrier()  # Barriers are added to help visualize how the functions are created.
        qc = add_cx(qc, f"{state:0b}")
        qc.mcx(list(range(num_qubits)), num_qubits)
        qc = add_cx(qc, f"{state:0b}")

    qc.barrier()

    return qc

クエリーゲートの量子回路実装は、通常通り draw 。

display(dj_query(3).draw(output="mpl"))

Output:

Output of the previous code cell

次に、クエリーゲートの量子回路実装を引数として、Deutsch-Jozsa回路を作成する関数を定義する。

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in the Deutsch-Jozsa algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)
    qc.h(range(n + 1))
    qc.compose(function, inplace=True)
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

最後に、Deutsch-Jozsa回路を一度実行する関数が定義されている。

def dj_algorithm(function: QuantumCircuit):
    # Determine if a function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if "1" in measurements[0]:
        return "balanced"
    return "constant"

ランダムに関数を選び、その関数に対するクエリゲートの量子回路実装を表示し、その関数に対してDeutsch-Jozsaアルゴリズムを実行することで、我々の実装をテストすることができる。

f = dj_query(3)
display(f.draw("mpl"))
display(dj_algorithm(f))

Output:

Output of the previous code cell 
'balanced'

バーンスタイン＝ヴァジラニ問題

次に、 バーンスタイン＝ヴァジラニ問題として知られる問題について説明しよう。 これはフーリエ・サンプリング問題とも呼ばれるが、この問題にはもっと一般的な定式化もあり、その名前でも呼ばれている。

まず、いくつかの記号について説明しましょう。 長さが nn である任意の 2 つの 2 進文字列 x=xn−1⋯x0x = x_{n-1} \cdots x_0 および y=yn−1⋯y0y = y_{n-1}\cdots y_0 について、次のように定義する

x⋅y=xn−1yn−1⊕⋯⊕x0y0.x \cdot y = x_{n-1} y_{n-1} \oplus \cdots \oplus x_0 y_0.

この演算を 2進ドット積と呼ぶことにする。 別の言い方をすれば、こうなる。

x⋅y={1xn−1yn−1+⋯+x0y0 is odd0xn−1yn−1+⋯+x0y0 is evenx \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is odd}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is even} \end{cases}

これは対称的な操作であることに注意してください。つまり、 xx と yy を入れ替えても結果は変わらないため、都合の良いときはいつでも自由に入れ替えることができます。 場合によっては、2進内積 x⋅yx \cdot y を、文字列 yy が 11 を含む位置における xx のビットのパリティ、あるいは同等に、文字列 xx が 11 を含む位置における yy のビットのパリティとして考えることが有用な場合があります。

この表記法を手にして、我々は今、Bernstein-Vazirani問題を定義することができる。

Bernstein-Vazirani problem

入力：関数 f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\} \ 約束：すべての x∈Σnx\in\Sigma^n に対して f(x)=s⋅xf(x) = s\cdot x が成り立つバイナリ文字列 s=sn−1⋯s0s = s_{n-1} \cdots s_0 が存在する。 \ 出力：文字列 ss

この問題には、実は新しい量子アルゴリズムは必要ない。ドイチュ・ヨッサ・アルゴリズムが解決してくれる。 わかりやすくするために、ORを計算するという古典的な後処理を含まない上記の量子回路を、 ドイチュ・ヨッサ回路と呼ぶことにしよう。

アルゴリズム分析

Bernstein-Vazirani問題の約束を満たす関数に対してDeutsch-Jozsa回路がどのように働くかを分析するために、まず簡単な観察から始めよう。 バイナリー・ドット・プロダクトを用いると、 nn ハダマード・ゲートの標準基底状態（ nn クビット）に対する作用を次のように記述することができる。

H⊗n∣x⟩=12n∑y∈Σn(−1)x⋅y∣y⟩H^{\otimes n} \vert x \rangle = \frac{1}{\sqrt{2^n}} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert y\rangle

Deutschのアルゴリズムを分析したときに見たのと同様、これは、任意の整数 kk に対する値 (−1)k(-1)^k が、 kk が偶数か奇数かにのみ依存するからである。

Deutsch-Jozsa回路に目を向けると、第1層のハダマードゲートが実行された後、 n+1n+1 の量子ビットの状態は次のようになる

∣−⟩⊗12n∑x∈Σn∣x⟩.\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} \vert x \rangle.

その後、クエリーゲートが実行され、（位相キックバック現象によって）状態は次のように変換される

∣−⟩⊗12n∑x∈Σn(−1)f(x)∣x⟩.\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} (-1)^{f(x)} \vert x \rangle.

ハダマードゲートの層の作用に関する公式を使えば、ハダマードゲートの第2層はこの状態を次のように変換することがわかる

∣−⟩⊗12n∑x∈Σn∑y∈Σn(−1)f(x)+x⋅y∣y⟩.\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{f(x) + x \cdot y} \vert y \rangle.

ここで、和の式中の −1-1 の指数について、いくつか簡略化を行うことができます。 ある文字列 s=sn−1⋯s0s = s_{n-1} \cdots s_0 に対して、 f(x)=s⋅xf(x) = s\cdot x が成り立つことが約束されているため、状態は次のように表すことができる

∣−⟩⊗12n∑x∈Σn∑y∈Σn(−1)s⋅x+x⋅y∣y⟩.\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{s\cdot x + x \cdot y} \vert y \rangle.

s⋅xs\cdot x と x⋅yx\cdot y は2進数値なので、加算を排他的論理和に置き換えることができる。 −1-1 の指数で整数にとって重要なのは、偶数か奇数かということだけだからである。 バイナリー・ドット・プロダクトの対称性を利用して、このような表現が得られる：

∣−⟩⊗12n∑x∈Σn∑y∈Σn(−1)(s⋅x)⊕(y⋅x)∣y⟩.\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\cdot x) \oplus (y \cdot x)} \vert y \rangle.

(わかりやすくするために括弧がつけられているが、2進のドット積は排他的論理和よりも優先順位が高いものとして扱われるのが通例であるため、実際には必要ない)

この時点では、以下の公式を使用する。

(s⋅x)⊕(y⋅x)=(s⊕y)⋅x(s\cdot x) \oplus (y \cdot x) = (s \oplus y) \cdot x

この公式は、ビットに関する同様の公式によって求めることができる、

(ac)⊕(bc)=(a⊕b)c,(a c) \oplus (b c) = (a \oplus b) c,

バイナリのドット積とビット単位の排他的論理和の展開と一緒に：

(s⋅x)⊕(y⋅x)=(sn−1xn−1)⊕⋯⊕(s0x0)⊕(yn−1xn−1)⊕⋯⊕(y0x0)=(sn−1⊕yn−1)xn−1⊕⋯⊕(s0⊕y0)x0=(s⊕y)⋅x\begin{aligned} (s\cdot x) \oplus (y \cdot x) & = (s_{n-1} x_{n-1}) \oplus \cdots \oplus (s_{0} x_{0}) \oplus (y_{n-1} x_{n-1}) \oplus \cdots \oplus (y_{0} x_{0}) \\ & = (s_{n-1} \oplus y_{n-1}) x_{n-1} \oplus \cdots \oplus (s_{0} \oplus y_{0}) x_{0} \\ & = (s \oplus y) \cdot x \end{aligned}

これにより、測定直前の回路の状態をこのように表現することができる：

∣−⟩⊗12n∑x∈Σn∑y∈Σn(−1)(s⊕y)⋅x∣y⟩.\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle.

最後のステップは、すべての2進数文字列 z=zn−1⋯z0z = z_{n-1}\cdots z_0 に対して有効な、さらに別の式を利用することです。

12n∑x∈Σn(−1)z⋅x={1if z=0n0if z≠0n\frac{1}{2^n} \sum_{x \in \Sigma^n} (-1)^{z \cdot x} = \begin{cases} 1 & \text{if $z = 0^n$}\\ 0 & \text{if $z\neq 0^n$} \end{cases}

ここでは、このレッスンであと何度か使うことになる、文字列を表す簡単な表記法を用いています。 0n0^n は、長さが nn の、すべて 0 からなる文字列です。

この式が成り立つことを示す簡単な方法は、2つのケースを別々に検討することです。 z=0nz = 0^n ならば、任意の文字列 x∈Σnx\in\Sigma^n に対して z⋅x=0z\cdot x = 0 が成り立つ。したがって、和の各項の値は 11 となり、これらを合計して 2n2^n で割ると、 11 が得られる。 一方、 zz のビットのいずれかが 11 と等しい場合、二進内積 z⋅xz\cdot x は、 x∈Σnx\in\Sigma^n の取り得る値のちょうど半分については 00 に等しく、残りの半分については 11 に等しくなる。これは、 zz が 11 を持つ位置で xx の任意のビットを反転させると、二進内積 z⋅xz\cdot x の値が反転する（ 00 から 11 へ、あるいは 11 から 00 へ）ためである。

ここで、この式を測定前の回路の状態を単純化するために適用すると、次のようになる

∣−⟩⊗12n∑x∈Σn∑y∈Σn(−1)(s⊕y)⋅x∣y⟩=∣−⟩⊗∣s⟩,\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle = \vert - \rangle \otimes \vert s \rangle,

s⊕y=0ns\oplus y = 0^n であるのは、 y=sy = s である場合に限られるという事実による。 したがって、測定結果からは、まさに私たちが探している文字列 ss が明らかになる。

古典的難度

Deutsch-Jozsa回路は1回の問い合わせでBernstein-Vazirani問題を解くが、古典的な問い合わせアルゴリズムはこの問題を解くために少なくとも nn。

これは、いわゆる情報理論的な議論によって推論することができるが、この場合は非常に単純である。 古典的なクエリーは、それぞれ解に関する1ビットの情報を明らかにする。 nn ビットの情報を明らかにする必要があるので、少なくとも nn クエリーが必要になる。

実際、バーンスタイン・ヴァジラニ問題を古典的に解くことは可能である。具体的には、単一の 11 を持つ nn の各文字列について、考えられるすべての位置で関数を問い合わせ、その他のビットについては 00 を問い合わせることで、 ss のビットを1つずつ明らかにしていく。 したがって、この問題において量子アルゴリズムが古典アルゴリズムに対して持つ利点は、 11 回のクエリ対 nn 回のクエリである。

バーンスタイン＝ヴァジラニ問題とQiskit

前述の通り、すでにドイチュ・ジョザ回路を実装済みですが、ここではそれを活用してバーンスタイン・ヴァジラニ問題を解いていきます。 まず、任意の2進文字列 ss が与えられた場合の、バーンスタイン・ヴァジラニ問題に対するクエリゲートを実装する関数を定義します。

def bv_query(s):
    # Create a quantum circuit implementing a query gate for the
    # Bernstein-Vazirani problem.

    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc


display(bv_query("1011").draw(output="mpl"))

Output:

Output of the previous code cell

ここで、先に定義した compile_circuit 関数を使って、関数上でDeutsch-Jozsa回路を実行する関数を作ることができる。

def bv_algorithm(function: QuantumCircuit):
    qc = compile_circuit(function)
    result = AerSimulator().run(qc, shots=1, memory=True).result()
    return result.get_memory()[0]


display(bv_algorithm(bv_query("1011")))

Output:

'1011'

命名法に関する注記

Bernstein-Vazirani問題の文脈では、Deutsch-Jozsaアルゴリズムが "Bernstein-Vaziraniアルゴリズム "と呼ばれるのが一般的である というのも、BernsteinとVaziraniが彼らの研究で明確にしていたように*、* このアルゴリズムはDeutsch-Jozsaアルゴリズムだからだ。

Deutsch-JozsaアルゴリズムがBernstein-Vazirani問題を解くことを示した後、BernsteinとVaziraniが行ったことは（上記の通り）、 再帰的フーリエサンプリング問題として知られる、より複雑な問題を定義することだった。 これは高度に仕組まれた問題で、問題のさまざまなインスタンスに対する解答が、ツリー状に配置された問題の新たなレベルを効果的に解き放つ。 Bernstein-Vazirani問題は本質的に、この複雑な問題の基本ケースに過ぎない。

再帰的フーリエサンプリング問題は、量子アルゴリズムが確率的アルゴリズムに対していわゆる超多項式的な優位性を持ち、Deutsch-Jozsaアルゴリズムによる古典的アルゴリズムに対する量子の優位性を凌駕する問い合わせ問題の最初の例として知られている。 直観的に言えば、この問題の再帰的バージョンは、量子アルゴリズムの 11 対 nn の利点を、より大きなものに増幅する。

この優位性を確立する数学的分析で最も困難な点は、古典的なクエリーアルゴリズムでは多くのクエリーを行わないと問題を解決できないことを示すことである。 これは極めて典型的な例である。多くの問題において、それらを効率的に解決する創造的な古典的アプローチを除外することは非常に難しい。

サイモンの問題と、次のセクションで説明するそのアルゴリズムは、古典的アルゴリズムに対する量子の超多項式的な（実際には指数関数的な）利点を示す、より単純な例を提供している。 とはいえ、それ自体が興味深い計算問題ではある。

このページは役に立ちましたか？
バグや誤字の報告、またはコンテンツの要求はGitHubで行ってください。