量子コンピュータ

2022年時点でおよそ数十社が量子コンピュータ関連の開発競争に加わっており、主な企業としては、IBM (IBM Quantum)、Google Quantum AI、Microsoft、Intel、AWS Braket、Atos Quantumなどが挙げられる。

研究成果の年表については、英語版のen:Timeline_of_quantum_computing_and_communicationを参照のこと。

 

1959年、アメリカの物理学者リチャード・P・ファインマンが量子力学の仕組みを計算に持ち込み、1980年、アルゴンヌ国立研究所のポール・ベニオフ（英語版）により、理論上量子コンピュータ（チューリングマシン）を開発することは可能であるとした。2011年、カナダのD-Wave Systemsより、量子アニーリングを用いた世界初の商用量子コンピュータ 「D-Wave One」を発表。2019年、IBM Quantum社からは、量子ハードウェア「IBM Q System One」を発表。数千人の開発者がそれを利用できる状態になっている。IBM Quantumは量子プロセッサを定期的に配布している。

量子計算を「量子ゲート」を用いて行う方式のものについての研究がいまは最もさかんであるが、他の方式についても研究・開発は行われている。

いわゆる電気回路による従来の通常の2値方式のデジタルコンピュータ（以下「古典コンピュータ」）の素子は、情報について、なんらかの手段により「0か1」のような排他的な2値のいずれかの状態だけを持つ「ビット」（古典ビット）により扱う。それに対して量子コンピュータは、「量子ビット」 (英: qubit; quantum bit、キュービット) により、量子状態の重ね合わせ（量子波動関数）によって情報を扱う。ここで言う重ね合わせとは「0,1,重なった値」という第三の値と言う意味ではなく、両方の値を一定の確率で持っており、観測時にどちらかに確定すると言うものである。

n量子ビットがあれば${\displaystyle 2^{n}}$ の状態を同時に計算し、${\displaystyle 2^{n}}$ 個の重ね合わされた結果を得ることができる。しかし、重ね合わされた結果を観測しても確率に従ってランダムに選ばれた結果が1つ得られるだけであり、古典コンピュータに対する高速性は得られない。高速性を得るためには欲しい答えを高確率で求める工夫を施した量子コンピュータ用のアルゴリズムが必須である。もしも数千量子ビットのハードウェアが実現したならば、この量子ビットの重ね合わせ状態を利用することで、量子コンピュータは古典コンピュータでは到底実現し得ない規模の並列コンピューティング（計算速度の量子超越性）を実現すると言われている。

量子コンピュータの能力については、理論上の話（予測や予測に関する議論）と、製作中の量子プロセッサの製作者が考えている予定値と、すでに製作された現実の機械についての実測値がある。実現した値については、やはり上述の英語版の年表が詳しい。（当記事の後半の#計算能力や#実際の節は、内容が更新がされておらず、かなり古い内容なので、あまり参考にはならない。）

将来に量子コンピュータの販売が行われるようになれば、初期の発展段階で量子コンピュータの重要な特許を多く取得した会社が莫大な収益や利益をあげると予想され、後手にまわった側は、特許を保有する側に対して膨大な特許実施使用料を支払う立場になったり、競争に負けて会社が衰退してしまう可能性もある。そのため2022年の時点では上で説明した数社だけではなくて、ほかにもあわせて数十社ほどが量子コンピュータ関連の開発を競い合っている。

なお単なるコンピュータの利用者になるだけのつもりの人にとっての「目先の利用価値」について言えば、2022年の時点ではスーパーコンピュータや普通のPCの方が利用価値が高いといえる（量子コンピュータが実用的な問題の処理に本格的に使えるようになるまでには「もうしばらく」時間がかかると考えられている）。

1980年代

量子コンピュータの歴史は、1980年に ポール・ベニオフ（英語版） が量子系においてエネルギーを消費せず計算が行えることを示したことに端を発し、1982年、ファインマンも量子計算が古典計算に対し指数関数的に有効ではないかと推測している。これらに続き、1985年、ドイッチュは、「量子計算模型」と言える量子チューリングマシン（英語版）を定義し、1989年に量子回路を考案した。

1990年代

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

1994年にピーター・ショアは、実用的なアルゴリズム『ショアのアルゴリズム（英語版）』を考案し、量子コンピュータの研究に火をつけた。これは、ヴァジラーニらの量子フーリエ変換や、同年のSimonの研究を基礎に置いている。古典コンピュータでは現実的な時間では解けないと考えられている素因数分解は、量子コンピュータに特有であるこのショアのアルゴリズムでは理論上極めて短時間で解けることになるので、素因数分解の困難さを暗号の安全性の根拠としているRSA暗号は，もしも実用的な量子コンピュータが実現されたならば容易に破られることを示した。

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

