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

202

10

章 量子探索

位相論理

演算

振幅増幅

図 10-10  

これは、ブールステートメントが値

a=1

、

b=0

、

c=1

で満たされることを示しています。

この例では、ブールステートメントを満たす一連の入力値を特定できました。では、解が存在しない

場合はどうなるでしょうか？

幸いなことに、充足可能性のような

NP

問題は、答えの発見に計算コスト

がかかりますが、答えが正しいかどうかのチェックでは計算コストはかかりません。問題が充足不可能

である場合、レジスタ内の位相は反転されず、鏡映（

mirror

）演算の結果として振幅の大きさが変わ

ることもありません。すべての値の等しい重ね合わせから出発するので、最後の読み出しではランダム

にレジスタから

1

つの値が得られます。私たちとしては、論理ステートメントを満たすかどうかを単に

確認する必要があるだけです。もし満たされなければ、ステートメントが充足不可能であることを確か

めることができます。次にこのケースについて考えてみましょう。

10.3.2

 ハンズオン：充足不可能な

3-SAT

問題

それでは、充足不可能な

3-SAT

問題を見てみましょう。

(a OR b) AND (NOT a OR c) AND (NOT b OR NOT c) AND (a OR c) AND b

これが充足不可能とわかっているので、変数

a

、

b

、

c

にどんな値を代入しても、

1

が出力されること

はないと予想されます。図 10-11で示される、 ...