《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

量子コンピュータの基礎と物理との接点
東京大学 大学院工学系研究科 附属光量子科学研究センター
藤井啓祐

2017 年 6 月 8 日

1 はじめにこのテキストでは，量子力学の復習から進めて，量子情報及び量子計算の基礎事項について丁寧に説明している．そのかわり，講義の時には，必ずしも詳細な計算や証明については触れない．各自，テキストをもとに自分で計算してみて，量子情報による記述に慣れていただきたい（もちろん講義以外の時間を利用して質問にくることは大歓迎である）．一方，紙面の関係から，トポロジカル秩序やマヨラナ粒子を用いたトポロジカル量子計算等についてはテキストに含めることができなかった．講義のときに丁寧に説明することにする．
量子情報では，特定の物理系にできるだけ依存することなく，複雑な量子系における現象を普遍的に記述することを目指している．そうすることで，計算理論や情報理論などの情報科学的手法を大いに利用し緻密な議論を展開することができる．また，このテキストでも説明する万能性の議論から，任意の量子系のダイナミクスを量子コンピュータで効率よく模倣することができる．このため，量子コンピュータの挙動や限界を理解することによって，より深い物理の理解に繋がるであろう．例えば最近では，量子コンピュータを雑音から守るために作り出された量子誤り訂正理論が，トポロジカル秩序やブラックホールの理解に使われている．今後も，このような例はます
ます増えていくのではないかと期待される．また，実際に量子コンピュータが実現されることによって，それがたとえ小規模であったとしても，可解模型や古典コンピュータによる数値計算だけでは捉えきれない複雑性の極限にある物理に関する新たな知見を得るための強力な実験的手段となるであろう．また，量子物質設計や量子化学計算などのように潜在的に「量子」の言語で定義された問題を解く上で量子コンピュータが役に立つことは言うまでもなく，今後，機械学習などの一見量子とは関係のない分野においても量子コンピュータがその実現の困難性を引いても余りあるような貢献をする可能性もある．
一方，情報や計算といった概念は，通常の物理系学部の学生はあまり触れてこなかったと思う．よって，一通り
慣れてしまうまでは，議論の展開が殺伐としていて（それが良いところでもあるのだが）物理とのつながりが感
じにくく思われるかもしれない．最近では，小さいサイズではあるが万能性がある真の量子コンピュータ（IBMquantum experience）がウェブ上で公開されており，誰でも（今のところ）無料で利用することができる．このテキストに書かれていることを自分でサーバー上の量子コンピュータを使って確認してみるのもよいであろう．
今回は，量子デバイスの物理には踏み込む余裕はないが，量子コンピュータの理論は，それを支える量子デバイスの物理や実験技術の蓄積に支えられている（従来のコンピュータが固体物理学や半導体技術の蓄積によって支えられているように）．量子コンピュータを実現するためには，超伝導量子ビットに代表されるような量子情報デバイスの物理をよりよく理解し，それを制御するための技術も重要な鍵となってくる．実験に興味がある意欲的な学生は，量子情報デバイスの物理にも挑戦してもらいたい．

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

2 量子力学の復習から量子情報へ
本節では，量子力学の復習を兼ねて，量子情報でよく使われる表記方法や，時間発展（量子操作），測定，密度演
算子などの取り扱いについて説明する．すでに知っている人は，本節を飛ばして次節から読み進めてもらいたい．