また西森秀稔による、量子焼きなまし法（量子アニーリング法）の提案もこの時代であった。

2000年代

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

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

2010年代

2011年に突如として、カナダの企業D-Wave Systemsが量子コンピュータ「D-Wave」の建造に成功したと発表した。D-Waveはこの記事の多くの部分で説明している量子ゲートによるコンピュータではなく、量子焼きなまし法による最適化計算に特化した専用計算機である。発表当初のものは128量子ビットであった。D-Waveが本当に量子コンピューティングを実現したものか否か、当初は疑う向きも多かったものの、確かに量子コンピューティングによるものとする調査論文が英科学誌ネイチャーに発表され、グーグルを筆頭とするベンチャー企業がD-Waveと協業を開始するなど、2018年1月現在、確実視されて来ている。

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

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

2014年9月米グーグル社はUCSBのJohn Martinisと連携し量子コンピュータの独自開発を開始すると発表した。

2016年5月、IBMは5量子ビットの量子コンピュータをオンライン公開した。デイヴィビッド・コーリー ウォータールー大学教授がテストした結果、ほぼ同じ結果を得ることができた。 2017年5月、IBMは同社の汎用量子コンピュータシステムであるIBM Q向け16量子ビット・プロセッサを開発したとアナウンスした

2019年1月8日、IBMはCESにおいて世界初の商用量子コンピューター（名称：IBM Q System One）を開発したと発表した。

2019年10月23日、グーグルは世界最高速のスーパーコンピューターが1万年かかる計算問題を量子コンピューターSycamoreプロセッサは3分20秒で解くことに成功して量子超越性を世界で初めて実証したと発表し、CEOのサンダー・ピチャイは地球から最初に飛び立った宇宙ロケットに匹敵する成果と述べた。

2020年代

• 2020年12月3日（米国時間）、中国の潘建偉が率いる量子研究グループが、独自の量子コンピュータ九章にて量子超越性を達成したことを『サイエンス』誌で発表した。
• 2021年11月16日 - 東京大学大学院工学系研究科の武田俊太郎准教授と榎本雄太郎助教らの研究チームが、光量子ビットスライサの開発成功を発表した。
• 2021年12月22日 – NTTや東京大学、理化学研究所などの共同研究で、光子を利用する光量子コンピュータの基幹技術となる「スクィーズド光源」と呼ばれる量子光源を世界で初めて開発したと発表した。実用化すれば従来の量子コンピュータに必要だった大規模な冷却システムが不要となる。

• 2023年3月27日 - 理化学研究所（理研）は、国産の初号機を開発し、研究者が利用できるサービスを3月27日から始めた。開発は、量子コンピューター研究における日本の第一人者で理化学研究所センター長の中村泰信、および国内企業などからなる研究グループである。理研は、初号機の公開が改善や性能の向上につながると期待している。

理化学研究所センター長、中村泰信の談話
中村は開発の意義について「大規模な量子コンピューターの実現はチャレンジングな課題で、世界的に見てもまだまだハードルが高い技術だ。開発は長いレースになるので、われわれが技術的に貢献する余地は十分ある」と話している。
理化学研究所の初号機は3月27日から本格稼働し、当面は、共同で研究する契約を結んだ大学や企業の研究者に利用してもらい、さらなる改良や関連するソフトウエア開発などを加速させたい考えである。
ただし、公開後もすぐに実用化できるわけではなく、量子ビットは不安定で、計算中に誤りを起こしてしまうため、誤りを自ら訂正するには膨大な量子ビットが必要で、実用化の大きな課題となっている。

アルゴリズム

量子コンピュータ特有のアルゴリズムがいくつか知られており、伝統的に有名なものを示す。他の物は、Quantum Algorithm Zooなどを参照。

ショアのアルゴリズム

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

2001年12月にIBMアルマデン研究所にて7量子ビットの量子コンピュータで15 (= 3×5) の素因数分解に成功した（Nature, 12月20日発行号）。

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

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

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

例えば、N = 15, a = 7 とする。

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 (mod 15)
7⁷ = 13 (mod 15)
7⁸ = 1 (mod 15)
7⁹ = 7 (mod 15)
⋮

1,7,4,13,1,7,4,13,1,7,…という周期 4 の数列が生成される。

よって、周期 r = min{x > 0|7^x = 1 (mod 15)} = 4

手順の概略は以下の2つである。

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

グローバーのアルゴリズム

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

このアルゴリズムはデータ数に見合うだけ十分な量子ビット数があることを前提としているが、古典コンピュータにおいてデータに見合うだけの十分な並列度がある場合、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などがある。詳細は、量子プログラミング言語 を参照。

シミュレーター

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

