量子コンピュータ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

量子コンピュータ (りょうしコンピュータ、英語:quantum computer) は、量子力学的な重ね合わせを用いて並列性を実現するコンピュータ量子計算機とも言う。

概要[編集]

従来の計算機(量子計算機に対して、古典計算機という)は1ビットにつき、0か1の何れかの値しか持ち得ないのに対して、量子計算機では量子ビット (qubit; quantum bit) により、1ビットにつき0と1の値を任意の割合で重ね合わせて保持することが可能である。

n量子ビットあれば、2^nの状態を同時に計算できる。もし、数千qubitのハードウェアが実現したら、この量子ビットを複数利用して、量子計算機は古典計算機では実現し得ない規模の並列処理が実現する。理論上、現在の最速スーパーコンピュータ(並列度が2^{20}以下)で数千年かかっても解けないような計算でも、例えば数十秒といった短い時間でこなすことができる。

従来のノイマン型コンピュータはプログラムによってどのような計算でも実行できる汎用計算機であるのに対し、現時点での量子コンピュータは、特定のアルゴリズムを高速に処理する専用計算機や、古典計算機を補助するコプロセッサとして考察されている(量子コンピュータは非ノイマン型である)。多くの量子計算機用のプログラミング言語はコプロセッサ方式を前提としている。

歴史[編集]

1980年代[編集]

量子計算機の歴史は、1980年に Paul Benioff が量子系においてエネルギーを消費せず計算が行えることを示した[1]ことに端を発し、1982年ファインマンも量子計算が古典計算に対し指数関数的に有効ではないかと推測している[2]。これらに続き、1985年ドイッチュは、量子計算機の原モデルである量子チューリングマシン英語版[3]を定義し、1989年量子回路英語版[4]を考案した。

1990年代[編集]

1992年に、ドイッチュとジョサ英語版は、量子コンピュータが古典コンピュータよりも速く解ける問題でドイッチュ・ジョサのアルゴリズム英語版を考案した[5]1993年に、ウメーシュ・ヴァジラーニ英語版と生徒のEthan Bernsteinは、万能量子チューリングマシン英語版量子フーリエ変換英語版のアルゴリズムを考案した[6]

1994年ピーター・ショア英語版は、実用的なアルゴリズム『ショアのアルゴリズム英語版[7]』を考案し、量子コンピュータの研究に火をつけた。これは、ヴァジラーニらの量子フーリエ変換や、同年のSimonの研究[8]を基礎に置いている。量子計算機特有のアルゴリズムであるショアのアルゴリズムが、古典計算機では現実的な時間で解くことができない素因数分解を、極めて短い時間で実行出来ることから、素因数分解の困難性を利用したRSA暗号の安全性は実用的な量子計算機が実現されれば崩れることを示した。

1995年に、アンドリュー・スティーン英語版[9]ピーター・ショア英語版[10]により、量子誤り訂正のアルゴリズムが考案された。 1996年に、ロブ・グローバー英語版により、その後、様々なアルゴリズムに応用されるグローバーのアルゴリズム[11]が考案された。同年、セルジュ・アロシュは、実験的観測によって量子デコヒーレンスを証明し、 [12] [13] 量子デコヒーレンスが量子コンピューター実現への障害となることが実証された。 1997年に、Edward FarhiとSam Gutmannにより、量子ウォーク[14]Continuous-time quantum walk、略称: CTQW)が考案された。1998年に、量子コンピュータ用のプログラミング言語である、QCL (Quantum Computation Language) の実装が公開された。

2000年代[編集]

ハードウェア開発に大きな進展があり、2008年イオントラップ英語版の専門家デービッド・ワインランドは、個々のイオンをレーザー冷却して捕捉することが出来ることを示し、個々の量子もつれ状態にあるイオンをマニピュレーションする、イオン・トラップ型量子コンピューター英語版の研究が進展した。[15]

