量子コンピュータ （りょうしコンピュータ、英語：） は、量子力学的な重ね合わせを用いて並列性を実現するとされるコンピュータ。従来のコンピュータの論理ゲートに代えて、「量子ゲート」を用いて量子計算を行う原理のものについて研究がさかんであるが、他の方式についても研究・開発は行われている。従来のコンピュータ（以下「古典コンピュータ」）の基本素子は、情報量が0か1の何れかの値しか持ち得ない1ビットを扱うものであるのに対して、量子コンピュータでは量子ビット (qubit; quantum bit、キュービット) により、1キュービットにつき0と1の値を任意の割合で重ね合わせて保持する。n量子ビットあれば、formula_1の状態を同時に計算できる。もし、数千qubitのハードウェアが実現した場合、この量子ビットを複数利用して、量子コンピュータは古典コンピュータでは実現し得ない規模の並列コンピューティングが実現する。理論上、現在の最速スーパーコンピュータ（並列度がformula_2以下）で数千年かかっても解けないような計算でも、例えば数十秒といった短い時間でこなすことができる、とされている。古典コンピュータは一般に万能である。これに対し、提案されている量子コンピュータは現在のところ、いわゆる専用計算機であり、実用上は何らかの古典コンピュータに接続して使うものとなる。量子コンピュータの歴史は、1980年に Paul Benioff が量子系においてエネルギーを消費せず計算が行えることを示したことに端を発し、1982年、ファインマンも量子計算が古典計算に対し指数関数的に有効ではないかと推測している。これらに続き、1985年、ドイッチュは、「量子計算模型」と言えるを定義し、1989年にを考案した。1992年に、ドイッチュとは、量子コンピュータが古典コンピュータよりも速く解ける問題でを考案した。1993年に、と生徒のEthan Bernsteinは、とのアルゴリズムを考案した。1994年には、実用的なアルゴリズム『』を考案し、量子コンピュータの研究に火をつけた。これは、ヴァジラーニらの量子フーリエ変換や、同年のSimonの研究を基礎に置いている。量子コンピュータ特有のアルゴリズムであるショアのアルゴリズムが、古典コンピュータでは現実的な時間で解くことができない素因数分解を、極めて短い時間で実行出来ることから、素因数分解の困難性を利用したRSA暗号の安全性は実用的な量子コンピュータが実現されれば崩れることを示した。1995年に、やにより、量子誤り訂正のアルゴリズムが考案された。1996年に、により、その後、様々なアルゴリズムに応用されるグローバーのアルゴリズムが考案された。同年、セルジュ・アロシュは、実験的観測によって量子デコヒーレンスを証明し、量子デコヒーレンスが量子コンピュータ実現への障害となることが実証された。1997年に、Edward FarhiとSam Gutmannにより、量子ウォーク（、略称: CTQW）が考案された。1998年に、量子コンピュータ用のプログラミング言語である、QCL () の実装が公開された。また、1990年代には量子焼きなまし法も考案されている。ハードウェア開発に大きな進展があり、2008年にの専門家デービッド・ワインランドは、個々のイオンをレーザー冷却して捕捉することが出来ることを示し、個々の量子もつれ状態にあるイオンをマニピュレーションする、の研究が進展した。ショアのアルゴリズムは、2001年に核磁気共鳴により、2007年に量子光学により、2009年に光集積回路により15の素因数分解 (=3*5) が実装された。2011年に突如として、カナダの企業D-Wave Systemsが量子コンピュータ「D-Wave」の建造に成功したと発表した。D-Waveはこの記事の多くの部分で説明している量子ゲートによるコンピュータではなく、量子焼きなまし法による最適化計算に特化した専用計算機である。発表当初のものは128量子ビットであった。D-Waveが本当に量子コンピューティングを実現したものか否か、当初は疑う向きも多かったものの、確かに量子コンピューティングによるものとする調査論文が英科学誌ネイチャーに発表されるなど、2014年10月現在、確実視される方向にある。2012年、セルジュ・アロシュとデービッド・ワインランドがノーベル物理学賞を受賞した。受賞理由は「個別の量子系に対する計測および制御を可能にする画期的な実験的手法に関する業績」である。エドワード・スノーデンの開示文書によると、NSAにおいて暗号解読のための実用化が研究されているとされる。2014年9月米グーグル社はUCLAのと連携し量子コンピュータの独自開発を開始すると発表した。2015年2月　日立製作所が室温動作可能な新型半導体コンピュータを試作、2015年2月22日～26日まで、アメリカサンフランシスコで開催されるIEEEの半導体集積回路に関する国際会議「2015 International Solid-State Circuit Conference」で発表。2016年5月、IBMは５量子ビットの量子コンピュータをオンライン公開した。デイヴィビッド・コーリー ウォータールー大学教授がテストした結果、ほぼ同じ結果を得ることができた。量子コンピュータ特有のアルゴリズムがいくつか知られており、伝統的に有名なものを示す。他の物は、などを参照。（とも）とは、素因数分解問題を高速に（多項式時間で）解くことができるアルゴリズムのことである。古典コンピュータでは非現実的な時間（準指数時間）で解くアルゴリズムしか知られていない。1994年にによって発見された。ショアは本件で、ネヴァンリンナ賞とゲーデル賞を受賞した。2001年12月にIBMアルマデン研究所にて7qubitの量子コンピュータで15(＝3×5)の素因数分解に成功した（Nature,12月20日発行号）。少し改造することで離散対数問題（DLP,ElGamal暗号や楕円曲線暗号の安全性の根拠）も多項式時間で解くことができる。このアルゴリズムの基本的なアイデアを拡張したものが、可換隠れ部分群問題についての量子アルゴリズムである。現在は、これをさらに非可換隠れ部分群問題に拡張する研究が進展している。ショアのアルゴリズムは、量子コンピュータが離散フーリエ変換を高速に実行できることによる。また、アルゴリズム全体は確率的(BQP)であり、正しい答えが得られるまで、何度も試行する。N を因数分解するにあたり、a は N に対して素な数とし、a の mod N に関する位数、min{x|a=1 (mod N)} を求める。つまり、a の周期 r を求める。位数が高速に求められれば、因数分解は高速に行える。例えば, N = 15 , a = 7 とする。 7 = 7 (mod 15)7 = 4 (mod 15) 7 = 13 (mod 15) 7 = 1 (mod 15)7 = 7 (mod 15)7 = 4 (mod 15)7 = 13 (mod 15)7 = 1 (mod 15)7 = 7 (mod 15)7,4,13,1,7,4,13,1,7・・・という周期 4 の数列が生成される。よって,周期 r = min{x|7=1 (mod15)} = 4手順の概略は以下の2つ。formula_3個のデータの中から、ある特定のデータをformula_4ステップで取得することができるアルゴリズム。正確には、1～Nのある一つの値で、オラクル関数f(z)が1になり、それ以外はf(z) = 0となる、オラクル関数fにおいて、f(z) = 1となるzを求める問題。オラクル関数とは計算量が0の関数である。古典コンピュータではおよそformula_5ステップが必要である。1996年にが発表した。きわめて広範な種類の確率的アルゴリズムや量子アルゴリズムと組み合わせて、計算時間をその平方根まで落とすことができる。ショアのアルゴリズムほどその効果は劇的ではないが、広い応用をもつことが特徴である。検索条件や検索対象について改良されている。このアルゴリズムはデータ数に見合うだけ十分なqubit数があることを前提としているが、古典コンピュータにおいてデータに見合うだけの十分な並列度がある場合、f(z) = 1 を探すのはO(1)であり、関数の最小値を探す問題は、O(log log n) である。ランダムウォークを量子コンピュータ上で実行する。いくつかのアルゴリズムがこれを利用して作られている。振幅に対して離散フーリエ変換を行うが、振幅は直接は観測できないことに注意が必要。ショアのアルゴリズムで使われている。QCLでのソースコードは以下の通り。変数 q を離散フーリエ変換している。V は conditional phase、H はアダマール変換である。量子コンピュータ用のプログラミング言語とその処理系の実装方法が多数提案されており、QCLなどがある。詳細は、量子プログラミング言語 を参照。量子コンピュータのアルゴリズムをシミュレーションにより実行するためのシミュレーターが多数作られている。一覧については、を参照。ハードウェアは量子ゲートを組み合わせたによって実現されるが、数学的に等価な量子ゲートが物理的には核磁気共鳴、量子光学、量子ドット、超伝導素子、レーザー冷却などによって構成出来るため、様々な実験的ハードウェアの実現法が研究されている。近年、核磁気共鳴（NMR）や電子スピン共鳴を用いた量子コンピュータの研究開発が行われている。2001年、7量子ビット量子コンピュータによる素因数分解が実装された。核磁気共鳴 (NMR) により、1998年に2量子ビット、1999年に3量子ビット、2000年に5量子ビット、2001年に7量子ビット、2005年に8量子ビットqubit、2006年に12量子ビットが実現した。1量子ビット増えるごとに並列度は2倍になる。ちなみに、古典コンピュータでは、集積度（並列度）を2倍にするのに約18か月かかっていて、ムーアの法則と呼ばれる。国内では大阪大学や沖縄科学技術大学院大学が主な研究拠点であり、核スピン・電子スピンを用いた量子情報処理の実験が行われている。国内では横浜国立大、京大が主な研究拠点であり、窒素空孔欠陥を用いた量子メディア変換・量子情報処理の実験が行われている。また慶応義塾大学では、シリコン中の核スピンを用いた量子情報処理実験が行われている。国内では理化学研究所、東京大学が主な研究拠点であり、量子コンピュータの実現に向けた取り組みがなされている。特に光子を用いているものは光子コンピュータ、光量子コンピュータとも呼ばれる。2001年、非線形光学を使わずに、量子コンピュータを作成する方法が考案された。線形光量子コンピュータ (、LOQC) と呼ばれ、その後の光量子コンピュータの主流となる。2007年、光子を使い、4qubit量子コンピュータによる素因数分解が実装された。さらに、2009年、光集積回路（シリコンフォトニクス）上で、4qubit量子コンピュータによる素因数分解が実装された。超伝導素子を用いた量子コンピュータの量子ビットは、ジョセフソン・ジャンクションを用いた超伝導回路によって構成されている。超伝導回路中の電荷(クーパー対)の自由度を用いた量子ビットを、電荷量子ビット、またはクーパー対箱と呼ぶ。1999年、日本電気において中村、Pashkin、蔡らにより実現された。当時の量子ビットのコヒーレンス時間は約1ナノ秒であった。超伝導量子ビットはの研究とともに発展し、2004年にはコプラナ導波路により実装された超伝導共振器と電荷量子ビットとの強結合が観測されている。共振器や導波路を組み合わせた回路量子電磁力学は、超伝導量子ビット間の相互作用や、量子非破壊測定を行うとても良いツールとなっている。SQUIDを含み、磁束量子の重ね合わせ状態を用いた量子ビットをと呼ぶ。2003年、デルフト工科大においてChiorescu、中村、Harmans、Mooijらにより実現された。これらは社が開発した量子焼きなまし法による最適化手法に採用されている。2007年に電荷量子ビットにおける電荷揺らぎ雑音を回避する量子ビットが提案され、と呼ばれる。比較的シンプルな構成で長コヒーレンス時間が実現され、米国を中心に盛んに研究が進められている。2011年、量子計算や量子誤り訂正に必須となる単一試行のが実現し、トランズモン型超伝導量子ビットの量子跳躍が観測されている。これらの技術の背景には、標準量子限界に近い雑音指数を達成する低雑音増幅器(ジョセフソンパラメトリック増幅器)の実現がある2013年、上記の基礎技術とFPGAによる高速フィードバック処理により量子テレポーテーションの実験が行われ、空間的に離れた量子ビット間の状態転送が実現した。2014年には160マイクロ秒のコヒーレンス時間が実現し、1999年の発見から15年の間に約10万倍という飛躍的な改善がなされている。同年、Google社のJohn Martinisらのグループは、誤り耐性符号の一つであるの誤りしきい値を下回る、高い忠実度の基本量子ゲートを実現した。これにより誤り耐性量子計算が現実化し、超伝導量子ビットを用いた量子計算機の開発が一層加速することになる。2015年、9量子ビットによるを実行し、論理量子ビットのエラー確率を物理量子ビットに比べ約1/8まで小さくすることに成功した。同年には、新しい機能性材料の開発を飛躍的に加速する、フェルミ粒子のディジタル量子シミュレーションが、小さな系にて実装されている。大規模化に向けた取り組みが始まり、2016年には三次元集積技術による実装が議論されている。国内では東京大学と理化学研究所が量子コンピュータや量子情報処理の研究を、NTT物性科学基礎研究所、情報通信研究機構が量子物理の研究を行っており、主な研究拠点である。海外ではGoogle、IBM、デルフト工科大学（インテル・マイクロソフトが支援）、マサチューセッツ工科大学、チューリッヒ工科大学が主な研究拠点である。を用いる量子コンピュータでは、レーザー冷却によってイオンの捕捉とマニピュレーションを行なう。国内では阪大にて量子シミュレータ・量子コンピュータに向けた研究がなされている。古典コンピュータでの計算は、ブール論理にもとづいた論理ゲートによる論理演算をベースとして行われる。これに対し、量子コンピュータの量子回路では、量子演算の演算子に対応する演算を行うゲートは量子ゲートと呼ばれ、ユニタリー行列でなくてはならない。任意の1量子ビットに対するユニタリー行列は以下の形式で表現できる。可逆計算であることも特徴である。formula_61量子ビットに対する任意のユニタリー変換とCNOTゲートの組合せによって、n量子ビットの場合も任意のユニタリ変換を構成出来ることが知られている。NOTはパウリ行列の1つでもある。formula_7formula_8formula_9formula_10CNOTと呼ばれる。XORに相当する。formula_11formula_12formula_7formula_14formula_15formula_16formula_17formula_18formula_19はアダマール行列である。CPhaseと呼ばれる。formula_201量子ビットの場合は、以下の通り。formula_21formula_22formula_23ヴァジラーニらは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価であることを示した。したがって、古典チューリングマシンで原理的に解くことができない問題は量子チューリングマシンにも解くことはできない。量子コンピュータは容易に古典コンピュータをエミュレートすることが可能であるため、古典コンピュータで速く解ける問題は、量子コンピュータにも速く解くことができる。よって、量子コンピュータは古典コンピュータ「以上」に強力な計算速度を持つ。つまりは完全な上位互換である。ただし、「より大きい」計算速度を持つのかどうか（量子コンピュータにしか速く解けない問題が存在するのかどうか）は、P≠NP予想という、現在のところ証明されていない予想に依存する。ショアのアルゴリズムにより、NP問題（検算はすぐにできるが、解くのに時間がかかる問題）である素因数分解を素早く解くことができるため、例えば素因数分解問題が古典コンピュータに多項式時間で解けないということを示せば量子コンピュータは古典コンピュータより強力であることになる。

出典:wikipedia