ドイチュ・ジョサのアルゴリズムとは

/量子回路

概要

ドイチュとジョサは、量子コンピュータを用いることで、従来のコンピュータより圧倒的に速く計算が行える問題を最初に発見しました。この問題を解く手順(アルゴリズム)は、ドイチュ-ジョサのアルゴリズムと呼ばれています。

ドイチュ-ジョサの問題とは、あるビット配列のパターンが以下のどちらであるかを判定する問題です。

  • パターンⅠ:全て「0」または全て「1」
  • パターンⅡ:「0」と「1」の数が同数

上記以外のパターンは考えないとする前提ですので、この問題の実用性は不明ですが、量子コンピュータの高速性が最初に証明された問題です。

量子回路

量子コンピュータで行う演算は大きく3つの段階があります。

  1. 量子の重ね合わせの状態を作る
  2. 重ね合わせの状態で並列処理を行う
  3. 結果を取り出す

この2つ目の並列処理が、量子コンピュータが圧倒的に高速である秘密です。この処理を実現する量子回路は以下になります。ここでは4ビットのパターンを検索する回路を例にとります。

この図の、入力側の $x_1,x_2$ はアドレスビットで、4ビットの配列の位置を表します。$y$ はレジスタビットで、アドレスに対するビットに対応します。[H]はアダマールゲート、[B]はビット読み出し、[U]は制御位相シフトゲートを表します。具体的な動作は後で説明します。

4つの操作の内、操作Aで量子ビットの重ね合わせの状態を作り、操作Bでビット読み出しの並列処理を行い、操作Cと操作Dで一意的な結果を取り出します。

尚、各量子ビットの入力(初期状態)は、全て0であると仮定します。

$$\Psi_0=\ket{\psi_0,y}=\ket{x_1x_2,y}=\ket{00,0}$$

そして、操作A~Dを行い、最後の $\psi_4$ で $\ket{00}$ 以外の項が残るかどうかで、パターンⅠかパターンⅡかの判断を行います。

  • パターンⅠ:$\ket{00}$ の項のみ残る
  • パターンⅡ:$\ket{00}$ の項以外も残る

アルゴリズムの説明

重ね合わせの状態を作る

操作Aのアダマールゲートは、量子ビットに対し以下の操作を行います。

$$H\ket{0}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})  ,  H\ket{1}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$$

そのため、

$$H\ket{00,0}=\frac{1}{2}(\ket{0}+\ket{1})\otimes(\ket{0}+\ket{1}) \otimes\ket{0}$$

これを計算すると以下のように、4ビットに相当するアドレスビットのパターンが生成されます。

$$\Psi_1=\frac{1}{2}(\ket{00,0}+\ket{01,0}+\ket{10,0}+\ket{11,0})$$

並列処理を行う

操作Bでは、各アドレスに相当するビットをレジスタビットで読み出します。例えばビット列が[1111](パターンⅠ)と[0110](パターンⅡ)の場合を書くと $\Psi_2$ は以下になります。

パターン($y$) $\Psi_2$
[1111] $(\ket{00,1}+\ket{01,1}+\ket{10,1}+\ket{11,1})/2$
[0110] $(\ket{00,0}+\ket{01,1}+\ket{10,1}+\ket{11,0})/2$

ここで、4ビットの読み出しが1回で(並列で)行われていることがポイントです。

結果を取り出す

操作Cは制御位相シフトゲートで、レジスタビットが「1」の場合に、位相を反転(符号を反転)させます。2つのビットパターンで具体的に書くと以下になります。

パターン($y$) $\Psi_3$
[1111] $(-\ket{00,1}-\ket{01,1}-\ket{10,1}-\ket{11,1})/2$
[0110]  $(+\ket{00,0}-\ket{01,1}-\ket{10,1}+\ket{11,0})/2$

次の操作Dでは、再度アダマールゲートを通します。$\ket{00}$ 以外の操作結果は以下になります。

