メインコンテンツへスキップ

Deutsch-Jozsaアルゴリズム

Deutschのアルゴリズムはクエリ問題においてすべての古典アルゴリズムを上回りますが、その優位性は比較的控えめです。クエリ数は1回対2回です。 Deutsch-Jozsaアルゴリズムはこの優位性を拡張します。そして実際に、2種類の異なるクエリ問題を解くために使用できます。

以下はDeutsch-Jozsaアルゴリズムの量子回路の説明です。 解こうとしている具体的な問題によっては、図には示されていない追加の古典後処理ステップも必要になる場合があります。

Deutsch-Jozsaアルゴリズム

もちろん、このアルゴリズムがどのような問題を解くかについてはまだ説明していません。これについては続く2つのセクションで説明します。

Deutsch-Jozsa問題​

まず、Deutsch-Jozsaアルゴリズムが元々解くことを意図していたクエリ問題、すなわちDeutsch-Jozsa問題から始めます。

この問題の入力関数は、任意の正の整数 nn に対して f:Σn→Σf:\Sigma^n \rightarrow \Sigma という形を取ります。 Deutschの問題と同様に、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問題

入力：関数 f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\}
約束：ff は定数か平衡のどちらかである
出力：ff が定数なら 00、ff が平衡なら 11

1回のクエリによるDeutsch-Jozsaアルゴリズムは、次の意味でこの問題を解きます。 nn 個の測定結果がすべて 00 であれば、関数 ff は定数です。 そうでなく、測定結果の少なくとも1つが 11 であれば、関数 ff は平衡です。 別の言い方をすると、上記の回路に続いて、測定結果のORを計算して出力を生成する古典後処理ステップが行われます。

アルゴリズムの解析​

Deutsch-Jozsa問題に対するDeutsch-Jozsaアルゴリズムの性能を解析するには、まず1層のアダマールゲートの作用について考えるとよいでしょう。 アダマール演算は通常の方法で行列として表すことができます。

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 の2進数文字列を xn−1⋯x0x_{n-1}\cdots x_0 および yn−1⋯y0y_{n-1}\cdots y_0 と書いていることに注意してください。

この公式は、上記の量子回路を解析するための便利なツールを提供します。 最初のアダマールゲート層が実行された後、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 演算が実行されると、Deutschのアルゴリズムの解析で見たのとまったく同じ位相キックバック現象により、この状態は次のように変換されます。

∣−⟩⊗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={1f が定数のとき0f が平衡のとき\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{$f$ が定数のとき}\\[1mm] 0 & \text{$f$ が平衡のとき} \end{cases}

詳しく説明すると、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 で割り、絶対値の2乗を取ると 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 回のクエリが必要です。 その理由は、決定論的アルゴリズムが 2n−12^{n-1} 以下の異なる文字列に対して ff にクエリを行い、毎回同じ関数値を得た場合、両方の答えがまだ可能だからです。 関数が定数である可能性も、または平衡だが運悪くすべてのクエリが同じ関数値を返している可能性もあります。

2番目の可能性は可能性が低いように見えますが、決定論的アルゴリズムにはランダム性や不確実性がないため、特定の関数に対して系統的に失敗します。 したがって、この点において量子アルゴリズムは古典アルゴリズムに対して大きな優位性を持ちます。

ただし、落とし穴があります。確率的な古典アルゴリズムは、わずかなクエリ数で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のアルゴリズムからの改善を示しています。

QiskitによるDeutsch-Jozsa​

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

QiskitでDeutsch-Jozsaアルゴリズムを実装するには、まず dj_query という関数を定義します。この関数は、Deutsch-Jozsa問題の約束を満たすランダムに選ばれた関数に対して、クエリゲートを実装する量子回路を生成します。 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"))

前のコードセルの出力

次に、クエリゲートの量子回路実装を引数として取り、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回路を1回実行する関数を定義します。

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))

前のコードセルの出力

'balanced'

Bernstein-Vazirani問題​

次に、Bernstein-Vazirani問題として知られる問題について説明します。 これはフーリエサンプリング問題とも呼ばれますが、この名前で呼ばれるより一般的な定式化も存在します。

まず、いくつかの記法を導入しましょう。 長さ 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.

この演算を二進内積と呼びます。 別の定義方法は次のとおりです。

x⋅y={1xn−1yn−1+⋯+x0y0 が奇数のとき0xn−1yn−1+⋯+x0y0 が偶数のときx \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ が奇数のとき}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ が偶数のとき} \end{cases}

