動かして学ぶ量子コンピュータプログラミング ―シミュレータとサンプルコードで理解する基本アルゴリズム

10.4

 従来型アルゴリズムの高速化

205

読み取りで任意の値を同等に得ることができたのであれば、いままで学んできたことに意味がないよ

うに思えるかもしれません。しかし、読み出す

a

、

b

、

c

の

3

つの値のいずれでも、ブールステートメン

トに入力してみることが可能です。結果が

0

であれば、論理ステートメントが充足可能でないという結

論になります（そうでなければ、満足のいく値を読み取ることが期待されます）。

10.4

 従来型アルゴリズムの高速化

振幅増幅の最も顕著な特徴の

1

つは、特定のケースでは、力任せで行う従来のアルゴリズムだけで

なく、最高の従来型の実装を超えるような、

2

次関数的な計算速度の向上を達成できることです。

振幅増幅を高速化するアルゴリズムは、片側誤差を持つアルゴリズムです。これらは、

yes/no

の答

えを出力するサブルーチンを含む決定問題に対するアルゴリズムです。このアルゴリズムは、問題に対

す る 答 え が「

no

」で あ れ ば 、 そ の ア ル ゴ リ ズ ム は 常 に「

no

」を出力し、問題に対する答えが「

yes

」の 場 合

は、アルゴリズムは「

yes

」という答えを確率

p

＞

0

で出力します。先ほどの

3-SAT

問題の場合、アルゴ

リズムは（式が充足可能で）充足可能な割り当てが見つけられる場合にのみ、「

yes

」を 出 力 し ま す 。

望ましい確率を持つ解を見つけるためには、これらの従来型のアルゴリズムは、確率的なサブルー

チンを数回（アルゴリズムが

O(k

n

poly (n))

という実行時間