ハードウェアは、数学的に等価な量子ゲートが物理的に核磁気共鳴、量子光学、量子ドット、超伝導素子、レーザー冷却などによって構成できるため、様々な実験的ハードウェアの実現法が研究されている。

核磁気共鳴・電子スピン共鳴

近年、核磁気共鳴（NMR）や電子スピン共鳴を用いた量子コンピュータの研究開発が行われている。

2001年、7量子ビット量子コンピュータによる素因数分解が実装された。核磁気共鳴 (NMR) により、1998年に2量子ビット、1999年に3量子ビット、2000年に5量子ビット、2001年に7量子ビット、2005年に8量子ビット、2006年に12量子ビットが実現した。1量子ビット増えるごとに並列度は2倍になる。

国内では大阪大学や沖縄科学技術大学院大学が主な研究拠点であり、核スピン・電子スピンを用いた量子情報処理の実験が行われている。

窒素空孔欠陥スピン・シリコン核スピン

国内では横浜国立大学、京都大学が主な研究拠点であり、窒素空孔欠陥を用いた量子メディア変換・量子情報処理の実験が行われている。また慶応義塾大学 では、シリコン中の核スピンを用いた量子情報処理実験が行われている。

量子ドット

国内では理化学研究所、東京大学が主な研究拠点であり、量子コンピュータの実現に向けた取り組みがなされている。

量子光学

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

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

2017年9月、東京大学 工学系研究科の古澤明教授と武田俊太郎助教のグループは、大規模光量子コンピュータ実現法を発明と告知。

2020年に中国の九章が光子を用いたコンピュータでの量子実現性を世界で初めて実現して世界中で話題となった。

国内の主な研究拠点には東京大学や東京理科大学が挙げられる。

超伝導素子

超伝導素子を用いた量子コンピュータの量子ビットは、ジョセフソン・ジャンクションを用いた超伝導回路によって構成されている。超伝導回路中の電荷(クーパー対)の自由度を用いた量子ビットを、電荷量子ビット、またはクーパー対箱と呼ぶ。1999年、日本電気において中村、Pashkin、蔡らにより実現された。当時の量子ビットのコヒーレンス時間は約1ナノ秒であった。 超伝導量子ビットは回路量子電磁力学（英語版）の研究とともに発展し、2004年にはコプレーナ導波路により実装された超伝導共振器と電荷量子ビットとの強結合が観測されている。共振器や導波路を組み合わせた回路量子電磁力学は、超伝導量子ビット間の相互作用や、量子非破壊測定を行うとても良いツールとなっている。

SQUIDを含み、磁束量子の重ね合わせ状態を用いた量子ビットを磁束量子ビット（英語版）と呼ぶ。2003年、デルフト工科大においてChiorescu、中村、Harmans、Mooijらにより実現された。これらはDWAVE社が開発した量子焼きなまし法による最適化手法に採用されている。

2007年に電荷量子ビットにおける電荷揺らぎ雑音を回避する量子ビットが提案され、トランズモン型量子ビット（英語版）と呼ばれる。比較的シンプルな構成で長コヒーレンス時間が実現され、米国を中心に盛んに研究が進められている。 2011年、量子計算や量子誤り訂正に必須となる単一試行の量子非破壊測定（英語版）が実現し、トランズモン型超伝導量子ビットの量子跳躍が観測されている。これらの技術の背景には、標準量子限界に近い雑音指数を達成する低雑音増幅器(ジョセフソンパラメトリック増幅器)の実現がある。 2013年、上記の基礎技術とFPGAによる高速フィードバック処理により量子テレポーテーションの実験が行われ、空間的に離れた量子ビット間の状態転送が実現した。 2014年には160マイクロ秒のコヒーレンス時間が実現し、1999年の発見から15年の間に約10万倍という飛躍的な改善がなされている。 同年、Google社のJohn Martinisらのグループは、誤り耐性符号の一つである表面符号（英語版）の誤りしきい値を下回る、高い忠実度の基本量子ゲートを実現した。これにより誤り耐性量子計算が現実化し、超伝導量子ビットを用いた量子計算機の開発が一層加速することになる。2015年、9量子ビットによるビット反転エラー訂正（英語版）を実行し、論理量子ビットのエラー確率を物理量子ビットに比べ約1/8まで小さくすることに成功した。同年には、新しい機能性材料の開発を飛躍的に加速する、フェルミ粒子のディジタル量子シミュレーションが、小さな系にて実装されている。大規模化に向けた取り組みが始まり、2016年には三次元集積技術による実装が議論されている。

国内では東京大学と理化学研究所が量子コンピュータや量子情報処理の研究を、NTT物性科学基礎研究所、情報通信研究機構が量子物理の研究を行っており、主な研究拠点である。

