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

194

10

章 量子探索

これらの状態は、論理割り当て

(a=0, b=0, c=1)

、

(a=1, b=0, c=1)

、

(a=1, b=1, c=1)

をそ

れぞれエンコードします。これらは、図 10-5 に示した元のブールステートメントを充足する唯一の論

理入力です。

10.2

 論理パズルを解く

ブールステートメントを充足する値の位相を特徴付ける新しい機能を使用すると、振幅増幅を使用

して充足可能性（

boolean satisfiability

）の問題を解決できます。これは、ブールステートメントを満た

す入力値があるかどうか（位相論理演算で達成するために学習した内容）を判断する問題です。

充足可能性は、コンピュータサイエンス

＊

1

で重要な問題であり、モデル検査、人工知能の計画、ソ

フトウェアの検証などに応用されています。充足可能性問題

（そしてこの問題を解決する方法）を理解

するために、あまりお金になりませんが、とても面白い応用を通じて、

QPU

がどのように役立つのか

を調べてみましょう。論理パズルを解くようなものです。

10.2.1

 子猫とトラに関する問題

遠く、遠く離れた島に、一人の王女が住んでいました。彼女は、誕生日のプレゼントに子猫を強く願っ

ていました。王女の父親である王は、この願いを知っていたのですが、自分の娘が本当に真剣に猫を

飼いたいのかどうかを確かめるために、誕生日に

1

つのなぞなぞを出しました（図 10-6）

＊

2

。

図 10-6

＊

1

充足可能性は

NP

完全であることが証明された最初の問題であ ...