ショアのアルゴリズムは、2001年核磁気共鳴[16]により、2007年量子光学[17]により、2009年に光集積回路[18]により15の素因数分解 (=3*5) が実装された。

2011年カナダD-Wave Systemsは商用量子コンピューターと称する計算機を世界で初めて発売した。これは128量子ビットのシステムで、量子焼きなまし法による最適化計算に特化したものである[19]。これが本当に量子効果を用いた計算機であるかという点について、現在はまだ疑いがもたれているが、確かに量子効果を用いた計算機であるらしいとの調査論文が英科学誌ネイチャーに発表[20]されており、他の物理学者の追試が待たれる。

2012年セルジュ・アロシュデービッド・ワインランドノーベル物理学賞を受賞した。受賞理由は「個別の量子系に対する計測および制御を可能にする画期的な実験的手法に関する業績」である。

エドワード・スノーデンの開示文書によると、NSAにおいて暗号解読のための実用化が研究されているとされる[21]

ソフトウェア[編集]

アルゴリズム[編集]

量子計算機特有のアルゴリズムがいくつか知られており、古典的に有名なものを示す。他の物は、Quantum Algorithm Zoo[22]などを参照。

ショアのアルゴリズム[編集]

ショアのアルゴリズム英語版: Shor's factorizationとも)とは、素因数分解問題を高速に(多項式時間で)解くことができるアルゴリズムのことである。古典計算機では非現実的な時間(準指数時間)で解くアルゴリズムしか知られていない。1994年ピーター・ショア英語版によって発見された[7][23]。ショアは本件で、ネヴァンリンナ賞ゲーデル賞を受賞した。

2001年12月にIBMアルマデン研究所にて7qubitの量子計算機で15 (=3×5) の素因数分解に成功した(Nature,12月20日発行号[16])。

少し改造することで離散対数問題(DLP,ElGamal暗号楕円曲線暗号の安全性の根拠)も多項式時間で解くことができる。このアルゴリズムの基本的なアイデアを拡張したものが、可換隠れ部分群問題についての量子アルゴリズムである。現在は、これをさらに非可換隠れ部分群問題に拡張する研究が進展している。

ショアのアルゴリズムは、量子コンピュータが離散フーリエ変換を高速に実行できることによる。また、アルゴリズム全体は確率的(BQP)であり、正しい答えが得られるまで、何度も試行する。

N を因数分解するにあたり、a は N に対してな数とし、a の mod N に関する位数、\min \{ x | a^x = 1 \pmod N\} を求める。つまり、a^x の周期を求める。位数が高速に求められれば、因数分解は高速に行える。

手順の概略は以下の2つ。

  1. 全ての x に対して、均等な確率となるように初期化する。そして、それを a^x~\bmod N のみ確率を持ち、それらは均等になるように変換する。この計算は量子コンピュータ的であるものの、基本的な考えは古典コンピュータと変わらない。そのために、2進数の足し算・引き算や、ビットによる条件分岐などを用意する。
  2. a^x~\bmod N は周期 r を持つ。この周期が求める位数である。従って、1で得られた結果を離散フーリエ変換する。すると、周波数 1 / r のところの確率が大きくなるので、観測すると、高い確率で r が得られる。失敗した場合は、成功するまで繰り返す。

グローバーのアルゴリズム[編集]

n個のデータの中から、ある特定のデータを\sqrt nステップで取得することができるアルゴリズム。正確には、1〜Nのある一つの値で、オラクル関数f(z)が1になり、それ以外はf(z) = 0となる、オラクル関数fにおいて、f(z) = 1となるzを求める問題。オラクル関数とは計算量が0の関数である。古典計算機ではおよそn/2ステップが必要である。 1996年ロブ・グローバー英語版が発表した[11][24]。きわめて広範な種類の確率的アルゴリズムや量子アルゴリズムと組み合わせて、計算時間をその平方根まで落とすことができる。ショアのアルゴリズムほどその効果は劇的ではないが、広い応用をもつことが特徴である。検索条件や検索対象について改良されている。

