ドイチュ・ジョザのアルゴリズム

位相オラクルとアダマール変換 $H^{\otimes n} ∣ x ⟩ = 2^{- n /2} \sum_{y} (- 1)^{x \cdot y} ∣ y ⟩$ を使い、定数関数・均衡関数（やバーンスタイン・ヴァジラニ型の関数）に対する各測定結果の確率を求められる

前提

量子ゲートと量子回路の計算（大学院物理量子情報・量子計算）

この技能までの道筋（107 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
行列式（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
線形変換と行列（大学数学線形代数）
核と像と次元定理（大学数学線形代数）
固有値と固有ベクトル（大学数学線形代数）
掃き出し法による逆行列（大学数学線形代数）
基底の変換と表現行列（大学数学線形代数）
対角化と行列の累乗（大学数学線形代数）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
三角比の定義と値（数学I 図形と計量）
内積となす角（数学C ベクトル）
内積空間とグラム・シュミットの直交化（大学数学線形代数）
対称行列の直交対角化（大学数学線形代数）
2 次形式の標準形と符号（大学数学線形代数）
エルミート行列とエルミート形式の符号（大学数学線形代数）
音の伝わり方と大きさ・高さ（中学理科物理分野の用語と知識）
音の振動数と波形（中学理科光と音）
比例・反比例の式とグラフ（中学数学関数）
光子のエネルギーと運動量（高校物理原子）
根号の乗除と加減（中学数学数と式）
分母の有理化（中学数学数と式）
乗法公式・分配法則を使う根号の式の展開（中学数学数と式）
根号を含む式の計算と分母の有理化（数学I 数と式）
重力と力の大きさ（中学理科力のはたらき）
2 力のつり合いと作用・反作用（中学理科力のはたらき）
力の種類とはたらき（中学理科物理分野の用語と知識）
重力・垂直抗力・張力の性質（高校物理力と運動（知識））
慣性の法則と力のつり合い（高校物理力と運動（知識））
力の分解と質点のつり合い（高校物理力と運動）
静止摩擦力・最大摩擦力・動摩擦力（高校物理力と運動（知識））
静止摩擦力と動摩擦力（高校物理力と運動）
仕事（高校物理仕事・エネルギーと運動量）
運動エネルギーと仕事の関係（高校物理仕事・エネルギーと運動量）
物質波（ド・ブロイ波）（高校物理原子）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
多項式の不定積分（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
$sin x / x$ の極限（数学III 極限）
三角関数の導関数（数学III 微分法）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
基本的な関数の不定積分（数学III 積分法）
置換積分（数学III 積分法）
部分積分（数学III 積分法）
定積分の計算（数学II 微分法と積分法）
定積分の置換・部分積分と偶関数・奇関数（数学III 積分法）
広義積分（大学数学微分積分）
波動関数の規格化と確率解釈（大学物理量子力学（1 次元の問題））
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
複素数と 2 次方程式の虚数解（数学II 複素数と方程式）
演算子と期待値（大学物理量子力学（1 次元の問題））
スピン 1/2 とパウリ行列（大学物理量子力学（角運動量・近似法））
密度行列と混合状態（大学院物理量子情報・量子計算）
テンソル積と部分トレース（大学院物理量子情報・量子計算）
量子ゲートと量子回路の計算（大学院物理量子情報・量子計算）

説明

ドイチュ・ジョザのアルゴリズムは、 $n$ ビットの入力 $x \in {0, 1}^{n}$ に $0$ か $1$ を返す関数 $f$ が「定数関数」か「均衡関数（ちょうど半数の入力で $1$ を返す）」かを、オラクルをただ 1 回呼ぶだけで確実に見分ける量子回路です。この技能では、回路の最後の測定で各ビット列 $y$ が出る確率を、アダマール変換の公式から一般に計算できるようにします。同じ計算で、 $f (x) = s \cdot x$ 型の関数の隠れたビット列 $s$ を 1 回で読み出すバーンスタイン・ヴァジラニのアルゴリズムや、定数でも均衡でもない関数の場合の確率も扱えます。

なぜそうしてよいのか

まずオラクルを位相の形にします。ビットオラクル $U_{f} ∣ x ⟩ ∣ b ⟩ = ∣ x ⟩ ∣ b \oplus f (x)⟩$ の補助ビットを $∣ - ⟩ = \frac{∣0 ⟩ - ∣1 ⟩}{2}$ にしておくと、 $f (x) = 0$ なら何も変わらず、 $f (x) = 1$ なら $∣0 ⟩$ と $∣1 ⟩$ が入れ替わって $- ∣ - ⟩$ になります。つまり $U_{f} ∣ x ⟩ ∣ - ⟩ = (- 1)^{f (x)} ∣ x ⟩ ∣ - ⟩$ で、補助ビットは変化せず、入力レジスタに符号 $(- 1)^{f (x)}$ だけが返ってきます（位相キックバック）。以後は補助ビットを省き、 $O_{f} ∣ x ⟩ = (- 1)^{f (x)} ∣ x ⟩$ という位相オラクルとして扱います。

