Skip main navigation

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

Marking Desired States/希望の状態をマークする
© Keio University
Groverのアルゴリズムは、マーキングと拡散の2つの部分で構成されています。 まず、前のステップで紹介した構造を少し厳密に議論し、次にマークルーチンの例を見て、次のステップで拡散とパフォーマンスについて議論します。

アルゴリズムの概要

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

© Keio University
This article is from the free online

量子コンピュータ入門

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education