１９９４年にIEEE誌に発表された素因数分解に関するShorの論文は，高速な暗号解読を可能とする量子コンピュータの研究を推進する起爆剤となった。これらの画期的な量子技術の研究を推進させる元になっている基本原理は量子エンタングルメント（量子の絡み合い; entanglement）と呼ばれており，その代表的な例は電子のスピン一重項状態，すなわち全スピンがゼロの状態（スピン+1/2≡def|0>と，スピン-1/2≡def|1>の合成された状態）にある２電子系である。正確には，“複数の部分系からなる量子系において，個々の部分系の積では表されないような‘分離不能な状態’に現れる非局所的な相関”と定義される。古典系には存在しない，量子系特有の相関なので‘量子相関’と呼ばれることもある。
２電子系スピン一重項状態の量子エンタングルメントを|0>，|1>を用いて例示すると，（|0>電子１|1>電子２ - |1>電子１|0>電子２）/√２のように書ける。電子１，電子２をいちいち書くのは煩雑なので，今後はサフィックスをはずして（|0>|1> - |1>|0>）/√２と書くことにする。|0>|1>は電子１の|0>状態と電子２の|1>状態の複合状態であり，通常テンソル積と呼ばれ，テンソル記号を
とすれば|0>|1>のようにも書く。誤解が生じない限りテンソル積の記号も省略されることが多い。（|0>|1> + |1>|0>），もまたエンタングルメント状態であるが，（|0> + |1>）|0>，はエンタングルメント状態ではない。電子１は（|0> + |1>）状態で，電子２が|0>状態であり，それぞれ分離・独立している。分離している状態がエンタングルメント状態になったり（その逆も）するには相互作用が必要である。相互作用がないと，分離した状態はいつまで経っても分離したままである。自然界は複雑であり，独立した状態よりもエンタングルメント状態に多くの特質が見られ，本当に調べたい問題が多く存在する。分離している状態がエンタングルメント状態になる相互作用の例としては，方解石に入射し通過する光子がある。入射前の光子（状態はα|0>＋β|1>，|0>，|1>は偏光状態）が経路W上を進む全体の系はΨ = （α|0>＋β|1>）
|ｗ>と書ける。通過後には正常光|0>は経路Xを，異常光（屈折光）|1>は経路Yを進むので，全体の状態はΨ' = α|0>|X>＋β|1>|Y>となる。通過後はエンタングルメント状態である。注意すべきなのが変換Ψ → Ψ'の性質である。この変換をUとすれば，Ψ'= UΨであるが，明らかに全体の系の大きさ(|α|2 + |β|2 )は変化していないので，方解石の通過の相互作用はユニタリー変換(UU† = U†U = 1)である。このユニタリー性を計算のアルゴリズムの中核に据えているのが量子コンピュータである。（１）量子ゲート
古典的な情報の単位は“ビット(bit)”と呼ばれ２つの変数０と１で表されるが，対応する量子的な情報単位は“量子ビット(qubit)”と呼ばれる。量子系の状態が古典系と基本的に異なる点は，任意の重ね合わせ状態，例えばα|0>＋β|1>，を考えることができることである。この重ね合わせ原理とユニタリー変換によって量子コンピュータが構成されるのだが，その前に現在のコンピュータ（古典計算機）の論理ゲートを整理しておく。
古典計算機はNOT，AND，OR，XORの４つの代表する論理ゲートで構成される。NOTは論理否定であり，働きは１ビットのフリップ（反転）である。即ち，
|0> → |1>，
|1> → |0>
ANDは2ビットの入力から１ビットの出力を行い，その働きは，
|0>|0> → |0>，
|0>|1> → |0>，
|1>|0> → |0>，
|1>|1> → |1>
ORも2ビットの入力から１ビットの出力を行い，その働きは，
|0>|0> → |0>，
|0>|1> → |1>，
|1>|0> → |1>，
|1>|1> → |1>
XORも2ビットの入力から１ビットの出力を行い，その働きは，
|0>|0> → |0>，
|0>|1> → |1>，
|1>|0> → |1>，
|1>|1> → |0>
であって，入力のうちどちらか１ビットのみ|1>の場合に|1>を出力する。別の言い方をすれば，XORは２を法とする足し算であって，|a>|b> → |a+b, mod2>である。詳細は省くが，古典チューリングマシンはNOTとANDのみで構成されることが分かっている。つまり，古典計算機は２ビットを入力として，１ビットを出力することが基本原理である。
一方，量子計算はユニタリー変換が基本であり，逆変換が必ず存在しなければならない。NOTは|0>を|1>，|1>を|0>に変換するので，明らかに逆変換が存在し，それは自分自身である。NOT・NOT ＝ １だからである。
もう一つ，古典でのANDのような働きをする論理ゲートが必要であるが，それは制御NOT(Controlled NOT, c-NOT)ゲートと呼ばれ，２ビットを入力し２ビットを出力する。その働きは，
|0>|0> → |0>|0>，
|0>|1> → |0>|1>，
|1>|0> → |1>|1>，
|1>|1> → |1>|0>
である。最初のビットは制御ビット，2番目のビットは標的ビットと呼ばれている。機能的には，制御ビットが|0>なら標的ビットは変化しない，即ち，
|0>|0> → |0>|0>，
|0>|1> → |0>|1>
ということ，及び，制御ビットが|1>なら標的ビットは反転する，即ち，
|1>|0> → |1>|1>，
|1>|1> → |1>|0>
ということが特徴である。NOTと制御NOTがあれば全てのユニタリー変換が構成されることが証明されており，万能量子チューリングマシンが作れることが分かっている。しかし，様々な試みはなされているが，現在に至るまで制御NOTゲートを物理的に構成することは達成されていない。 制御NOTは古典でのXORのような機能に似ているともいえる。
制御NOTゲートはエンタングルメント状態を作ることと同じであることは容易に分かる。
（|0> + |1>）|0> → |0>|0> + |1>|0> ⇒c-NOT|0>|0> + |1>|1>
つまり，制御NOTゲートはユニタリー相互作用の量子計算での表現であるとも考えることができるのである。制御NOTゲートが量子計算にとって本質的であることが理解できると思う。制御NOTゲートの量子回路図を図1で示す。
（２）量子アルゴリズム
NOTと制御NOTがあれば任意のユニタリー変換が構成されることを証明し，量子コンピュータの基本原理を述べる。構成されたユニタリー変換回路は制御－U(Control-U)と呼ばれている。制御NOTは制御－Uの特別な場合である。
簡単な例として，2行2列のユニタリー行列で，行列式が１であるSU(2)を考える。行列Ａ，Ｂ，Ｃ，ＵをSU(2)の元とし，制御NOTをＸで表すと，任意のＵに対して，
ＡＢＣ＝１
Ｕ ＝ ＡＸＢＸＣ
となるように行列Ａ，Ｂ，Ｃを選ぶことができる。図２に量子回路を示す。制御ビットが|0>の時は制御NOTであるＸは働かないので，標的ビットはＡＢＣの変換を受けるが，これは定義により恒等変換である。また，変換Ａ，Ｂ，Ｃは標的ビットにのみ作用するので１キュービットのユニタリー変換であるという。制御ビットが|1>の時はＸがNOT変換として働くのでＡＸＢＸＣ（＝Ｕ）の変換が働く。Ｕは制御ビットの値により標的ビットに作用するので２キュービット制御－Uという。このようなＡ，Ｂ，ＣとＵの例としては，
Ｕ = Ｒz(α）Ｒy(β）Ｒz(γ）
（オイラー角（α，β，γ）を用いた任意の回転）及び，
Ａ = Ｒz（(α-γ)/2）
Ｂ = Ｒz（-(α+γ)/2）Ｒy(-β/2）
Ｃ = Ｒy(β/2）Ｒz(γ）
と採れば上記の条件ＡＢＣ = １，Ｕ ＝ ＡＸＢＸＣを満たすことができる。Ｒξ(α）= Exp（iασξ/2）を用いてこれを確認する計算は単純であり省略する。ここでσξ（= σxまたはσyまたはσz）は通常のパウリ行列を表す。
次に，一般的な２キュービットの場合でも，
〔a〕任意のユニタリー変換である制御－Uが
〔b〕制御NOT（上記Ｘ）と
〔c〕１キュービットのユニタリー変換（例えば上記Ａ，Ｂ，Ｃ）
で構成されることを証明する。３キュービット以上に拡張することは比較的容易である。
以下の手順で証明する。
[1]．任意の２キュービットのユニタリー変換をＳとすると，Ｓがユニタリーであるということは，Ｓの固有状態を|Ψm>として，
Ｓ|Ψm> = e iσm|Ψm>
が成立することである。従ってＳは，この固有状態を用いて，
Ｓ = Σm=03e iσm|Ψm><Ψm|
と書くことができる。
[2]．|0>，|1>を直交状態とする２キュービットの任意の重ねあわせ状態|Ψn>を直交基底の|n>に変換するユニタリー変換Ｇ(Ψn)は，〔b〕制御NOTと〔c〕１キュービットのユニタリー変換で構成される（〔証明〕）。ここに，|n>のｎは，|0>=|0>|0>，|1>=|0>|1>，|2>=|1>|0>，|3>=|1>|1>の，０から３までを表す。従って，
|Ψn> = Σm=03Cm|m>
Ｇ(Ψn)|Ψn> = |n>
が成立する。
[3]．上記Ｇ(Ψn)を用いて作るユニタリー行列Ｓ'，
Ｓ’= Πm=03Ｇ(Ψm)-1ＸmＧ(Ψm)
を考える。ここに，Ｘmは
Ｘ0 = e iσ0|0><0| + |1><1| + |2><2| + |3><3|
Ｘ1 = |0><0| + e iσ1|1><1| + |2><2| + |3><3|
Ｘ2 = |0><0| + |1><1| + e iσ2|2><2| + |3><3|
Ｘ3 = |0><0| + |1><1| + |2><2| + e iσ3|3><3|
であり，これは特別な制御－Ｕ（後述）を用いて作ることができ，制御NOTと１キュービットのユニタリー変換で構成される。
Ｓ’はＧ(Ψm)とＸmで構成されており，従って，〔b〕制御NOTと〔c〕１キュービットのユニタリー変換で構成される，ということができる。
[4]．Ｓ’はＳそのものに等しい（〔証明〕）。故に，任意の２キュービットのユニタリー変換Ｓは，〔b〕制御NOTと〔c〕１キュービットのユニタリー変換で構成されることが証明できた。
（３）量子コンピュータはなぜ速いか？
量子コンピュータがなぜ速いか，という理由は以下のように説明される。
まず第一が重ね合わせを使った量子並列計算である，
ということである。これはＮキュービットの量子コンピュータでは，２Ｎ次元のユニタリー変換を，（２）で説明した量子ゲートと呼ばれる基本的なユニタリー変換の組み合わせで，並列実行するからである。例えば，Ｎ個のキュービットを一斉に回転して，0から2N－ 1までの数を表す重ね合わせ状態を瞬時につくることができる。これを，2進数表示によってラベルした状態
Σn=02N-1|a)で表し，このaが奇数であるラベルの状態を反転させる変換（マイナス符号を付けるに等しい）を考える。古典計算では，状態一つ一つにあたる作業が必要なので2N個の計算セットを必要とする。一方，量子計算では，単にＮ番目のキュービットで，
|0> → |0>，|1> → －|1>を行うだけでよい。たった1回の操作が2N個の操作と等しい結果を生じることができるのである。
第二の理由が，普通の高速フーリエ変換にも出てくる，テンソル積による計算の高速化である。
フーリエ変換といっても，量子状態は有限個のキュービットで表されるので，離散的フーリエ変換である。また，関数ではなく，状態をフーリエ変換するので，単に量子力学における表示の変換と言ったほうが適切かもしれない。２n項の離散的フーリエ変換を実行するのに，逐次的にわずかｎ回程度の制御－Ｕで実現できることが売りである。量子フーリエ変換については後述する。
テンソル積による計算の例として，マトリックスＭをベクトルｖに演算することを考える。Ｍを２n行２n列のマトリックスとし，ｖを２n次元ベクトルとすると，ｗ = Ｍｖの素朴な計算には（２n）2 回の掛け算が必要になる。
Ｍとｖをｎ個のテンソル積に分解できたとする。
Ｍ = Ｓ(1)
Ｓ(2)…Ｓ(n)ｖ = ｖ(1)
ｖ(2)…ｖ(n)ここに，Ｓ(i)はｉ番目のビット（ｖ(i)）にのみ働く2行2列のマトリックスである。ｗ = Ｍｖを具体的に書けば，
ｗ = Ｓ(1)ｖ(1)
Ｓ(2)ｖ(2)…Ｓ(n)ｖ(n)ｗj1…jn= Σi1…inＳ(1)j1i1…Ｓ(n)jninｖi1…in
となる。Ｓ(1)ｖ(1)の演算には4回の掛け算が必要であり，従って，Ｓ(1)，Ｓ(2)，…，Ｓ(n)全部の演算を行うには４ｎ回必要になる。テンソル積の計算は量子並列計算により1回で行うことができるので合計４ｎ＋１回の掛け算で計算が完了する。任意のマトリックスがテンソル積に分解できるわけではないので，量子計算が有効なアプリケーションは限定されることになる。
（４）量子フーリエ変換
量子フーリエ変換は，テンソル積で計算できるアプリケーションの代表例である。２n項の離散的フーリエ変換を実行するのに，逐次的にわずかｎ回程度の制御－Ｕで実現できることが売りである。以下に量子フーリエ変換の原理を示す。
量子暗号で述べたマッハ・ツエンダー干渉計（MZ干渉計）を使うと，
|0> → (eiφB|0> + ieiφA|1>)/√２
= ei(φA + φB)/2*(ei(φB - φA)/2|0> + ie-i(φB - φA)/2|1>)/√２
がハーフビームスピリッタBS2への入力状態となる。最終出力としては， |0> → ei(φA + φB)/2*{ei(φB - φA)/2(|0> + i|1>)+ ie-i(φB - φA)/2(i|0> + |1>)}/２
= iei(φA + φB)/2*{sin(φB - φA)/2*|0> + cos(φB - φA)/2*|1>}
を得ることができる（〔MZ干渉計〕）。 ここで，ビームスピリッタ（BS1，BS2）の役割をゲート記号〔Ｈ〕(Hadamard Gate)で表し，位相変化(φB - φA)/2をもたらす機能をゲートとして〔Θ〕で表すと，MZ干渉計は量子ゲートとして以下のように表すことができる。
入力○―〔Ｈ〕―〔Θ〕―〔Ｈ〕―○出力
また，最終出力前の状態は，全体にかかる位相は無視し，θ=φA - φBとおくと，
(ei(φB - φA)/2|0> + ie-i(φB - φA)/2|1>)/√２
= (e‐iθ/2|0> + ieiθ/2|1>)/√２
であり，これは量子ゲート表示では，
入力○―〔Ｈ〕―〔Θ〕―○出力
と同値である。〔Θ〕を2回続けると(e‐2*iθ/2|0> + ie2*iθ/2|1>)/２となることは容易に分かる。〔Θ〕をｎ回続けると同様にして，
(e‐n*iθ/2|0> + ien*iθ/2|1>)/２n/2
を得る。従って，以下のような量子ゲートを作成すれば，ｎキュービットの量子フーリエ変換ができる。
入力|0>○―〔Ｈ〕―〔Θ〕―○出力
入力|0>○―〔Ｈ〕―〔Θ〕〔Θ〕―○出力
入力|0>○―〔Ｈ〕―〔Θ〕〔Θ〕〔Θ〕―○出力
・
・
・
入力|0>○―〔Ｈ〕―〔Θ〕〔Θ〕…〔Θ〕（ｎ個のΘゲート）―○出力
何故なら，上記の量子ゲートは，以下の変換を表すからである。
|0>|0>…|0> → (e‐n*iθ/2|0> + ien*iθ/2|1>)…
(e‐2*iθ/2|0> + ie2*iθ/2|1>) (e‐iθ/2|0> + ieiθ/2|1>)
= Σa=02n-1eiaθ|a)
最後の形がフーリエ変換であることを示している。量子フーリエ変換はショアの因数分解の主要なアルゴリズムを占めており，因数分解の時間がｎの多項式の程度でおさまることが証明されている。これは，現在のRSA方式が数分で解読されることを意味し，このことにより量子コンピュータの研究が多いに加速されることになった。
（２００２年５月１８日；第一版 Copyright 寒泉）