このアルゴリズムはデータ数に見合うだけ十分なqubit数があることを前提としているが、古典コンピュータにおいてデータに見合うだけの十分な並列度がある場合、f(z) = 1 を探すのはO(1)であり、関数の最小値を探す問題は、O(log log n) である。

ドイッチュ・ジョサのアルゴリズム[編集]

量子ウォーク[編集]

ランダムウォークを量子コンピュータ上で実行する。いくつかのアルゴリズムがこれを利用して作られている。

離散フーリエ変換[編集]

振幅に対して離散フーリエ変換を行うが、振幅は直接は観測できないことに注意が必要。ショアのアルゴリズムで使われている。QCLでのソースコードは以下の通り。変数 q を離散フーリエ変換している。V は conditional phase、H はアダマール変換英語版である。

for i = 1 to #q {
  for j = 1 to i - 1 {
    V(pi / 2^(i - j), q[#q - i] & q[#q - j]);
  }
  H(q[#q - i]);
}
flip(q);

プログラミング言語[編集]

量子コンピュータ用のプログラミング言語とその処理系の実装が多数提案されており、QCL[25]などがある。詳細は、en:Quantum programming を参照。

シミュレーター[編集]

古典コンピュータ上で量子コンピュータのアルゴリズムを実行するためのシミュレーターが多数作られている。一覧については、List of QC simulators[26]を参照。

ハードウェア[編集]

ハードウェアは量子ゲートを組み合わせた量子回路英語版によって実現されるが、数学的に等価な量子ゲートが物理的には核磁気共鳴量子光学量子ドット超伝導素子、レーザー冷却などによって構成出来るため、様々な実験的ハードウェアの実現法が研究されている。2011年現在、ハードウェアは実用化レベルに至っていない。

核磁気共鳴[編集]

近年、核磁気共鳴(NMR; 例:[1])を用いた量子コンピュータの研究開発が行われている[2]。関西では、大阪大学、京都大学、大阪市立大学や、近畿大学に設立された量子コンピューター研究センターなどで盛んに研究が行われている。

2001年、7qubit量子コンピュータによる素因数分解が実装された[16][27]

qubit数を増やすことは、課題を抱えている。核磁気共鳴 (NMR) により、1998年に2qubit、1999年に3qubit、2000年に5qubit、2001年に7qubit[28]、2005年に8qubit[29]、2006年に12qubit[30]が実現した。1qubit増えるごとに並列度は2倍になる。ちなみに、古典コンピュータでは、集積度(並列度)を2倍にするのに約2年かかっていて、ムーアの法則と呼ばれる。

量子光学[編集]

特に光子を用いているものは光子コンピュータ光量子コンピュータとも呼ばれる。 2001年非線形光学を使わずに、量子コンピュータを作成する方法が考案された[31]。線形光量子コンピュータ (: linear optical quantum computer、LOQC) と呼ばれ、その後の光量子コンピュータの主流となる。

2007年光子を使い、4qubit量子コンピュータによる素因数分解が実装された[17]。さらに、2009年、光集積回路(シリコンフォトニクス)上で、4qubit量子コンピュータによる素因数分解が実装された[18]

量子ドット[編集]

超伝導素子[編集]

SQUIDを含む超伝導素子を用いた量子コンピューターのqubitは、ジョセフソン・ジャンクションの状態によって構成されている[32][33]

レーザー冷却[編集]

イオントラップ英語版を用いる量子コンピュータでは、レーザー冷却によってイオンの捕捉とマニピュレーションを行なう。

量子回路[編集]

量子ゲート[編集]

古典コンピュータは、ANDやORやNOTやXORなど、複数の基本論理演算子を備えているが、数学的にはNANDゲートからAND,OR,NOTを構成できるため、NANDゲートのみからなる回路で任意の計算を行える。NANDゲートは、リレー真空管トランジスタといった物理的な実現方法が知られている。

量子コンピュータでは、量子回路の基本論理演算子は量子ゲートと呼ばれ、ユニタリー行列でなくてはならない。任意の1量子ビットに対するユニタリー行列は以下の形式で表現できる。


e^{i \psi}
\begin{pmatrix}
e^{i(-\alpha -\beta)}\cos\theta & -e^{i(-\alpha +\beta)}\sin\theta \\
e^{i(\alpha -\beta)}\sin\theta & e^{i(\alpha +\beta)}\cos\theta
\end{pmatrix}

1量子ビットに対する任意のユニタリー変換とCNOTゲートの組合せによって、n量子ビットの場合も任意のユニタリ変換を構成出来ることが知られている。

NOT[編集]

NOTはパウリ行列の1つでもある。


X = NOT = 
\begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix}


X|x\rangle = |\tilde{x}\rangle

スワップ[編集]


S_{10} = \begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}


S_{10}|x\rangle |y\rangle = |y\rangle |x\rangle

制御NOT[編集]

CNOTと呼ばれる。XORに相当する。


C_{10} = \begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{pmatrix}


C_{10}|x\rangle |y\rangle = |x\rangle |y \oplus x\rangle

パウリ行列[編集]


X = NOT = 
\begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix}


