量子コンピューティングでは、基本的な情報単位は量子ビット（キュービット）です。これは、従来のデジタルエレクトロニクスのビットに似ていますが、キュービットは2つの「基底」状態の重ね合わせに存在することができます。つまり、同時に両方の状態にあるということです。キュービットを測定すると、その結果は古典的なビットの確率的な出力になりますが、これにより量子コンピュータは一般に非決定的になります。量子コンピュータは、特定の方法でキュービットを操作することで、所望の測定結果を増幅させる波の干渉効果を利用することができます。量子アルゴリズムの設計は、量子コンピュータが効率的かつ迅速に計算を実行できるようにする手順を作成することを含んでいます。
量子コンピュータは、特定のタスクに対して古典的なコンピュータよりも指数関数的に少ない計算ステップで解決できることが量子複雑性理論によって示されていますが、全ての計算タスクにおいて量子スピードアップがあるわけではありません。基本的なタスク、例えばソーティングに関しては、量子スピードアップが存在しないことが証明されています。しかし、量子コンピュータの可能性には、量子物理学によって可能になる新しい理論上のハードウェアの幅広い範囲に対する楽観が燃えています。ただし、量子コンピューティングの制限に関する理解が深まるにつれて、この楽観はバランスをとっています。特に、ノイズのない量子コンピュータに対して伝統的に推定されていた量子スピードアップは、ノイズの影響と量子エラー訂正の使用によって低い多項式スピードアップを損なう可能性があります。
量子コンピューティングの歴史を振り返ると、量子力学とコンピュータ科学は長年にわたって異なる学術コミュニティを形成してきました。量子力学は1920年代に原子スケールで観察された波粒二重性を説明するために発展し、デジタルコンピュータはその後の数十年で面倒な計算のために人間の計算者を置き換えるために出現しました。量子コンピュータの開発に関する実験的研究には、国家政府が大きく投資しています。最も有望な技術の2つは、電気抵抗をなくすことによって電流を隔離する超伝導体と、電磁場を使用して単一のイオンを閉じ込めるイオントラップです。
量子コンピューティングへの投資は公共部門と民間部門の両方で開発が進んでいます。