海外ではGoogle、IBM、デルフト工科大学（インテル・マイクロソフトが支援）、マサチューセッツ工科大学、チューリッヒ工科大学が主な研究拠点である。

イオントラップ

イオントラップを用いる量子コンピュータでは、レーザー冷却によってイオンの捕捉とマニピュレーションを行なう。 国内では阪大にて量子シミュレータ・量子コンピュータに向けた研究がなされている。

その他

量子コンピュータによる量子アルゴリズムを記述する方法の一つである。N量子ビットを用いるアルゴリズムの場合、N本の線を書き、その量子ビットに対する量子操作(初期値設定、量子演算、測定)を時系列で左から右に記述した図である。

一般的には、左端に「初期値設定」、右端で明示的あるいは暗黙的に量子ビットの情報を読み出す「測定」が行なわれる。「測定」の結果得られる値は0または1で、「測定」した瞬間に量子重ね合わせ状態は破壊され、以降は読みだされた単純な0または1の状態になる。

古典的論理回路との意味の違い

量子コンピュータが量子回路で構成されていると思われがちだが、実際は違う。量子ゲートは、無調整で動作する論理ゲートと異なり、動作中に常時、制御と調整が必要であるため、個々の量子ゲートに対して量子チップ外からの制御線を必要とする。このため、機能の定まった複数の量子ゲートを縦続接続するには、量子チップとそれを制御するための外部回路との間に、多数の制御信号が必要となり実装困難である。

実際に作られたIBMやGoogleのチップでは、近接する量子ビット間を、パラメーターで様々なゲート機能を実現できる少数のゲートで接続し、アルゴリズムの実行に伴ってパラメーターを変化させることで、量子回路で表現されたアルゴリズムを実現している。このように、量子回路は量子アルゴリズムを記述するためのもので、ハードウェア構造と密接に関連する、論理回路とは位置づけが異なる。

量子ゲート

古典コンピュータでの計算は、ブール論理にもとづいた論理ゲートによる論理演算をベースとして行われる。これに対し、量子コンピュータの量子回路では、量子演算の演算子に対応する演算を行う機能は量子ゲートと呼ばれ、ユニタリー行列で記述できる。任意の1量子ビットに対するユニタリー行列は以下の形式で表現される。可逆計算であることも特徴である。この式を見ると分かる通り、量子ゲートは本質的にアナログ信号処理であり、アナログ処理に伴う誤差が問題となる点が論理演算とは異なる。このことが量子コンピュータ実現上の最大の問題である。

