Skip to main content
IBM Quantum Platform

Deutsch-Jozsaアルゴリズム

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

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

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

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

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

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

この問題の入力関数は、任意の正の整数に対して f:Σn→Σf:\Sigma^n \rightarrow \Sigma の形をとる。 n.n. Deutschの問題と同様に、 ff が定数なら 00 を、 ff が釣り合いなら 11 を出力することである。これは、関数が値 00 をとる入力文字列の数と、関数が値 11 をとる入力文字列の数が等しいことを意味する。

nn が 1,1, より大きい場合、定数でも釣り合いでもない 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 の測定結果のすべてが 0,0, である場合、関数 ff は定数である。 それ以外の場合、すなわち測定結果のうち少なくとも1つが 1,1, である場合、関数 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}

ちなみにここでは、 nn の長さのバイナリ文字列を、Qiskitのインデックス規則に従って、 xn−1⋯x0x_{n-1}\cdots x_0 と yn−1⋯y0,y_{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.

この式はやや複雑に見えるので、関数についてもっと詳しく知らなければ、異なる測定結果を得る確率についてあまり多くのことを結論づけることはできない。 f.f.

幸いなことに、私たちが知る必要があるのは、すべての測定結果が 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 が定数である場合、すべての文字列について f(xn−1⋯x0)=0f(x_{n-1}\cdots x_0) = 0 のどちらかとなる。 xn−1⋯x0,x_{n-1}\cdots x_0, f(xn−1⋯x0)=1f(x_{n-1}\cdots x_0) = 1 となり、その場合の和の値は 2n,2^n, となる。 xn−1⋯x0,x_{n-1}\cdots x_0, である。 −2n.-2^n. 2n2^n で割り、絶対値の2乗をとると、次のようになる。 1.1.

一方、 ff が釣り合っている場合、 ff は文字列の半分に値 00 をとり、 xn−1⋯x0x_{n-1}\cdots x_0 と残りの半分に値 11 をとる。したがって、合計の +1+1 の項と −1-1 の項は相殺され、次のような値が残る。 0.0.

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

古典的難度

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+1.2^{-k + 1}. k=11,k = 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'

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

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

まず、いくつかの表記法を紹介しよう。 長さ n,n, の任意の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 と y,y, を入れ替えても結果は変わらない。 バイナリのドット積 x⋅yx \cdot y を、文字列 yy が 1,1, を持つ位置における xx のビットのパリティ、あるいは同等に、文字列 xx が を持つ位置における yy のビットのパリティと考えると便利なことがある。 1.1.

この表記法を手にして、我々は今、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、いくつかの簡略化を行うことができる。 f(x)=s⋅xf(x) = s\cdot x、文字列 s=sn−1⋯s0,s = s_{n-1} \cdots s_0,、次のように表現できる

∣−⟩⊗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.

最後のステップは、すべてのバイナリ文字列に対して機能する、さらに別の公式を使うことである。 z=zn−1⋯z0.z = 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 は、長さがすべてゼロの文字列である。 n.n.

この公式が機能することを論証する簡単な方法は、2つのケースを別々に考えることである。 もし z=0n,z = 0^n, ならば、すべての文字列に対して z⋅x=0z\cdot x = 0 x∈Σn,x\in\Sigma^n,。したがって、和の各項の値は 1,1, となり、和と除算によって 11 が得られる。 2n.2^n. xx 一方、 zz のいずれかのビットが 1,1, に等しい場合、バイナリドット積 z⋅xz\cdot x は、 x∈Σnx\in\Sigma^n の選択肢のちょうど半分について 00 に等しく、残りの半分について 11 に等しくなります。 z⋅xz\cdot x の値が反転する（ 00 から 11 へ、または 11 から 00 へ）のは、 zz が 1.1.

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

∣−⟩⊗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 if and only if y=s.y = s. したがって、この測定は、我々が探しているストリング ss を正確に明らかにしている。

古典的難度

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

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

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

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

ドイチュ・ヨツァ回路はすでに実装したが、ここではそれを使ってバーンスタイン・ヴァジラニ問題を解く。 まず、任意の2進文字列が与えられた場合のBernstein-Vazirani問題のクエリーゲートを実装する関数を定義する。 s.s.

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で行ってください。