Marking Desired States／希望の状態をマークする

アルゴリズムの概要

まずは何らかの入力(x)をとり、真偽値(真または偽)を返す関数(f(x))について考えましょう。 あなたの目標は、(f(x))が真を返す(x)の値を見つけることです。 （現時点では、必ずしもそうである必要はありませんが、真を返す(x)の値が1つしかないと仮定します。） ここでは、問題の特性として(x)の取りうる値の数が多く、良いと思われる(x)が何であるかを情報に基づいて推測する方法がないと仮定します。 たとえあなたが(f(x))を計算したとしても、それはあなたに真偽を提供するだけで、 “近い”などのどんな値が次のに適しているのか推測することができる情報を得ることはできません。あなたができることは、異なる値の(x)を試し続けることだけです。

私(バンミーター)はこう呼ぶことが良いとは思いませんが、この種の問題は、無作為化されたデータベース検索問題とも呼ばれます。 これらの問題は「どのような(x)の値が(f(x)=k)であるか」という質問に言い換えることができます。このような構造化されていない問題は、効率的に解決することが難しいです。効率的な検索能力がない場合、1回真を返すまでに、平均して(x)の取りうるものの半分の回数試行することが期待されます。

Groverのアルゴリズムを使用すると、その関数の計算回数を減らすことができます。(N)を(x)の取りうる値の数とすると、(f(x))を計算する必要があるのは(O(sqrt{N}))回のみになります。また、50%以上(通常は100％に近い)の確率で答えを返します。

もちろん、量子アルゴリズムに対する基本的なアプローチによれば、この効果は、状態の位相に依存する干渉を用いて達成されます。 Lov Groverの洞察は、この干渉を作り出す「平均についての逆転」操作を実装可能であるということです。これについては次に説明します。

これを達成するには、2つのルーチンが必要です。ひとつは答えが良いか悪いかを示すマークルーチン、もうひとつは確率振幅を他のダイヤルの上に「塗りつぶす」拡散演算子です。 拡散の正確な効果は、その状態がマークされているかどうかによって異なります。

マークルーチン

マークルーチンは、質問に対する答えを見つけたかどうかをテストします。 もちろん、すでに説明した単一のゲートを使って実装されていますが、これは単純に古典的なアナログを使って(f(x))を計算し、真または偽を返すタスクです。

チェスの例では、(x)は一連の移動であり、(f(x))は、シーケンスが勝利になる場合はtrueを返し、敗北になる場合はfalseを返す関数です。 議論のために、4つの可能な動きがあってそのうちの1つがチェックメイト（勝利）になると仮定します。

古典的に最良の動きを見つけるには、最悪の場合、勝つまでに4回試してみなければなりません。平均して2.5回が必要です。 2つの量子ビットとGroverの検索アルゴリズムを備えた量子コンピュータを使うと、私たちはチェック操作を1回だけ使えば答えを見つけることができます。

アルゴリズムを開始するには、4つの状態すべてを重ね合わせます。 （量子ビットを使って4つの状態をエンコードするには、2量子ビットを使って、 (00), (01), (10), (11) として、それぞれ移動シーケンスの1つを表します）。(vert xrangle)には、それぞれ振幅と位相が同じ4つのダイヤルがあります。 この初期設定では、この記事の一番上にある図の左に4つのダイヤルがあります。 (ここでは視覚的に分かりやすくするために、ダイヤルに正確なベクトル長を使用していません。)

次に、(f(x))が真である状態のみの位相を反転する((pi)で位相を変更する)マークルーチンを実行します。 これは、図の矢印に対応する遷移です。 オレンジ色で示されている勝利の移動シーケンスに対応する状態は、3つの失った移動の位相とは反対に、今度は下を向いています。

ここで、答えを知らなくても関数(f)を作るためにゲートを使って回路を作成可能であることが重要です。 関数は答えを認識する方法を知っていなければなりませんが、その情報は直接含まれているわけではありません。それ以外の場合、アルゴリズムはすでに知っていることを確認するだけです。