量子コンピューターとは何か？
量子コンピュータとは、量子力学的現象を利用したコンピュータである。小さなスケールでは、物理物質は粒子と波の両方の性質を示し、量子コンピューティングは特殊なハードウェアを使ってこの性質を利用する。古典物理学ではこれらの量子デバイスの動作を説明することはできず、スケーラブルな量子コンピューターは、現代の「古典的」コンピューターよりも指数関数的に高速な計算を実行することができる。特に、大規模な量子コンピューターは、広く使われている暗号化方式を破ったり、物理学者の物理シミュレーションを支援したりすることができる。

量子コンピューターにおける情報の基本単位は量子ビットで、従来のデジタル電子工学におけるビットと似ている。古典的なビットとは異なり、量子ビットは2つの「基底」状態の重ね合わせで存在することができる。量子ビットを測定すると、その結果は古典ビットの確率的出力となる。量子コンピュータが量子ビットを特定の方法で操作すると、波動干渉効果によって望ましい測定結果が増幅される。量子アルゴリズムの設計では、量子コンピュータが効率的に計算を実行できるような手順を作成する。

高品質な量子ビットを物理的に設計することは難しい。物理的な量子ビットがその環境から十分に隔離されていないと、量子デコヒーレンスに苦しみ、計算にノイズが混入する。各国政府は、より長いコヒーレンス時間と低いエラー率を持つスケーラブルな量子ビットの開発を目的とした実験的研究に多額の投資を行っている。最も有望な技術の2つは、超伝導体（電気抵抗をなくすことで電流を分離する）とイオントラップ（電磁場を用いて原子粒子を閉じ込める）である。

古典的なコンピューターで解くことができる計算問題は、量子コンピューターでも解くことができる。逆に、量子コンピューターで解くことができる問題は、少なくとも原理的には、十分な時間があれば古典コンピューターでも解くことができる。言い換えれば、量子コンピュータはチャーチ・チューリングの定理に従う。つまり、計算可能性という点では、量子コンピュータは古典コンピュータを上回る利点はないが、特定の問題に対する量子アルゴリズムは、対応する既知の古典アルゴリズムよりも時間的複雑度が著しく低いということである。注目すべきは、量子コンピュータは、古典的なコンピュータが実現可能な時間内に解くことができないような特定の問題を素早く解くことができると考えられていることである。量子コンピュータに関する問題の計算複雑性の研究は、量子複雑性理論として知られている。