現在の情報科学の理論は、1936年のAlan Turlingによるチューリングマシンを用いた計算機(コンピュータ)の理論や、1948年のClaude Shannonによる通信の数学的な基礎づけから始まりました。 トランジスタとレーザー(メーザー)の発明がそれぞれ1947年と1951年になされたことを考えると、TurlingやShannonが、情報処理に使用される機器がす べて古典力学に乗っ取って動作することを、 暗黙の仮定していたことは当然と言えるでしょう。彼らの研究から現在までに、情報科学技術は、TurlingやShannonが想像もしなかった規模で発展してきました。 現在、情報通信はコヒーレント状態と呼ばれる量子状態にあるレーザー光を、 光ファイバーを通して送信することで行われています。 また、半導体加工技術の進展により、最新のコンピュータに使われている集積回路は、10nmオーダー、原子にして数百個のサイズで、自然に量子性を帯び始めています。 そこで、デバイスが量子力学に基づいて動作をするという仮定に基づいて、情報科学の理論を作り直すことにより、従来の古典力学に基づいた 情報科学では実現ができなかった画期的な情報処理の実現を、量子情報科学の分野では目指しています。

量子通信

量子情報科学の分野が何時始まったのかという問いに、正確に答えるのは困難です。 しかし、エ ンタングルメント、ベルの不等式、量子測定の定式化といった、情報科学とは全く独 立に開始された研究を除くと、最初に情報科学の理論に量子力学を持ち込む必要性に気づいたのは通信理論の研究者達でした。レーザー技術の 発達に刺激を受けて、 Carl W. Helstromは、1960年代の中盤に、 量子的なレーザー光を使って通信をする際の信号検出の限界に関する研究を開始し、 2つの量子状態からなる信号の検出限界(Helstrom限界)を与えました[Helstrom67]。 その後、1970年代に、Alexsander Holevoは信号検出や量子状態の推定のみならず、 情報理論の枠組みで、量子情報を用いた情報通信を扱うことを開始し、 古典情報(従来式のビットに符号化された情報)を量子通信路を用いて送信する場合の、 通信路容量の上限であるHolevo限界を与えました[Holevo73]。しかしそ の後、量子通信の研究は停滞期に入ります。 後で説明する、量子鍵配送や量子計算の研究が進展したのちに、 量子通信の分野はBenjamin Schumacherによる量子情報源符号化定理の証明により、再度注目を浴びることになります[Schumacher95]。 Schumacherの結果によると、Gibbsエントロピーの量子版であるvon Neumannエントロピーにより、 量子状態に符号化可能な古典情報のレートが与えられます(量子情報源符号化定理)。 つまり、von Neumannエントロピーは、Shannonエントロピーの情報理論的な意味で正しい量子版でもあることが示され、 統計力学と情報理論が量子力学の上で美しく融合することが分かりました。このSchmacherらのなどに触発されたHolevoは量子通信の研究に復帰します。 そして、Holevoは、SchumacherとMichael Westmorelandと独立に量子通信路を用いた古典情報の送信の限界である、Holevo限界が実際に達成可能であることを証明し、古典情報の量子通信に対する通信 路符号化定理を完成させます[Holevo98] [SW97]。 その後、量子通信の研究は、量子状態の送信に関する通信路符号化の構築や[Lloyd97][Shor02][Devetak05]、 様々な多者間量子通信路プロトコルの研究[Winter01]などへ進展をしていきました。

量子暗号

量子通信の次に研究が開始されたのは量子暗号でした。 Stephen Wiesnerは1970年代に量子力学に基づく安全性を持つ電子マネーである量子マネーのプロトコルを発明しました。 しかし、そのあまりにも独創的な内容に、彼の論文は幾多の論文雑誌に採録を拒否され続け、1983年まで日の目を見ることはありませんでした[Wiesner83]。 もっとも、採録が拒否されている間にも、Wiesnerの量子マネーに関する研究は少数の研究者の間で興味をもって読まれ、その後の量子情報科学の発展に大きな影響を与え ます。 特に、Wiesnerの友人であったIBMのCharles H. Bennettは、 Wiesnerのプロトコルを他の研究者に紹介することを根気よく続けます。 1979年、BennettからWiesnerのプロトコルを紹介されたGilles Brassardは、 Bennettと一緒に、Wiesnerのプロトコルを元にした暗号通信プロトコルを構築することを思いつきます。 このプロトコルは最終的には、光の偏光からなる４つの量子状態をランダムに送信して、受信者は2つの観測方法をランダムに行うことで秘密鍵の配送を行う、 秘密鍵配送プロトコルの形にまとめられます。 彼らのプロトコルは通信路にノイズが無い場合には、どれだけ強い計算能力を持つ盗聴者に対しても(量子コンピュータが存在しない限り)安全であることが自明であり、 1983年に国際会議IEEE Symposium on Information Theoryに採録されることによって日の目を見ます[BB83]。 これが最初の量子鍵配送プロトコルであるBB84プロトコルです。 ちなみに、1983年に初めて発表されたプロトコルがBB84と呼ばれているのは、83年の国際会議の出版物が1ページのアブストラクトのみであったためで、 翌84年の別の国際会議のプロシーディングで初めて論文になったからです[BB84]。

