出典検証済みレベル 3
ドイチュ-ジョザ アルゴリズム
ドイチュ-ジョザアルゴリズムはブーリアン関数が定数か均衡かを1回のクエリで決定し、古典的決定論的アルゴリズムに対して指数的高速化を提供します。
動きで見る
無料登録後、そのままこの概念に戻ります。
どういう意味か
ブラックボックス関数が定数か均衡かを1回のクエリで決定します。古典的には最悪2^(n-1)+1クエリ必要。量子並列性と干渉を活用します。日常のたとえ
1つのランプにつながった封印されたスイッチ箱を想像してください。ランプは常に同じ（定数）か、入力のちょうど半分でだけ点く（均衡）かのどちらかです。古典的には確信するために入力の半分以上を試す必要がありますが、ドイチュ・ジョサのアルゴリズムは振幅を干渉させ、1回の問い合わせでどちらの箱かを教えてくれます — 個々の出力は教えてくれません。
封印された投票箱をチェックするようなもの。
よくある誤解
- 高速化は決定論的古典アルゴリズムに対してです。
- 関数が何を計算するかは教えてくれません。
要点
- 1回のオラクルクエリで定数vs均衡を決定。
- 量子優位を証明した最初のアルゴリズム。
- 重ね合わせ、位相キックバック、干渉を使用。
理解度チェック
必要なオラクルクエリ数は？
- A.n
- B.2^n
- C.1
- D.log(n)
答えを見る
答え: C. 1
理由: 1回のオラクルクエリのみ必要です。
前提となる概念
関連する概念
一次資料: Deutsch & Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. A 439, 553 (1992), doi:10.1098/rspa.1992.0167