$$H\ket{01}=\frac{1}{2}(\ket{0}+\ket{1})\otimes(\ket{0}-\ket{1})=\frac{1}{2}(\ket{00}-\ket{01}+\ket{10}-\ket{11})$$

$$H\ket{10}=\frac{1}{2}(\ket{0}-\ket{1})\otimes(\ket{0}+\ket{1})=\frac{1}{2}(\ket{00}+\ket{01}-\ket{10}-\ket{11})$$

$$H\ket{11}=\frac{1}{2}(\ket{0}-\ket{1})\otimes(\ket{0}-\ket{1})=\frac{1}{2}(\ket{00}-\ket{01}-\ket{10}+\ket{11})$$

これを $\Psi_3$ の式に代入して計算します。見やすくするためアドレスビットに注目すると、ビットパターン[1111]の場合は、以下のように $-\ket{00}$ の項のみ残ります。

パターン $\psi_3\times 2$ $H\psi_3\times 4$ $\psi_4$
[1111] $-\ket{00}$ $-(\ket{00}+\ket{01}+\ket{10}+\ket{11})$ $-\ket{00}$
$-\ket{01}$ $-(\ket{00}-\ket{01}+\ket{10}-\ket{11})$
$-\ket{10}$ $-(\ket{00}+\ket{01}-\ket{10}-\ket{11})$
$-\ket{11}$ $-(\ket{00}-\ket{01}-\ket{10}+\ket{11})$

また、ビットパターン[0000]の場合は、左から2列目の項が全て「+」になるため、$+\ket{00}$ の項のみ残ることが見て分かると思います。

次に、ビットパターン[0110]の場合は、同様に計算すると以下になります。

パターン $\psi_3\times 2$ $H\psi_3\times 4$ $\psi_4$
[0110] $+\ket{00}$ $+(\ket{00}+\ket{01}+\ket{10}+\ket{11})$ $+\ket{11}$
$-\ket{01}$ $-(\ket{00}-\ket{01}+\ket{10}-\ket{11})$
$-\ket{10}$ $-(\ket{00}+\ket{01}-\ket{10}-\ket{11})$
$+\ket{11}$ $+(\ket{00}-\ket{01}-\ket{10}+\ket{11})$

このビットパターンをどのように変えてみても、必ず $\ket{00}$ 以外の項が残ってしまうことが分かります。

ステップ数の比較

ドイチュ-ジョサの問題を従来のコンピュータで解く場合、ビット配列を端から1つづつ確認する必要があります。例えば、4ビット(=$2^2$ ビット)の場合、2ビットを確認して全て「0」でも、たまたまである可能性もあるので、まだパターンⅠがパターンⅡかの判断はできません。必ずビット数の半分より1つ多い回数(2+1回)確認する必要があります。

一般に $2^N$ ビットの配列の場合は、$2^{N-1}+1$ 回のステップが必要になります。

一方、量子回路のステップ数を数えると、操作Aでは2つのアダマールゲートがあるので2ステップ、操作B~Cは2ステップ、操作Dは操作Aと同様2ステップで、合計6ステップとなります。

これはビット配列の数は4ビット($=2^2$)の場合ですが、ビット配列が増えても、操作Aと操作Dのステップ数は増えるのみで、操作B~Cのステップ数は変わりません。一般に $2^N$ ビット配列の場合は、ステップ数は $2N+2$ 程度になります。

従来のコンピュータと量子コンピュータのステップ数を、ビット数ごとに比べると以下になります。

ビット数 ステップ数 $2^2(4)$ $2^5(32)$ $2^{10}(1024)$ $2^{20}$
従来コンピュータ ~$2^{N-1}+1$ 3 17 513 523,288
量子コンピュータ ~$2N+2$ 6 12 22 42

このように、ビット数が増えた場合は、量子コンピュータでは圧倒的に少ないステップ数で計算を完了させることができます。

 

物性物理
統計力学、個体物理、プラズマ物理、宇宙物理、エレクトロニクス、量子コンピュータ
散策路TOP
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

 

タイトルとURLをコピーしました