量子コンピューターでの古典計算

ここでは、量子コンピューターに古典的なアルゴリズムを実装することに注目します。 古典的なブール回路で実行できる計算はすべて、同様の漸近的な計算コストで量子回路によっても実行できます。 さらに、これは後ほど説明する「クリーンな」方法で行うことができ、これはより大きな量子計算のサブルーチンとしてこれらの計算を使用するための重要な要件です。

ブール回路を量子回路でシミュレートする

ブール回路はAND、OR、NOT、FANOUTゲートで構成されています。 量子回路でブール回路をシミュレートするために、まずこれら4つのゲートそれぞれを量子ゲートでどのようにシミュレートできるかを示します。 それが完了すれば、与えられたブール回路を量子回路に変換することは、1つずつゲートをシミュレートするだけの簡単な作業です。 これを行うために必要なのはNOTゲート、制御NOTゲート、トフォリゲートだけであり、これらはすべてユニタリ演算であるとともに決定論的な演算でもあります。

トフォリゲート

トフォリゲートは、制御-制御-NOTゲートとも呼ばれ、標準基底状態に対する作用は以下の図のとおりです。

Qiskitの順序付け規則（上から下に向かって重要度が増す順に量子ビットが並ぶ）を念頭に置くと、このゲートの行列表現は以下のとおりです。

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

トフォリゲートについての別の考え方として、これらは本質的にAND関数のクエリゲートであるということです。前のレッスンで見た、バイナリ文字列の入出力を持つ任意の関数のユニタリクエリゲート実装のパターンに従っています。

トフォリゲートは先ほどのレッスンで説明したデフォルトのゲートセットには含まれていませんが、$H,$ $T,$ $T^{\dagger},$ およびCNOTゲートから以下のようにトフォリゲートを構成することが可能です。

トフォリゲート、制御NOTゲート、NOTゲートによるブールゲートのシミュレート

1つのトフォリゲートを少数のNOTゲートと組み合わせることで、ANDゲートおよびORゲートを実装でき、FANOUTゲートは以下の図が示すように制御NOTゲートを使用して簡単に実装できます。

3つのケースすべてにおいて、AND、OR、FANOUTゲートが作用する量子ビットは左から入力として入ってきます。また、それぞれに対してゼロ状態に初期化された1つのワークスペース量子ビットが必要です。 これらのワークスペース量子ビットはゲート実装を表すボックスの内側に表示されており、これらが新しく追加されたものであり、実装のコストの一部であることを示しています。

ANDゲートとORゲートの場合、出力量子ビットに加えて2つの量子ビットが残ります。 例えば、ANDゲートのシミュレーションを表すボックスの内側では、上の2つの量子ビットが $\vert a\rangle$ および $\vert b\rangle$ の状態のまま残っています。 これらの量子ビットはもはや必要とされず出力の一部ではないため、ボックスの内側に残っているものとして図示されています。 今は無視してかまいませんが、後ほど改めて注目します。

残りのブールゲートであるNOTゲートは、デフォルトの量子ゲートセットに含まれているため、このゲートのシミュレーションは必要ありません。

ブール回路のゲートごとのシミュレーション

ここで、AND、OR、NOT、FANOUTゲートで構成された通常のブール回路 $C$ があり、 $n$ 個の入力ビットと $m$ 個の出力ビットを持つとします。 $t = \operatorname{size}(C)$ を $C$ のゲート数とし、$C$ が計算する関数に $f$ という名前を付けます。この関数は以下の形をとります。

$$f:\Sigma^n\rightarrow\Sigma^m$$

ただし $\Sigma = \{0,1\}$ です。

次に、$C$ のAND、OR、FANOUTゲートを1つずつ処理し、それぞれを上述の対応するシミュレーションに置き換え、必要なワークスペース量子ビットも追加した場合を考えます。 得られた回路を $R$ と名付け、$C$ の $n$ 個の入力ビットが $R$ の上位 $n$ 個の量子ビットに対応し、ワークスペース量子ビットが下部に来るように $R$ の量子ビットを順序付けます。

ここで、$k$ は必要なワークスペース量子ビットの数（$C$ のAND、OR、FANOUTゲートそれぞれに1つ）であり、$g$ は $R$ を実行した後のゲートシミュレーションによって作成された残余量子ビットの状態を記述する $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ の形の関数です。 図では、出力 $f(x)$ に対応する量子ビットが上部にあり、$g(x)$ を格納する残余量子ビットが下部にあります。 これを実現したい場合は、3つの制御NOTゲートで以下のように実装できるSWAPゲートを使用して量子ビットを並べ替えることができます。

次のセクションで見るように、このように出力量子ビットを並べ替えることは必須ではありませんが、希望すれば簡単に行うことができます。

残余量子ビットの古典的な状態を記述する関数 $g$ は回路 $C$ によって決まりますが、実際にはあまり気にする必要はありません。 計算が終了したときにこれらの量子ビットがどの状態にあるかを具体的に気にする必要はないのです。 文字 $g$ は $f$ の後に来るのでその意味では妥当な名前ですが、$g$ という名前を選ぶより良い理由があります。 それはガベージ（garbage）の略だからです。

ガベージの後始末

