量子コンピュータ

量子コンピュータ （りょうし-） は、量子力学的な重ね合わせを用いて並列性を実現する次世代のコンピュータ。2011年現在、実用的なレベルでのハードウェアの実現には至っていない。量子計算機とも言う。特に光子を用いているものは光子コンピュータ、光量子コンピュータとも呼ばれる。

概要

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

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

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

歴史

1980年代

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

1990年代

1992年に、DeutschとJozsaにより、量子コンピュータが古典コンピュータよりも速く解ける問題が考案された。 1993年に、BernsteinとVaziraniにより、万能量子チューリングマシンが記述され、翌年のShorのアルゴリズムで重要な役割を果たすフーリエ変換のアルゴリズムが考案された。

初めて実用的なアルゴリズムを構築し、量子コンピュータの研究に火をつけたのは、1994年にショアによって考案されたいわゆる、Shorのアルゴリズムである。これは、同年のSimonの研究を基礎に置いている。 Shorのアルゴリズムは量子計算機特有のアルゴリズムであり、古典計算機では現実的な時間で解くことができないと予想されている素因数分解を、量子計算において極めて短い時間で解決することが出来ることが示されている。このため、実用的な量子計算機が実現されれば、素因数分解の困難性を利用したRSA暗号の安全性が崩れることになる。

1995年に、Andrew SteaneやPeter Shorにより、量子誤り訂正のアルゴリズムが考案された。 1996年に、Lov K. Groverにより、その後、様々なアルゴリズムに応用されるGroverのアルゴリズムが考案された。 1997年に、FarhiとGutmannにより、量子ウォークが考案された。1998年に、量子コンピュータ用のプログラミング言語である、QCL (Quantum Computation Language) の実装が公開された。

2000年代

ハードウェアに進展があった。Shorのアルゴリズムは、2001年に核磁気共鳴により、2007年に量子光学により、2009年に光集積回路により15の素因数分解 (=3*5) が実装された。

計算能力

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

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

アルゴリズム

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

Shorのアルゴリズム

素因数分解問題を高速に（多項式時間で）解くことができるアルゴリズム。古典計算機では非現実的な時間（準指数時間）で解くアルゴリズムしか知られていない。1994年にShorによって発見された。Shorは本件で、ネヴァンリンナ賞とゲーデル賞を受賞した。

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

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

詳細

Shorのアルゴリズムは、量子コンピュータが離散フーリエ変換を高速に実行できることによる。また、アルゴリズム全体は確率的(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 が得られる。失敗した場合は、成功するまで繰り返す。

Groverのアルゴリズム

詳細は「グローバーのアルゴリズム」を参照

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

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

量子ウォーク

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

離散フーリエ変換

振幅に対して離散フーリエ変換を行うが、振幅は直接は観測できないことに注意が必要。Shorのアルゴリズムで使われている。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);

ハードウェア

実験的には、核磁気共鳴、量子光学、量子ドット、超伝導素子、レーザー冷却などによる実現法が研究されている。

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

核磁気共鳴

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

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

量子光学

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

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

量子回路

量子ゲート

古典コンピュータには、ANDやORやNOTやXORなど、基本的な論理演算がある。それらは量子コンピュータでは量子ゲートに相当する。量子ゲートはユニタリー行列でなくてはならない。

古典コンピュータではNANDのみでAND,OR,NOTを構成できるため、NAND一つで任意の計算を行える。 それに対し、n量子ビットの場合は1量子ビットに対する任意のユニタリー変換とCNOTゲートがあれば任意のユニタリ変換を行えることが知られている。

任意の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}}$

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={\sqrt {\frac {1}{2}}}(X+Z)={\sqrt {\frac {1}{2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}$

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$

プログラミング言語

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

シミュレーター

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

関連項目

• 量子ビット
• 量子状態
• 量子もつれ
• 量子テレポーテーション
• フォールトトレラント量子計算
• アインシュタイン＝ポドルスキー＝ローゼンのパラドックス
• 量子暗号
• NMR
• 集積回路
• ノイマン型
• DNAコンピュータ
• ニューロコンピュータ
• 光コンピュータ
• 光コンピューティング
• 量子ウォーク(量子ランダムウォーク)