概要
ドイチュとジョサは、量子コンピュータを用いることで、従来のコンピュータより圧倒的に速く計算が行える問題を最初に発見しました。この問題を解く手順（アルゴリズム）は、ドイチュ-ジョサのアルゴリズムと呼ばれています。
ドイチュ-ジョサの問題とは、あるビット配列のパターンが以下のどちらであるかを判定する問題です。
- パターンⅠ：全て「０」または全て「１」
- パターンⅡ：「０」と「１」の数が同数
上記以外のパターンは考えないとする前提ですので、この問題の実用性については不明ですが、量子コンピュータの高速性が最初に証明された問題です。
量子回路
量子コンピュータで行う演算は大きく３つの段階があります。
- 量子の重ね合わせの状態を作る
- 重ね合わせの状態で並列処理を行う
- 結果を取り出す
この２つ目の並列処理が、量子コンピュータが圧倒的に高速である秘密です。この処理を実現する量子回路は以下になります。ここでは４ビットのパターンを検索する回路を例にとります。
この図の、入力側の $x_1,x_2$ はアドレスビットで、4ビットの配列の位置を表します。$y$ はレジスタビットで、アドレスに対するビットに対応します。［Ｈ］はアダマールゲート、［Ｂ］はビット読み出し、［Ｕ］は制御位相シフトゲートを表します。具体的な動作は後で説明します。
４つの操作の内、操作Ａで量子ビットの重ね合わせの状態を作り、操作Ｂでビット読み出しの並列処理を行い、操作Ｃと操作Ｄで一意的な結果を取り出します。
尚、各量子ビットの入力（初期状態）は、全て０であると仮定します。
$$\Psi_0=\ket{\psi_0,y}=\ket{x_1x_2,y}=\ket{00,0}$$
そして、操作Ａ～Ｄを行い、最後の $\psi_4$ で $\ket{00}$ 以外の項が残るかどうかで、パターンⅠかパターンⅡかの判断を行います。
- パターンⅠ：$\ket{00}$ の項のみ残る
- パターンⅡ：$\ket{00}$ の項以外も残る
アルゴリズムの説明
重ね合わせの状態を作る
操作Ａのアダマールゲートは、量子ビットに対し以下の操作を行います。
$$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}$$
これを計算すると以下のように、４ビットに相当するアドレスビットのパターンが生成されます。
$$\Psi_1=\frac{1}{2}(\ket{00,0}+\ket{01,0}+\ket{10,0}+\ket{11,0})$$
並列処理を行う
操作Ｂでは、各アドレスに相当するビットをレジスタビットで読み出します。例えばビット列が［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$ |
ここで、４ビットの読み出しが１回で（並列で）行われていることがポイントです。
結果を取り出す
操作Ｃは制御位相シフトゲートで、レジスタビットが「１」の場合に、位相を反転（符号を反転）させます。２つのビットパターンで具体的に書くと以下になります。
| パターン（$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$ |
次の操作Ｄでは、再度アダマールゲートを通します。
$$H\ket{00}=\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{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］の場合は、左から２列目の項が全て「＋」になるため、$+\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}$ 以外の項が残ってしまうことが分かります。
ステップ数の比較
ドイチュ-ジョサの問題を従来のコンピュータで解く場合、ビット配列を端から１つづつ確認する必要があります。例えば、４ビット（＝$2^2$ ビット）の場合、２ビットを確認して全て「０」でも、たまたまである可能性もあるので、まだパターンⅠがパターンⅡかの判断はできません。必ずビット数の半分より１つ多い回数（２＋１回）確認する必要があります。
一般に $2^N$ ビットの配列の場合は、$2^{N-1}+1$ 回のステップが必要になります。
一方、量子回路のステップ数を数えると、操作Aでは２つのアダマールゲートがあるので２ステップ、操作B～Cは２ステップ、操作Dは操作Aと同様２ステップで、合計６ステップとなります。
これはビット配列の数は４ビット（$=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 |
このように、ビット数が増えた場合は、量子コンピュータでは圧倒的に少ないステップ数で計算を完了させることができます。
