そもそも量子コンピュータとは

アイデア

古典コンピュータでは情報は0 or 1のどちらかの状態をとる「古典ビット」で表される。
量子コンピュータは0と1の両方の状態を同時にとることができる「量子ビット」で表現される。

量子コンピュータの原理を用いることで、古典コンピュータに比べて飛躍的に高速に計算を行える場合がある。

量子コンピュータの方が古典コンピュータよりも高速なのかどうか、いまだにわかっていない問題の方が圧倒的に多い。一部の問題については現状の古典コンピュータアルゴリズムよりも高速であることが証明されている。

e.g. 1 ) 素因数分解、1995年にショアが量子アルゴリズムを発見。
e.g. 2 ) 整理されていないデータから目的のデータを探しだす探索問題、1996年にグローバーが考案。
e.g. 3 ) 連立一次方程式の解を求める問題、2009年に開発。HHLアルゴリズム。

応用分野: 流体解析、電磁気解析、機械学習など。

計算途中に生じた量子ビットの誤り(エラー)を検知し、本来の状態に訂正する技術。

量子コンピュータでこれを実現するには1量子ビットあたりに、誤り訂正機能を持った量子ビットが$10^4$個程度必要。これが実現されるのは数十年先(FTQC: Fault Torrelant Quantum Computer)。

現在のGoogleなどが開発済みの、ノイズを含む中規模量子デバイスのこと。誤り訂正機能がないため、限られた量子アルゴリズムしか実行できない。しかし、量子化学計算や機械学習といった領域で、現在の古典コンピュータを凌駕する性能を発揮すると予想されている。

量子回路を古典計算機でシミュレーションできなくなること。

実用的な問題で、量子コンピュータが優位になること。

1999年、当時NECにいた中村・葵らが世界初の量子ビットを超伝導物質で実現。
2014年、マルティネスがエラー訂正可能な精度で5量子ビットコンピュータを実現。

量子コンピュータを作る際にコヒーレンス時間が重要となる。

量子コンピュータのサイズ(量子ビット数)も重要。

量子コンピュータの量子ビット数の開発推移

操作精度も重要。

スケーラビリティ: 量子ビット数を増やす時に、配線とサイズが指数的に増大してはならない。
ユニバーサルな演算: 制御演算のリソースが指数的に増大してはならない。
訂正可能性: 初期化と測定を効率的に行い、エラーを訂正可能でなければならない。

量子コンピュータは指数的に多くのパターンを並列化して計算するから速い、は間違い

理由: 重ね合わせ状態を同時に計算することは可能だが、量子状態を測定すると一つの状態に収束する。
-> 欲しい状態を得る確率は指数的に低い
-> 欲しい状態を得るために指数的に多い回数試したら速くない

今のパソコンの制御信号はGHzに対して、超伝導量子ビットの量子コンピュータの制御パルスはMHz。誤り訂正を行うとさらに遅くなる(ただし光量子コンピュータはTHzオーダーの動作が期待される)。

量子アルゴリズム動物園: https://quantumalgorithmzoo.org/

グローバーのアルゴリズムは$\mathcal{O}(\sqrt{N})$より速くならないことが証明されている。膨大なデータでないとデータベース検索・最適化の優位性は低い。

量子コンピュータで速くなるアルゴリズムは、解くために制約がある。同じ制約を設ければ、古典コンピュータでも同じくらい速くなるのでは？(0量子ビットコンピュータアプリケーションとも呼ばれる)