Y = 
\begin{pmatrix}
0 & -i \\
i & 0
\end{pmatrix}


Z = 
\begin{pmatrix}
1 & 0 \\
0 &-1
\end{pmatrix}


\sqrt{X} = \sqrt{NOT} = H \sqrt{Z} H =
\frac{1}{2}
\begin{pmatrix}
1+i & 1-i \\
1-i & 1+i
\end{pmatrix}


\sqrt{Z} = 
\begin{pmatrix}
1 & 0 \\
0 & i
\end{pmatrix}

アダマール変換[編集]


H = \frac{1}{\sqrt2}(X+ Z) = 
\frac{1}{\sqrt2}
\begin{pmatrix}
1 & 1 \\
1 &-1
\end{pmatrix} = \frac{1}{\sqrt2} H_2

H_2アダマール行列である。

Conditional Phase[編集]

CPhaseと呼ばれる。


V(\phi): |x\rangle \to 
\begin{cases}
e^{i \phi}|x\rangle & \mbox{if }x = 111\cdots \\
|x\rangle & \mbox{otherwise}
\end{cases}

1量子ビットの場合は、以下の通り。


V(\phi) = 
\begin{pmatrix}
1 & 0 \\
0 & e^{i \phi}
\end{pmatrix}

回転[編集]


U(\theta) = 
\begin{pmatrix}
\cos\theta & -\sin\theta \\
\sin\theta & \cos\theta
\end{pmatrix}

トフォリゲート[編集]

Toffoliゲート。制御-制御NOTゲート(ccNOTゲート)ともいわれる。


T|x\rangle |y\rangle |z\rangle = |x\rangle |y\rangle |z \oplus (x \land y)\rangle

フレドキンゲート[編集]

計算能力[編集]

ヴァジラーニらは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価であることを示した。したがって、古典チューリングマシンで原理的に解くことができない問題は量子チューリングマシンにも解くことはできない。

量子コンピュータは古典コンピュータを容易にシミュレートすることが可能であるため、古典的なコンピュータで速く解ける問題は、量子コンピュータにも速く解くことができる。よって、量子コンピュータは古典コンピュータ「以上」に強力な計算速度を持つ。ただし、「より大きい」計算速度を持つのかどうか(量子コンピュータにしか速く解けない問題が存在するのかどうか)は、P≠NP予想という、現在のところ証明されていない予想に依存する。 ショアのアルゴリズムにより、NP問題(検算はすぐにできるが、解くのに時間がかかる問題)である素因数分解を素早く解くことができるため、例えば素因数分解問題が古典コンピュータに多項式時間で解けないということを示せば量子コンピュータは古典コンピュータより強力であることになる。