与えられたブール回路 $C$ で計算される関数 $f$ を量子回路で評価することだけに興味がある場合は、ゲートごとのシミュレーションから先に進む必要はありません。 これは、関数の出力に加えて、大量のガベージが残ることを意味します。

しかし、古典的な計算をより大きな量子計算のサブルーチンとして実行したい場合には、これでは不十分です。なぜなら、それらのガベージ量子ビットが問題を引き起こすからです。 干渉という現象は量子アルゴリズムにとって非常に重要であり、ガベージ量子ビットは量子アルゴリズムを機能させるために必要な干渉パターンを損なう可能性があります。

幸いなことに、いわばガベージを後始末することはそれほど難しくありません。 鍵となるのは、$R$ が量子回路であるため、各ゲートをその逆演算に置き換えて逆順に適用することで逆向きに実行し、演算 $R^{\dagger}$ の量子回路を得られるという事実を利用することです。 トフォリゲート、CNOTゲート、NOTゲートは実際には自分自身の逆演算ですので、$R$ を逆向きに実行することは実質的にゲートを逆順に適用するだけですが、より一般的にはあらゆる量子回路を先述のように逆向きにすることができます。

具体的には、$m$ 個の量子ビットをさらに追加し（関数 $f$ が $m$ 個の出力ビットを持つことを思い出してください）、CNOTゲートを使用して $R$ の出力をこれらの量子ビットにコピーし、$R$ を逆向きに実行してガベージを後始末します。 以下の図は、得られた回路と標準基底状態に対するその作用を示しています。

回路全体をボックスで囲んで $Q$ と呼ぶと、次のようになります。

$C$ が $t$ 個のゲートを持つ場合、回路 $Q$ は $O(t)$ 個のゲートを持ちます。

$k$ 個の追加ワークスペース量子ビットを無視すると、回路 $Q$ は関数 $f$ のクエリゲートとまったく同様に機能します。 ある文字列 $x$ に対して関数 $f$ を単純に計算したい場合は、$y = 0^m$ と設定すると、下位 $m$ 個の量子ビットに結果 $f(x)$ が現れます。また、下位 $m$ 個の量子ビットに異なる状態を入力することもできます （例えば、ドイチュアルゴリズムやドイチュ-ジョザアルゴリズムのように位相キックバックを利用するなど）。

これは、任意のクエリアルゴリズムにおいて、入力関数を計算するブール回路があれば、各クエリゲートをその回路実装に置き換えることができ、クエリアルゴリズムが正しく機能することを意味します。

なお、このプロセスを機能させるためにワークスペース量子ビットが必要ですが、組み合わせた回路が実行されると初期状態に戻ります。 これにより、これらの量子ビットを他の目的のワークスペース量子ビットとして再利用することができます。 また、必要なワークスペース量子ビットの数を削減する既知の戦略もありますが（回路を大きくするコストがかかります）、ここではそれらの戦略については説明しません。

可逆関数の実装

先ほど説明した構成により、任意のブール回路をガベージフリーな方法で量子回路でシミュレートすることができます。 $C$ が関数 $f:\Sigma^n \rightarrow \Sigma^m$ を実装するブール回路であれば、標準基底状態に対して以下のように動作する量子回路 $Q$ が得られます。

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

$k$ は合計で必要なワークスペース量子ビットの数を示します。 これはこのコースの目的には十分ですが、関数 $f$ 自体が可逆である場合には、この手法をさらに一歩進めることが可能です。

正確に言うと、関数 $f$ が $f:\Sigma^n \rightarrow \Sigma^n$ の形をとり、さらにすべての $x\in\Sigma^n$ に対して $f^{-1}(f(x)) = x$ を満たす関数 $f^{-1}$ が存在するとします（これが存在する場合、必然的に一意です）。 これは、すべての $x\in\Sigma^n$ に対して $\vert x \rangle$ を $\vert f(x) \rangle$ に変換する演算がユニタリであることを意味し、以下で定義されるユニタリ演算を実装する量子回路を構築できると期待できます。

$$U \vert x \rangle = \vert f(x) \rangle$$

すべての $x\in\Sigma^n$ に対してです。

明確にしておくと、これがユニタリ演算である事実は $f$ が可逆であることに依存しています。$f$ が可逆でない場合はユニタリではありません。 ワークスペース量子ビットを無視すると、$U$ は回路 $Q$ が実装する演算とは異なります。なぜなら、入力のコピーを保持して任意の文字列にXORするのではなく、$x$ を $f(x)$ で置き換えるからです。

問題は、$f$ が可逆である場合にこれができるかどうかです。

答えはイエスです。ただし、ワークスペース量子ビットの使用が許可されており、さらに $f$ を計算するブール回路に加えて $f^{-1}$ を計算するブール回路も持っている場合に限ります。 つまり、これは計算による逆関数の求め方を既に知らない場合のショートカットではありません！ 以下の図は、$f$ と $f^{-1}$ の関数それぞれに対して上述の方法で得られた2つの量子回路 $Q_f$ と $Q_{f^{-1}}$ を合成し、$n$ 個のスワップゲートを組み合わせることでどのように実現できるかを示しています。ここで、$k$ は $Q_f$ と $Q_{f^{-1}}$ が必要とするワークスペース量子ビット数の最大値とします。