BB84プロトコルは、1989年にBennettら自身によって最初の実証実験が行われます[BB89]。 その後1991年には、Bennett達とは独立にArtur K. Ekertがエン タングル状態を用いた量子鍵配送プロトコルを考案します[Ekert91]。 このプロトコルでは、スピン一重項 (singlet)状態にある量子状態を2 人の受信者に送信して、受信者達はそれぞれ3つの方向に対する観測をランダムに行います。すると、後で説明するベル不等式の破れが安全性を保障するというものでした。さら に1992年にBennettは2つの非直交な量子状態のみを用いた量子鍵配送プロトコルを考案します [Bennett92]。 量子鍵配送プロトコルはこの後も色々発明されますが、BB84,E91,B92の3つのプロトコルは、量子鍵配送の基本形となっており、 その後のプロトコルのほとんどは、 このどれかに似たプロトコルになっています。90年代半ば以降、量子鍵配送の研究は既存のプロトコルの安全性の証明を中心になされていくことになります。そのような方向性 の代表的な結果としては、Dominic MayersやPeter W. ShorとJohn Preskilらによるノイズの存在する状況下での、無限に強い計算力を持つ量子コン ピュータを持った盗聴者に対する BB84プロトコルの安全性証明があります[Mayers01][SP00]。 90年代半ば以降も、新しい鍵配送プロトコルの開発は行われますが、それらはより現実的な安全性や高いビットレートなどを付与するために従来のプロトコルを改造するという 方向性が中心になっていきます。例えば、Won-Young Hwangが導入したデコイ法[Hwang03]や、 Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, Valerio Scarani達が 共同で提案した装置独立な量子鍵配送法[ABGMPS07]、 Hoi-Kwong Lo, Marcos Curty, Bing Qi達による測定装置独立な量子鍵配送法[LCQ12]な どは、そのようなプロトコルの代表であると考えられます。 その後、2000年ごろから量子鍵配送を実用化する動きが活発化され、 今では、我々は、いくつかの企業から量子鍵配送の商用化されたシステムを購入できるといった状況になっています。 また、量子鍵配送以外にも、量子公開鍵暗号プロトコル[OTU00]、量子秘密分散[HBB99]、 量子コイン投げ[Ambainis04]、 量子秘匿計算[BFK09]な どといった様々な量子暗号プ ロトコルがこれまでに考案されています。

量子コンピュータ

量子コンピュータの提案

Shannonの情報理論やレーザーの発明からそれほど長い時間を経ずに、量子通信の研究は始まりましたが、 一方で、量子力学を用いて計算を高速化するという量子計算の研究は、Turlingの計算理論の開始から50年近く経ないと始まりませんでした。 このことは、レーザーが純粋な光の量子状態を作り出していたのに対して、コンピュータに使われる集積回路の量子性はそれほど高いものでは なく、計算に役立つどころか、ノイズ源としての厄介者と考えられていたからだと思われます。

最初に、物理学と計算理論との関連を研究し始めたのは、IBMのRolf Landauerです。 Landauerは1960年代の初頭より計算で発生する熱を最小化するという研究にとりかかり、 計算過程の詳細な解析の結果、熱の発生が原理的に避けられないのは、演算そのものではなく、メモリを消去する過程にあるというLandauer原理を見出しました[Landauer61]。 このLandauerの研究に触発されて、Bennett、Ed Fredkin、Tommaso Toffoliらは可逆計算の理論を発展させますが[Bennett73][Toffoli80][FT82]、 可逆計算の理論は、時間発展のユニタリ性より必然的に可逆計算にならざるを得ない、量子計算 の理論の発展に後程大きく寄与するものでした。 一方、1970年代より、著名な物理学者であるJohn Wheelerの研究室は、 物理学、特に量子力学の基礎を情報科学の理論に求める研究を進めていました。 当時の彼の研究室には、後に量 子情報源符号化を証明するSchumacherや、エンタングルメントの 研究で活躍するWilliam Woottersなどといった後に量子情報の発展に大きな足跡を残す科学者たちが含まれています。

このように計算理論と物理学の関係に興味を覚える研究者達が増えていき、 1981年には"Physics and Computation"というおそらく世界で初めて物理と計算理論との関連を取り扱った国際会議がLandauer, Fredkin, Toffoliらの主催により開かれます。 この国際会議の中で、著名な物理学者であるRichard Feynmanは、 量子力学を従来の計算機上で効率よくシミュレーションすることが不可能であることを示すとともに、 量子力学の原理に従って動作するコンピュータの作成がこの問題の解決法であるということを示唆しました[Feynman82]。 　Feynmanは具体的な量子コンピュータのモデルの提唱は行いませんでしたが、Feynmanが量子コンピュータの最初の提唱者であ ると考えられています。 　この国際会議に出席したWheelerは、同様のトピックを扱うセミナーを同年に開きます。 このセミナーには、Wheelerの学生や、Bennettらとともに、Wheelerと親交のあったDavid Deutschが参加しました。 量子力学の多世界解釈の研究をしていたDeutschは、 このセミナーに影響を受けて、チューリングマシンの理論を量子力学に基づき作り直した、 万能量子チューリングマシンの理論を完成させます。 そして、万能量子チューリングマシンは、任意の量子力学的な過程を表現できることを証明しました[Deutsch85]。 ちなみに、同時期に全く独立にPaul BenioffもDeutschとは大きく見た目の異なる量子チューリングマシンの定式化にたどり着きました[Benioff82]。 しかし、Benioffの定式化は、Deutscheの定式化ほどは、その後の量子計算の発展に大きな影響は与えなかったようです。

