量子コンピュータ
量子コンピュータ (りょうしコンピュータ、quantum computer)は量子力学の原理を計算に応用したコンピュータ。古典的なコンピュータで解くには複雑すぎる問題を、量子力学の法則を利用して解くコンピュータのこと。量子計算機とも。極微細な素粒子の世界で見られる状態である重ね合わせ(や量子もつれなど)を利用して、従来の電子回路などでは不可能な超並列的な処理を行うことができると考えられている。
2022年時点でおよそ数十社が量子コンピュータ関連の開発を競い合っている。
そのうちの主な会社を挙げると、IBM(IBM Quantum)、Google Quantum AI、Microsoft、Intel、AWS Braket、Atos Quantumなどである。
研究成果の年表については、英語版のTimeline_of_quantum_computing_and_communicationを参照のこと。
量子コンピュータは30年前には単なる理論上のものでしかなかったが、IBM Quantum社は、すでに現実に量子ハードウェアを製作しており、数千人の開発者がそれを利用できる状態になっている。IBM Quantumは量子プロセッサを定期的に配布している。
量子計算を「量子ゲート」を用いて行う方式のものについての研究がいまは最もさかんであるが、他の方式についても研究・開発は行われている。
いわゆる電気回路による従来の通常の2値方式のデジタルコンピュータ(以下「古典コンピュータ」)一般的でない例としては、数は少ないが3状態の素子で動作するコンピュータや、多値論理の応用などとして研究されている。MLC NANDフラッシュのように実用例も一部にはある。の素子は、情報について、なんらかの手段により「0か1」のような排他的な2値のいずれかの状態だけを持つ「ビット」(古典ビット)により扱う。量子コンピュータはそれとは違って、「量子ビット」 (qubit; quantum bit、キュービット) により、量子状態の重ね合わせ(量子波動関数)によって情報を扱う。ここで言う重ね合わせとは「0,1,重なった値」という第三の値と言う意味ではなく、両方の値を一定の確率で持っており、観測時にどちらかに確定すると言うものである。
n量子ビットがあれば2^nの状態を同時に計算し、2^n個の重ね合わされた結果を得る事が出来る。しかし、重ね合わされた結果を観測しても確率に従ってランダムに選ばれた結果が1つ得られるだけであり、古典コンピュータに対する高速性は得られない。高速性を得るためには欲しい答えを高確率で求める工夫を施した量子コンピュータ用のアルゴリズムが必須である。もしも数千量子ビットのハードウェアが実現したならば、この量子ビットの重ね合わせを状態を利用することで、量子コンピュータは古典コンピュータでは到底実現し得ない規模の並列コンピューティング(計算速度の量子超越性)を実現すると言われている。
量子コンピュータの能力については、理論上の話(予測や予測に関する議論)と、製作中の量子プロセッサの製作者が考えている予定値と、すでに製作された現実の機械についての実測値がある。実現した値については、やはり上述の英語版の年表が詳しい。(当記事の後半の#計算能力や#実際の節は、内容が更新がされておらず、かなり古い内容なので、あまり参考にはならない。)
将来に量子コンピュータの販売が行われるようになれば、初期の発展段階で量子コンピュータの重要な特許を多く取得した会社が莫大な収益や利益をあげると予想され、後手にまわった側は、特許を保有する側に対して膨大な特許実施使用料を支払う立場になったり、競争に負けて会社が衰退してしまう可能性もある。そのため2022年の時点では上で説明した数社だけではなくて、ほかにもあわせて数十社ほどが量子コンピュータ関連の開発を競い合っている。
なお単なるコンピュータの利用者になるだけのつもりの人にとっての「目先の利用価値」について言えば、2022年の時点ではスーパーコンピュータや普通のPCの方が利用価値が高いといえる(量子コンピュータが実用的な問題の処理に本格的に使えるようになるまでには「もうしばらく」時間がかかると考えられている)。
量子コンピュータの歴史は、1980年に ポール・ベニオフ が量子系においてエネルギーを消費せず計算が行えることを示したことに端を発し、1982年、ファインマンも量子計算が古典計算に対し指数関数的に有効ではないかと推測している。これらに続き、1985年、ドイッチュは、「量子計算模型」と言える量子チューリングマシンを定義し、1989年に量子回路を考案した。
1992年に、ドイッチュとリチャード・ジョサは、量子コンピュータが古典コンピュータよりも速く解ける問題でドイッチュ・ジョサのアルゴリズムを考案した。
1993年に、ウメーシュ・ヴァジラーニと生徒のEthan Bernsteinは、量子チューリングマシンと量子フーリエ変換のアルゴリズムを考案した。
1994年にピーター・ショアは、実用的なアルゴリズム『ショアのアルゴリズム』を考案し、量子コンピュータの研究に火をつけた。これは、ヴァジラーニらの量子フーリエ変換や、同年のSimonの研究を基礎に置いている。古典コンピュータでは現実的な時間では解けないと考えられている素因数分解は、量子コンピュータに特有であるこのショアのアルゴリズムでは理論上極めて短時間で解けることになるので、素因数分解の困難さを暗号の安全性の根拠としているRSA暗号は,もしも実用的な量子コンピュータが実現されたならば容易に破られることを示した。
1995年に、アンドリュー・スティーンやピーター・ショアにより、量子誤り訂正のアルゴリズムが考案された。
1996年に、ロブ・グローバーにより、その後、様々なアルゴリズムに応用されるグローバーのアルゴリズムが考案された。同年、セルジュ・アロシュは、実験的観測によって量子デコヒーレンスを証明し、
量子デコヒーレンスが量子コンピュータ実現への障害となることが実証された。
1997年に、Edward FarhiとSam Gutmannにより、量子ウォーク(Continuous-time quantum walk、略称: CTQW)が考案された。1998年に、量子コンピュータ用のプログラミング言語である、QCL (Quantum Computation Language) の実装が公開された。
また西森秀稔による、量子焼きなまし法(量子アニーリング法)の提案もこの時代であった。
ハードウェア開発に大きな進展があり、2008年にイオントラップの専門家デービッド・ワインランドは、個々のイオンをレーザー冷却して捕捉することが出来ることを示し、個々の量子もつれ状態にあるイオンをマニピュレーションする、トラップド・イオン量子コンピュータの研究が進展した。
ショアのアルゴリズムは、2001年に核磁気共鳴により、2007年に量子光学により、2009年に光集積回路により15の素因数分解 (=3*5) が実装された。
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年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|ax = 1 (mod N)} を求める。つまり、ax の周期 r を求める。この位数が高速に求められれば、因数分解は高速に行える。
例えば、N = 15, a = 7 とする。
70 = 1 (mod 15)
71 = 7 (mod 15)
72 = 4 (mod 15)
73 = 13 (mod 15)
74 = 1 (mod 15)
75 = 7 (mod 15)
76 = 4 (mod 15)
77 = 13 (mod 15)
78 = 1 (mod 15)
79 = 7 (mod 15)
⋮
1,7,4,13,1,7,4,13,1,7,…という周期 4 の数列が生成される。
よって、周期 r = min{x > 0|7x = 1 (mod 15)} = 4
手順の概略は以下の2つである。
全ての x に対して、均等な確率となるように初期化する。そして、それを ax mod N のみ確率を持ち、それらは均等になるように変換する。この計算は量子コンピュータ的であるものの、基本的な考えは古典コンピュータと変わらない。そのために、2進数の足し算・引き算や、ビットによる条件分岐などを用意する。
ax 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 はアダマール変換である。
量子コンピュータ用のプログラミング言語とその処理系の実装方法が多数提案されており、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量子ビットに対するユニタリー行列は以下の形式で表現される。可逆計算であることも特徴である。この式を見ると分かる通り、量子ゲートは本質的にアナログ信号処理であり、アナログ処理に伴う誤差が問題となる点が論理演算とは異なる。この事が量子コンピュータ実現上の最大の問題である。
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はパウリ行列の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
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はアダマール行列である。
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}
T|x\rangle |y\rangle |z\rangle = |x\rangle |y\rangle |z \oplus (x \land y)\rangle
ヴァジラーニらは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価であることを示した。したがって、計算可能性の点では既存のあらゆるコンピュータと量子チューリングマシンは変わらない。つまり、量子チューリングマシンで「計算可能」な問題は古典チューリングマシンでも「計算可能」であるし、古典チューリングマシンで「計算可能」でない問題は量子チューリングマシンでも「計算可能」でない。(なお、ここで「計算可能」というのは、計算理論の専門用語であって、「原理的に解くことができない」というような表現から一般の人がイメージするような素朴な印象はおそらくたいていは正確ではない)(単に計算可能という場合には、計算が有限の時間で終了して答えが得られるという意味である。その時間の長さが現実的かどうかについては問われない。)
計算可能性の理論に関しては以上のようであるのだが、では、計算複雑性の理論としてはどうだろうか、というのが関心のある所であろう。