量子回路

量子情報理論における量子回路（りょうしかいろ）とは、量子ゲートの組み合わせにより記述される量子計算モデルである。古典的コンピュータの回路がビットレジスタの不可逆変換であるのに対し、量子回路は量子ビットレジスタの可逆変換を行う。各回路素子である量子ゲートやそれらの間の結合を表現するための記法として、現在主にペンローズのグラフィカル記法が用いられている。

可逆な古典的論理ゲート

一般に、NOTゲート以外の古典的コンピュータの基本論理ゲートは不可逆演算であり、入力から出力にかけて情報が失われる。たとえば2入力ANDゲートにおいて出力ビットが0であったという結果のみから、それが01, 10, 00のどの入力ビットの組み合わせから得られたものなのか知ることは不可能である。

ただし、古典的コンピュータにおいても、NOTゲートに代表されるように、任意の長さのビット列に対して可逆ゲートを構成することができないわけではない。理想的には、可逆ゲートは情報の損失と物理学的エントロピーの増加に伴う電力消費や熱損失の問題を生じないため、応用面でも関心が寄せられている。一般に可逆ゲートは、ビット列を入力として受け取り、同じ長さのビット列を出力する可逆な関数として表される。長さnのビット列は、0と1だけで構成される文字列x₁x₂ ... x_n∈{0,1}ⁿとして表現され、このようなビット列は全部で2ⁿ通り存在する。

より厳密には、可逆ゲートとは、ビット列の集合{0,1}ⁿから自身への全単射写像fとして表現される。このような可逆ゲートfの例としては、たとえば入力に定められた置換を適用する写像などが挙げられる。現在、こうした置換を用いて可逆な古典的論理ゲートを構成する手法は、真偽表などを用いて簡単に表現できる範囲の小さいn（例： n = 1, 2, 3）についてのみ研究されている。

量子論理ゲート

量子ゲートを定義するため、古典的論理ゲートの場合と同様、n-量子ビットの置換について考える。古典的なビット列空間{0,1}ⁿの量子版はヒルベルト空間である。

H_{\operatorname {QB} (n)}=\ell ^{2}(\{0,1\}^{n}).

これは定義により、{0,1}ⁿの複素関数空間、すなわち内積空間である。この空間は、古典的なビット文字列の線形重ね合わせで構成されていると見なすこともできる。（H _{QB（ n ）}は、 2ⁿ-次元の複素のベクトル空間であることに注意。）この空間の要素を量子ビット列（n-量子ビット）と呼ぶ。

古典的ビット列x ₁ x ₂ ... x _nに対し、ディラックのケット表記を使用し表記される量子ビット列、

|x_{1},x_{2},\cdots ,x_{n}\rangle \quad

を考える。これは古典的ビット列x ₁ x ₂ ... x _nを1へ、他のすべてのビット文字列を0へ写す関数に対応する特殊な量子ビット列である。これら古典的ビット列に対応する特殊な量子ビット列は計算基底状態と呼ばれ、ビット長nに対し2ⁿ個存在する。また、すべての量子ビット列は、これらの計算基底状態の複素線形結合である。

