書記が物理やるだけ#323 Deutsch–Jozsaのアルゴリズム

量子コンピュータが古典コンピュータよりも優れている事例として，主にDeutsch–Jozsaのアルゴリズムを見ていく。

問題

説明

Deutsch–Jozsaのアルゴリズムは，オラクルを用いて関数が定値か均等かを決定する問題において古典アルゴリズムより高速に解ける。

類似のアルゴリズムを簡単に紹介しておく。

Bernstein–Vaziraniのアルゴリズムは，特定のビット列を求めるものである。

Simonのアルゴリズムは，関数が1to1か1to2かを判別する。

解答

以下のオラクルを判別するのに，古典コンピュータでは2回fを実行する必要がある。

それに対し，以下に示すDeutschのアルゴリズムでは1回で済む。

ここで使うオラクルは以下の通りである。

例としてオラクルをU_f11とした場合を示す。出力を見ると，確かに0番目のビットが|0>であり，定数関数であることが正しく判定できている。

これを一般化したものがDeutsch–Jozsaのアルゴリズムであり，古典コンピュータでは2^(n-1)-1回かかるところを量子コンピュータにより1回で済ませることができる。

本記事のもくじはこちら：