インクリメント回路

量子コンピュータが従来の古典コンピュータを凌駕できると言われる理由の一つが、重ね合わせ上で演算を実行できることです。 たとえば、1 から 100 の数字が書かれた一山のカードがあるとします。 量子コンピュータの重ね合わせ演算では、この山に含まれるカードすべてに対して「数を 3 で割った余りを計算する」といった演算をまとめて一度に実行できます。 つまり量子コンピュータは計算を並列に実行できると言えます。 一方で古典コンピュータでは、カード 1 枚ずつに対して「数を 3 で割った余りを計算する」という計算を計 100 回繰り返す必要があります。 もし重ね合わせたカードが 1 万枚、100 万枚とどんなに増えても、量子コンピュータなら重ね合わせによって並列に計算できるため、 繰り返し処理が必要な古典コンピュータよりもその点では強力です。

では、重ね合わせに対して実行する計算は、具体的に量子回路でどのように書けるでしょうか？ 実は基本的には、従来のデジタル回路 (古典の回路) で行うビット単位の論理演算 (AND や NOT、OR など) と量子版の論理演算には大きな違いはありません。ただし、量子回路では AND や NOT といった従来の論理ゲートの代わりに、 や といった量子ゲートを使うという違いがあります。 もう一つの違いは、量子ゲートは重ね合わせ状態を入力できる点です。 このため、いったん量子版の論理演算回路を作ってしまえば、重ね合わせた量子ビットの演算にも自動的に対応できます。

インクリメント (+1) 回路

まず簡単な例として、「数字に +1 する」つまりインクリメントする回路を作ってみましょう。 これを量子ゲートで実現するためには、「数字に +1 する」という処理をビット単位での演算、つまり二進数での演算で考える必要があります。

まずは入力を 0 として、インクリメントして 1 を計算する回路を考えます。 これは単純に 0 → 1 にすればいいのですから、次のように で反転させれば OK です。

次は入力を 1 として、インクリメントして 2 を計算する回路を考えます。 1 を二進数で表すと 01、2 を二進数で表すと 10 なので、これは 01 → 10 に変換する回路と言えます。 これはつまり、ビット 0 が 1 であればビット 2 を反転し、その後にビット 0 を反転させれば良さそうです。 こうした「ビット 0 が 1 であればビット 2 を反転」という条件付き反転は、CNOT ゲートで書けます。 これと によるビット 0 の反転を組合わせると、1 を 2 にインクリメントする回路は次のように書けます。

この CNOT ゲートはビット 0 が 1 の時に一桁上のビット 1 を 1 に反転させるので、繰り上げ (ビット演算では「キャリー」と呼ばれる) を計算しています。 この CNOT ゲートはビット 0 が 1 の時にしか発動しないため、最初の 0 を 1 にインクリメントする回路 (X ゲート 1 つの回路) の機能も含んでいます。 つまり、0 または 1 をインクリメントする回路は、この CNOT と X による回路ひとつで表すことができます。

同様にビットを増やしていくと、3 ビットまでの数 (0から7) に +1 する回路は、以下のように作ることができます。 入力の 1 が実際に 2 にインクリメントされるかどうか試してみましょう。 また、入力を作る X ゲートの配置を変えることで 0 から 7 までの入力を作ることができます。 こちらも実際に +1 されるかどうか試してみましょう (ビット 0 の X ゲートをビット 1 に移動すると 2 (二進数で 10)、ビット 2 に移動すると 4 (二進数で 100) を入力できます)。

重ね合わせを入力する

では、この回路が重ね合わせに対応していることを確認しましょう。 これまで見てきたように、重ね合わせを作るには を使います。 たとえば以下のようにビット 0 に 、ビット 2 に を置くと、1 と 5 の重ね合わせを入力できます。 これに対して先ほどのインクリメント回路を適用すると、1 と 5 それぞれに +1 した、2 と 6 の重ね合わせが出力されます。

ハンズオン

入力を作る と の配置を変えることで、いろいろな重ね合わせに対してインクリメント回路を動作させてみましょう。

• 5 と 7 の重ね合わせを入力するにはどうしたらよいでしょうか?
• 0 〜 7 すべての重ね合わせを入力するにはどうしたらよいでしょうか？

注意点: 重ね合わせはそのまま取り出せない

重ね合わせ演算を入力して何らかの算術演算をすると、同様に重ね合わされた状態が出力されます。 注意しなければならないのは (そしてすぐ忘れてしまいがちなのは)、重ね合わせはそのまま取り出せず、測定によってどれか 1 つの値だけしか確率的に取り出せないということです。 Qni はシミュレータであるため、実行中の量子コンピュータの重ね合わせ状態を見ることができますが、通常は量子コンピュータから値を取り出すには必ず測定をしなければなりません。 量子回路で表すと、計算結果を取り出すには次のように ゲートを用いて値を取り出す必要があります。

「なんだ、たとえ 100,000 個の重ね合わせに並列に計算を実行できても、そのうち 1 個しか計算結果を取り出せないんなら、並列の意味がないじゃないか」。 そう思うかもしれません。

しかし、はじめにで紹介したグローヴァーのアルゴリズム (量子探索) では、この重ね合わせ演算を次のようにうまくデータ探索に活用します。

• たくさんの重ね合わせデータに対して並列に演算を行う。この演算は算術演算ではなく、「条件に合うデータ (みつけたいデータ) に印をつける」という処理を並列に行う。
• 印をつけたデータの確率を増幅させ、測定したときに印をつけたデータが出力される確率を上げる

つまり、グローヴァーのアルゴリズムでは「大量のデータのうち条件にあうものに印をつける」という処理に重ね合わせによる並列処理を使います。 2 の確率を増幅させる操作はまだ説明していませんが、これを振幅増幅と呼び後の項目で詳しく扱います。 それまでは、重ね合わせ上の演算テクニックについてより詳しく見ていきましょう。