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

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

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

古典的なコンピュータで解決できる計算問題は、量子コンピュータでも解決できる。逆に、量子コンピュータが解決できる問題は、十分な時間があれば、少なくとも原理的には古典コンピュータでも解決できる。つまり、量子コンピュータは「チャーチ・チューリング定理」に従う。つまり、量子コンピュータは計算可能性という点では古典コンピュータに勝るとも劣らないが、ある問題に対する量子アルゴリズムは、対応する既知の古典アルゴリズムよりも時間的複雑度が著しく低いということである。特に、量子コンピュータは、古典的なコンピュータが解決できないような問題を、実現可能な時間内で高速に解決できると考えられている。"量子至上主義 "と呼ばれる偉業だ。量子コンピュータの計算量に関する研究は、量子複雑性理論として知られています。