2.1 量子状態:ヒルベルト空間
量子状態は内積*1 が定義された完備*2 な複素線型空間である複素ヒルベルト空間 H の元 |ψ⟩ ∈ H によって記述される．有限次元複素ヒルベルト空間の場合であれば，|ψ⟩ を複素列ベクトル |ψ⟩ = (c1 , ..., cd )T だと思って差し
支えない．双対空間*3 H∗ 上の元を ⟨ψ| と書くことにし，内積を ⟨ψ|ϕ⟩ と書くことにする．双対空間上の元は，有限次元複素ベクトル空間の場合，複素行ベクトル ⟨ψ| = (c∗1 , ..., c∗d ）だと思って問題ない．このように，ヒルベルト空間，及びその双対空間上の元を |· · ·⟩（ケット）や ⟨· · ·| （ブラ）を用いて記述することをディラックのブラケッ
ト表記という．A をヒルベルト空間 H から H への線型演算子としよう．|ψ⟩ ∈ H を A で写した元 |ψ ′ ⟩ = A|ψ⟩に対応する双対空間上の元は ⟨ψ ′ | ∈ H∗ になるが，⟨ψ ′ | = ⟨ψ|A† を満たすような演算子 A† を A の随伴演算子と呼び † のマークを用いて書く．つまり，双対空間上での A の作用に対応するものをもとの空間で書いたものが A†と言える*4 ．|ψ⟩ に対応する双対空間上の元に対しても ⟨ψ| = (|ψ⟩)† のように書いたりすることもある．有限次元複素ベクトル空間では，随伴 † は転置および複素共役をとること，つまりエルミート共役に等しい．

2.2 Schrödinger 方程式と波動関数との関係
量子力学の授業で習った波動関数との関係を見ておこう．量子系の状態の時間発展を記述する Schrödinger 方
程式は，

iℏ

∂
ψ(x, t) = Hψ(x, t)∂t(1)で与えられ，ψ(x, t) は波動関数（適当な境界条件によって規格化できるものとする），ハミルトニアン H はエネ
ルギーに対応する演算子（波動関数に微分演算子や掛け算演算子として作用する）である．時刻 t に位置 x に粒子を見出す確率密度は |Ψ(x, t)|2 = Ψ∗ (x, t)Ψ(x, t) （ボルン則）で与えられる．Schrödinger 方程式は，波動関数を空間と時間で分離し，空間部分のエネルギー固有関数Hψk (x) = Ek ψk (x)(2)

を求めることによって解くことができる．Ek は k 番目のエネルギー固有関数の固有値である．境界条件がうまく与えられており，ψk (x) が規格化できる，すなわち∫

dx|ψk (x)|2 が収束するような場合のみ考えることにする．

以降，ψk (x) は規格化されたものとする．このエネルギー固有関数の時間発展は，iℏ∂ψk (x) = Ek ψk (x)∂t(3)*1 内積とは，線型空間の任意の２つの元 |ψ⟩ と |ϕ⟩ と複素数 (|ψ⟩, |ϕ⟩) ∈ C に対応させたものである．
*2 完備性とは，コーシー列 ∥|ψ⟩n − |ϕ⟩m ∥ → 0 が空間の元 |ψ⟩ に収束する ∥|ψ⟩n − |ψ⟩∥ → 0 ということである．有限次元複素線型*3空間であれば，複素数の完備性から線型空間の完備性が保証される．
ヒルベルト空間 V の元 v に作用し複素数を返すような汎関数 f : V → C について考える．汎関数 f と g に対して f + g やスカラー倍 αf も定義できるので，汎関数の集合も線型空間になっており，これを線型空間 V の双対空間 V ∗ と呼ぶ．ことのき Riesz の定理より，ある汎関数 f は必ずヒルベルト空間 V のある元 v と内積 (v, ·) を用いて，f (v ′ ) = (v, v ′ ) という形で一意的に表されるため，そのような汎関数を fv と書くことにする．V の元 v をケット |v⟩，双対空間 V ∗ の元 fv をブラ ⟨v| と表記するのがディラックのブラケット表記である．

*4 fAv (v ′ ) = fv (A† v ′ )《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

をとけば良いので，ψk (x, t) = e−iEk t/ℏ ψk (x) となる．波動方程式では，解の重ね合わせも解として許されるため，エネルギー固有関数の重ね合わせ Ψ(x, t) =∑k ck ψk (x, t) =∑k ck e−iEk t/ℏψk (x) （ck ∈ C）が Schrödinger

方程式の一般解となる．ある２つの解の和（重ね合わせ）やスカラー倍が定義できるので，波動関数は線型空間を∫構成していることがわかる．さらに，２つの解 Ψ(x, t) と Φ(x, t) を空間的に積分dxΨ∗ (x, t)Φ(x, t) すること

によって複素数を得ることができるので，内積を定義することもできる．また，適当な境界条件によって規格化できるということは，この内積から得られるノルム ∥Ψ(x, t)∥2 が収束するような関数からなる空間，L2 空間を考えていることになり，完備性も示すことができる．つまり，Schrödinger 方程式の解からなる集合は，複素ヒルベルト空間を構成していることがわかる．興味のあるエネルギースケールなどの制約から，有限のエネルギー固有状態（k = 1, 2, ..., d）だけに興味がある状況を考えよう．この場合，任意の量子状態は，

Ψ(x, t) =d∑

ck ψk (x, t)

(4)

k=1

とかける．ψk (x, t) をヒルベルト空間の元として |ψk ⟩（k = 1, ..., d）と書くことにする．ハミルトニアンはエネル
ギー固有状態を用いて，H =∑dk=1 Ek |ψk ⟩ ⟨ψk | とかけ H†= H すなわち，自己随伴（有限次元の場合はエルミート）演算子になっている．このため２つのエネルギー固有状態 |ψk ⟩ と |ψj ⟩ に対して，⟨ψk | H |ψj ⟩ = Ek ⟨ψk |ψj ⟩ =Ej ⟨ψk |ψj ⟩ になることから，Ej ̸= Ek の場合は２つの固有状態は直交 ⟨ψk |ψj ⟩ = 0 する．また，Ej = Ek の場合に√縮退している場合でも，２つの直交しない固有状態 |ψk ⟩ と |ψj ⟩ から，|ψj ⟩ = ⟨ψk |ψj ⟩ |ψk ⟩+ 1 − | ⟨ψk |ψj ⟩ |2 |ψk⊥ ⟩とすることによって新たに |ψk⊥ ⟩ を定義する（Gram-Schmidt の直交化）ことによって直交した状態を得ることができる．これらの正規直交基底 {|ψk ⟩} を用いて波動関数 |Ψ(x, t)⟩ を列ベクトル表示することによって，波動関数と複素列ベクトルが対応することになる．

2.3 時間発展:ユニタリー演算子
Schrödinger 方程式をブラケット表示で書き直してみよう：iℏ∂|ψ(x, t)⟩ = H |ψ(x, t)⟩ .
∂t(5)

時刻 t = 0 の状態 |ψ(x, 0)⟩（波動関数）が与えられているとして，Schrödinger 方程式を形式的に解くと，|ψ(x, t)⟩ = e−iHt/ℏ |ψ(x, 0)⟩ ,(6)が得られる．H はエルミート演算子だったので，e−iHt/ℏ はユニタリー演算子（U † U = Id *5 を満たす）になる．
このように，量子系の時間発展は，複素ヒルベルト空間上で作用するユニタリー演算子 U によって記述される．

2.4 量子測定:射影演算子
物理における状態とは，そもそも対象とする物理系から実験的に得られる物理量の値やその統計性に関する予言を与えるために必要となるものであった．量子系における測定は，射影演算子 {Pi }di=1 を選び，それに基づいた射影測定を行うことになる．射影演算子とは Pi Pj = δij Pi と∑di=1 Pi = Id を満たすエルミート演算子の集合dのことである．例えば，正規直交基底 {|i⟩}i=1 を１つ選び，Pi = |i⟩⟨i| とすれば射影演算子が得られる．状態 |ψ⟩に対して，射影演算子 {Pi } による射影測定を行ったときに，測定結果 i を得る確率 pi は，

pi = ∥Pi |ψ⟩∥2 = ⟨ψ| Pi |ψ⟩*5 Id を d 次元空間の恒等演算子とした．

(7)

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

で与えられる．射影演算子の性質から∑

i pi = 1 になっている．時間発展はユニタリー演算子（内積を保存する）

であるため，初期状態が規格化されていれば，常に確率は保存される．古典状態とは異なり，量子状態は確定した
１つの状態 |ψ⟩ であっても，測定の仕方によってその結果は確率的に与えられることになる．測定結果 i を得た後√の状態は Pi |ψ⟩/ pi となる．ここまでで，量子系における状態・時間発展・測定の記述が与えられたことになる．
全く同じ量子状態 |ψ⟩ がたくさん与えられ，何度も繰り返し測定するような状況を考えよう．測定結果 i が得られた時の物理量（確率変数）を ai とする．例えば，エネルギーに関する射影測定 {|ψk ⟩⟨ψk |}dk=1 の場合はエネル
ギー固有値 Ek になる．このとき，物理量の平均値はエルミート演算子 A =

⟨A⟩ ≡

d
∑

∑d

i=1 ai Pi を用いて

ai pi = ⟨ψ| A |ψ⟩ ,

(8)

i=1

と計算できる．逆にエルミート演算子であれば，射影演算子 Pi を用いてスペクトル分解 A =∑di=1 ai Pi でき，物理量 A の射影測定や物理量 A の平均値を計算することができるため，A は可観測量と呼ばれる．

2.5 複合系:テンソル積
2 つの量子系 1,2 から成る複合系について考えよう．複合系も全体としては何らかの量子系になっているので複合系の量子状態はあるヒルベルト空間 H1,2 の元として書くことができるであろう．このような状態の例
としては，量子系 1 の状態 |ψ⟩1 ∈ H1 と，量子系 2 の状態 |ϕ⟩2 ∈ H2 との直積状態 (|ψ⟩1 , |ϕ⟩2 ) が含まれているだろう．複合系の線型性から２つの直積状態 (|ψ⟩1 , |ϕ⟩2 ) と (|ψ ′ ⟩1 , |ϕ′ ⟩2 ) の線型和も複合系 H1,2 に含まれることになる．このようにして，H1 と H2 の元の直積状態によって張られる線型空間のことをテンソル積空間

H1,2 = H1 ⊗ H2 と呼ぶ．直積状態は，(|ψ⟩1 , |ϕ⟩2 ) の代わりに |ψ⟩1 ⊗ |ϕ⟩2 や，特に混乱しない場合は |ψ⟩1 |ϕ⟩2′と書く．テンソル積空間の基底としては，H1 と H2 の基底をそれぞれ {|i⟩1 }di=1 と {|j⟩2 }dj=1 として，それらの′直積状態 {|i⟩1 |j⟩2 }di=1 dj=1 を採用することができる．したがって H1,2 の次元は dd′ となる．テンソル積の計算には以下のルール（双線型性）が適用される．

(|ψ⟩ + |ψ ′ ⟩) ⊗ |ϕ⟩ = |ψ⟩ ⊗ |ϕ⟩ + |ψ ′ ⟩ ⊗ |ϕ⟩ ,|ψ⟩ ⊗ (|ϕ⟩ + |ϕ′ ⟩) = |ψ⟩ ⊗ |ϕ⟩ + |ψ⟩ ⊗ |ϕ′ ⟩ ,α(|ψ⟩ ⊗ |ϕ⟩) = (α |ψ⟩ ⊗ |ϕ⟩) = (|ψ⟩ ⊗ α |ϕ⟩).

(9)
(10)
(11)

′

{|i⟩1 }di=1 と {|j⟩2 }dj=1 を基底として列ベクトル表示した状態 |ψ⟩1 = (a1 , ..., ad )T と |ϕ⟩2 = (b1 , ..., bd′ )T のテン′

ソル積状態，|ψ⟩1 ⊗ |ϕ⟩2 を基底 {|i⟩1 |j⟩2 }di=1 dj=1 に対してベクトル表示すると，




a1 b1

 

 
 a1 b2 
b1
a1
 .. 
  .  |ψ⟩1 ⊗ |ϕ⟩1 =  ...  ⊗  ...  =  a1 bd′ 


bd′
ad
 . 
.
 . 
ad bd′(12)となる．このように d 次元ベクトルと d′ 次元ベクトルから dd′ 次元ベクトルを構成することをクロネッカー積と呼ぶ．H1,2 上の状態は必ずしも |ψ⟩1 ⊗ |ϕ⟩2 と書けるとは限らない．特に，|ψ⟩1 ⊗ |ϕ⟩2 と書ける場合を直積状態と呼び，そのようにかけない状態をエンタングル状態と呼ぶ．

H1 と H2 上の演算子 A と B のテンソル積演算子 A ⊗ B の H1,2 上での作用は，(A ⊗ B)|ψ⟩1 ⊗ |ϕ⟩2 = (A|ψ⟩1 ) ⊗ (B|ϕ⟩2 )(13)

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

で定義される．テンソル積演算子も双線型性(A + A′ ) ⊗ (B + B ′ ) = A ⊗ B + A ⊗ B ′ + A′ ⊗ B + A′ ⊗ B ′が成り立つ．したがって，A =∑′i,i′ ai′ i |i ⟩⟨i| と B =

(14)

∑

′
′
′
′
j,j ′ bj j |j ⟩⟨j| として ai i と bj j を成分として行列表示

すると，テンソル積演算子は∑(A ⊗ B) =ai′ i bj ′ j (|i′ ⟩ ⊗ |j ′ ⟩)(⟨i| ⊗ ⟨j|)(15)

i,i′ ,j,j ′で与えられることになるので，２つの行列のクロネッカー積は



ad1


=

 
a1d
b11
..  ⊗  ..
.   .

···
..
.
···

a11
 ..
A⊗B = .

a11 B
..
.
ad1 B

add

bd′ 1


···
..
.
···


b1d′
.. 
. 
bd′ d′

a11 b11
 
...
a1d B


..  =  a b ′.   11 d 1

..
add B

.
ad1 bd′ 1

···
..
.
···

(16)

···
..
.
···

a11 b1d′..
.

···a11 bd′ d′···ad1 bd′ d′

···
..
.
···


a1d b1d′..
.

a1d bd′ d′ 
.

..

.
add bd′ d′(17)

2.6 密度演算子，一般量子操作，一般化測定
これまで確率 1 で１つの定まった量子状態 |ψ⟩ が与えられるような状況を考えてきた．これを拡張して，確率的に異なる量子状態が与えられるような状況を考えよう．このためには，密度演算子 ρ = |ψ⟩⟨ψ| を用いて状態を記述すると便利である（状態とは測定に係る統計性を予言するためのものであったのでその目的が果たせれば何でもよい）．射影演算子 {Pk } による射影測定は，
dd∑∑pk = ⟨ψ|Pk |ψ⟩ = ⟨ψ|(|i⟩⟨i|)Pk |ψ⟩ =⟨i|Pk |ψ⟩⟨ψ||i⟩i=1= Tr[Pk |ψ⟩⟨ψ|]のように，トレース Tr[· · · ] =

∑

(18)

i=1

(19)

∑d

d
i=1 ⟨i| · · · |i⟩ を用いて計算することができる．ただし正規直交基底 {|i⟩}i=1 の完全i |i⟩⟨i| = Id を用いた．トレース Tr は正規直交基底の選び方に依存せず決まり，また，Tr[ABC] = Tr[CAB]

性

を満たす．
さて，確率 {qj } で異なる量子状態 {|ψj ⟩} が与えられ，射影測定 {Pi } を行う状況を考えよう．確率の結合法則を認めると，測定結果 i を得る確率は，

pi =

∑

qj Tr[Pi |ψj ⟩⟨ψj |] = Tr[Pijとなる．よって密度演算子として ρ ≡∑qj |ψj ⟩⟨ψj |]

(20)

j

∑

j qj |ψj ⟩⟨ψj | を採用しておけば，このような古典的な確率的混合状態に対する射影測定の確率分布は pi = Tr[Pi ρ] によって与えられる．
密度演算子 ρ の性質を確認しておこう．
†∑

i pi = 1 になるために，Tr[ρ] = 1 が要求される．また，定義から密度演算子はエルミート演算子 ρ = ρ である．ρ =∑j qj |ψj ⟩⟨ψj | のような分解ができることから任意の |v⟩ に対*6

して，⟨v|ρ|v⟩ ≥ 0，つまり，半正定値（positive-semidefinite） 演算子となっている．特に ρ がランク 1 の場合，
つまり ρ = |ψ⟩⟨ψ| と書ける場合に純粋状態と呼ばれる．Tr[ρ2 ] は純粋度と呼ばれ，Tr[ρ2 ] = 1 となる時だけが純粋状態である．密度演算子 ρ に対するユニタリー時間発展は ρ → U ρU † . によって記述される．
*6 任意の |v⟩ に対して ⟨v|A|v⟩ ≥ 0 となる演算子 A を半正定値演算子という．すべての固有値が ≥ 0 となる演算子としてもよい．

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

そもそも，なぜ密度演算子を導入する必要があるのだろうか？確率的に量子状態を送りつけてくる装置も含めて”コヒーレント”に複合系の量子状態を純粋状態∑ √qj |j⟩|ψj ⟩ として記述しておけば，古典的な確率混合を排j除できるはずである．しかし，しばしば，複合系も含めて（宇宙全体の純粋状態を）書くと面倒になることがある．量子状態を送りつけてくる装置にアクセスできないという状況では，部分系だけを混合状態として密度演算子として書くことによって簡潔に状態が記述できることがよくある．
例えば，量子系 1,2 の複合系の状態 ρ1,2 = |Ψ⟩⟨Ψ|1,2 があるとする．この時，量子系 2 からの情報を一切受け取らずに量子系 1 のみで射影測定 {Pk } を行った時の確率は，pk = Tr [(Pk ⊗ Id′ )|Ψ⟩⟨Ψ|1,2 ]になる．複合系でのトレースは

(21)

∑

ij ⟨i|1 ⟨j|2 · · · |i⟩1 |j⟩2 で与えられるが，先に量子系 2 上でのトレースを複合系の状態に対してとってやる′d∑ρ1 ≡ Tr2 [ρ1,2 ] =(Id ⊗ ⟨j|2 )ρ1,2 (Id ⊗ |j⟩2 )

(22)

j=1

ことによって，

pk = Tr1 [Pk ρ1 ] .

(23)

このように部分系に関するトレースをとることを部分トレースと呼び，部分トレースをとった密度演算子 ρ1 のこ∑ √qj |j⟩|ψj ⟩ の場合，装置にアクセスできなj∑
いもとでは装置系に対して部分トレースをとると，縮約密度演算子として混合状態 j qj |ψj ⟩⟨ψj | が得られる．ことを縮約密度演算子 (reduced density operator) と呼ぶ．先の例のように，宇宙全体の状態がたとえ純粋状態であったとしても，我々が興味をもつ部分系だけで閉じた議論をする
ときには，その系は古典的な混合状態として密度演算子を用いて記述されることになる．逆に，任意の密度演算子
は，スペクトル分解することによって直交する状態 {|ψj ⟩} を用いて ρ =∑j qj |ψj ⟩⟨ψj | と書けるので，何らかの∑ √補助系を付け加えて，それらの複合系上で純粋状態 j qj |ψj ⟩|j⟩ として記述することもできる．これを純粋化（purification）と呼ぶ．同様に，複合系を付け加えた複合系でのユニタリー時間発展や射影測定を部分系のみで記述することによって，部分系だけで閉じた形で量子操作や量子測定を一般化することができる．
密度演算子に対する物理的に許されたもっとも一般的な量子操作について考える．物理的に許される密度演算子 ρ はトレースが 1 である半正定値演算子であった．量子操作においても確率が保存されるとすると，トレースを保存し，かつ半正定値性を保つ写像が物理的に許される量子操作といえそうだ．しかし，それではまだ不十分である．先の議論のように，密度演算子を扱う場合は，補助系を追加されるような状況を含めたい．このため，密度演算子そのものの正定値性だけでなく，任意の補助系を追加してその複合系の状態を考えても正定値性が保たれていなければならないという強い要請が必要になる．これを満たすものが CPTP 写像（completely-positive trace

preserving map）である．L(H) を H 上で作用する演算子からなる空間とすると，CPTP 写像 E : L(H) → L(H)は，E(ρ + σ) = E(ρ) + E(σ), (線型性)Tr[E(ρ)] = 1 (ただし Tr[ρ] = 1), (trace preserving)E ⊗ I(ρ̃) ≥ 0 (complete positivity)

(24)
(25)
(26)

を満たすものである．I は追加した補助系上の恒等操作，ρ̃ は補助系も含めた複合系の密度演算子，≥ 0 は半正定値性を意味する．物理的な操作になるためには完全正値性が必要である具体例を見ておこう．密度演算子の転置《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

T (ρ) = ρT をとるような操作を考える．ρ =⟨v|ρ|v⟩ =∑ij rij |i⟩⟨j| とすると，T (ρ) =∑rij ⟨v|i⟩⟨j|v⟩ =

ij

∑

∑

ij rji |i⟩⟨j| となる．一方，rji ⟨v|j⟩⟨i|v⟩

(27)

ij
∗


∑
∗
=
rji ⟨v|i⟩⟨j|v⟩ = (⟨v|T (ρ)|v⟩)

(28)

ij

となるので ρ ≥ 0 から，T (ρ) ≥ 0 も言える．よって転置をとる操作は正値性を満たすことになる．複合系でのエンタングル状態|Φ+ ⟩ ≡

|0⟩1 |0⟩2 + |1⟩1 |1⟩2
√
2

(29)

に対して 1 系だけに転置をとる操作 T ⊗ I を考える．密度演算子は，



1
1
0
+
+
|Φ ⟩⟨Φ | = 
2 0
1


0 0 1
0 0 0 
0 0 0 
0 0 1

(30)

なので，系 1 の転置は，



1

1
0
T ⊗ I(|Ψ+ ⟩⟨Φ+ |) = 
2 0
0


0 0 0
0 1 0 
,
1 0 0 
0 0 1

(31)

となり，負の固有値を持つため半正定値演算子にはならない．エンタングルした状態の一方に量子操作を施した
結果物理的ではない状態が得られるような量子操作は認めたくない．よって，着目している系の正定値性を保つだけではなく，補助系を追加した複合系においても正定値性が保たれる，CPTP 写像が物理的に許された量子操
作を表すことになる．CPTP 写像 E は必ず，∑†k Ek Ek = I を満たす Kraus 演算子 Ek を用いて，

Eρ =

∑

Ek ρEk†(32)

kと書くことができる（Kraus 表現）．また，このような CPTP 写像は，補助系 (a) と着目している系 (s) の複合系
上のユニタリー時間発展 Us,a に対して，補助系をトレースアウトすることによって得られる:†Eρ = Tra [Us,a ρ ⊗ |e⟩⟨e|a Us,a]=∑

Ek ρEk† ,(33)

k

この時，{|k⟩a } を補助系の正規直交基底として，Kraus 演算子は，Ek = (Is ⊗ ⟨k|a )Us,a (Is ⊗ |e⟩a ) と書き表される．CPTP 写像や量子操作というとユニタリー時間発展とは本質的に異なる難しいことをしているように感じるかもしれないが，宇宙全体でみたときには単なる純粋状態に対するユニタリー時間発展に対応するものを，（必ずしも宇宙全体を操作したり観測したりすることはできないし，そもそも宇宙全体をわざわざ記述することも面倒なので）興味のある着目した系だけで閉じた都合の良い形で書いているだけのことである．
同様に，着目する系（s）と補助系（a）から成る複合系において，s 系と a 系の初期状態をそれぞれ ρs と |e⟩⟨e|aとし複合系のユニタリー時間発展を Us,a とし，補助系において射影測定 {|k⟩⟨k|a } をすることにする．測定結果

k を得る確率は，†
pk = Trs,a [Is ⊗ |k⟩⟨k|a Us,a (ρs ⊗ |e⟩⟨e|a ) Us,a]

= Trs [Ek† Ek ρs ]

(34)
(35)

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）†となる．つまり，Ek = Is ⊗ ⟨k|a Us,a Is ⊗ |e⟩s として定義した演算子 Mk ≡ Ek Ek を射影演算子の代わりすることによって，着目する系だけで閉じた形，

pk = Trs [Mk ρs ]で書くことができる．定義から Mk ≥ 0 かつ

∑

(36)

k Mk = Is となっており，pk は確かに確率になっている（複合系の射影測定を行っていることから自明である）．測定結果 k が得られたときの測定後の状態は，

Ek ρEk† /Tr[Ek ρEk† ]となっている．このようにして，一般に Mk ≥ 0 かつ

∑

(37)

k Mk = I となる演算子の集合 {Mk } を POVM 演算子（positive operator valued measure）と呼び，一般化測定（POVM 測定），

pk = Tr[Mk ρ](38)√が定義される．測定後の状態はあるユニタリー演算子 Uk を用いて定義した測定演算子 Ek ≡ Uk Mk *7 によって

Ek ρEk† /Tr[Ek ρEk† ](39)で与えられる．以上のように，純粋状態，ユニタリー時間発展，射影測定を複合系において行い，着目する系だけにおいて記述することによって，密度演算子，CPTP 演算子，POVM 測定が得られた．

3 量子ビット
3.1 Bloch 球
量子力学系（有限次元）の一般的な取り扱いについて一通り説明したので，本題である量子コンピュータの話をすすめていく．古典の情報の世界における情報の最小単位はビットという 0 と 1 の２値をもつ変数である．
同様に，量子の世界の情報の最小単位は，2 次元複素ヒルベルト空間上の状態，量子ビットによって記述される．量子ビットは，直交する２つの状態（量子計算に使う基準となる基底として，計算基底と呼ぶことにする）
( )
( )

|0⟩ =

1
0

と |1⟩ =

0
1

, の線型和として|ψ⟩ = α|0⟩ + β|1⟩,(40)と一般的に書くことができる．ここで，α と β は，|α|2 + |β|2 = 1 を満たす複素数とした．|0⟩ と |1⟩ の直交する２状態としては，原子の２つのエネルギー状態，光子の直交する偏光状態，電子・核スピンなど，直交する２つの量子状態であればなんでも良い．これらの複素数は，θ ∈ [0, 2π) と ϕ ∈ [0, π/2) を用いてθ
α = cos ,2θ
β = eiϕ sin ,2(41)と書くことができる．ここで，量子状態全体に作用する位相 eiγ |ψ⟩ は測定確率には一切寄与しないので無視していることに注意する．これら θ と ϕ を用いて量子ビットの状態を半径 1 の球面（Bloch 球）上に表示することが
できる．

*7

エルミート（自己随伴）演算子 A の関数 f (A) は，演算子 A の固有値 {ai } と固有空間への射影演算子 {Pi } を用いたスペクトル分
√
∑ √
∑
∑
解A=
i ai Pi と定義される．
i ai Pi を利用して，f (A) =i f (ai )Pi として定義される．特に， A =《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

|0�
z

θ

| − i�
|0�φ|+�

y | + i�

x

|1�

|−�

θ

| − i�

φ

|+�

z

|−�

y | + i�x|1�

3.2 パウリ演算子
量子計算に必要となる量子ビットに対する演算子を定義していこう．もっとも重要な演算子はパウリ演算子で
ある：

(
I=

1 0
0 1

)

(

0
1

, X=

1
0

)

(
, Y =

0 −i
i 0

)

(
, Z=

1 0
0 −1

)
.

(42)

X, Y, Z を σ1 , σ2 , σ3 と書くこともあるが，量子情報では X, Y, Z と書くと便利なことが多いので，このように書くことにする．X 2 = Y 2 = Z 2 = I, XZ = −ZX （どの２つも互いに反交換する），Y = iXZ などの関係式はよく使うので覚えておこう．量子ビットを定義した基底は |0⟩ と |1⟩ パウリ Z 演算子の固有状態 Z|0⟩ = |0⟩，

Z|1⟩ = −|1⟩ となっている．計算基底 {|0⟩, |1⟩} に対するパウリ X 演算子の作用は，|1⟩ = X|0⟩, |0⟩ = X|1⟩.

(43)のように量子ビットを反転させる作用となる．パウリ X 演算子の固有状態として，|0⟩ と |1⟩ の重ね合わせ状態，|+⟩ ≡|0⟩ + |1⟩|0⟩ − |1⟩√√, |−⟩ ≡
,
2
2

(44)

を定義しておこう．同様に，パウリ Y 演算子の固有状態として| + i⟩ ≡|0⟩ + i|1⟩|0⟩ − i|1⟩√√
, | − i⟩ ≡
,
2
2

(45)

を定義しておく．これらパウリ X, Y , Z 演算子の固有状態からなる基底をそれぞれ X, Y , Z 基底と呼ぶことにする．これらパウリ演算子の固有状態は，Bloch 球上の x, y, z 軸上に存在する．Bloch 球上の座標は，パウリ演
算子を用いて(rx , ry , rz ) = (Tr[Xρ], Tr[Y ρ], Tr[Zρ]),(46)

として与えることもできる．この場合，純粋状態だけではなく，１量子ビットの任意の混合状態の場合も記述することが可能である．純粋度は Tr[ρ2 ] = rx2 + ry2 + rz2 となることから，純粋状態は半径 1 の球面上，混合状態はその内部に対応することになる．確率 |0⟩, |1⟩ の確率 1/2 での混合状態 21 (|0⟩⟨0| + |1⟩⟨1|) は Bloch 球の原点に対応
する．古典ビットや，その確率的混合は，Bloch 球では z 軸上の状態に対応する一方，一般の量子状態は半径 1 の球面上及びその内部を状態としてとれることから，古典情報よりも一般的な情報を表現できることがわかる．

3.3 アダマール・位相演算子
次に重要な 1 量子ビット演算子はアダマール演算子 H と位相演算子 S である：

1
H=√
2

(

1 1
1 −1

)

(
,

S=

1
0

0
i

)
.

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

これらの演算子は，あるパウリ基底を他のパウリ基底へと変換する．例えば，H : {|0⟩, |1⟩} ↔ {|+⟩, |−⟩}，

S : {|+⟩, |−⟩} ↔ {| + i⟩, | − i⟩}．これは，これらの演算子をパウリ演算子に対して共役作用*8 させたとき他のパウリ演算子が得られることに対応する:

X = HZH,

Y = SXS † .

(47)

アダマール演算子 H の Bloch 球上での作用は，x 軸と z 軸の入れ替えに対応している．位相演算子 S の作用は，

z 軸を中心に π/2 回転していることになる．このように，共役作用のもとでパウリ演算子を再びパウリ演算子に写す演算子を Cliﬀord 演算子*9 とよぶ．

3.4 １量子ビットの任意の回転
アダマール演算子や位相演算子を繰り返し作用させても任意の１量子ビットのユニタリー演算子を構成することはできない．1 量子ビットのユニタリー演算子 U は一般に

(

U=

u11
u21

u12
u22

)
(48)

の 4 つの複素数によって記述され，U † U = I より，|u11 |2 + |u21 |2 = 1,u∗12 u11 + u∗22 u21 = 0,|u22 |2 + |u12 |2 = 1(49)を満たすことになる．これを満たす複素数は必ず，

u11 = eiα e−i(β+δ)2 cos(γ/2),iα −i(β−δ)/2

u12 = −e e

u21 = eiα ei(β−δ)/2 sin(γ/2),(50)iα i(β−δ)/2(51)

sin(γ/2), u22 = e ecos(γ/2),と書き表すことができる．このことから，

U = eiα e−i(β/2)Z e−i(γ/2)Y e−i(δ/2)Z(52)のように分解できることになる．ここで，e−i(θ/2)A = cos(θ/2)I − i sin(θ/2)A（A = X, Y, Z ）は，Bloch 球上でそれぞれ x, y, z 軸を中心に θ 回転させる操作に対応する．よって，任意の 1 量子ビットユニタリー演算子は全体の位相 eiα を除いて，2 つの直交する軸を中心とした回転に分解することができる（オイラー分解）．
一般に Bloch 球上での (rx , ry , rz ) 方向（|rx |2 + |ry |2 + |rz |2 = 1）を中心とした θ 回転は，

e−i(θ/2)(rx X+ry Y +rz Z)(53)となる．これは，以下の事実から示すことができる．まず，Bloch 球上の点 (1, 0, 0) を (rx , ry , rz ) に写すユニタ
リー演算子を U とした時，点 (1, 0, 0) が |+⟩ に対応することを使うと，(rx , ry , rz ) = (Tr[U |+⟩⟨+|U † X], Tr[U |+⟩⟨+|U † Y ], Tr[U |+⟩⟨+|U † Z])(54)を満たしていることになる．σi（i = 0, 1, 2, 3）をパウリ演算子（I, X, Y, Z ）として，Tr[σi σj ] = 2δij となることから，

I +X †
I + rx X + ry Y + rz Z
U =2
2
⇔ U XU † = rx X + ry Y + rz Z,
U |+⟩⟨+|U † = U

(55)
(56)

*8 演算子 A の演算子 B に対する共役作用とは，ABA† によって定義される．
*9パウリ演算子から生成される群をパウリ群とすると，Cliﬀord 演算子はパウリ群を共役作用のもとで不変にする，つまり，パウリ群を
正規部分群としてもつ演算子である．このような演算子は群を成し，Cliﬀord 群と呼ばれる．

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）となる．(1, 0, 0) 軸に対する θ 回転は e−i(θ/2)X なので，(rx , ry , rz ) 軸に対する θ 回転は U e−i(θ/2)X U † =e−i(θ/2)(rx X+ry Y +rz Z) と書けることがわかる．

3.5 ユニタリー演算子の近似と計算の精度
1 量子ビットの任意のユニタリー演算子を実現するためには，特定の軸周りに任意の角度で回転させる必要があった．量子コンピュータを構成する上では，有限個の量子演算から任意の量子計算，つまり万能量子計算を構成したい．厳密な意味で 1 量子ビットのユニタリー演算子を実現するためには，無限個の量子演算を必要とすることになるが，実際には厳密なユニタリー演算を実現する必要はなく，十分良い精度 ϵ で任意のユニタリー演算子を近似できれば良い．例えば，演算子 1-ノルム（もしくはトレースノルム）∥·∥1 *10 を用いて，理想的なユニタリー
演算子 {Ui }N
i=1 に対して， Ũi − Ui
算子の積 U ≡∏N

i=1 Ui と Ũ ≡∏N

1

≤ ϵ を満たすような {Ũi }Ni=1 が実現されたとしよう．これらユニタリー演

i=1 Ũi の誤差は，演算子 1-ノルムの性質（ユニタリー不変性及び三角不等式）

を使うとŨ − U=
1N∏

Ũi − UN

N
−1
∏

i=1

..
.
=

N
∑
k=1

≤

N
∑
k=1

Ũi + UN

i=1

[(

N
∏

N
∏

Ũi −

i=1

)
(Ũk − Uk )

Ui

i=k+1

[(

N
−1
∏

(Ũk − Uk )

Ui

i=1

(k−1
∏
(k−1
∏

N
[
]
∑
=
(Ũk − Uk )
k=1

1

(58)
(59)

Ũi
)]

1

(60)

Ũi

i=1

i=k+1

(57)
1

)]

i=1

)
Ui

N
∏

1

≤ Nϵ

(61)

となる．これら近似的なユニタリー演算子を作用させたのち射影測定を行ったときの確率分布 {p̃k } と理想的な場
合 {pk } との誤差は l1 -ノルム（確率分布の全変動距離, total variation distance）を用いて∑∥p̃k − pk ∥1 =|p̃k − pk | =

k

∑

≤

∑

|Tr[Pk W ]| =k|wj | |⟨wj |Pk |wj ⟩| ≤

∑

∑ ∑
k

wj ⟨wj |Pk |wj ⟩

(62)

j

|wj | = ∥W ∥1

(63)

j

k,j

ただし，W ≡ Ũ |ψ⟩⟨ψ|Ũ † − U |ψ⟩⟨ψ|U † とし（W = W † ），|wj ⟩ を W の固有値 wi ∈ R の固有ベクトルとした．
一方，∥W ∥1 = Ũ |ψ⟩⟨ψ|Ũ † − U |ψ⟩⟨ψ|U †(64)
1= (Ũ − U )|ψ⟩⟨ψ|Ũ † − U |ψ⟩⟨ψ|(U † − Ũ † )≤ (Ũ − U )|ψ⟩⟨ψ|Ũ †1= 2 (Ũ − U )|ψ⟩⟨ψ|Ũ †≤ 2 (Ũ − U )
√

1

(65)
1

+ U |ψ⟩⟨ψ|(U † − Ũ † )

(66)
1

(67)
1

|ψ⟩⟨ψ|Ũ †= 2N ϵ.

(68)

1√AA† ．もしくは A を特異値分解し，すべての特異値（ AA† の固有値）の和をとったものである．∥A∥1 = A† 1 及び，任意のユニタリー演算子に対して ∥A∥1 = ∥AU ∥1 = ∥U A∥1 を満たす．また，劣加法性∥A + B∥1 ≤ ∥A∥1 + ∥B∥1 及び，劣乗法性 ∥AB∥1 ≤ ∥A∥1 ∥B∥1 を満たす．

*10 演算子 1-ノルム（1-norm）は，Tr

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

よって，近似的な確率分布は l1 ノルムの意味で誤差 2N ϵ の範囲内にいる．つまり，１つのユニタリー演算の誤差

ϵ をユニタリ演算子の総数 N よりも十分小さくすることができれば，十分精度の高い出力が得られることになる．

3.6 Solovay-Kitaev アルゴリズム
アダマール演算子や位相演算子は，Bloch 球上での軸の入れ替えや π/2 回転に対応していたため，これらの演算子の積で任意のユニタリー演算子を構成することはできない．1 量子ビットユニタリ演算子を任意の精度 ϵ で近似するためには，これらの他に π/8 演算子

T = e−i(π/8)Z(69)が必要となる．π/8 回転は π の有理数倍になるので，この演算子（及び，H と S ）の積から任意の 1 量子ビット
ユニタリー演算子を構成できないような気もするが，実は T HT H がある方向についての π の無理数倍の角度の回転になっていることが以下の議論からわかる．まず，

]
√
1 [√
V ≡ T HT H = e−i(π/8)Z e−i(π/8)X = √ ( 2 + 1)I − iX − iZ − i( 2 − 1)Y ,
2 2
]
√
1 [√
V † = √ ( 2 + 1)I + iX + iZ + i( 2 − 1)Y ,
2 2

(70)
(71)

とすると，

√
2
V XV =(X + Y )2√
1
V Y V † = (−X + Y + 2Z)
2√
1†
V ZV = (X − Y + 2Z)2†になるため，√
X+(−1+ 2)Y +Z
√ √
はV
5−2 2

√

の共役作用のもとで不変であることがわかる．(1, −1 +

√

(72)
(73)
(74)
√
2, 1) 方向と直交す√√

る方向として Bloch 球上の点 (1/ 2, 0, −1/ 2) 方向を選び，V によって回転させると，点 ( 2−4 2 , 2+4 2 , − 21 ) が得られる．よって回転角は内積の公式から，

( √
)
2 2−1
θ = arccos
4(75)を満たす角度となる．この回転角は π の無理数倍になっており，V を繰り返し作用させることによってこの軸方向の回転に対しては稠密（任意の角度の回転を近似できる）になっている．また，同様の議論から，HV H は(1, 1 −√

2, 1) 方向を中心とした π の無理数倍の回転になっている．2 つの異なる軸に対して，任意の角度の回転を近似することができるので，これらを繰り返すことによって任意の 1 量子ビットユニタリー演算子を近似する
ことができる．よって，{H, T } の２つの 1 量子ビット演算から任意の 1 量子ビットユニタリー演算が近似的に構成できることがわかった．Solovay-Kitaev の定理より，演算子ノルムの意味で誤差 ϵ の近似に必要な {H, T }の個数は，log(1/ϵ) の多項式で十分であることが知られている（例えば [1] もしくは [2] 参照）．前述の議論から，

1/ϵ は 1 量子ビット演算の個数に対して高々多項式的にしか増えないので，非常に効率よく理想的な 1 量子ビット演算を近似することができる．

4 万能量子計算
万能量子計算とは，n 量子ビットの任意のユニタリー演算を近似的に実行できるような量子計算を意味する．
我々の世界が量子力学によって記述されていることを考慮すると，万能量子コンピュータは，量子力学のルールで

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

動きかつあらゆる量子系のダイナミクスを含んだ任意の物理系と互換性があるマシンであるといえる．したがって，万能量子コンピュータにおける時間発展（量子計算）において何らかの制約が明らかになったとき，任意の物
理系は（量子力学に従う限り）その制約に従わなければならないことになる．以下では，どのようにして，有限個の量子演算から，n 量子ビットの任意のユニタリー演算が構成されるかを見ていきたい．

4.1 CNOT 演算
任意の n 量子ビットのユニタリー演算を構成するためには，相互作用を必要とする 2 量子ビット演算が必要になる．2 量子ビット演算の代表的なものが CNOT（controlled-not）演算，

Λc,t (X) = |0⟩⟨0|c It + |1⟩⟨1|c Xt ,である*11 ．c 系（コントロール系）が 1 のときに t 系（ターゲット系）に対してパウリ X 演算子を作用させる．計算基底の入力 |i⟩c |j⟩t に対して CNOT 演算は排他的論理和（XOR）をターゲット系に出力する，

Λc,t (X)|i⟩c |j⟩t = |i⟩c |i ⊕ j⟩t ．c 系の入力状態が重ね合わせ状態 |+⟩c |0⟩t のとき，出力状態は最大エンタングル

H

状態

S

√
Λc,t (X)|+⟩c |0⟩t = (|00⟩ + |11⟩)/ 2，(77)になる．CNOT 演算は，コントロール側を黒丸，ターゲット側を白丸にして以下のような回路図で記述する：

古典論理回路にならって，水平な線は量子ビットが通過するワイヤを表しており，左から右へと量子状態が進んでいく．CNOT 演算のダイアグラムを通過したときに ΛX が作用する．

=

アダマール演算 H と位相演算 S はパウリ演算子をパウリ演算子に写す Cliﬀord 演算であった．CNOT 演算もH

H

2 量子ビットのパウリ演算子からなるパウリ群 {±1, ±i} × {I, X, Y, Z}⊗2 を共役作用のもとで不変にする．このように，一般に共役作用 U : G → U GU † のもとで，n 量子ビットパウリ群 {±1, ±i} × {I, X, Y, Z}⊗n が不変になるような U を Cliﬀord 演算子と呼ぶ．CNOT 演算については，具体的に

Λ(X)c,t Xc It Λ(X)†c,t = Xc Xt ,(78)

Λ(X)c,t Ic Xt Λ(X)†c,t = Ic Xt ,Λ(X)c,t Zc It Λ(X)†c,t = Zc It ,(79)

Λ(X)c,t Ic Zt Λ(X)†c,t = Zc Zt ,

(81)

(80)

となり，Cliﬀord 演算子であることが確認できる．これまで出てきた {H, S, CNOT} の Cliﬀord 演算から，任意の n 量子ビット Cliﬀord 演算を構成することができる．

*11 k 番目の量子ビットに作用する演算子 A を
k−1

n−k−1

z }| {z}|{
Ak = I ⊗ · · · ⊗ I ⊗A ⊗ I ⊗ · · · I,と書くことにする．

(76)

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

4.2 Cliﬀord 演算と Gottesman-Knill の定理
1 量子ビットの場合，H と S からは任意の 1 量子ビットユニタリー演算を構成することはできなかった．同様に，Cliﬀord 演算 {H, S, CNOT} からは任意の n 量子ビットユニタリー演算子を構成することはできない．それどころか，Z 基底での初期状態準備，Cliﬀord 演算，及び，Z 基底での射影測定から構成される量子計算*12 は，古典計算機で効率よくシミュレーションすることができてしまう（エンタングルメントした状態はいくらでも生成できるのに！）．このことを理解するために，量子計算を演算子を用いて特徴づけしてみよう．初期状態として初期化された n 量子ビット |0⟩⊗n を用意する．この状態は，演算子 {Zi }ni=1 の固有値 +1 の固有状態になっている．
このように，状態をその固有状態として特徴付ける演算子をスタビライザー演算子と呼ぶことにする．ある，n 量
子ビット Cliﬀord 演算 U を作用させたのちに得られる状態は，U |0⟩⊗n であるが，この状態を固有状態に持つス
タビライザー演算子は，

U |0⟩⊗n = U Zi |0⟩⊗n = U Zi U † (U |0⟩⊗n ) ≡ Si (U |0⟩⊗n ),(82)†
から {Si }ni=1 （Si ≡ U Zi U ）ということになる．U は今，Cliﬀord 演算に限定しているので，{Si } は互いに交換

する，n 量子ビットのパウリ演算子のテンソル積であることがわかる．{Si } の固有状態に対する Z 基底で射影測定した場合の確率分布は，{Si } と Z 演算子の交換関係から効率よく計算することができる（Gottesman-Knillの定理，例えば [1] もしくは [2] を参照）
．このように，量子状態をその状態を固有状態として持つスタビライザー
演算子（から成るスタビライザー群）を用いて記述する形式をスタビライザー形式と呼ぶ．Gottesman-Knill の定理は，Cliﬀord 演算だけから構成された量子回路が古典シミュレーションできてしまうことを意味するが，同時に，高くエンタングルした複雑な量子状態であっても効率よく記述できる場合があることも意味する．実際，量子誤り訂正符号や測定型量子計算のリソース状態など，量子情報において重要になる多体エンタングル状態の多く
は，スタビライザー形式で効率よく記述することができる（例えば，[3] 参照）．

4.3 制御ユニタリー演算
話を万能量子計算に戻そう．実は，すでに導入した任意の 1 量子ビットユニタリー演算を近似できる {H, T } とCNOT の３種類のユニタリー演算から任意のユニタリー演算を構成することができる．その構成方法はやや込み入っているので，1 つ 1 つ段階を踏んで構成していこう．まず，必要になるのが，制御 U 演算

Λc,t (U ) = |0⟩⟨0|c It + |1⟩⟨1|c Ut ,(83)

である．コントロール系が |0⟩ の場合は何もせず，|1⟩ の場合はユニタリー演算 U をターゲット系に作用させる．CNOT 演算の一般化だと思えばよい．この制御 U 演算を CNOT と 1 量子ビットユニタリー演算から構成する方法を見ていこう．まず，ユニタリー演算 U はオイラー分解より U = eiα e−iβZ e−iγX e−iδZ と分解できた
ので，U = eiα I *13 と U = e−i(θ/2)A （A = X, Y, Z ）に対して Λ(U ) が実現できれば良いことになる．まず，

Λ(eiα I) は，コントロール系の量子ビットの相対位相に他ならないので，コントロール系に e−i(α/2)Z を作用させればよい．次に具体的に，A = Z として，Λ(e−i(θ/2)Z ) について考えよう．e−i(θ/2)Z = e−i(θ/4)Z Xei(θ/4)Z X と

I = e−i(θ/4)Z Iei(θ/4)Z I を利用すると，
Λc,t (e−i(θ/2)Z ) = Λc,t (X)ei(θ/4)Zt Λc,t (X)e−i(θ/4)Zt(84)*12 Cliﬀord 演算を用いて基底の変換が行えるので初期状態や測定をパウリ基底で行っても同じことが主張できる*13 eiα は全体の位相なので重要でないように思うかもしれないが，制御演算の場合には相対位相になるのできちんと対処しなければならない．

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

�

�
1 0
0 軸や
eiα y 軸に関しても回転さが得られる．ターゲット系に H や S を（共役に）作用させることによって，同様に x=せることができるので，任意の１量子ビットユニタリー演算に対して制御 U 演算が構成できたことになる．

U

B

C

A

例えば，制御アダマール演算 Λ(H) は，H = eiπ/8Y Xe−iπ/8 であることを利用して以下のように実現される：

=

H

π

π

e−i 8 Yei 8 Y（回路は左から右に進むが，数式では左から掛けていくので注意すべきである．）

4.4 Toﬀoli 演算と可逆計算
��
1 Toﬀoli0
次に，万能性を証明するために重要となるもう一つのユニタリー演算，Toﬀoli 演算，を導入しておく．
iα0 e
演算は，３量子ビットに作用するユニタリー演算で，

=

U

C

Λ2c1 ,c2 ,t (X) = (Ic1 Ic2 − |1⟩⟨1|c1 |1⟩⟨1|c2 )It + |1⟩⟨1|c1 |1⟩⟨1|c2 Xt ,

B

A

(85)

と定義される．２つのコントロール系があり，両方とも |1⟩ 状態の時のみターゲット系にパウリ X 演算子を作用=させる，CNOT 演算の一般化になっている．計算基底の入力状態 |i1 ⟩c1 |i2 ⟩c2 |j⟩t に対して，
ππΛ2c1 ,c2 ,t (X)|i1 ⟩c1 |i2 ⟩c2 |j⟩tH= |i1 ⟩c1 |i2 ⟩c2 |j ⊕ (i1 ·ei2−i)⟩t 8. Y

ei 8 Y(86)

ターゲット系に論理積（AND）を出力する．

Toﬀoli 演算も {H, T, CN OT } から構成できることを示しておこう．Toﬀoli 演算は CNOT 演算にコントロー
ル系を追加すれば良いので，Λ(Λ(X)) を実現すればよいことになる．一般に Λ2 (U ) = Λ(Λ(U )) は，√√ †√Ut Xc Λc,t ( U )Xc Λc,t ( U )

(87)

√
√ †
√
Λ2c1 ,c2 ,t (U ) = Λc1 ,t ( U )Λc1 ,c2 (X)Λc2 ,t ( U )Λc1 ,c2 (X)Λc,t ( U )(88)Λc,t (U ) =となるので，これをさらに制御化するには，

=

=
U

p

U

U

p

U

†

p

U
(89)

√
とすれば良いことになる．U = X とすれば Toﬀoli 演算が構成できる．Λ( X) は，先に述べた制御ユニタリー演
T†
算の構成を用いて，

=

T†
H

T
T

T†

T

T†

H

T = e (⇡/8)iZ

T

= T

《講義ノート》

H

T

†

T†

T

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

T†

T

H

T = e (⇡/8)iZ

p

X

T

=

=

H =T

T†
p

p †
U
U
のようになり，Toﬀoli 演算は T 演算を用いて以下のように分解できる．

U

U

H
p

U

T

= T

T

H

T

†

T†

T

T†

H

T = e (⇡/8)iZ

ひとたび Toﬀoli 演算が構成されると補助系を用いることによって，以下のようにコントロール系をいくらでも増やすことができる：

X

ancilla qubits

=

T

{

control qubits

p

=

H

T

T†

H

|0i
|0i
|0i
|0i

target qubit

Toﬀoli 演算は，ターゲット系の入力状態を |1⟩ にしておけば，ターゲット系の出力は古典論理回路における
NAND 演算に対応することになる．つまり，Toﬀoli 演算は，NAND 演算を可逆なユニタリー演算で実現していることになる．任意の論理回路（ブール関数）は NAND 演算から構成でき，古典論理回路において万能性がある
ことが知られていることから，量子計算は古典計算を自明に含むことがわかる．さらに，量子計算はユニタリー演算を用いて計算をするので，可逆に計算ができることになる．実際に，入力 x ∈ {0, 1}n に対するブール関数

f : {0, 1}n → {0, 1} の出力の可逆計算を構成してみよう．f は NAND 演算から構成できることがわかっている
ので，f に対応するユニタリー演算 Uf を Toﬀoli 演算，パウリ X 演算，補助量子ビットを用いて構成できる．

| · · · ⟩input , | · · · ⟩ancilla , | · · · ⟩answer をそれぞれ，入力，補助量子ビット，答えを記録する量子ビットとすると，Ufの作用は，

Uf |x⟩input |0...0⟩ancilla |0⟩answer = |x⟩input |g(x)⟩ancilla |f (x)⟩answer ,(90)となり，出力 f (x) が得られる．しかしながら，計算を可逆にするために，補助量子ビットに計算のゴミ |g(x)⟩ancillaが残ってしまうことになり，この初期化のためには不可逆な操作が必要になると思うかもしれない．しかし，
このゴミは計算結果 f (x) を新たな量子ビットにコピーして保存し（直交状態なのでコピーできる），逆計算

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）†（uncomputation）Uf を施すことによって初期状態に戻すことができる:

Uf† Λanswer,out (X)Uf |x⟩input |0...0⟩ancilla |0⟩answer |0⟩out= Uf† |x⟩input |g(x)⟩ancilla |f (x)⟩answer |f (x)⟩out= |x⟩input |0...0⟩ancilla |0⟩answer |f (x)⟩out .

Uf†

Uf

ancillae…

|00...0�

|x�

…

|x�

input

(91)

|00...0�

answer |0�
output|0�|f (x)�

|0�

以上のようにして，可逆な操作のみからゴミを残さずに f (x) を計算できることがわかった．この結果は，量子計算が定式化される前の 80 年代に計算の物理的限界（消費エネルギーや発熱問題）を研究する過程で，Toﬀoli とFredkin らによって得られた．その後，量子力学を積極的に計算に利用する万能量子計算へと研究が進んでいくことになった．

4.5 万能量子計算
やっと準備が整ったので，{H, T, CN OT } から任意の n 量子ビットユニタリー演算子を近似的に構成できることを示しておこう．まず，2n 次元複素ヒルベルト空間 Hn に作用する任意の n 量子ビットユニタリー演算子 Uは，m ≡ 2n 次元空間の 2 次元部分空間内のユニタリー演算子（2 準位ユニタリー演算子）に分解できることを示
そう．基底を 1 から m までの整数でラベルし直して，|i⟩ と |j⟩（i, j ∈ {1, 2, ..., m}）の２つの基底に対する２準位ユニタリー演算子を Tij としよう．*14 このとき，Tm m−1 の要素を適切に選ぶことによって，



u11
..
.



U Tm m−1 =  um−1 1
um 1

···
..
.
···
···

u1 m−1..
.

u′m−1 m−1
0

u1 m
..
.





,
′
um−1 m 
u′m m

(92)

と変形することができる．ここで (U )kl = ukl を U の行列要素とした. この操作を繰り返し行うことによって，



u′′11
..
.



U Tm m−1 Tm m−2 · · · Tm 1 =  u′′m−1 1
0

···
..
.
···
···

u′′1 m−1..
.

u′′m−1 m−1
0u′′1 m
..
.






′′
um−1 m 
u′′m m(93)のように，m 行目を対角項を除いてすべて 0 にすることができる．また，ユニタリー演算子であることから自動的に u′′1 m = · · · = u′′m−1 m = 0 と |u′′mm | = 1 がわかる. これらの操作をまとめて，Rm ≡ Tm m−1 Tm m−2 · · · Tm 1 ,とかくことにする．この操作 Rk を k = 1, ..., m に対して繰り返すことによって，U を対角ユニタリー演算子 Dへと変形することができる:

U = D(Rm · · · R1 )† .

(94)

*14 Tij の行列要素を (Tij )kl とするとき，k, l ̸= i, j のときは (Tij )kl = δkl であり，k, l = i, j に対応する 4 つの要素が 2 × 2 ユニタ

リー演算子を構成する．つまり部分空間 {|i⟩, |j⟩} の外では恒等演算子として作用することに注意する．

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

D はもはや対角項しかないので，2 準位ユニタリー演算子（対角な）の積に分解できることは自明である．よって，U を 2 準位ユニタリー演算子の積に分解できた．
最後に，２準位ユニタリー演算子 Tij が Toﬀoli 演算と制御 U 演算（および {H, T, CNOT}）を用いて実行できることを示そう．Toﬀoli 演算も制御 U 演算も，{H, T, CNOT} から構成できたので，これを示せば {H, T, CNOT}
から任意の n 量子ビットユニタリー演算が構成できることになる．

i と j は 1 から m までの整数であったが，これを２進数（n ビット列）を用いて書き直したものをそれぞれ
s = s1 s2 ...sn と t = t1 t2 ...tn とする．このとき，s からスタートし各ステップごとに 1 つのビットだけを反転させて t に至るような，ビット列の列 {gk }dk=1 ，

s = g0 → g1 → · · · → gd = t(95)

を簡単にみつけることができる．ここで，d を２つのビット列 s と t の異なるビットの総数（Hamming 距離）とした．
ビット列 s と g1 は 1 ビットだけ異なるので，パウリ X 演算や Toﬀoli 演算を用いて，同じビット列部分をコ
ントロール系にし，ターゲット系を異なるビットにすることによって，|s⟩ 基底を |g1 ⟩ 基底へと変換するユニタ
リー演算子を構成することができる．これを繰り返していくと，|s⟩ を |gd−1 ⟩ まで基底の変換を行うことができる．最後に，|t⟩ と |gd−1 ⟩ は 1 ビットだけ異なるので，この基底では２準位ユニタリー演算子は，同じビット列をコントロール系とした１量子ビット（部分空間）のユニタリー演算子となる．制御ユニタリー演算を用いてこれを実行し，再び元の基底に戻すことによって，|s⟩ と |t⟩ の２準位ユニタリー演算を構成することができた．
具体例として，３量子ビット（8 次元空間）の部分空間 {|000⟩, |111⟩} に作用するユニタリー演算子の実装例を示しておく：

X

V

X

X

X

X

X

{

{

X

X

|000� ↔ |011�

|000� ↔ |011�

以上をまとめておくと，アダマール演算 H ，π/8 演算 T を用いて任意の 1 量子ビットユニタリー演算が構成で
き，CNOT 演算と 1 量子ビット演算を用いて，制御ユニタリー演算と Toﬀoli 演算が構成できる．Toﬀoli 演算があれば，コントロール系を追加することもできた．これらを用いて，任意の 2 準位に関する２準位ユニタリー演
算が構成でき，それから任意の n 量子ビットユニタリー演算子が構成できた．よって，{H, T, CNOT} の３種類の演算があれば万能量子計算が実行できることになる．このような演算集合を，万能演算集合と呼ぶ.

5 量子アルゴリズム
ここでは，量子コンピュータが古典コンピュータに対してどういった優位性があるのかを，アダマールテストという量子アルゴリズムを通じて説明する．アダマールテストの発展系として，量子アルゴリズムとして非常に重要な位相推定アルゴリズム，及び素因数分解アルゴリズムを理解することができる．

5.1 間接測定
光子検出器のように，測定後量子状態を破壊してしまう場合がしばしばある．このような場合において，測定後に射影された状態を残すためには，補助系を用いて間接測定を行う必要がある．A を固有値が ±1 のエルミート

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

演算子としよう．演算子 A の間接測定は，制御 A 演算 Λ(A) を用いて:

|0i

H

H

Z

A
|0i H |0⟩ は補助系の入力状態を意味し，黒丸に繋がれた箱
H|0i H Sのように構成することができる．左端に書かれた状態
Uは
H
Z
Z
補助系をコントロール系とする制御 U 演算 Λ(U ) を表している．右端のメータが書かれた箱は Z 基底での射影測

|0i

|0i

となることからも理解できるし，被測定系における POVM 演算子が……

√I + (−1)s A|ψ⟩/ Tr[(I + (−1)s A)/2|ψ⟩⟨ψ|], |0i
|0i
2

……

……

定後の状態が補助系の測定結果 s ∈ {0, 1} に依存して，U……

定を意味している．この量子回路が A の間接測定になっていることは，直接計算することによって被測定系の測
|0i
|0i

U

(96)

It +(−1)s At
で与えられることからも理解で
2

きる．
例えば，３体の演算子 X1 X2 X3 の間接測定は以下のように構成される．

|+�

U

X

……

……

I ⊗n
2

|+�

X

Bell measurement
このような多体パウリ演算子の間接測定は量子誤り訂正におけるスタビライザー演算子の測定に頻繁に使われることになる．
Alice

|ψ�

Z

m1

|+�

X

m2

5.2 アダマールテスト
Bob|0i1 |ψ�H
Z m2 X m

|0�

H

Z

H

Z

一般に，任意のn 量子ビットユニタリー演算子 U に対してアダマールテストを補助量子ビットと制御 U 演算を
maximally entangled stateA

用いて以下のように定義する：

|0i

|0i

H

H

U

Z

……

|0i
|0i

S

……

U

……

……

| i

H

|0i
入力状態を |ψ⟩ とすると，測定前の状態は，

1√ [|+⟩|ψ⟩ + |−⟩(U |ψ⟩)]2(97)

なので，測定結果 0 を得る確率は，

p0 =

1
1
∥(I + U )|ψ⟩∥ , p1 = ∥(I − U )|ψ⟩∥ ,
4
4

(98)

となる．補助系における測定結果 0, 1 を得る確率は簡単な計算から，

p0 =

1
1
(1 + Re⟨ψ|U |ψ⟩) , p1 = (1 − Re⟨ψ|U |ψ⟩) .
2
2

(99)

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）となることがわかる．補助系に位相演算 S を付け加えると，実部 Re を虚部 Im に置き換えたものが得られる．
従って，アダマールテストを何回も繰り返すことによって，ユニタリー演算子 U の行列要素⟨ψ|U |ψ⟩(100)を推定することができる．アダマールテストを M 回繰り返し，測定結果 0 が M0 回得られたとすると，Chernoﬀ-

Hoeﬀding 限界から
(
Prob

M0
− p0 > ϵM)< 2e−2ϵ M ,
2

(101)

となり，M = poly(1/ϵ) のサンプル数で誤差 ϵ の近似ができることになる．
入力状態 |ψ⟩ を U の固有状態 |λ⟩（U |λ⟩ = eiλ |λ⟩）とすると，アダマールテストから固有値 eiλ を推定することができる．一般の状態 |ψ⟩ を入力した場合は，測定後の状態に作用する演算子は (I ± U ) の定数倍なので，ユニタリー演算子の固有状態 |λ⟩ はこの測定において不変である．従って，測定後の状態を再び入力としてアダマール
テストを繰り返す極限を考えると次第に特定の固有状態へと確率的に収束し，eiλ が推定できることになるので，
アダマールテストを繰り返した極限では，U の固有状態 {|λ⟩} に関する間接的な射影測定になっている．

n 量子ビットのユニタリ演算子 U の行列要素を計算することくらい古典コンピュータでも簡単にできると思うかもしれない．しかし，U は 2n × 2n 行列なので，例えば，n = 50（たった 50 量子ビットからなる系）であったとしても，行列の要素の数は 250 ∼ 1015 になり，倍精度の複素数 1 つに対して 128 ビットのメモリーが必要になるので，U の行列要素の計算には 100 ペタビットのメモリーが必要になる．もちろん U は，局所的なユニタリー
演算子の積から構成されるので，このサイズの行列の積をひたすら計算する必要がある．量子系はテンソル積構造をもつため，量子系において部分系にユニタリー操作をする場合でも（量子デバイス上ではその部分系のみに操作をすればいいのであるが），古典コンピュータ上では 2n × 2n の行列積の処理をする必要があることにも注意したい．量子コンピュータを用いてアダマールテスト行った場合は，行列要素の近似になるが，おなじ近似精度を要求しても古典コンピュータの場合は（特定の都合の良い構造がない限り），愚直に指数的なサイズの行列を操作するしかないのだ．ここに，量子コンピュータの古典に対する優位性が端的に現れている．
アダマールテストを用いた量子アルゴリズムの例としては，ユニタリー演算 U としてブレイド群のユニタリ表
現をとれば，その行列要素と組紐不変多項式であるジョーンズ多項式との数学的対応から，ジョーンズ多項式を近似する量子アルゴリズムを構成することができる．U としてハミルトニアンダイナミクス e−iHt を採れば，量子多体系の実時間発展を意のままに追うこともできる．前述の議論から入力状態 |ψ⟩ のエネルギーに関する射影測定を行うこともできる．アダマールテストでは，何回も繰り返して度数分布を作る必要があったが，測定に用いる補助系をもう少しうまく工夫した位相推定アルゴリズムを用いることによって，固有値をより精度よく求めることができる．素因数分解アルゴリズムは，特殊な U に対して位相推定を行い，固有値を精度よく求めることによって構成される．

5.3 位相推定
ユニタリー演算子 U の固有状態 |E⟩ が与えられていれば，その固有値 eiϕ をアダマールテストを用いて推定することができた．

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

|+�

U

…

…

|Ei �

X

残念ながらアダマールテストでは，固有値 eiϕ の指数にある位相 ϕ を指数精度（多項式桁まで）求めることはできない．しかし，うまく補助系を構成した Kitaev による位相推定アルゴリズムを用いれば，ϕ を指数精度で推定できる場合がある. 位相 eiϕ を 2 進小数を使って e2πi0.j1 j2 ...jn（jk ∈ {0, 1}）と書くことにする．2 進小数の定義は，0.j1 j2 ...jn =n∑jk (1/2)k .

(102)

k=1

である．アダマールテストと異なり位相推定アルゴリズムでは，n 量子ビットの補助系を用いてビット列 j1 , ..., jn
を以下のような回路で求めることになる：

…
…
…

|+i

…

|Ei i

UQFT†

Z

…

…

…

|+i
|+i

Z
Z

U2

0

U2

1

…
…

U2

…

n

}

i

1

ここで，UQFT は量子フーリエ変換であり，後に説明する. n 個の補助量子ビットを |+⟩ にし，それぞれを制御量kk

子ビットとして Λ(U 2 )（k = 0, ..., n − 1）を作用させる．U 2 の固有状態が入力すると，補助量子ビットが |1⟩k状態のときだけ固有値 (e2πi0.j1 j2 ...jn )2 = e2πi0.jk+1 ...jn が位相として乗る（phase kickback）ことになる．よって，量子フーリエ変換前の補助系の量子状態は，|0⟩ + e2πi0.jk+1 ...jn |1⟩|0⟩ + e2πi0.jn |1⟩|0⟩ + e2πi0.j1 ...jn |1⟩ |0⟩ + e2πi0.j2 ...jn |1⟩
√
√
√
√
···
···
2
2
2
2

(103)

となる．最終的な目標は，この状態を |j1 ⟩|j2 ⟩ · · · |jn ⟩ に変換し，計算基底の測定から j1 , ..., jn の情報を得ることである．量子フーリエ変換の作用は，

UQFT |j1 j2 ...jn ⟩ =|0⟩ + e2πi0.j1 j2 ...jn |1⟩ |0⟩ + e2πi0.j2 ...jn |1⟩ |0⟩ + e2πi0.jn |1⟩
√
√
√
...
2
2
2

(104)

で定義されるので，逆量子フーリエ変換がまさに目標のタスクになっている．逆量子フーリエ変換のための量子回路は，

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

|j1 i

H

2

Z(e2⇡i/2 )Z(e2⇡i/2 )

…

H

…

n

… Z(e2⇡i/22Z(e2⇡i/2 )n1|0i + e2⇡i0.j1 ...jn |1i) …

|0i + e2⇡i0.j2 ...jn |1i

…

…

…

|j2 i

…

H

…

|jn i

|0i + e2⇡i0.jn 1 jn |1i2

Z(e2⇡i/2 )

…

H

…

…

≡! UQFT|0i + e2⇡i0.jn |1i!
!
で構成される．ポイントは，制御ユニタリー演算を用いて各補助量子ビットの位相の小数第 1 位にのみビット

jk が出てくるようにし，アダマール変換をしてビット |jk ⟩ を得ている．例えば， |0⟩+e √2

2π0.jn|1⟩√= |0⟩+(−1)
2

jn

|1⟩

より，n 番目の補助量子ビットはアダマール変換をすると |jn ⟩ が得られる．(n − 1) 番目の補助量子ビットは，|0⟩+e2π0.jn−1 |1⟩|0⟩+e2π0.jn−1 jn |1⟩√√
なので，|jn ⟩ から制御 e2π0.01 を作用させると，小数第 2 位がキャンセルされて，22が得られ，アダマール変換から |jn−1 ⟩ を得る．これを繰り返し行っていくことになる．最後に補助量子ビットを計算基底で測定すれば j1 , ..., jn が得られる．
n位相推定アルゴリズムを用いて効率よく位相を n 桁目まで求めるためには，U 2 を効率よく作用させる必要がある．n が問題のサイズに対して多項式的に増える場合は，U を指数回作用させる必要があると思うかもしれなn

いが，U の古典的記述がうまく与えられているときは，U 2 を多項式個の量子演算から構成できる場合がある．
素因数分解アルゴリズムではまさにそのような例が使われている．

5.4 素因数分解アルゴリズム
準備が整ったので，Shor による素因数分解アルゴリズムを紹介しよう．N を素因数分解したい整数だとしよう．N と互いに素な整数 x を見つけてくる．適当に x を選びユークリッドの互除法で共約数が見つかれば素因数分解ができることになるし，見つからなければ互いに素ということになる．以降の議論では表記を簡単にするため，{|0⟩, ..., |N − 1⟩} の基底を用いて書くことにする．x と N を用いてユニタリー演算子

Ux =

∑

|xy (mod N )⟩⟨y|,

(105)

y

を定義する．このユニタリー演算子の場合，
k

Ux2 =

∑

k

|x2 y (mod N )⟩⟨y|,

(106)

y
k

な の で ，冪 剰 余 x2 mod N ≡ e を 先 に 計 算 し て お け ば U を 2k 回 作 用 さ せ る こ と な く ，直 接 Ux2∑

y |ey (mod N )⟩⟨y| を作用させれば良い．さて，位数 r を x

r

k

=

= 1 mod N を満たす整数と定義すると，固有状態のラベル 0 ≤ s ≤ r − 1 を用いて，Ux の固有状態は，

1 ∑ −2πi(s/r)k k|x (mod N )⟩.
e|us ⟩ = √r

(107)

Ux |us ⟩ = e2πi(s/r) |us ⟩,

(108)

r−1

k=0

固有値は，

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

であることがわかる．位相推定をする入力状態は，|1⟩ =∑r−1

s=0 |us ⟩ になることから，|1⟩ を入力させると，位相推定によって確率的に固有状態 |us ⟩ が得られる．位相推定アルゴリズムを用いると，s/r を効率よく推定することができ，連分数展開を用いて有理数で書き直すと r の候補が得られる．|1⟩ からランダムに |us ⟩ を選ぶと高い確率で s と r が互いに素になるので，位数 r を得ることができる．また，得られる位数が高い確率で偶数になることも保証されている．よって xr = 1 (mod N ) を変形して，(xr/2 − 1)(xr/2 + 1) = 0 (mod N )

(

)(

)

に至る． xr/2 − 1 (mod N ) xr/2 + 1 (mod N ) が N で割りきれることになるが，xr = 1 (mod N ) から

xr/2 (mod N ) < N − 1 なので，xr/2 ± 1 (mod N ) が N で割りきれることはない．つまり，xr/2 − 1 もしくは
xr/2 + 1 と N との共約数が N の約数になっていることになるので，ユークリッド互除法を用いて N の約数を見つけることができる．

5.5 BQP 問題とアダマールテスト
これまでアダマールテストを中心に量子アルゴリズムを構成してきた．アダマールテストは，量子回路の一例なので，アダマールテストで行列要素 ⟨ψ|U |ψ⟩ を求めるという問題は，量子コンピュータで解くことができる問題のクラスよりも狭いと感じるかもしれない．しかし，それらは同等に難しいということも示すことができる．まず，量子コンピュータで解くことができる問題を定義しておこう．多くの問題において yes (0)，no (1) の２値を返すような問題に帰着することができるので，もっとも単純化された yes か no を判定する問題を考える．例えば，素因数分解の場合は，1 ≤ M ≤ N なる整数 N , M に対して，x ≤ M なる x で N が割り切れるか？という決定問題を考えることができる．yes，no の回答から２分探索していくことによって，実質的に因数 x を見つけることができる．その他，ある整数 N が素数かどうかを判定する素数判定問題も決定問題の一種であり，これは
古典コンピュータで多項式時間で解けることが知られている．
さて，量子コンピュータで解ける決定問題の定義に戻ろう．量子系の場合，出力は一般的に確率的に与えられる
ので，非常に高い確率で正解できればよいという条件にする．つまり，問題のサイズ n に対して多項式的なサイズの量子回路 U が存在して，答えが yes もしくは no の問題のそれぞれに対して，量子コンピュータの出力が yesを返す確率が，Prob(yes|yes) > 1/2 + δ, Prob(yes|no) < 1/2 − δ(109)

であれば良いことにする．δ は問題のサイズ n に依存しないパラメータである．また，0 < δ < 1/2 であればその値に依存せずに問題のクラスを定義することができる．なぜならば，多数決を行う量子回路を U の中に組み込んでしまえばいくらでも成功確率を増幅することができるからだ．よって，必要であれば量子回路 U に増幅回路を組み込むことによって，指数的に 1 に近い確率で正解できることになる．このような意味で解ける問題のクラス
を BQP（bounded error quantum polynomial time computation）と呼ぶ．
上記の判定問題を解く量子回路の出力は 1 量子ビット測定であるが，可逆計算のときに用いた逆計算を利用することによって，新たにユニタリー演算子 V を

V = U † Λ(X)c,t U,

…

…

V

=

U

(110)

U†
(111)

と定義することによって，

p0 = Tr[P0 U (|0⟩⟨0|)⊗n U † ] = |⟨0|⊗n V |0⟩⊗n |2 = ⟨0|⊗2n (V ⊗ V † )|0⟩⊗2n(112)

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）と書ける．従って，判定問題を解く量子回路 U に対応してユニタリー演算子 Ṽ = V ⊗ V † が常に存在し，その行
列要素 ⟨0|⊗2n (V ⊗ V † )|0⟩⊗2n が 1/2 + δ よりも大きいか，1/2 − δ よりも小さいかを判定する問題に等しい．つまり，行列要素 ⟨0|⊗2n (V ⊗ V † )|0⟩⊗2n が近似できることによってクラス BQP に含まれる問題を全て解くことができる．このように BQP 問題に含まれる問題すべてと同等に難しいとき BQP 困難であるという．一方，行列要素の大小の判定問題は万能量子コンピュータを用いてアダマールテストを行えば判定できるので BQP 問題に含まれる．よって，与えられたユニタリー演算子 W に対して ⟨0|⊗n W |0⟩⊗n が 1/2 + δ よりも大きいか，1/2 − δ よりも小さいかを判定する問題は BQP 完全問題と呼ばれる．BQP 問題というと物理とはかけ離れた人工的な問題を取り扱っているように感じられるかもしれないが，これはユニタリー演算子の行列要素を良い精度で近似できるか？という問題と互換性があるため，量子多体系の物理において幅広く扱う問題の難しさを自然な形で定式化しているといえる．
例えば，n 量子ビット系と (M + 1) 次元量子系の複合系における以下のようなハミルトニアンを考えよう:

H=

M
−1 (
∑

)
†
Ui+1 ⊗ |i + 1⟩⟨i| + Ui+1
⊗ |i⟩⟨i + 1| .

(113)

i=0

これは，Feynman が 80 年代に考えたハミルトニアンで，n 量子ビット系は量子計算を実行する作業空間，M 次
元量子系は計算のタイムステップに対応するクロック空間になっている．初期状態を |0⟩⊗n ⊗ |0⟩ として，定常ハ
ミルトニアンによって時間発展させると量子計算がステップ k まで進んだ状態の重ね合わせ状態（history stateと呼ばれる）
−iHt

e

⊗n

(|0⟩

⊗ |0⟩) =M−1∑

Ck (t)

( k
∏

)
⊗n

Ui |0⟩⊗ |k⟩.

(114)

i=1

k=0

が得られる．よって，定常ハミルトニアンによるユニタリー演算子の行列要素は，

⟨0|

⊗n

−iHt

⟨M |e

⊗n

|0⟩

⊗n

|0⟩ = ⟨0|

CM (t)

(M
∏

)
Ui

|0⟩⊗n

(115)

i=1

となり，BQP 完全問題を埋め込むことができるので，*15 自然な定常ハミルトニアンのもとでの実時間ダイナミク
スの遷移確率振幅にも万能量子計算と同等に複雑な計算が埋め込まれていることになる．Feynman が構成した H
は，人工的な模型のように思えるかもしれないが，現在では，ランダムネスのある 2 次元正方格子上に並んだ量子ビット（スピン 1/2 粒子）に対する最近接 2 体相互作用ハミルトニアンにもこのようなダイナミクスを埋め込むことができることが知られている．よって，とある物性研究者が研究対象としているランダムネスを含む量子多体系の実時間ダイナミクスが，計らずしも万能量子コンピュータと同等に複雑な問題を取り扱っているということがありえても不思議ではない．

6 量子デコヒーレンス
一般的に，量子状態は環境系との結合によるデコヒーレンスに弱く，量子性はすぐに失われてしまう．例えば，
基底状態と励起状態を量子ビットとして使っている場合，励起状態がエネルギーを放出して基底状態になる縦緩和現象や，エネルギー間隔が外場の影響を受けて揺らぐことによる位相緩和現象などが生じうる．外界との結合（エンタングルメント）によるデコヒーレンスを簡単なモデルで理解してみよう．まず，着目している量子ビット系（s）と環境系（e）からなる複合系を考える．量子ビットの状態は，|ψ⟩ = α|0⟩ + β|1⟩ とする．最初は簡単のために環境系も１つの量子ビットから構成されており，初期状態は |0⟩e にいるとする．この状態が，ハミルトニアン

Hamp = g(σs+ σe− + σs− σe+ )(116)*15 CM (t) を厳密に計算するか，もしくは ⟨1|⟨0|⊗n−1 ⟨M |e−iHt |0⟩⊗n |0⟩ との比から判定問題の出力に対応する p0,1 が得られる．

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）のもとで時間発展するとしよう．ここで σ + = |1⟩⟨0|， σ − = |0⟩⟨1| とした．|0⟩ を低エネルギー状態，|1⟩ を高エ
ネルギー状態としたとき，σ ± はエネルギーを昇降する演算子になっている．*16 時間 t における量子状態は，−−

e−iHamp t = e−igt(σs σe +σs σe ) |ψ⟩|0⟩= α|00⟩ + β[cos(gt)|10⟩ − i sin(gt)|01⟩]
+

+

(117)
(118)

となり，量子ビットは環境系とエンタングルしていることがわかる．環境系にはアクセスできないものとして，s系の縮約密度行列を求めると，†

ρs = [α|0⟩ + β cos(gt)|1⟩] [α|0⟩ + β cos(gt)|1⟩] + |β|2 sin2 (gt)|0⟩⟨0|)(|α|2 + |β|2 sin2 (gt) αβ ∗ cos(gt)=α∗ β cos(gt)|β|2 cos2 (gt)となり，|1⟩ 状態の振幅が減少する．|ψ⟩⟨ψ| → ρs の写像は，Kraus 演算子を

(

E1 =

1
0

0
cos(gt))(, E2 =00

sin(gt)
0

(119)
(120)

)
,

(121)

として

Eamp [t](ρ) = E1 ρE1† + E2 ρE2†

(122)

で与えられる．
もう一つの例を見てみよう．環境系の初期状態が |+⟩ にあり，相互作用ハミルトニアンが

Hph = (g/2)Zs Ze(123)

で与えられる状況を考えよう．先の例とは異なり環境系とのエネルギーのやりとりはない．時間 t の複合系の状
態は，

e−iHph t =eigt/2e−igt/2(α|00⟩ + β|11⟩) +(α|01⟩ + β|10⟩)
2
2

(124)

となり，やはり環境系とエンタングルする．e 系をトレースアウトして，s 系の縮約密度演算子を計算すると，

(

ρs =

|α|2
cos(gt)α∗ βcos(gt)αβ ∗
|β|2

)

(125)

となり，非対角項が減少する．|ψ⟩⟨ψ| → ρs の写像 Eph [t] は，Eph [t](ρ) =と書くことができ，確率1 − cos(gt)
1 + cos(gt)
ρ+
ZρZ
2
2

(126)

1−cos(gt)
でパウリ演算子 Z が作用すると考えても良い．
2

ここまでの議論は，１量子ビットからなる環境系を考えていたので，しばらく時間がたつと系にコヒーレンスが戻ってくることになる．しかし，実際には着目する系を取り巻く環境系は大自由度の系になっていることが多い．
したがって，それぞれの結合 g は小さい（常に gt ≪ 1 が成り立つ）とし，環境系に独立に M （≫ 1）個ある量子ビットと結合してしまう状況を考えよう．
最初の例の場合の時間 t に対応する写像はM(Eamp [t])

ρ=

∑

(M
∏

i1 ,...,iM ∈{1,2}×M

k=1= E1M ρE1† M +

M
−1
∑

) (M
)†
∏
Eik ρ
Eik

(127)

k=1

(E1k E2 E1M −k−1 )ρ(E1k E2 E1M −k−1 )† ,

(128)

k=0
*16

それぞれの量子ビットのハミルトニアン Hs = −ωs Zs および He = −ωe Ze を顕には考えていないが，ωe = ωs として相互作用描像を考えていると思えば良い．

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）と書ける．ここで，E22 = 0 を使った．さらに，

(
E1M =

1
0

)

0

,

cosM (gt)E1k E2 E1M −k−1 =(0 sin(gt) cosM −1−k (gt)
0
0

)
(129)

となる．このことから，時間 t の写像の Kraus 演算子は，γ = gM として（gM を固定し，g → 0 の極限で）
，

(
E1M =

1
0
0 e−γt

(

)
,

0
0

E2 =

√∑
M −1

M −k−1 (gt)k=0 sin(gt) cos
0

)

(
=

0
0

)
√
1 − e−γt
,
0

(130)

で与えられることになる．時間 t に対して指数的に |1⟩ の振幅が減衰する，振幅減衰ノイズになっている．同様に２つめの例に対して計算をすると，
M(Eph [t])1 − cosM (gt)
1 + cosM (gt)
ρ+
ZρZ
2
2
1 + e−γt
1 − e−γt
=
ρ+
ZρZ
2
2
=

(131)
(132)

となり，減衰定数 γ = gM で非対角項が減衰する．これを位相減衰ノイズと呼ぶ．これらのような極限では，もはやコヒーレンスは系には戻ってこない．デコヒーレンスが生じてしまうと，量子情報は失われてしまい，量子コ
ンピュータはうまく動かない．それに対処するための方法が次に説明する量子誤り訂正である．

7 量子誤り訂正
量子誤り訂正では，量子状態を雑音から保護するために量子情報を大きな次元のヒルベルト空間（多量子ビットからなる空間）の部分空間に埋め込む．このため，効率よく部分空間を記述することが必要となるが，そのための一つの方法であるスタビライザー形式について説明し，それによって定義されるスタビライザー符号を導入する．

n 量子ビットからなる 2n 次元ヒルベルト空間を考えよう．n 量子ビットのパウリ演算子のテンソル積から構成される n 量子ビットパウリ群{±1, ±i} × {I, X, Y, Z}⊗n(133)の可換部分群でかつ要素に −I ⊗n を含まないものをスタビライザー群 S を定義する（以降，特に混乱がない場合
は恒等演算子を次元に関係なくすべて I と書くことにする）．i 番目の量子ビットに作用する演算子を

Ai ≡ I ⊗ I ⊗ · · · ⊗ A ⊗ I ⊗ · · · ⊗ I(134)として，例えば S2 = {I, X1 X2 , Z1 Z2 , −Y1 Y2 } は可換群でありまた −I を含まないため，一つのスタビライザー群である．このようなスタビライザー群を定義するためには，スタビライザー群の独立な要素から成る最大の集合である生成元を定義すればよい．ここで，独立であるとは，ある集合に含まれる要素がその集合に含まれる他の要素の積で表すことができないことを意味する．例えば，前述の例の場合は，{X1 X2 , Z1 Z2 } を生成元として選ぶことができ，この要素の積で閉じるようにしてスタビライザー群 S2 を生成することができる．このとき S2 = ⟨{X1 X2 , Z1 Z2 }⟩ と書くことにする．スタビライザー形式では，状態をあらわに定義するかわりに，ス
タビライザー群の（要素の），状態に対する作用において安定となる状態，すなわち固有値 +1 の固有状態として状態を定義する．例えば，前述のスタビライザー群 S2 に対するスタビライザー状態は最大エンタングル状態√(|00⟩ + |11⟩)/ 2 である．これは，|0⟩1 |0⟩2 + |1⟩1 |1⟩2
|0⟩1 |0⟩2 + |1⟩1 |1⟩2
√
√
=
2
2
|0⟩1 |0⟩2 + |1⟩1 |1⟩2
|0⟩1 |0⟩2 + |1⟩1 |1⟩2
√
√
X1 X2
=
2
2
Z1 Z2

(135)
(136)

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

表1

スタビライザー符号 ⟨Z1 Z2 , Z2 Z3 ⟩ のに対するビット反転エラーとシンドローム．

Z1 Z2 \ Z2 Z3

+1

−1

+1

I, X1 X2 X3

X3 , X1 X2−1

X1 , X2 X3

X2 , X1 X3であることから確認される．
スタビライザー群には −I が含まれないので，生成元 {Si } の元は Si2 = I を満たす．よって固有値は ±1 の２通りになることがわかる．１つの生成元に対して，固有値 +1 と −1 の固有空間の 2 通りに分割されるので，生成元の個数を m とすると，2n 次元のヒルベルト空間を 2m 個に分割し，2n−m 次元の部分空間内の状態がすべてス
タビライザー状態となる．このような部分空間をスタビライザー部分空間と呼ぶことにしよう．スタビライザー
符号とは，このようなスタビライザー部分空間に情報を埋め込む量子誤り訂正符号のことである．
一般的な定義の前に，具体的にスタビライザー演算子が ⟨Z1 Z2 , Z2 Z3 ⟩ で与えられるようなスタビライザー部分
空間を考えて，スタビライザー符号を構成してみよう．量子ビットの数 3 に対して生成元の数は 2 であるので，2次元の部分空間（縮退）が定義される．この部分空間を張る基底を符号状態（code state）として論理量子ビット（logical qubit）を構成する．この縮退を解くために，スタビライザー演算子と独立でかつスタビライザー演
算子と可換な演算子 Z1 を１つ選び，この演算子の ±1 の固有状態 Z1 |0̄⟩ = |0̄⟩ ，Z1 |1̄⟩ = −|1̄⟩ として論理基底（logical basis）|0̄⟩ ≡ |000⟩, |1̄⟩ ≡ |111⟩(137)を定義する．同様に X1 X2 X3 と選び，基底を特定することもできる．このような，スタビライザー群と可換でありかつスタビライザー群と独立な演算子の作用において，スタビライザー部分空間は不変である．一方，スタビ
ライザー演算子とは異なり，部分空間内部では X1 X2 X3 |0̄⟩ = |1̄⟩ のように非自明に作用する．このような演算子
を符号化された論理量子ビットに作用する演算子という意味で，論理演算子（logical operator）と呼ぶ．Z1 とX1 X2 X3 は互いに反可換であり，符号状態 α|0̄⟩ + β|1̄⟩ に対するパウリ演算子として振る舞うことがわかる．このような論理演算子の選び方は一意的でないことに注意しておこう．というのも，スタビライザー演算子は符号
状態 |ψ̄⟩ に対して，自明に作用する

Si |ψ̄⟩ = |ψ̄⟩ for all Si ∈ S(138)

ので，L を論理演算子とすると，LSi （Si ∈ S ）も同じ作用をする論理演算子ということになる．つまり，論理演
算子の作用は，スタビライザー群と交換する演算子に対してスタビライザー群についての同値類をとったものに対応する．
一つ目の量子ビットにビット反転エラー X1 が発生したとしよう．符号状態 α|0̄⟩ + β|1̄⟩ は基底 {X1 |0̄⟩ =|100⟩, X1 |1̄⟩ = |011⟩} によって貼られる直交空間へと移される．スタビライザー演算子 Z1 Z2 とビット反転演算
子 X1 は反交換するので，固有値は +1 から −1 へと反転する．つまり，スタビライザー演算子の固有値の反転か
らエラーの発生（正しい部分空間にいるかどうか）に関する情報が得られる．このためエラー発生後のスタビラ
イザー演算子の固有値のことをシンドローム値と呼び，シンドローム値の集合をシンドロームと呼ぶことにする．
今考えている 3 量子ビットから成るスタビライザー符号のエラーの種類とシンドロームの対応は 1 のようになる．
ビット反転エラーが 1 つの量子ビットにしか発生しない場合は対応表からエラーを識別し，エラーを訂正することができる．しかし，X2 X3 のように 2 つの量子ビットに同時にエラーが発生してしまった場合は X1 と区別することができず，異なる符号状態になる論理エラーとなる．この符号は，ビット反転に対する誤り訂正が可能なので，3 量子ビット・ビット反転符号（3-qubit bit-flip code）と呼ぶ．

《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

一般に，m = n − k 個のスタビライザー生成元 ⟨S1 , ...Sm ⟩ から構成されるスタビライザー符号に対して，スタビライザー演算子と独立でかつ可換な k 個の互いに独立な論理演算子 ⟨Z̄k ⟩ を選び，その固有状態として k 個の論
理量子ビットを定義することができる．シンドロームはスタビライザー生成元 {Si } の固有値の集合 {si } によって与えられる．また，それぞれの演算子と反交換する演算子 X̄i (i = 1, ..., k)，つまり，すべての i, j ∈ 1, ..., k に対してX̄i Z̄j = (−1)δij Z̄i X̄j , X̄i X̄j = X̄j X̄i(139)を満たす演算子 X̄i が常に存在する．{X̄i , Z̄i } は符号化された自由度における i 番目の論理量子ビットに作用す
るパウリ演算子と見なす．
このようにして定義されたスタビライザー符号のエラーに対する耐性を測る指標として符号距離（codedistance）がある．符号距離は，論理演算子に含まれるパウリ演算子の数を，全ての論理演算子に対した最小化したときの最小値 d として定義される．つまり，演算子 A に含まれる（I 以外の）パウリ演算子の数を wt(A) として，L を論理演算子が構成する群とすると，d ≡ minL wt(L) ということになる．例えば，前述の 3 量子ビット符号の場合は符号距離は d = 1 である．これは，１つのパウリ Z エラーが作用してもスタビライザー空間内にとどまり，そのエラーの検出および訂正が出来ないことを意味する．きちんとした量子誤り訂正符号を構成するためには，もうすこし複雑な構造が必要になる．
少々天下り的であるが，以下のようにうまくスタビライザー群の生成元を選ぶことによって d = 3 の 5 量子
ビット・スタビライザー符号を構成することができる：

S1 = X ⊗ Z ⊗ Z ⊗ X ⊗ I,
S2 = I ⊗ X ⊗ Z ⊗ Z ⊗ X,
S3 = X ⊗ I ⊗ X ⊗ Z ⊗ Z,
S4 = Z ⊗ X ⊗ I ⊗ X ⊗ Z,

(140)
(141)
(142)
(143)

例えば，X ⊗5 や Z ⊗5 が論理演算子になるが，論理演算子に対してスタビライザー演算子の積をとっても論理演算子になることからすべての論理演算子に対して調べると d = 3 であることが確認できる．
符号距離 d は，符号空間内の１つの符号状態から始めてパウリ演算子を１つ１つ作用させていき，d 個作用させたときに初めて異なる符号状態になるという意味で，符号空間内の異なる 2 状態間の距離を表している．したがって，ある符号状態に対して (d − 1)/2 以下のパウリ演算子がエラーとして発生（パウリエラー）した場合，その状態から最も近い符号状態は一意的にもとの符号状態になる．従って，エラーが発生してしまい，あるシンド
ローム {si } によって定義される直交空間に符号状態が移ってしまったとき，その空間から元の符号空間に戻すことができる最小パウリ演算子で回復させることによって，⌊(d − 1)/2⌋ 個までのパウリエラーを訂正することができる．このような復号方法を最小距離復号という．前述の 5 量子ビット・スタビライザー符号は d = 3 なので１つの量子ビットに対するパウリエラーを訂正することができる．つまり，従って，ビット反転エラー（X ）に加え，位相反転エラー（Z ），ビット・位相反転エラー（Y ）のすべてを訂正することができる．

5 量子ビットの空間は 32 次元であり，4 つの生成元によって 16 通りのシンドロームに対応した部分空間に分割される．一方，１量子ビットのパウリエラーのパターンの総数は各量子ビットに対して３種類あるので 3 × 5 = 15個あり，エラーが全く発生していない 1 つを加え合計 16 通りのエラーパターンがある．16 個の直交する部分空間と 16 通りのエラーパターン（エラー無しを含む）がそれぞれ１対１対応していることに注意したい．このような性質を満たしうる最小の符号が上記の 5 量子ビット・スタビライザー符号である．
既に述べたように，スタビライザー演算子を適切に選んでおけば，ビット反転が生じる X エラー，位相反転が生じる Z エラー，もしくはその両方である Y エラーが作用した状態は，スタビライザー空間と直交する部分空間へと移され，t = ⌊(d − 1)/2⌋ 個以下のエラーであれば訂正が出来るのであった．それでは，一般的な CPTP 写像
で与えられるような量子ノイズであった場合はどうなるだろうか．実は，1 量子ビットの CPTP 写像の Kraus 演《講義ノート》

物性研究・電子版 Vol. 6, No. 4, 064217（2017年11月号）

算子 Ek は，パウリ演算子を基底として以下のように展開することができる．

Ek = ηkI I + ηkX X + ηkY Y + ηkZ Z.

(144)

この事実と X, Y, Z の全ての種類のエラーを訂正できることから一般的な量子ノイズであっても訂正可能であることが以下のように示される．R をパウリエラーに対して回復操作を行う超演算子としてその Kraus 演算子を Rjとすると，スタビライザ符号状態 |Ψ⟩ に対してパウリエラー A = X, Y, Z がうまく訂正されもとの状態に戻るので，以下の式が満たされていることになる：

Rj A|Ψ⟩ ∝ |Ψ⟩.

(145)(144) 式の分解のそれぞれにこの条件を適用することにより Rj Ek |Ψ⟩ ∝ |Ψ⟩ を得るので，
R ◦ E(|Ψ⟩⟨Ψ|) = |Ψ⟩⟨Ψ|,(146)となる（ここで R と E はともにトレースを保存することを使った）．よって，符号距離 d のスタビライザー符号
は Kraus 演算子が非自明に作用する量子ビットの数が高々 d 個であるような任意の量子ノイズを訂正することができることになる．
量子状態は古典ビットと異なり，連続的な自由度（波動関数）をもつ．従って，量子状態に対する量子ノイズは連続的な自由度を微妙に変化させるアナログ的なノイズが生じると考えられ，本来の状態とエラーが生じた状態を区別し訂正を行うことは，古典デジタル情報のそれとは異なり，難しいのではないかと考えられていた．古典の世界においてもアナログ計算機を定義することはできるが，もしアナログノイズを考慮せずに無限精度のアナロ
グ計算機を仮定すると（そのようなマシンを作ることを物理法則が許すとは思えないが）PSPACE という NP 問
題を含んだ非常に難しい問題をも効率よく解けてしまうことになる．PSPACE は，従来の古典 Turing 機械（デジタル古典計算機だと思ってよい）においてメモリー空間は多項式的であるが，計算時間は指数的にかけても良い，という非常に難しい問題のクラスである．しかし，このような強力なアナログ計算機が実現していないのは，
アナログノイズを克服できないからである（だからといってアナログ計算機が有用ではないということではなく，風洞実験のように，古典デジタル計算機でシミュレーションすることが難しい状況において有用であることは大いにある．また，最近ではアナログデバイスの並列性を利用して最適化問題や機械学習などを実測時間で高速化しようという試みもある）．もし，量子コンピュータが量子力学がもつアナログ性を顕につかって，アナログマシ
ンの意味で計算を加速しているのであれば，その興味はもっと限定されたものになるであろう（もちろん量子シ
ミュレーターなど，アナログ量子計算としても利用価値はある）．しかし，重ね合わせの原理を逆に利用することによって，エラーをパウリエラーとして離散化し訂正することが可能であることは興味深い．つまり，ある種アナログ的な情報をもつ量子状態に対するアナログエラーは，量子誤り訂正符号という量子多体系におけるエンタン
グルした構造を導入することによって離散化され，訂正することができることになる．この意味で，量子誤り訂正によって保護された万能量子計算はデジタル量子計算であるということができる．そして，量子誤り訂正によって誤り耐性のある量子コンピュータを構築できるという事実は，量子コンピュータという計算モデルが物理法則で許された計算の原理的限界を追求する上で適切なモデルであるという理論的保証も与える．

参考文献[1] Nielsen, M. A., Chuang, I. L. Quantum computation and quantum information. (Cambridge university
press 2010).
[2] K. Fujii, Quantum Computation with Topological Codes -From Qubit to Topological Fault-Tolerance-,
SpringerBriefs in Mathematical Physics (Springer-Verlag 2015).
[3] 小柴 健史, 藤井 啓祐, 森前 智行，「観測に基づく量子計算」（コロナ社 2017）．