回路は $∣0 ⟩^{\otimes n} \to H^{\otimes n} \to O_{f} \to H^{\otimes n} \to$ 測定です。1 ビットでは $H ∣ x ⟩ = \frac{1}{2} \sum_{y = 0}^{1} (- 1)^{x y} ∣ y ⟩$ なので、テンソル積をとると $H^{\otimes n} ∣ x ⟩ = 2^{- n /2} \sum_{y} (- 1)^{x \cdot y} ∣ y ⟩$ になります。ここで $x \cdot y = x_{1} y_{1} + \dots + x_{n} y_{n}$ を $2$ で割った余り（符号 $(- 1)^{x \cdot y}$ には偶奇しか効かない）です。これを 2 回使うと、最後の状態は
$∣ ψ ⟩ = y \sum c_{y} ∣ y ⟩, c_{y} = \frac{1}{2 ^{n}} x \sum (- 1)^{f (x) + x \cdot y}$
となり、 $y$ が測定される確率は $P (y) = ∣ c_{y} ∣^{2}$ です。

特に $y = 0 \dots 0$ では $x \cdot y = 0$ なので $c_{0} = \frac{1}{2 ^{n}} \sum_{x} (- 1)^{f (x)}$ は「 $(- 1)^{f (x)}$ の平均」です。 $f$ が定数なら平均は $\pm 1$ で $P (0 \dots 0) = 1$ 、均衡なら $+ 1$ と $- 1$ が同数で打ち消し合って $P (0 \dots 0) = 0$ になります。だから $0 \dots 0$ が出たら定数、それ以外が出たら均衡と確実に判定できます。また $\sum_{x} (- 1)^{x \cdot z} = \prod_{i = 1}^{n} (1 + (- 1)^{z_{i}})$ は $z = 0 \dots 0$ のとき $2^{n}$ 、それ以外は $0$ なので、 $f (x) = s \cdot x \oplus b$ なら $c_{y} = \frac{( - 1 ) ^{b}}{2 ^{n}} \sum_{x} (- 1)^{x \cdot (s \oplus y)}$ は $y = s$ のときだけ絶対値 $1$ となり、 $s$ が確率 $1$ で測定されます。

手順

オラクルを位相の形 $O_{f} ∣ x ⟩ = (- 1)^{f (x)} ∣ x ⟩$ にする（ビットオラクルなら補助ビットを $∣ - ⟩$ にして位相キックバックを使う）
最初のアダマール変換で一様な重ね合わせを作る: $H^{\otimes n} ∣0 \dots 0 ⟩ = 2^{- n /2} \sum_{x} ∣ x ⟩$
オラクルを作用させて各項に符号を付ける: $2^{- n /2} \sum_{x} (- 1)^{f (x)} ∣ x ⟩$
2 回目のアダマール変換を公式で展開し、知りたい $y$ の振幅 $c_{y} = \frac{1}{2 ^{n}} \sum_{x} (- 1)^{f (x) + x \cdot y}$ を書く（ $x \cdot y$ は各ビットの積の和の偶奇）
$x$ についての和を、関数の値表を使って実際に足し上げる
確率 $P (y) = ∣ c_{y} ∣^{2}$ を求める（定数なら $P (0 \dots 0) = 1$ 、均衡なら $P (0 \dots 0) = 0$ になることで検算できる）

例題

2 量子ビットの入力 $x = x_{1} x_{2} \in {00, 01, 10, 11}$ に対し、関数 $f (x) = x_{1} x_{2}$ （ $x_{1}$ と $x_{2}$ がともに $1$ のときだけ $1$ 、ほかは $0$ ）の位相オラクル $O_{f} ∣ x ⟩ = (- 1)^{f (x)} ∣ x ⟩$ を用いて、ドイチュ・ジョザの回路 $∣00 ⟩ \to H^{\otimes 2} \to O_{f} \to H^{\otimes 2} \to$ 計算基底で測定を実行する。測定結果が $00$ となる確率を求めよ。

例題の解答

手順 1: オラクルは問題文で位相の形 $O_{f} ∣ x ⟩ = (- 1)^{f (x)} ∣ x ⟩$ として与えられている。 $f (00) = f (01) = f (10) = 0$ 、 $f (11) = 1$ であり、この $f$ は定数でも均衡でもない。

手順 2: $H^{\otimes 2} ∣00 ⟩ = \frac{1}{2} (∣00 ⟩ + ∣01 ⟩ + ∣10 ⟩ + ∣11 ⟩)$ 。