古典的な論理ゲートとは対照的に、量子論理ゲートは常に可逆である。これには特別な種類の可逆関数、すなわちユニタリ作用素、つまりエルミート内積を保存する複素内積空間の線形変換を用いる。すべての量子ビット列に対する（可逆）量子ゲートは、n-量子ビット空間H_QB(n）から自己へのユニタリ作用素Uである。

通常、我々はnの小さな値のゲートのみに関心がある。

可逆なn-ビットの古典的論理回路は、次のように可逆なn-ビット量子ゲートを生成する。可逆なnビット論理ゲートfには、次のように定義された量子ゲートW _fが対応する。

W_{f}(|x_{1},x_{2},\cdots ,x_{n}\rangle )=|f(x_{1},x_{2},\cdots ,x_{n})\rangle .

W_fは計算の基底状態を置換することに注意。

中でも特に重要なのは、2-量子ビットの入出力に対して定義される制御NOTゲート（ CNOTゲートとも呼ばれる） W _CNOTである。古典的な論理ゲートから派生した量子論理ゲートの他の例としては、トフォリゲートとフレドキンゲートが挙げられる。

しかし、量子ビットのヒルベルト空間構造は、古典的ゲートでは表現できない多くの量子ゲートを可能にする。たとえば以下の相対位相シフトは、ユニタリ行列の乗算によって与えられる1-量子ビットのゲートである。

U_{\theta }={\begin{bmatrix}e^{i\theta }&0\\0&1\end{bmatrix}},

すなわち、

U_{\theta }|0\rangle =e^{i\theta }|0\rangle \quad U_{\theta }|1\rangle =|1\rangle .

可逆論理回路

再び、最初の「可逆な」古典計算について考える。概念的には、可逆なnビット回路と可逆なnビット論理ゲートの間に違いはない。なぜならどちらも、 nビット列空間上の単なる可逆関数だからである。ただし前節で述べたように、工学的な理由から、可逆回路を構成するために組み合わせられる少数の単純な可逆ゲートが必要である。

この構成の過程を説明するために、可逆なn-ビットゲートfと、可逆なm-ビットゲートgがあるとする。これらを合成することは、次の図のように、 fのk-ビットの出力を、gのk-ビットの入力に接続して新しい回路を作成することを意味する。以下の例では、 n = 5, k = 3, m = 7である。結果の回路も可逆で、(n +m-k)-ビットで動作する。

この方法は古典的結合(classical assemblage)と呼ばれる。（この概念は、以下に引用するKitaevの先駆的な論文の技術的定義に対応している。）。これらの可逆機械を構成するために、中間的な機械も可逆であることを確認することが重要である。この条件は、計算の途中で「ゴミ」が生成されないことを保証する。（正味の物理的効果は、エントロピーを増加させることである。これは、この演習を行う動機の1つである。）

これで、トフォリゲートが汎用ゲートであることを示すことができる。これは、任意の可逆的な古典的なnビット回路hが与えられた場合、上記の方法でトフォリゲートの古典的結合により、次のような（ n + m ）ビット回路fを生成できることを意味する。

f(x_{1},\ldots ,x_{n},\underbrace {0,\dots ,0} _{m})=(y_{1},\ldots ,y_{n},\underbrace {0,\ldots ,0} _{m})

さらに次式が成立する。

(y_{1},\ldots ,y_{n})=h(x_{1},\ldots ,x_{n})

.

この最終結果では、常に補助ビットとしてm個のゼロの文字列があることに注意。いわゆる「ゴミ」は生成されないため、この計算は実際には、物理学的エントロピーを増加させない。この問題は、Kitaevの論文で注意深く説明されている。

より一般に、任意の関数f は、（全単射・それ以外どちらであっても）トフォリゲートのみ回路によって模倣できることが知られている。写像が単射でない場合は、計算途中（たとえば、最後のステップ）で「ゴミ」が生成されることは明らかである。

量子回路については、量子ビットゲートの同様の構成を定義できる。つまり、上記のような任意の古典的結合に関連して、 fの代わりにn-量子ビットゲートUが、 gの代わりにm-量子ビットゲートWがある場合、可逆な量子回路を生成できる。ここでは以下の図を例に説明する。

この方法でゲートを接続することで、 (n+m-k)-量子ビット空間におけるユニタリ作用素が生成されるという事実は簡単に確認できる。実際の量子コンピュータでは、ゲート間の物理的な接続は、デコヒーレンスが発生する可能性がある場所の1つであるため、工学上の課題である。

普遍性、すなわち、少数の種類のゲートの組み合わせのみで、任意の量子回路が構成できることも証明されている。こうした量子回路の普遍性定理(universality theorems)は、たとえばあるθに対する1-量子ビットの位相ゲートU_θと、2-量子ビットCNOTゲート W _CNOTの組に対してのものが知られている。

ただし、量子回路の普遍性定理は、古典的回路の普遍性定理よりも弱い主張になっている。なぜなら、任意の可逆n-量子ビット回路が、これら2つの基本ゲートから組み立てられた回路によって任意に適切に近似できることのみを主張しているからである。また、古典的回路とは異なり、非可算な角度θに対して同じ量だけの位相ゲートが存在するため、少なくともこれらは有限の{(U_θ, W_CNOT)}のみでは表現できないことにも注意が必要である。

量子計算

ここまでで、量子回路を使用して計算を実行する方法は示していなかった。多くの重要な数値問題は有限次元空間でユニタリ変換Uを計算することに還元されるため（有名な離散フーリエ変換が主な例）、変換Uを実行するようにいくつかの量子回路を設計できると期待できる。原理的には、一方が入力の計算基底状態の適切な重ね合わせとして、n-量子ビットの状態ψを用意し、出力Uψを測定するだけでよい。ただし残念ながら、これには2つの課題がある。

観測者が任意の計算基底状態における位相ψを測定することは不可能であり、正確な出力を読み取る方法がない。これは量子力学における測定の性質である。
入力状態である重ね合わせψを用意する効果的な方法が今のところない。

これは、離散フーリエ変換の量子回路が他の量子回路の中間ステップとして使用できることを否定するものではないが、実用化は一層困難である。実際、量子計算は確率的であるといわれている。

以下では、量子回路を確率的な古典的コンピュータによって模倣する数理モデルを紹介する。まず、レジスタ空間H _QB(r)上の r-量子ビット回路U、

H_{\operatorname {QB} (r)}\rightarrow H_{\operatorname {QB} (r)}.

を考える。 Uはユニタリ作用素である。この回路をビット列の古典的写像に関連付けるには、次のように指定する。

入力レジスタ：m-古典的ビット列 'X' = {0,1}^m
出力レジスタ：n-古典的ビット列 Y = {0,1}ⁿ

入力レジスタの内容x = x ₁ .. x _mは、量子ビットレジスタを何らかの方法で初期化するために使用される。理想的には、これは以下の計算基底状態として与えられる。

|{\vec {x}},0\rangle =|x_{1},x_{2},\cdots ,x_{m},\underbrace {0,\dots ,0} _{r-m}\rangle ,

ただし、前述の通りこのように理想的な初期状態を用意することは現実的には不可能であるため、初期状態がいくつかの適切な近似尺度の理想化された入力に近い密度演算子Sによって与えられた混合状態であると仮定する。

\operatorname {Tr} \left({\big |}|{\vec {x}},0\rangle \langle {\vec {x}},0|-S{\big |}\right)\leq \delta .

同様に、出力レジスタ空間は、観測値Aの Y値によって、量子ビットレジスタに関連付けられる。量子力学の観測は、通常、射影測定(projection valued measure) Rで定義される。変数が離散的である場合、射影測定は、可算集合上のパラメータλで添字付けされた族{E_λ}に還元される。同様に、Y値の観測は、次の性質を満たすYの要素によってインデックスが付けられたペアワイズ直交投影{E_y }の族に関連付けることができる。

I=\sum _{y\in Y}\operatorname {E} _{y}.

与えられた混合状態Sに対し、これは次式で与えられるY上の確率測度に対応する。

\operatorname {Pr} \{y\}=\operatorname {Tr} (S\operatorname {E} _{y}).

長さmのすべてのビット文字列xに対して次式が成立するとき、関数F ： X → Yは回路U ： H _{QB（ r ）} → H _{QB（ r ）}によって誤差εで回路内で計算できるとする。

\left\langle {\vec {x}},0{\big |}U^{*}\operatorname {E} _{F(x)}U{\big |}{\vec {x}},0\right\rangle =\left\langle \operatorname {E} _{F(x)}U(|{\vec {x}},0\rangle ){\big |}U(|{\vec {x}},0\rangle )\right\rangle \geq 1-\epsilon .

ここで、

\left|\operatorname {Tr} (SU^{*}\operatorname {E} _{F(x)}U)-\left\langle {\vec {x}},0{\big |}U^{*}\operatorname {E} _{F(x)}U{\big |}{\vec {x}},0\right\rangle \right|\leq \operatorname {Tr} ({\big |}|{\vec {x}},0\rangle \langle {\vec {x}},0|-S{\big |})\|U^{*}\operatorname {E} _{F(x)}U\|\leq \delta

そのため

\operatorname {Tr} (SU^{*}\operatorname {E} _{F(x)}U)\geq 1-\epsilon -\delta .

定理もしε+δ<1/2であるならば、Y上の確率分布

\operatorname {Pr} \{y\}=\operatorname {Tr} (SU^{*}\operatorname {E} _{y}U)

は、十分に大きなサンプルサイズに対して、多数決サンプリングによって誤差の確率が任意に小さいF(x)を決定できる。具体的には、 Y上の確率分布からk個の独立したサンプルを取得し、サンプルの半分以上が一致する値を選択する。値F (x)がk / 2回以上サンプリングされる確率は少なくとも次式で表される。

1-e^{-2\gamma ^{2}k},

ただし、γ= 1/2-ε-δである。これはチェルノフ限界を適用することで得られる。

参考文献

Biham, Eli; Brassard, Gilles; Kenigsberg, Dan; Mor, Tal (2004), “Quantum computing without entanglement”, Theoretical Computer Science 320 (1): 15–33, arXiv:quant-ph/0306182, doi:10.1016/j.tcs.2004.03.041, MR 2060181
Freedman, Michael H.; Kitaev, Alexei; Larsen, Michael J.; Wang, Zhenghan (2003), “Topological quantum computation”, Bulletin of the American Mathematical Society 40 (1): 31–38, arXiv:quant-ph/0101025, doi:10.1090/S0273-0979-02-00964-3, MR1943131 。
Hirvensalo, Mika (2001), Quantum Computing, Natural Computing Series, Berlin: Springer-Verlag, ISBN 3-540-66783-0, MR1931238 Hirvensalo, Mika (2001), Quantum Computing, Natural Computing Series, Berlin: Springer-Verlag, ISBN 3-540-66783-0, MR1931238 Hirvensalo, Mika (2001), Quantum Computing, Natural Computing Series, Berlin: Springer-Verlag, ISBN 3-540-66783-0, MR1931238 。
Kitaev, A. Yu. (1997), “Quantum computations: algorithms and error correction” (Russian), Uspekhi Mat. Nauk 52 (6(318)): 53–112, Bibcode: 1997RuMaS..52.1191K, doi:10.1070/RM1997v052n06ABEH002155, MR1611329 。
Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, ISBN 0-521-63235-8, MR1796805 Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, ISBN 0-521-63235-8, MR1796805 Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, ISBN 0-521-63235-8, MR1796805 。

外部リンク

Q-circuit - LaTeXで量子回路図を描くためのマクロパッケージ
量子回路シミュレータ（Davy Wybiral） - ブラウザベースの量子回路図エディタ
Quantum Computing Playgroundは - ブラウザベースの量子スクリプト環境
Quirk-Quantum Circuit Toy - ブラウザベースの量子回路図エディタ