参考文献[編集]

  1. ^ The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines
  2. ^ Simulating Physics with Computers
  3. ^ Quantum theory, the Church-Turing principle and the universal quantum computer
  4. ^ Quantum computational networks
  5. ^ Rapid Solution of Problems by Quantum Computation
  6. ^ Quantum complexity theory
  7. ^ a b Peter W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", In Proceeding of 35th IEEE FOCS, pp.124-134, Santa Fe, NM, Nov 20-22, 1994. (ショアのアルゴリズムの論文)
  8. ^ On the Power of Quantum Computation
  9. ^ Multiple Particle Interference and Quantum Error Correction
  10. ^ Good Quantum Error-Correcting Codes Exist
  11. ^ a b Lov K. Grover, "A fast quantum mechanical algorithm for database search", STOC'96, pp.212-219, Philadelphia, Pennsylvania, United States, May 22-24, 1996. (グローバーのアルゴリズムの論文)
  12. ^ Serge Haroche, Jean-Michel Raimond & Michel Brune ; Le chat de Schrödinger se prête à l'expérience - Voir en direct le passage du monde quantique au monde classique, La Recherche 301 (Septembre 1997) 50 (disponible en ligne)
  13. ^ Serge Haroche ; Une exploration au cœur du monde quantique, dans : Qu'est-ce que l'Univers ?, Vol. 4 de l'Université de Tous les Savoirs (sous la direction d'Yves Michaux), Odile Jacob (2001) 571.
  14. ^ Quantum Computation and Decision Trees
  15. ^ Christopher R. Monroe en David J. Wineland. "Quantum Computing with Ions." Scientific American, 11 augustus 2008.
  16. ^ a b c Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
  17. ^ a b Demonstration of Shor's quantum factoring algorithm using photonic qubits
  18. ^ a b Shor's Quantum Factoring Algorithm on a Photonic Chip
  19. ^ Learning to program the D-Wave One”. 2013年6月閲覧。
  20. ^ Experimental signature of programmable quantum annealing”. 2013年6月閲覧。
  21. ^ Steven Rich; Barton Gellman (2014年1月3日). “NSA seeks to build quantum computer that could crack most types of encryption” (English). The Washington Post. http://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_story.html?hpid=z1 2014年1月9日閲覧。 
  22. ^ http://www.its.caltech.edu/~sjordan/zoo.html
  23. ^ Peter W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing, Vol.26, No.5, pp.1484-1509, Oct 1997. (ジャーナル版)
  24. ^ Lov K. Grover, "Rapid sampling though quantum computing", STOC'00, pp.618-626, Portland, Oregon, United States, May 21-23, 2000. (グローバーの新アルゴリズム)
  25. ^ http://tph.tuwien.ac.at/~oemer/qcl.html
  26. ^ http://www.quantiki.org/wiki/index.php/List_of_QC_simulators
  27. ^ IBM's Test-Tube Quantum Computer Makes History
  28. ^ 【レポート】量子コンピュータとは(2) - 鉄腕アトムの時代に向けて
  29. ^ 量子バイトを実現――量子コンピューティングへの大きな一歩
  30. ^ Benchmarking quantum control methods on a 12-qubit system
  31. ^ A scheme for efficient quantum computation with linear optics
  32. ^ Clarke, John; Wilhelm, Frank (June 19, 2008). “Superconducting quantum bits”. Nature 453 (7198): 1031–1042. Bibcode 2008Natur.453.1031C. doi:10.1038/nature07128. PMID 18563154. http://www.nature.com/nature/journal/v453/n7198/full/nature07128.html. 
  33. ^ William M Kaminsky (2004年). “Scalable Superconducting Architecture for Adiabatic Quantum Computation”. arXiv:quant-ph/0403090 [quant-ph]. 

関連項目[編集]

外部リンク[編集]