${\displaystyle 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つでもある。

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

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

スワップ

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

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

制御NOT

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

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

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

パウリ行列

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

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

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

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

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

アダマール変換

${\displaystyle H={\frac {1}{\sqrt {2}}}(X+Z)={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}={\frac {1}{\sqrt {2}}}H_{2}}$ 

${\displaystyle H_{2}}$ はアダマール行列である。

Conditional Phase

CPhaseと呼ばれる。

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

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

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

回転

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

トフォリゲート

${\displaystyle T|x\rangle |y\rangle |z\rangle =|x\rangle |y\rangle |z\oplus (x\land y)\rangle }$ 

フレドキンゲート

理論

ヴァジラーニらは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価であることを示した。したがって、計算可能性の点では既存のあらゆるコンピュータと量子チューリングマシンは変わらない。つまり、量子チューリングマシンで「計算可能」な問題は古典チューリングマシンでも「計算可能」であるし、古典チューリングマシンで「計算可能」でない問題は量子チューリングマシンでも「計算可能」でない。（なお、ここで「計算可能」というのは、計算理論の専門用語であって、「原理的に解くことができない」というような表現から一般の人がイメージするような素朴な印象はおそらくたいていは正確ではない）（単に計算可能という場合には、計算が有限の時間で終了して答えが得られるという意味である。その時間の長さが現実的かどうかについては問われない。）

計算可能性の理論に関しては以上のようであるのだが、では、計算複雑性の理論としてはどうだろうか、というのが関心のある所であろう。

 

量子コンピュータは容易に古典コンピュータをエミュレートすることが可能であるため、古典コンピュータで速く解ける問題（汎用問題）は、量子コンピュータでも同程度以上に速く解くことができる。よって汎用問題について、量子コンピュータは古典コンピュータ「以上」に強力な計算速度を持つ。ただし、同程度は可能だとしても、「より大きい」かどうかはよくわかっていない。

量子コンピュータに関係する複雑性クラスにBQPがありBQPはPを包含する。BQPとNPの関係は明確ではないが、BQPとNPは包含関係にないだろうと考えられている。

実際

Googleは量子ゲートマシンの高速性が2017年末までに実証されると予想した。古典コンピューターよりも実際の量子ゲートマシンの方が高速に解ける問題が存在することを、量子超越性と呼び、このような問題の探索が続けられている。2019年10月23日、Googleは、ランダムに作った量子回路の出力結果を推定すると言う問題で、量子超越性を実証したと発表した。

量子ゲートマシン上で素因数分解を行うショアのアルゴリズムは、2001年にIBMが世界で初めて15(=3×5)の分解に成功した。2012年にブリストル大学が21(=3×7)の素因数分解を行い記録を更新したが、21を超える数の素因数分解に成功したという報告はない(2019年9月時点)。

量子コンピュータとしては、量子ゲート型以外に、D-Waveなどの量子アニーリングやその他いくつかのタイプが提案されている、量子イジングマシンはQUBO(制約のない二値二次式の最適化)(英語版)に特化した専用計算機と言える。

注釈

出典

• 量子ビット
• 量子状態
• 量子もつれ
• 量子テレポーテーション
• フォールトトレラント量子計算
• アインシュタイン＝ポドルスキー＝ローゼンのパラドックス
• 量子暗号
• 量子アニーリング
• Qiskit

以下のリストは量子計算機やその数理について書かれた書籍を発行年代順に並べた。もちろん完全なものではない。

• 西野哲朗:「量子コンピュータ入門」、東京電機大学出版局、ISBN 978-4501526504（1997年3月10日）。
• 大矢雅則:「量子コンピュータの数理」、丸善、ISBN 978-4621046074 (1999年5月31日)。
• 上坂吉則:「量子コンピュータの基礎数理」、コロナ社、ISBN 978-4339023763（2000年5月26日）。
• C.P.ウィリアムズ、S.H.クリアウォータ（共著）、西野哲朗、荒井隆、渡邊昇（共訳）：「量子コンピューティング：量子コンピュータの実現へ向けて」、シュプリンガー・フェアラーク東京、ISBN 978-4431708698（2000年6月14日）。
• 西野哲朗：「量子コンピュータと量子暗号」、岩波講座 物理の世界 物理と情報（第4巻）、岩波書店、ISBN 978-4000111591（2002年3月15日）。※2022年11月10日にオンデマンド版が発行（ISBN 978-4007312595）。
• 広田修:「量子情報科学の基礎：量子コンピュータへのアプローチ」、森北出版、ISBN 978-4627827417 (2002年4月15日)。
• A.Yu.Kitaev、A.H.Shen、M.N.Vyalyi： "Classical and Quantum Computation"、American Mathematical Society、ISBN 978-0821832295（2002年7月1日）。
• ゲナディ P.ベルマン、ロンニエ マイニエリ:「入門量子コンピュータ」、パーソナルメディア、ISBN 978-4893621924 (2002年9月)。
• 西野哲朗：「量子コンピュータの理論：量子コンピューティング入門」、培風館、ISBN 978-4563015510 (2002年12月12日)。
• G.ミルバーン、林一 (訳)：「ファインマン・プロセッサ：夢の量子コンピュータ」、岩波書店、ISBN 978-4000059497（2003年1月29日）。
• Jozef Gruska（著）、伊藤正美、今井克暢、岩本宙造、外山政文、森田憲一（共訳）:「量子コンピューティング」、森北出版、ISBN 978-4627827912（2003年11月19日）。
• Michael A.Nielsen、Issac L.Chuang(共著)、木村達也（訳）：「量子コンピュータと量子通信（I）」、オーム社、ISBN 4-274-20007-8（2004年12月20日）。※全3巻
• 石井 茂:「量子コンピュータへの誘(いざな)い：きまぐれな量子でなぜ計算できるのか」、日経BP社、ISBN 978-4822282110（2004年12月23日）。
• Michael A.Nielsen、Issac L.Chuang(共著)、木村達也（訳）：「量子コンピュータと量子通信（II）」、オーム社、ISBN 4-274-20008-6（2005年1月10日）。※全3巻
• Michael A.Nielsen、Issac L.Chuang(共著)、木村達也（訳）：「量子コンピュータと量子通信（III）」、オーム社、ISBN 4-274-20009-4（2005年1月10日）。※全3巻
• 竹内繁樹:「量子コンピュータ：超並列計算のからくり」講談社 (ブルーバックス)、ISBN 978-4062574693（2005年2月20日）。
• 古澤明:「量子光学と量子情報科学」、数理工学社、ISBN 4-901683-23-3（2005年4月10日）。
• D.Bouwmeester、A.Ekert、A.Zeilinger(編):「量子情報の物理：量子暗号、量子テレポーテーション、量子計算」、共立出版、ISBN 978-4-320-03431-0 (2007年5月25日)。
• 西野哲朗:「（図解雑学）量子コンピュータ」、ナツメ社、ISBN 978-4816341311 (2007年7月18日)。
• N. David Mermin："Quantum Computer Science: An Introduction"、Cambridge University Press、ISBN 978-0521876582 (2007年8月30日）。
• 宮野健次郎、古澤明:「量子コンピュータ入門」、日本評論社、ISBN 978-4535784796 (2008年3月25日)。
• Noson S. Yanofsky、Mirco A. Mannucci："Quantum Computing for Computer Scientists"、Cambridge University Press、ISBN 978-0521879965 (2008年8月11日）。
• G.ベネンティ、G.ガザーティ、G.ストゥリーニ、廣岡一 (訳):「量子計算と量子情報の原理」、シュプリンガージャパン、ISBN 978-4431100096 (2009年5月)。
• N.D.マーミン、木村元(訳):「マーミン 量子コンピュータ科学の基礎」、丸善、ISBN 978-4621081464（2009年7月30日）。
• ジョージ・ジョンソン:「量子コンピュータとは何か」、早川書房（ハヤカワ文庫NF―数理を愉しむシリーズ）、ISBN 978-4150503611 (2009年12月9日)。
• 赤間世紀:「量子コンピュータがわかる本」、工学社、ISBN 978-4777515141 (2010年4月1日)。
• Michael A. Nielsen、Isaac L. Chuang： "Quantum Computation and Quantum Information: 10th Anniversary Edition"、Cambridge University Press、ISBN 978-1107002173（2010年12月9日）。
• Colin P. Williams: "Explorations in Quantum Computing"（2nd Ed.）, Springer、ISBN 978-1846288869 (2010年12月27日)。
• Willi-Hans Steeb、Yorick Hardy: "Problems and Solutions in Quantum Computing and Quantum Information"(3rd Ed.), World Scientific Pub、ISBN 978-9814366328 (2011年9月16日)。
• Jiannis K. Pachos: "Introduction to Topological Quantum Computation"、Cambridge Univ. Press,ISBN 978-1107005044（2012年4月12日）。
• G.ベネンティ、G.ガザーティ、G.ストゥリーニ、廣岡一 (訳)：「量子計算と量子情報の原理」、丸善出版、ISBN 978-4621062272（2012年6月5日）。※2009年5月にシュプリンガージャパンから出た本の再刊行。
• 石坂智、小川朋宏、河内亮周、木村元、林正人:「量子情報科学入門」、共立出版、ISBN 978-4320122994 (2012年6月10日)。
• ジョン・グリビン、松浦俊輔 (訳):「シュレーディンガーの猫、量子コンピュータになる。」、青土社、ISBN 978-4791767717 (2014年3月20日)。
• 情報処理学会（編）: 情報処理2014年7月号別刷「《特集》量子コンピュータ」、情報処理学会、ISBN 978-4907626013（2014年6月15日）。
• Eleanor G. Rieffel、Wolfgang H. Polak: "Quantum Computing: A Gentle Introduction"、MIT Press、ISBN 978-0262526678（2014年8月29日）。
• 中山茂:「量子アルゴリズム」、技報堂出版、ISBN 978-4765533430 (2014年10月1日)。
• Richard J. Lipton、Kenneth W. Regan: "Quantum Algorithms via Linear Algebra: A Primer"、MIT Press、ISBN 978-0262028394（2014年12月5日）。
• 竹内薫:「量子コンピューターが本当にすごい」、PHP研究所、ISBN 978-4569824987（2015年5月16日）。
• 西野哲朗、岡本 龍明、三原孝志:「量子計算」（ナチュラルコンピューティング・シリーズ第6巻）、近代科学社、ISBN 978-4764904866 (2015年10月31日)。
• 西野友年:「今度こそわかる量子コンピューター」、講談社、ISBN 978-4061566057（2015年10月23日）。
• Keisuke Fujii: "Quantum Computation with Topological Codes: From Qubit to Topological Fault-Tolerance", Springer、ISBN 978-9812879950（2016年1月13日）。
• 宮野健次郎、古澤明:「量子コンピュータ入門」(第2版)、日本評論社、ISBN 978-4535788053（2016年3月3日）。
• 中山茂:「クラウド量子計算入門：IBMの量子シミュレーションと量子コンピュータ」、カットシステム、ISBN 978-4877834081(2016年9月1日)。
• Tudor D. Stanescu: "Introduction to Topological Quantum Matter & Quantum Computation"、CRC Press、ISBN 978-1482245936 (2016年12月7日)。
• 西森秀稔、大関真之:「量子コンピュータが人工知能を加速する」、日経BP社、ISBN 978-4822251895（2016年12月9日）。
• 小柴健史、藤井啓祐、森前智行:「観測に基づく量子計算」、コロナ社、ISBN 978-4339028706(2017年3月10日)。
• 富田章久:「量子情報工学」、森北出版、ISBN 978-4627853812 （2017年3月3日）。
• Mingsheng Ying、川辺治之（訳）:「量子プログラミングの基礎」、共立出版、ISBN 978-4320124059（2017年3月31日）。
• 森前智行:「量子計算理論：量子コンピュータの原理」、森北出版、ISBN 978-4627854017（2017年11月13日）。
• 中山茂:「クラウド量子計算：量子アセンブラ入門」、NextPublishing Authors Press、オンデマンド印刷本 (2018年1月15日)。
• 中山茂：「Python クラウド量子計算 QISKITバイブル」、オンデマンド自主出版（2018年5月3日）。
• 西森秀稔、大関 真之：「量子アニーリングの基礎」、共立出版、ISBN 978-4320035386（2018年5月19日）。
• 中山茂：「Python量子プログラミング入門」、オンデマンド自主出版（2018年6月25日）。
• 長橋賢吾：「図解入門 よくわかる 最新 量子コンピュータの基本と仕組み」、秀和システム、ISBN 978-4798054551（2018年9月26日）。
• 中山茂：「Python量子プログラミング入門2」、オンデマンド自主出版（2018年10月28日）。
• 「量子コンピュータ／イジング型コンピュータ研究開発最前線」、株式会社情報機構、ISBN 978-4-86502-165-3 (2019年2月）。
• 古澤明：「光の量子コンピューター」、集英社インターナショナル (インターナショナル新書)、ISBN 978-4797680355（2019年2月7日）。
• 中山茂：「Qiskit 量子プログラミング入門」、オンデマンド自主出版（2019年2月8日）。
• 湊雄一郎：「いちばんやさしい量子コンピューターの教本」、インプレス、ISBN 978-4295006077（2019年5月20日）。
• 宇津木健、徳永裕己 (監修)：「絵で見てわかる量子コンピュータの仕組み」、翔泳社、ISBN 978-4798157467 （2019年7月10日）。
• 高木剛：「暗号と量子コンピュータ: 耐量子計算機暗号入門」、オーム社、ISBN 978-4274224102（2019年8月25日）
• Emily Grumbling and Mark Horowitz(Eds):"Quantum Computing: Progress and Prospects (2019)", The National Academies Press, Washington, DC, ISBN 978-0-309-47969-1 (Sep, 4th, 2019).
• Jack D. Hidary:"Quantum Computing: An Applied Approach"、Springer、ISBN 978-3030239213 (2019年9月20日)。
• 佐川弘幸、吉田宣章：「量子情報理論 第3版」、丸善出版、ISBN 978-4621304167（2019年10月30日）。
• 藤井啓祐：「驚異の量子コンピュータ: 宇宙最強マシンへの挑戦」、岩波書店 (岩波科学ライブラリー)、ISBN 978-4000296892（2019年11月20日）。
• Emily Grumbling ・Mark Horowitz 編:「米国科学・工学・医学アカデミーによる量子コンピュータの進歩と展望」、共立出版、ISBN 978-4-320-12455-4 (2020年1月14日).
• Chris Bernhardt、湊雄一郎 (監訳), 中田真秀 (監訳) ：「みんなの量子コンピュータ」、翔泳社、ISBN 978-4798163574（2020年1月24日）。
• 武田俊太郎：「量子コンピュータが本当にわかる! ― 第一線開発者がやさしく明かすしくみと可能性」、技術評論社、ISBN 978-4297111359（2020年2月19日）。
• 遠藤理平：「14日で作る量子コンピュータ：シュレディンガー方程式で量子ビット・量子ゲート・量子もつれを数値シミュレーション Python版」、カットシステム、ISBN 978-4877834715（2020年5月1日）。
• 小林雅一：「ゼロからわかる量子コンピュータ」、講談社現代新書、ISBN 978-4065282991（2022年6月15日）。
• 縫田光司：「耐量子計算機暗号」、森北出版、ISBN 978-4627872110 (2020年8月6日）。
• Eric R. Johnston, Nic Harrigan, Mercedes Gimeno-Segovia：「動かして学ぶ量子コンピュータプログラミング」、オライリージャパン、ISBN 978-4873119199 （2020年8月27日）。
• Maria Schuld、Francesco Petruccione、大関 真之 (監訳)：「量子コンピュータによる機械学習」、共立出版、ISBN 978-4320124622（2020年8月28日）。
• 嶋田義皓：「量子コンピューティング 基本アルゴリズムから量子機械学習まで」、オーム社、ISBN 978-4-274-22621-2（2020年11月9日）。
• 杉﨑研司：「量子コンピュータによる量子化学計算入門」、講談社、ISBN 978-4065218273（2020年12月7日）。
• 湊雄一郎, 加藤拓己, 比嘉恵一朗, 永井隆太郎：「IBM Quantumで学ぶ量子コンピュータ」、秀和システム、ISBN 978-4798062808 （2021年3月6日）。
• Sarah C. Kaiser, Christopher Granade：”Learn Quantum Computing with Python and Q#: A hands-on approach”、Manning、ISBN 978-1617296130（2021年6月22日）。
• Johnny Hooyberghs：”Introducing Microsoft Quantum Computing for Developers: Using the Quantum Development Kit and Q#”、Apress、ISBN 978-1484272459 (2021年12月10日)。
• Filip Wojcieszyn:"Introduction to Quantum Computing with Q# and QDK"、Springer、ISBN 978-3030993788（2022年5月7日）。
• Mariia Mykhailova:"Q# Guide: Instant Help for Q# Developers"、Oreilly、ISBN 978-1098108861（2022年7月19日）。
• S. C. Kaiser, C. Granade, 黒川 利明 (訳):「PythonとQ#で学ぶ量子コンピューティング」、朝倉書店、ISBN 978-4254122688 (2022年9月6日)。
• 西村治道:「基礎から学ぶ 量子計算：アルゴリズムと計算量理論」、オーム社、ISBN 978-4-274-22969-5（2022年11月18日）。
• 束野仁政：「量子コンピュータの頭の中――計算しながら理解する量子アルゴリズムの世界」、技術評論社、ISBN 978-4297135119（2023年6月19日）。
• 工藤 和恵：「基礎から学ぶ 量子コンピューティング: イジングマシンのしくみを中心に」、オーム社、ISBN 978-4274230509（2023年6月23日)。
• Yongshan Ding、Frederic T. Chong： 「量子コンピュータシステム: ノイズあり量子デバイスの研究開発」、オーム社、ISBN 978-4274230660（2023年7月3日）。

• Quantum Computing Information Site
• みんなの量子コンピューター～情報・数理・電子工学と拓く新しい量子アプリ～（戦略プロポーザル「みんなの量子コンピュータ」, 科学技術振興機構の研究開発戦略センター, 2018年12月1日. ）
• ACM Transactions on Quantum Computing (TQC)
• IEEE Quantum
• 一般社団法人情報処理学会の「量子ソフトウェア研究会」
• PennyLane , PennyLane Documentation
• 「量子計算機で産学連合　東大・みずほ・日立など協議会　ソフト開発に活路」（日本経済新聞記事2020年7月30日）。
• 分かる 教えたくなる 量子コンピューター (日本経済新聞解説記事：2020年06月24日 公開 2021年07月05日 更新)
• 『量子コンピュータ』 - コトバンク
• 「富士通が考える、量子コンピューティングの今後」（PC Watch 2022年6月1日記事）
• 世界初「ポータブル量子コンピュータ」が発売。2量子ビットで118万8,000円より（PC Watch 2022年12月15日記事）
• Bao Yan et al.:"Factoring integers with sublinear resources on a superconducting quantum processor", arXiv:2212.12372v1 (quant-ph, 23 Dec, 2022).
• グーグルがエラー訂正で成果、量子計算機の実用化に「大きな一歩」(朝日新聞2023年3月6日記事)
• 超高速量子計算のための世界最速４３ギガヘルツ リアルタイム量子信号測定に成功（ＪＳＴ，2023年3月6日）
• 「量子コンピュータって何？今はどこまで開発が進んでいる？話題を総まとめ」（PC Watch 2023年3月20日記事）
• 国産量子コンピューター初号機、２７日に利用開始 (読売新聞2023年3月24日記事)
• 東大とIBM、127量子ビット「IBM Quantum System One with Eagleプロセッサー」を秋に稼働開始（PC Watch 2023年4月21日記事）
• 「国産量子コンピューター初号機　大規模集積化に照準」(日経新聞2023年4月24日記事）　※日経サイエンス2023年6月号掲載記事の要約。
• Torsten Hoefler, Thomas Häner, Matthias Troyer: "Disentangling Hype from Practicality: On Realistically Achieving Quantum Advantage", Communications of the ACM, Vol.66, No.5 (May 2023), pp.82-87. DOI:10.1145/3571725
• ループ型光量子コンピューターの試作機できました　課題は精度の向上 (朝日新聞、2023年7月26日)
• 量子コンピューター、計算時の課題克服　米ハーバード大 (日本経済新聞、2023年12月7日)
• 光量子コンピューターの「量子ビット」でエラー修正する手法開発…東大など（読売新聞、2024年1月19日）