Deutschは、もともと、並行宇宙論への興味から万能量子チューリングマシンを考案したこともあり、 当時は、量子コンピュータを用いた計算(量子計算)は従来のコンピュータ(以後、古典コンピュータ)を用いた計算(古典計算)よりも速くなりはしないと考えていました。 実際、Deutschの論文にはQuantum pallarel processingを用いても古典コンピュータよりたいして早くならいない『証明』が載っています。 このことと、更には、そもそもDeutscheの論文が(Benioffの論文程ではないにせよ、)物理の用語で書かれており、 計算機科学者が理解できる形ではなかったこともあり、発表当時は、対して注目は集めなかったようです。 それでも、Deutschは量子計算に関する研究を続け、1989年には、新しい量子計算のモデルとして量子回路モデル(quantum circuit model)を考案します[Deutsch89]。 従来の回路モデルの量子版である量子回路モデルは、量子チューリングマシンと比べて遥かに見通しのよいモデルであり、 このモデルの登場によって量子計算研究への敷居が随分低くなりました。 量子計算に対する、量子回路モデルと量子チューリングマシンの2つの計算モデルの同等性は、Andrew Yaoにより1993年に証明されました[Yao93]。 現在では、この量子回路モデルが標準的な量子計算のモデルとして定着しています。

量子アルゴリズム

量子計算が古典計算よりも早くならないという『誤解』は、DeutscheとRechard Jozsaとの共同研究によって。 1992年、JozsaはDeutscheと共同で、従来のアルゴリズムよりも指数関数的に早くなる量子アルゴリズム(Deutsche- Jozsaアルゴリズム)の考案を行います[DJ92]。 これにより、量子計算を使うことにより従来の計算よりも劇的に早くなる例が出てきたわけですが、 残念ながら、Deutsche-Jozsaアルゴリズムは、実用的な問題に対するアルゴリズムではなく、 依然として、量子計算、そして量子情報は、一部の研究者のみが関心を持つマイナーな研究分野であり続けました。 この状況を打ち破ったのは、1994年のPerter Shorによる素因数分解と離散対数問題に対する多項式時間量子アルゴリズムの発見でした[Shor94]。 最も普及しているRSA暗号は素因数分解を元にしています。また、離散対数問題を元に作られている暗号も数多く存在します。 そのため、Shorのアルゴリズムを用いると、それらの暗号が解読可能であり、 量子コンピュータはの実用化は、現在の情報化社会の安全性を根底から揺るがすという 衝撃的な事実が明らかになりました。 このニュースは世界を駆け巡り、世界中の大学や企業の多くのグループが量子コンピュータの 　実現を目指す理論や実験を開始し、現在に続く量子情報科学の急速な発展が始まったのです。

Shorのアルゴリズムは、この後、隠れ部分群問題と呼ばれるクラスの量子アルゴリズムに一般化されることになります。 Shorのアルゴリズム以外にも隠れ部分群問題に対する量子アルゴリズムは多数知られており、 Simonのアルゴリズム[Simon94]や HallgrenによるPell方程式に対するアルゴリズム[Hallgren02]な ど が含まれます。 隠れ部分群問題以外の重要な、量子アルゴリズムとしては、Lav Gloverによる構造の入っていないデーターベースに対する探索アルゴリズムが存在します[Glover96]。 Gloverのアルゴリズムは、古典計算機でオーダーn (nは入力ビット数)で解けた探索問題を√n で解くもので、 Shorのアルゴリズムのように指数関数的な高速化を実現するものではありません。 しかし、Gloverのアルゴリズムは最適性が示されている上に、非常に広範囲の応用を持つことが知られています。 その他の、応用範囲の広い量子アルゴリズムとしては、ランダムウォークの量子版である量子ウォークを用いた量子アルゴリズムのクラスが知られています。 量子ウォークを用いた量子アルゴリズムの中には、指数関数的な高速化を実現するものもありますが[CSV07][CCDFGS03]、 多くは、グローバーのアルゴリズムと同様に、応用範囲の広い問題に対して多項式的な高速化を成し遂げるものです[Ambainis07] [MNRS07]。 最後に、説明は省略しますが、Jones多項式を近似する量子アルゴリズム[AJL06]、 ボーズ粒子サンプリングに対する量子アルゴリズム[AA11]、 更には様々な量子シミュレーションアルゴリズム[Lloyd96][AL97][FKW02] などが、重要な量子アルゴリズムとして知られています。

エンタングルメント(量子もつれ)

EPR論文とエンタングルメント

エンタングルメント(量子もつれ)とは、遠く離れた2つの量子系が持ちうる相関で、 今では、量子情報処理が対応する古典情報処理よりも優れているために必要不可欠な、情報処理のリソースとして考えられています。 エンタングルメントを持つ量子状態のことを、エンタングル状態と呼びますが、 エンタングル状態が最初に話題の中心になったのは、Albert Einstein、Boris Podolsky、Nathan Rosenが1935年に出版した歴史的な論文(EPR論文とよばれる)からです[EPR35]。 2体の最大エンタングル状態(もちろん当時はそのような用語は存在しない)は、 片方の系でどのような観測を行うかによって、もう一つの系が異なる非可換な物理量の固有関数になりうるという特殊な性質をもちます。 この論文の中でEinstein達は、『測定時において二つの系は、もはや相互作用をしていないので、一方の系に対する観測は、 もう一方の系にいかなる実際的変化も引き起こさない』という『局所性の仮定』と上記の性質から、 量子力学の波動関数による記述は『不完全』であるという結論を導きました。 これに対して、Niels BohrはEinstein達の『局所性の仮定』に同意せず、『相補性』を用いた議論で反論することにより[Bohr35]、 多くの物理学者たちを納得させることができました。 同年、SchroedingerもEinstein達の論文に触発されて、2体系の片側への測定によりもう片側の状態が変化する現象を取り扱う論文を書きます [Schroedinger35]。 "エンタングルメント(Entanglement)"という言葉は、この論文中で各系の波動関数の単純な積で記述できない2体系の波動関 数の持つ性質として 　初めて導入されます。

ベル不等式と隠れた変数の理論