これは対称な演算であることに注意してください。つまり、xx と yy を入れ替えても結果は変わらないため、都合のよいときにいつでも入れ替えることができます。 二進内積 x⋅yx \cdot y は、文字列 yy が 11 を持つ位置における xx のビットのパリティ、あるいは等価的に、文字列 xx が 11 を持つ位置における yy のビットのパリティとして考えると便利な場合があります。

この記法を使って、Bernstein-Vazirani問題を定義できます。

Bernstein-Vazirani問題

入力：関数 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 となる2進数文字列 s=sn−1⋯s0s = s_{n-1} \cdots s_0 が存在する
出力：文字列 ss

この問題のために新しい量子アルゴリズムは実際には必要ありません。Deutsch-Jozsaアルゴリズムが解いてくれます。 明確にするために、ORを計算する古典後処理ステップを含まない上記の量子回路をDeutsch-Jozsa回路と呼ぶことにします。

アルゴリズムの解析​

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回路に戻ると、最初のアダマールゲート層が実行された後、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進数の値であるため、加算を排他的論理和に置き換えることができます。これも、指数の中の整数にとって重要なのは偶数か奇数かだけだからです。 二進内積の対称性を利用すると、状態に対する次の式が得られます。

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

（二進内積は排他的論理和より高い優先順位を持つという慣例があるため実際には必要ありませんが、わかりやすくするためにカッコを追加しています。）

この時点で、次の公式を利用します。

(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={1z=0n のとき0z≠0n のとき\frac{1}{2^n} \sum_{x \in \Sigma^n} (-1)^{z \cdot x} = \begin{cases} 1 & \text{$z = 0^n$ のとき}\\ 0 & \text{$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 に等しい場合、x∈Σnx\in\Sigma^n の可能な選択肢のちょうど半分に対して二進内積 z⋅xz\cdot x は 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 が1つあり、他のすべてのビットが 00 である nn 個の文字列に対して関数をクエリすることで、ss のビットを1つずつ明らかにし、Bernstein-Vazirani問題を古典的に解くことが可能です。 したがって、この問題における量子アルゴリズムの古典アルゴリズムに対する優位性は、1回のクエリ対 nn 回のクエリです。

QiskitによるBernstein-Vazirani​

上でDeutsch-Jozsa回路を既に実装しました。ここではそれを利用してBernstein-Vazirani問題を解きます。 まず、任意の2進数文字列 ss に対してBernstein-Vazirani問題のクエリゲートを実装する関数を定義します。

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"))

前のコードセルの出力

次に、以前定義した 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")))
'1011'

命名法に関する注記​

Bernstein-Vazirani問題の文脈では、Deutsch-Jozsaアルゴリズムが「Bernstein-Vaziranアルゴリズム」と呼ばれることがよくあります。 これはやや誤解を招く表現です。なぜなら、このアルゴリズムはDeutsch-Jozsaアルゴリズムそのものであり、BernsteinとVazirani自身も彼らの研究でそのことを明確に述べているからです。

BernsteinとVaziranがDeutsch-Jozsaアルゴリズムがここで述べたBernstein-Vazirani問題を解くことを示した後に行ったのは、再帰的フーリエサンプリング問題として知られる、はるかに複雑な問題を定義することでした。 これは非常に人工的な問題であり、異なる問題インスタンスの解が木構造に配置された問題の新しいレベルを実質的に解放していきます。 Bernstein-Vazirani問題は本質的に、この複雑な問題の基本ケースにすぎません。

再帰的フーリエサンプリング問題は、量子アルゴリズムが確率的アルゴリズムに対して超多項式的な優位性を持つことが知られた最初のクエリ問題の例でした。これにより、Deutsch-Jozsaアルゴリズムが提供する量子対古典の優位性を超えることができました。 直感的に言えば、問題の再帰版は量子アルゴリズムの1対 nn の優位性をはるかに大きなものに増幅します。

この優位性を確立する数学的解析の最も困難な側面は、古典的なクエリアルゴリズムが多くのクエリなしに問題を解けないことを示すことです。 これは非常に典型的なことで、多くの問題において、それらを効率的に解く創造的な古典的アプローチを排除することは非常に困難です。

Simonの問題と次のセクションで説明するそのアルゴリズムは、量子アルゴリズムの古典アルゴリズムに対する超多項式的（そして実際には指数関数的）な優位性のはるかに単純な例を提供します。このため、再帰的フーリエサンプリング問題はあまり議論されることがありません。 しかし、それ自体として興味深い計算問題であることに変わりはありません。