出典検証済みレベル 3
ドイチュ-ジョザ アルゴリズム
ドイチュ-ジョザアルゴリズムはブーリアン関数が定数か均衡かを1回のクエリで決定し、古典的決定論的アルゴリズムに対して指数的高速化を提供します。
どういう意味か
ブラックボックス関数が定数か均衡かを1回のクエリで決定します。古典的には最悪2^(n-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