手順 3: オラクルで $f (x) = 1$ の項だけ符号が反転し、 $\frac{1}{2} (∣00 ⟩ + ∣01 ⟩ + ∣10 ⟩ - ∣11 ⟩)$ となる。

手順 4: 2 回目の $H^{\otimes 2}$ の後の $∣00 ⟩$ の振幅は、 $y = 00$ で $x \cdot y = 0$ なので
$c_{00} = \frac{1}{2 ^{2}} x \sum (- 1)^{f (x)} .$

手順 5: 値表から $\sum_{x} (- 1)^{f (x)} = (+ 1) + (+ 1) + (+ 1) + (- 1) = 2$ 。よって $c_{00} = \frac{2}{4} = \frac{1}{2}$ 。

手順 6: $P (00) = ∣ c_{00} ∣^{2} = \frac{1}{4}$ 。
（検算として、ほかの結果の振幅も同様に計算すると $c_{01} = c_{10} = \frac{1}{2}$ 、 $c_{11} = \frac{1}{4} (1 - 1 - 1 - 1) = - \frac{1}{2}$ で、確率の和は $4 \times \frac{1}{4} = 1$ となり矛盾はない。）

答え: $\frac{1}{4}$

よくある誤り

2 回目のアダマール変換で正規化を落とし、 $c_{y} = \frac{1}{2 ^{n /2}} \sum_{x} (- 1)^{f (x) + x \cdot y}$ としてしまう誤り。 $H^{\otimes n}$ を 2 回使うので係数は $2^{- n /2} \cdot 2^{- n /2} = 2^{- n}$ で、正しくは $c_{y} = \frac{1}{2 ^{n}} \sum_{x} (- 1)^{f (x) + x \cdot y}$ （定数関数で $P (0 \dots 0) = 1$ になるかで確かめられる）。
内積 $x \cdot y$ を普通の整数の和のまま扱い、ビット列の比較で $x \oplus y$ や $x$ と $y$ の一致などと取り違える誤り。正しくは $x \cdot y = x_{1} y_{1} + \dots + x_{n} y_{n} (mod 2)$ で、例えば $x = 11, y = 11$ なら $x \cdot y = 0$ 、 $(- 1)^{x \cdot y} = + 1$ 。
確率を振幅の和の絶対値の 2 乗ではなく、各項の確率の和 $\sum_{x} \frac{1}{2 ^{n}} (- 1)^{f (x) + x \cdot y}^{2} = \frac{1}{2 ^{n}}$ として計算してしまう誤り。干渉が起こるので、正しくは先に振幅を足して $P (y) = \frac{1}{2 ^{n}} \sum_{x} (- 1)^{f (x) + x \cdot y}^{2}$ 。
ビットオラクルの補助ビットを $∣0 ⟩$ のまま使い、 $U_{f} ∣ x ⟩ ∣0 ⟩ = (- 1)^{f (x)} ∣ x ⟩ ∣0 ⟩$ としてしまう誤り。 $∣0 ⟩$ では $∣ x ⟩ ∣ f (x)⟩$ になるだけで位相は返らない。正しくは補助ビットを $∣ - ⟩$ にして $U_{f} ∣ x ⟩ ∣ - ⟩ = (- 1)^{f (x)} ∣ x ⟩ ∣ - ⟩$ とする。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
3 ビットの入力 $x = x_{1} x_{2} x_{3} \in {0, 1}^{3}$ に対する関数 $f : {0, 1}^{3} \to {0, 1}$ を
$f (x) = {10 (x \in {000, 001, 010, 100}) (それ以外)$
で定める（ $f$ は 8 個の入力のうち 4 個で $1$ をとる均衡関数である）。オラクル $U_{f}$ は $U_{f} ∣ x ⟩ ∣ b ⟩ = ∣ x ⟩ ∣ b \oplus f (x)⟩$ （ $b \in {0, 1}$ , $\oplus$ は 2 を法とする和）と作用する。
ドイチュ・ジョザのアルゴリズムとして、次の操作を行う。
1. 3 量子ビットの入力レジスタを $∣000 ⟩$ 、補助量子ビットを $∣1 ⟩$ に用意する。
2. 4 個すべての量子ビットにアダマールゲート $H$ を作用させる。
3. $U_{f}$ を 1 回作用させる。
4. 入力レジスタの 3 量子ビットそれぞれに $H$ を作用させる。
5. 入力レジスタを計算基底で測定する。
ここで $H ∣0 ⟩ = \frac{1}{2} (∣0 ⟩ + ∣1 ⟩)$ , $H ∣1 ⟩ = \frac{1}{2} (∣0 ⟩ - ∣1 ⟩)$ とする。測定結果が $111$ となる確率を求めよ。