Bohrによって量子力学の危機は避けられましたが、EPR論文が『我々は、物理的実在の完全な記述を与える理論の存在を信じる』と結んだことで、 量子力学に新たな変数(『隠れた変数』と呼ぶ)を付け加えることで、 実在論的な理論を作ることを目指す『隠れた変数の理論』という研究が注目を集めることになります。 1952年にDavid Bohmは、そのような隠れた変数の理論の具体例を作成して見せました[Bohm52]。 しかし、Bohmの隠れた変数の理論は実在論的な性格はもっていましたが、局所性を満たさない奇妙なものでした。 量子力学と同じ予言を与える局所性を持つ隠れた変数の理論を作成する試みは、John S. Bellにより否定的に解決されます。 1964年の論文で、Bellは2体の2準位系を扱い、後にベル不等式と呼ばれる、 局所的な隠れた変数の理論で記述される系が満たさなければならない不等式を導きました[Bell64]。 そして、系が最大エンタングル状態にあるときには、ベル不等式は破れることを証明しました。 最終的に、ベル不等式の破れは S.J.Freedman, J.F. Clauser[FC72]やAlain Aspectら[AGR81]によって、実験的に検証されました。 つまり、局所実在論では現実の物理は記述することができないことが分かりました。

Bellの論文の後、ベル不等式に関する研究は多くの注目を集めることになります。 1974年にJohn Clauser、Michael Horne、Abner ShimonyとRichard Holtは、 Bellの議論を整理し、より一般化された不等式(CHSH不等式)を得ます[CHSH69]。 CHSH不等式は、現在最も広く知られているベル不等式となっています。 1980年にBoris Tsirelsonは量子力学の与えるCHSH不等式の破れには限界がある(ベル不等式の最大破れ)ことを証明します[Tsirelson80]。 また、1989年にDaniel Greenberger, Michael Horne, Anton Zeilingerは不等式を使わなくても、代数的な議論で局所的隠れた変数の理論を否定できることを示します[GHZ89]。 ベルの不等式の研究は90年以降の量子情報の発展と共にますます活発になってきました。 90年以降の研究の進展については、近年のN. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehnerらのレビューが一番詳しいと思われます[BCPSW14]。 なお、尾張もベル不等式の最大破れに関するレビュー論文を書いていますので、よろしければご覧ください[EMO09]。

80年代までは、上記のようにエンタングルメントはベルの不等式の文脈のみで扱われてきました。 つまり、量子状態の持つ『エンタングルメント』と『ベルの不等式の破れが示す非局所性(ベル非局所性)』という2つの性質の間の区別はありませんでした。 この2つの性質の違いに初めて言及したのは、1989年のReinhard Wernerの論文でした[Werner89]。 従来、エンタングル状態は純粋状態に対して『二つの局所量子系の状態のテンソル積(product状態)で書けない全体系の状態』という 形で定義されていましたが、 この論文でWernerは、『product状態にある純粋状態の凸結合で書くことができる混合状態』をSeparable状態と定義 し、 Separable状態ではない状態として、一般の混合状態に対するエンタングル状態の定義を初めて与えました。 更に、今ではWerner状態と呼ばれている対称性のよい量子状態(混合状態)の1パラメータ族を定義し、 この族のあるパラメータの範囲に属する状態は、エンタングルメントを持つが、局所的な隠れた変数の理論で記述ができ、 どのようなベル不等式も破られないことを示しました。つまり、ベル不等式を破るにはエンタングルメントを持たねばならないが、 エンタングルメントを持っているからといって、ベル非局所性を持つとは限らないという意味で、 エンタングルメントとベル非局所性は別の概念であることが示されました。

エンタングルメントを用いた情報処理プロトコル

80年代までは、量子情報の研究者(非常に数は少ないですが)はベルの不等式を通じてエンタングルメントのことを知っていましたが、 それが直接、量子情報処理に役立つとは考えていなかったようです。 最初に、エンタングルメントが量子情報処理に役立つことに気が付いたのはStephen Wiesnerのようなのですが、例によってその仕事は出版されるまで長い時間がかかりました。 そのために、最初のエンタングルメントを用いた量子情報処理の発表は、Artur Ekertに追い越されてしまいます。量子鍵配送の章で既に紹介をしましたが、Ekertは91年に、 遠距離に離れたAliceとBobが最大エンタングル状態を共有することで、秘密鍵の共有が成立することを示します[Ekert91]。 E91プロトコルと呼ばれるこの量子鍵配送プロトコルが、最初のエンタングルメントを用いた量子情報処理プロトコルになります。 続いて1992年にBennettとWiesnerは、かねてからWiesnerの温めていたプロトコルを論文にします[BW92]。 Superdense coding(超密度符号)と呼ばれるこのプロトコルでは、AliceとBobが最大エンタングル状態を最初に共有しておくことにより、 Aliceは最大エンタングル状態の片割れをBobに送るだけで、自分の系の2倍のサイズのビットをBobに送信しています。 このプロトコルは、エンタングルメントの共有が量子通信路容量を増加させるという典型的な例を与えました。 続けて1993年に、Superdense codingプロトコルから発想を得て、 Bennett, Brassard, Claude Crépeau, Jozsa, Asher PeresとWoottersは共同で、 エンタングルメントを量子状態を遠距離に送信する、『量子テレポーテーション』に関する論文を出版します[BBCJPW93]。 このプロトコルでは、AliceとBobはあらかじめ最大エンタングル状態を共有しています。 最初に、Aliceは未知の量子状態と最大エンタングル状態の片割れにベル測定と呼ばれる測定をします。 そして、その観測結果をBobに送信し、BobはAliceの観測結果に基づいてユニタリ変換を行うと、 Bobの系の状態は最初にAliceが持っていた未知の量子状態になります。 このプロトコルが量子テレポーテーションと呼ばるのは、 量子状態の送信なしに未知の量子状態がAliceからBobへ移動しているからです。 ちなみに、Bennett達も論文の中で述べいますが、 Aliceの観測結果を聞くまでは、Bobの系は完全混合状態になっているので、 光速を超えて量子状態を送信することはできず、相対論とは矛盾しません。 このように、非常にセンセーショナルな量子テレポーテーションですが、 情報理論的にも、最大エンタングル状態の共有が、 量子状態に対するノイズの無い通信路を与えるという非常に重要な結果を与えました。

