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

292

14

章 最先端を行く：文献案内

います。ぜひ、先駆的な量子コンピュータのアルゴリズムを調べてみてください。

14.8.1

 

Deutsch-Jozsa

のアルゴリズム

オラクル

n

ビットのバイナリ文字列をとり、そのバイナリ文字列に関数

f

を適用した結果となる単一

ビットを出力する。関数

f

は（ い つ も 出 力 が 同 じ に な る ）定 数 あ る い は（ 同 じ 数 の

0

と

1

の出力

がある）バランスがとられたもの、のどちらかになる。

問題

オラクルにするクエリができるだけ少なくなるようにして、

f

が一定か、またはバランスがと

られたものになるかを、絶対的な確度で決定すること。

クエリ計算量

従来型のコンピューティングでは、関数の性質を保証するためには、オラクルに

2

n

–1

＋

1

個の

クエリを作成する必要がある。

QPU

を使用すると、単一の量子クエリにより誤り確率ゼロで

問題を解くことができる。

このアルゴリズムは、

http://oreilly-qc.github.io?p=14-DJ

で実行できます。

14.8.2

 

Bernstein-Vazirani

アルゴリズム

オラクル

n

ビットのバイナリ文字列

x

を受け取り、

1

つのバイナリ番号を出力する。出力は

Σ

i

x

i

・

s

i

に

よって取得される。ここで、

s

はオラクルによって使用される秘密の文字列。

問題

秘密の文字列

s

を見つけること。

クエリ計算量

従来、入力ビットのそれぞれを学習するために、

n

回のオラクルクエリが必要だった。しかし、

QPU

を使用すると、単一のクエリで問題を解決