量子回路

量子情報理論における量子回路とは、量子ゲートの組み合わせにより記述される量子計算モデルである。古典的コンピュータの回路がビットレジスタの不可逆変換であるのに対し、量子回路は量子ビットレジスタの可逆変換を行う。各回路素子である量子ゲートやそれらの間の結合を表現するための記法として、 現在主にペンローズのグラフィカル記法が用いられている。 
可逆な古典的論理ゲート.
一般に、NOTゲート以外の古典的コンピュータの基本論理ゲートは不可逆演算であり、入力から出力にかけて情報が失われる。たとえば2入力ANDゲートにおいて出力ビットが0であったという結果のみから、それが01, 10, 00のどの入力ビットの組み合わせから得られたものなのか知ることは不可能である。 
ただし、古典的コンピュータにおいても、NOTゲートに代表されるように、任意の長さのビット列に対して可逆ゲートを構成することができないわけではない。理想的には、可逆ゲートは情報の損失と物理学的エントロピーの増加に伴う電力消費や熱損失の問題を生じないため、応用面でも関心が寄せられている。一般に可逆ゲートは、ビット列を入力として受け取り、同じ長さのビット列を出力する可逆な関数として表される。長さ"n"のビット列は、0と1だけで構成される文字列"x"1"x"2 ... "x""n"∈{0,1}"n"として表現され、このようなビット列は全部で2"n"通り存在する。 
より厳密には、可逆ゲートとは、ビット列の集合{0,1}"n"から自身への全単射写像"f"として表現される。このような可逆ゲート"f"の例としては、たとえば入力に定められた置換を適用する写像などが挙げられる。現在、こうした置換を用いて可逆な古典的論理ゲートを構成する手法は、真偽表などを用いて簡単に表現できる範囲の小さい"n"（例： "n" = 1, 2, 3）についてのみ研究されている。 
量子論理ゲート.
量子ゲートを定義するため、古典的論理ゲートの場合と同様、"n"-量子ビットの置換について考える。 古典的なビット列空間{0,1}"n"の量子版はヒルベルト空間である。 
これは定義により、{0,1}"n"の複素関数空間、すなわち内積空間である。 この空間は、古典的なビット文字列の線形重ね合わせで構成されていると見なすこともできる。（"H" QB（ "n" ）は、 2"n"-次元の複素のベクトル空間であることに注意。）この空間の要素を量子ビット列（"n-"量子ビット）と呼ぶ。 
古典的ビット列"x" 1 "x" 2 ... "x" "n"に対し、ディラックのケット表記を使用し表記される量子ビット列、 
を考える。これは古典的ビット列"x" 1 "x" 2 ... "x" "n"を1へ、他のすべてのビット文字列を0へ写す関数に対応する特殊な量子ビット列である。これら古典的ビット列に対応する特殊な量子ビット列は計算基底状態と呼ばれ、ビット長"n"に対し2"n"個存在する。また、すべての量子ビット列は、これらの計算基底状態の複素線形結合である。 
古典的な論理ゲートとは対照的に、量子論理ゲートは常に可逆である。 これには特別な種類の可逆関数、すなわちユニタリ作用素、つまりエルミート内積を保存する複素内積空間の線形変換を用いる。 すべての量子ビット列に対する（可逆）量子ゲートは、"n"-量子ビット空間"H"QB("n"）から自己へのユニタリ作用素"U"である。 
通常、我々は"nの"小さな値のゲートのみに関心がある。 
可逆な"n-"ビットの古典的論理回路は、次のように可逆な"n-"ビット量子ゲートを生成する。可逆な"n"ビット論理ゲート"fに"は、次のように定義された量子ゲート"W" "f"が対応する。 
"W""f"は計算の基底状態を置換することに注意。 
中でも特に重要なのは、2-量子ビットの入出力に対して定義される制御NOTゲート（ CNOTゲートとも呼ばれる） "W" CNOTである。 古典的な論理ゲートから派生した量子論理ゲートの他の例としては、 トフォリゲートとフレドキンゲートが挙げられる。 
しかし、量子ビットのヒルベルト空間構造は、古典的ゲートでは表現できない多くの量子ゲートを可能にする。 たとえば以下の相対位相シフトは、ユニタリ行列の乗算によって与えられる1-量子ビットのゲートである。 
すなわち、 
可逆論理回路.
再び、最初の「可逆な」古典計算について考える。 概念的には、可逆な"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"を生成できることを意味する。 
さらに次式が成立する。 
この最終結果では、常に補助ビットとして"m個の"ゼロの文字列があることに注意。 いわゆる「ゴミ」は生成されないため、この計算は実際には、物理学的エントロピーを増加させない。 この問題は、Kitaevの論文で注意深く説明されている。 
より一般に、任意の関数"f" は、（全単射・それ以外どちらであっても）トフォリゲートのみ回路によって模倣できることが知られている。 写像が単射でない場合は、計算途中（たとえば、最後のステップ）で「ゴミ」が生成されることは明らかである。 
量子回路については、量子ビットゲートの同様の構成を定義できる。 つまり、上記のような任意の古典的結合に関連して、 "fの"代わりに"n-"量子ビットゲート"U"が、 "gの"代わりに"m"-量子ビットゲート"W"がある場合、可逆な量子回路を生成できる。ここでは以下の図を例に説明する。 
 この方法でゲートを接続することで、 ("n+m-k")-量子ビット空間におけるユニタリ作用素が生成されるという事実は簡単に確認できる。 実際の量子コンピュータでは、ゲート間の物理的な接続は、 デコヒーレンスが発生する可能性がある場所の1つであるため、工学上の課題である。 
普遍性、すなわち、少数の種類のゲートの組み合わせのみで、任意の量子回路が構成できることも証明されている。こうした量子回路の普遍性定理()は、たとえばあるθに対する1-量子ビットの位相ゲート"Uθ"と、2-量子ビットCNOTゲート "W" CNOTの組に対してのものが知られている。 
ただし、量子回路の普遍性定理は、古典的回路の普遍性定理よりも弱い主張になっている。なぜなら、任意の可逆"n-"量子ビット回路が、これら2つの基本ゲートから組み立てられた回路によって任意に適切に近似できることのみを主張しているからである。また、古典的回路とは異なり、非可算な角度θに対して同じ量だけの位相ゲートが存在するため、少なくともこれらは有限の{("U"θ, "W"CNOT)}のみでは表現できないことにも注意が必要である。 
量子計算.
ここまでで、量子回路を使用して計算を実行する方法は示していなかった。 多くの重要な数値問題は有限次元空間でユニタリ変換"U"を計算することに還元されるため（有名な離散フーリエ変換が主な例）、変換"U"を実行するようにいくつかの量子回路を設計できると期待できる。原理的には、一方が入力の計算基底状態の適切な重ね合わせとして"、n-"量子ビットの状態ψを用意し、出力"U"ψを測定するだけでよい。 ただし残念ながら、これには2つの課題がある。 
これは、離散フーリエ変換の量子回路が他の量子回路の中間ステップとして使用できることを否定するものではないが、実用化は一層困難である。実際、量子計算は確率的であるといわれている。 
以下では、量子回路を確率的な古典的コンピュータによって模倣する数理モデルを紹介する。 まず、レジスタ空間"H" QB("r")上の "r-"量子ビット回路"U、" 
を考える。 "U"はユニタリ作用素である。この回路をビット列の古典的写像に関連付けるには、次のように指定する。 
入力レジスタの内容"x" = "x" 1 .. "x" "m"は、量子ビットレジスタを何らかの方法で初期化するために使用される。 理想的には、これは以下の計算基底状態として与えられる。 
ただし、前述の通りこのように理想的な初期状態を用意することは現実的には不可能であるため、初期状態がいくつかの適切な近似尺度の理想化された入力に近い密度演算子"S"によって与えられた混合状態であると仮定する。 
同様に、出力レジスタ空間は、観測値"Aの" "Y"値によって、量子ビットレジスタに関連付けられる。量子力学の観測は、通常、射影測定() Rで定義される。変数が離散的である場合、射影測定は、可算集合上のパラメータλで添字付けされた族{Eλ}に還元される。 同様に、"Y"値の観測は、 次の性質を満たす"Yの"要素によってインデックスが付けられたペアワイズ直交投影{E"y" }の族に関連付けることができる。 
与えられた混合状態"S"に対し、これは次式で与えられる"Y"上の確率測度に対応する。 
長さ"mの"すべてのビット文字列"x"に対して次式が成立するとき、関数"F" ： "X" → "Y"は回路"U" ： "H" QB（ "r" ） → "H" QB（ "r" ）によって誤差εで回路内で計算できるとする。 
ここで、 
そのため 
定理 もしε+δ<1/2であるならば、"Y"上の確率分布 
は、十分に大きなサンプルサイズに対して、多数決サンプリングによって誤差の確率が任意に小さい"F"("x")を決定できる。 具体的には、 "Y"上"の"確率分布から"k個の"独立したサンプルを取得し、サンプルの半分以上が一致する値を選択する。 値"F" ("x")が"k" / 2回以上サンプリングされる確率は少なくとも次式で表される。 
ただし、γ= 1/2-ε-δである。これはチェルノフ限界を適用することで得られる。