上記のように、最大エンタングル状態を共有することができると、 秘密鍵の共有や、古典情報の通信路容量の向上や、ノイズの無い量子通信などといった、 従来の情報理論では成し遂げられなかった様々な恩恵を預かることが分かりました。 しかし、遠距離に最大エンタングル状態を送信する方法は、まだ分かりませんでした。 というのも、遠距離に量子系を効率よく遅れるのは光の量子系を用いた場合ですが、 その場合でも光の減衰に伴ってエンタングル状態はノイズを受けてしまします。 結果として、AliceとBobのエンタングル状態は、最大エンタングル状態から程遠い、 ノイズの入った弱いエンタングル状態しか共有できないことになってしまいます。 この問題もBennettらによって解決されました。1995年に Bennett, Brassard, Sandu Popescu, Schumacher, John SmolinとW. K. Woottersは共同で、 遠距離にAliceとBobが、多数のノイズの入った混合状態にあるエンタングル状態から、 量子通信を使わずに、AliceとBobの局所量子系での量子操作と、観測結果の古典通信のみ(Local operation and classical communication; "LOCC"と略する)で、 少数の最大エンタングル状態を作成するプロトコルを発見しました[BBPSSW96]。 このようなプロトコルは以降、エンタングルメント蒸留(entanglement distillation)プロトコルと呼ばれるようになりますが、 このプロトコルのおかげで、遠距離でも最大エンタングル状態を共有する方法が得られ量子通信が現実性を大きく帯びてきました。

量子通信に関するノイズの問題に関しては、同時期にもう一つの方向性の研究が始まります。 以前紹介したように、1994年にShorは素因数分解アルゴリズムを発見しました。 しかし、Landauerを含む量子計算に否定的な研究者からは、 量子系はノイズに弱いので、計算がノイズに埋もれて続けれらなくなり、 結果として量子計算機は実現しないという批判が起きました。 それに対応するために、1995年Shorは、一つの量子ビットを9つの量子ビットに符号化することでノイズに対する耐性を持たせる、 所謂、量子誤り訂正符号を初めて開発しました。そして、この符号化を何度も繰り返して適用することで、 原理的にはノイズの影響を取り除ける可能性があることを示しました[Shor95]。 このShorの研究から、量子誤り訂正符号(qautnum error correcting codes)の研究の発展が始まり、現在までに大きな発展を遂げています[NC00]。 一方、Aliceが、自分の系に準備した最大エンタングル状態の片割れを、量子誤り訂正符号を用いて符号化しBobに送信することで、 AliceとBob間で最大エンタングル状態の共有を行うことが可能です。 よって、最大エンタングルメントの共有には、エンタングル蒸留と量子誤り訂正符号という二つの手法があることが分かりました。 　この二つのプロトコルが達成可能な最適レートは、それぞれ蒸留可能エンタングルメント(distillable entanglement)と量子通信路容量(quantum communication capacity)と呼ばれますが、 蒸留可能エンタングルメントと量子通信路容量との間に量子テレポーテーションプロトコルを介して、 定量的な関係が成立することをBennett, David DiVincenzo, Smolin, Woottersらは証明をしました。[BDSW96]

エンタングルメントの定量化

上記のように、エンタングルメントが量子通信に必要不可欠なリソースであることが明らかになりました。 このことを受けて、最大エンタングル状態を一つの単位として、それ以外のエンタングル状態の『量』(エンタングルメント量)を定義しようという研究が始まりました。 先ほど、紹介した蒸留可能エンタングルメントは、そのようなエンタングルメント量の一つで、与えられたエンタングル状態の多数のコピーか ら、 LOCCを用いて作成可能な最大エンタングル状態の漸近的なレートで定義されます。 逆に、LOCCを用いて、多数の最大エンタングル状態からLOCCを用いて、与えられたエンタングル状態のコピーを幾つも作成するプロトコルも考えることができます。 このようなプロトコルはエンタングルメント希釈(entanglement dilution)と呼ばれ、その最適レートはエンタングルメント量となります。 1995年にBennett, Herbert Bernstein, Popescu, Schumacherは共同で、2体の純粋状態に対しては、 蒸留可能エンタングルメントとエンタングルメント希釈の最適レートが一致して、その最適レートは部分系のエントロピーで与えられることを証明しました[BBPS96]。 よって、二体の純粋状態に対しては部分系のエントロピーという一つの指標で、エンタングルメントが定量的に評価できることが分かりまし た。さて、このころのBennett達の仕事から、混合状態にに対しては蒸留可能エンタングルメントとエンタングルメント希釈の最適レー トは一般的に一致せず、 また、それらの量を計算することも一般的には不可能であることが分かってきました。 そのため、混合状態に対する新しいエンタングルメント量の定義を目指す研究が盛んになりました。 中でも、Vlatiko Vedral, Martin Plenio, M.A. Rippin, Peter Knightは共同で、混合状態に対するエンタングルメント量が満たすべき条件を定義して、 その定義を実際に満たす新たなエンタングルメント量を量子相対エントロピーを用いて導入しました[VPRK97]。 また、同時期にGuifré Vidalも同様に、Vedralらとは少し異なる形で、エンタングルメント量が満たす条件を定義して、 純粋状態に対するエンタングルメント量から、混合状態に対するエンタングルメント量を機械的に定義する方法を導いています [Vidal98]。 彼らの定義により、与えられた関数がエンタングルメントの指標であると主張するために、最低限満たさないとならない条件として、 その関数がLOCCの下で広義の単調関数となるということが、一般的に受け入れられていきました。 すなわち、ある状態ψから別の状態φに変換するLOCCが存在するならば、ψはφより強い(もしくは同等の)エンタングルメントを持っているということです。 よって、エンタングルメントを完全に理解するには、ψからφにLOCCでの変換可能である必要十分条件を求めればよいことになります。 二体の純粋状態に対しては、この必要十分条件はMichael Nielsenによって求められ [Nielsen99]、 二体の純粋状態のエンタングルメントは解き明かされたといってよい状況になりました。 その後も、エンタングルメントの定量化の研究は、混合状態や三体以上の多体系の量子状態に対して盛んにおこなわれていきました。 これらのエンタングルメントの研究に関しては、Paweł Horodecki, Michał Horodecki, Karol Horodecki達によるレビューをご覧ください[HHH09]。

エンタングルメントと量子計算

最後に量子計算とエンタングルメントの関係について少し述べておきます。 　指数関数的な高速化を実現する代表的な量子アルゴリズムである、 隠れ部分群問題に対する量子アルゴリズムにおいてエンタングルメントが使われていることは明らかです。 しかし、一方でエンタングルメントをいくら作れたとしても、それだけでは量子計算は高速化しないことも分かっています。 1998年、Daniel GottesmanとEmanuel Knillは、クリフォード演算という限られたクラスに演算を制限した場合、 計算途中でエンタングルメントはいくらでも作れるにも関わらず、最終的な計算結果は、 古典計算機でシミュレート可能であることを証明しました[Gottesman98]。 また、他方では、Vidalは、エンタングルメントが系のサイズに対して少ない場合は、古典計算機でシミュレート可能であることを示しま した[Vidal03]。 これは、逆に言えば、純粋状態のみを用いた量子計算では、系サイズに対して十分なスピードで使用するエンタングルメントが増えるようなア ルゴリズムでないと、 指数的な高速化は無しえないことを意味します。 しかし、混合状態を用いた量子計算に対しては、 KnillとRaymond Laflammeは、1つのみ純粋状態で、 あとのすべての量子ビットが完全混合状態であるような初期状態を用いて、 指数関数的な高速化を成し遂げる量子アルゴリズムを発見しました[KL98]。 この結果から、混合状態に対しては量子計算の高速化に関わるのは、 エンタングルメントではなく、Quantum Discordと呼ばれる新たな量子相関ではないかという考えが生じました。 Animesh Datta, Anil Shaji, Carlton M. Caves達から始まったこの方向性の研究は、近年盛んに行われています[DSC08]。

参考文献リスト

量子暗号の初期の歴史に関しては、BB84プロトコルの開発者の一人であるBrassardの解説記事があります [Brassard05]。 量子コンピュータの初期の歴史は、日経サイエンスの古田彩さんが日本語で詳しい解説をしてくださっています[Furuta04]。 その他の量子情報の初期の歴史については、NielsenとIssac Chuangによる有名な教科書の"History and further reading"が詳しいです[NC00]。

[Brassard05]

G. Brassard, "Brief history of quantum cryptography: a personal perspective," IEEE Information Theory Workshop on Theory and Practice in Information-Theoretic Security, 2005. 19th Oct., pp.19 - 23; arXiv:quant-ph/0604072

[Furuta04]

古田彩, (2004) "二人の悪魔と多数の宇宙 : 量子コンピュータの起源, Two Demons and Many Worlds : The Quest for Quantum Computer"日本物理學會誌 59(8), 512-519,

[NC00]

M.A. Nielsen, I.L. Chuang, (2000), Quantum Computation and Quantum Information, Cambridge University Press,

[Helstrom67]

C. W. Helstrom, (1967) "Detection theory and quantum mechanics" Information and Control Vol. 10, Issue 3, Pages 254-291; C. W. Helstrom, "Detection theory and quantum mechanics(II)", Information and Control, Volume 13, Issue 2, August 1968, Pages 156–171

[Holevo73]

A.S. Holevo, (1973). "Bounds for the quantity of information transmitted by a quantum communication channel". Problems of Information Transmission 9: 177–183.

[Schumacher95]

B. Schumacher (1995). "Quantum coding". Physical Review A 51 (4): 2738–2747

[SW97]

B. Schumacher, M. Westmoreland, (1997), "Sending classical information via noisy quantum channels", Phys. Rev. A 56: 131–138

[Holevo98]

A.S. Holevo, (1998), "The Capacity of Quantum Channel with General Signal States", IEEE Transactions on Information Theory 44 (1): 269–273, arXiv:quant-ph/9611023,

[Lloyd97]

S. Lloyd (1997). "Capacity of the noisy quantum channel". Physical Review A 55 (3): 1613–1622. arXiv:quant-ph/9604015.

[Shor02]

P. Shor (2002). "The quantum channel capacity and coherent information" Lecture Notes, MSRI Workshop on Quantum Computation.

[Devetak05]

I. Devetak (2005). "The private classical capacity and quantum capacity of a quantum channel". IEEE Transactions on Information Theory 51: 44–55. arXiv:quant-ph/0304127.

[Winter01]

Andreas Winter, (2001) "The Capacity of the Quantum Multiple Access Channel," IEEE Trans. Info. Theor. 47, 3059-3065

[Wiesner83]

S. Wiesner, (1983)“Conjugate coding,” Sigact News 15(1), pp. 78 – 88

[BB83]

C. H. Bennett and G. Brassard, (1983)“Quantum cryptography and its application to provably secure key expansion, public-key distribution, and cointossing”, Proceedings of IEEE International Symposium on Information Theory, St-Jovite, Canada, page 91, September 1983.

[BB84]

C. H. Bennett and G. Brassard, (1984(“Quantum cryptography: Public key distribution and coin tossing,” Proceedings of IEEE International Conference on Computers, Systems & Signal Processing, Bangalore, India, pp. 175 – 179, December 1984

[Ekert91]

A. K. Ekert, (1991) "Quantum cryptography based on Bell’s theorem" Phys. Rev. Lett. 67, 661

[Bennett92]

C. H. Bennett, (1992) "Quantum cryptography using any two nonorthogonal states," Phys. Rev. Lett. 68, 3121

[Mayers01]

Dominic Mayers, (2001) "Unconditional security in Quantum Cryptography," JACM, vol 48, no 3, , p 351-406

[SP00]

Peter W. Shor and John Preskill, (2000) "Simple Proof of Security of the BB84 Quantum Key Distribution Protocol," Phys. Rev. Lett. 85, 441

[Hwang03]

Won-Young Hwang, (2003) "Quantum Key Distribution with High Loss: Toward Global Secure Communication," Phys. Rev. Lett. 91, 057901

[ABGMPS07]

A. Acín, N. Brunner, N. Gisin, S. Massar, S> Pironio, and V. Scarani,(2007) "Device-Independent Security of Quantum Cryptography against Collective Attacks," Phys. Rev. Lett. 98, 230501

[LCQ12]

H.-K. Lo, M. Curty, and B. Qi, (2012) "Measurement-Device-Independent Quantum Key Distribution," Phys. Rev. Lett. 108, 130503

[OTU00]

T. Okamoto, K. Tanaka, S. Uchiyama, (2000) "Quantum Public-Key Cryptosystems," Advances in Cryptology, 11th August 2000, Lecture Notes in Computer Science, Vol. 1880, pp 147-165

[HBB99]

Mark Hillery, Vladimír Bužek, and André Berthiaume, (1999)"Quantum secret sharing," Phys. Rev. A 59, 1829

[Ambainis04]

A. Ambainis, (2004)“A new protocol and lower bounds for quantum coin flipping”, Journal of Computer and System Sciences 68(2), pp. 398 – 416,

[BFK09]

A. Broadbent, J. Fitzsimons, E. Kashefi, (2009)"Universal blind quantum computation", Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 517-526

[Landauer61]

R. Landauer (1961), "Irreversibility and heat generation in the computing process" (PDF), IBM Journal of Research and Development 5 (3): 183–191

[Bennett73]

C.H. Bennett, (1973) "Logical Reversibility of Computation," IBM J. Res. Dev. 17(6), 525-532

[Toffoli80]

T. Toffoli, '~Reversible Computing," Tech. Memo MIT/LCS/TM-151, MIT Lab. for Comp. Sci. (1980).

[FT82]

E. Fredkin, T. Toffoli, (1982). "Conservative Logic" (PDF). International Journal of Theoretical Physics 21 (3-4): 219–253

[Feynman82]

R. P. Feynman, (1982). "Simulating physics with computers". International Journal of Theoretical Physics 21 (6–7): 467.

[Benioff82]

P. Benioff, “Quantum mechanical Hamiltonian models of Turing machines”, J. Stat. Phys. 29, 515 (1982)

[Deutsch85]

D. Deutsch, “Quantum theory, the Church-Turing principle and the universal quantum computer”, Proc. R. Soc. Lond. A 400, 97 (1985).

[Deutsch89]

D. Deutsch, “Quantum computational networks”, Proc. Roy. Soc. Lond. A 425, 73 (1989)

[Yao93]

A. C.-C. Yao, “Quantum Circuit Complexity”, Proceedings of the 34th Annual Symposium on the Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1993), p. 352.

[DJ92]

D. Deutsch, and R. Jozsa, “Rapid solution of problems by quantum computation”, Proceedings of the Royal Society, London, A439, 1992, 553–558.

[Shor94]

P. W. Shor, “Algorithms for quantum computation: discrete log and factoring”, Proceedings of the 35th Annual Symposium on the Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1994), p. 124.

[Simon94]

D. Simon, “On the power of quantum computation”, Proceedings of the 35th Annual Symposium on the Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1994), p. 116.

[Hallgren02]

S. Hallgren, (2002) “Polynomial time quantum algorithms or Pell’s equation and the principal ideal problem”, Symposium on the theory of computation STOC, May 2002.

[Grover96]

L. K. Grover, (1996). "A fast quantum mechanical algorithm for database search". arXiv:quant-ph/9605043

[Ambainis07]

Ambainis, A. (2007). "Quantum Walk Algorithm for Element Distinctness". SIAM Journal on Computing 37 (1): 210–239.

[MNRS07]

F. Magniez, A. Nayak, J. Roland, M. Santha, (2007). "Search via quantum walk". Proceedings of the 39th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. pp. 575–584.arXiv:quant-ph/0608026

[CSV07]

A. M. Childs, L. J. Schulman, U. V. Vazirani, (2007). "Quantum Algorithms for Hidden Nonlinear Structures". Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science. IEEE. pp. 395–404. arXiv:0705.2784

[CCDFGS03]

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, "Exponential algorithmic speedup by quantum walk," Proc. 35th ACM Symposium on Theory of Computing, pp. 59–68, 2003, quant-ph/0209131.

[AJL06]

D. Aharonov, V. Jones, Z. Landau, (2006). "A polynomial quantum algorithm for approximating the Jones polynomial". Proceedings of the 38th Annual ACM symposium on Theory of Computing. Association for Computing Machinery. pp. 427–436.

[AA11]

S. Aaronson, A. Arkhipov, "The computational complexity of linear optics", Proceeding STOC '11, Proceedings of the forty-third annual ACM symposium on Theory of computing Pages 333-342

[Lloyd96]

S. Lloyd, (1996) "Universal Quantum Simulators", Science Vol. 273 no. 5278 pp. 1073-1078

[AL97]

D.S. Abrams, S. Lloyd, (1997). "Simulation of many-body Fermi systems on a universal quantum computer". Physical Review Letters 79 (13): 2586–2589. arXiv:quant-ph/9703054

[FKW02]

M. Freedman, A. Kitaev, Z. Wang, (2002). "Simulation of Topological Field Theories by Quantum Computers". Communications in Mathematical Physics 227 (3): 587–603. arXiv:quant-ph/0001071

[EPR35]

A. Einstein; B. Podolsky, and N. Rosen (1935). "Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?". Phys. Rev. 47 (10): 777–780

[Bohr35]

N. Bohr, (1935) "Can Quantum-Mechanical Description of Physical Reality be Considered Complete?", Phys. Rev. 48, 696

[Schroedinger35]

E. Schroedinger (1935), "Disccusion of Probability Relation between Separated Systems", Methematical Proceedings of the Cambridge Philosophical Society, Vol.31, Issue 04, pp555-563

[Bohm52]

Bohm, David (1952). "A Suggested Interpretation of the Quantum Theory in Terms of 'Hidden Variables' I". Physical Review 85: 166–179

[Bell64]

J.S. Bell (1964), "On the Einstein-Podolsky-Rosen Paradox", Physics 1: 195–200

[FC72]

S.J. Freedman, J.F. Clauser (1972), "Experimental test of local hidden-variable theories", Phys. Rev. Lett. 28 (938),

[AGR81]

Alain Aspect, Philippe Grangier, Gérard Roger (1981), "Experimental Tests of Realistic Local Theories via Bell's Theorem", Phys. Rev. Lett. 47 (7): 460–3

[CHSH69]

J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Phys. Rev. Letters 23, 880 (1969).

[Tsirelson80]

B. S. Cirel'son, (1980) Quantum Generalizations of Bell's Inequality, Lett. Math. Phys. 4, 93 .

[GHZ89]

D. Greenberger, M. Horne, A. Zeilinger (1989). in: 'Bell's Theorem, Quantum Theory, and Conceptions of the Universe', M. Kafatos (Ed.), Kluwer, Dordrecht, pp.69-72; arXiv:0712.0921

[BCPSW14]

N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, (2014) "Bell nonlocality" Rev. Mod. Phys. 86, 419；arXiv:1303.2849

[EMO09]

David Avis, Sonoko Moriyama, Masaki Owari (2009) "From Bell Inequalities to Tsirelson's Theorem," IEICE Trans. on Fundamentals, vol. E92-A, No.5, pp.1254-1267; arXiv:0812.4887

[Werner89]

R. F. Werner, "Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model", Phys. Rev. A 40, 4277

[BW92]

C. H. Bennett and S. J. Wiesner, (1992) "Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states", Phys. Rev. Lett. 69, 2881

[BBCJPW93]

C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, (1993) "Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels" Phys. Rev. Lett. 70, 1895

[BBPSSW96]

C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Wootters, (1996) "Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels," Phys. Rev. Lett. 76, 722

[Shor95]

P. W. Shor, (1995) "Scheme for reducing decoherence in quantum computer memory" Phys. Rev. A 52, R2493(R)

[BDSW96]

C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters, (1996) "Mixed-state entanglement and quantum error correction" Phys. Rev. A 54, 3824

[BBPS96]

C. H. Bennett, Herbert J. Bernstein, S. Popescu, and B. Schumacher, (1996) "Concentrating partial entanglement by local operations" Phys. Rev. A 53, 2046

[VPRK97]

V. Vedral, M. B. Plenio, M. A. Rippin, and P. L. Knight, (1997) "Quantifying Entanglement," Phys. Rev. Lett. 78, 2275

[Vidal98]

Guifré Vidal, (2000) "Entanglement Monotone" Journal of Modern Optics, 47, 355

[Nielsen99]

M. A. Nielsen, (1999)"Conditions for a Class of Entanglement Transformations", Phys. Rev. Lett. 83, 436

[HHH09]

Paweł Horodecki, Michał Horodecki, and Karol Horodecki, (2009) "Quantum entanglementRyszard Horodecki", Rev. Mod. Phys. 81, 865

[Gottesman98]

D. Gottesman, (1998). "The Heisenberg Representation of Quantum Computers," Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics, eds. S. P. Corney, R. Delbourgo, and P. D. Jarvis, pp. 32-43 (Cambridge, MA, International Press, 1999)

[Vidal03]

Guifré Vidal, "Efficient Classical Simulation of Slightly Entangled Quantum Computations", Phys. Rev. Lett. 91, 147902 – Published 1 October 2003

[KL98]

E. Knill and R. Laflamme (1998) "Power of One Bit of Quantum Information", Phys. Rev. Lett. 81, 5672

[DSC08]

Animesh Datta, Anil Shaji, and Carlton M. Caves, (2008) "Quantum Discord and the Power of One Qubit," Phys. Rev. Lett. 100, 050502