量子力学
例えば、有名なシュレーディンガーの猫の思考実験では、観測とはどの時点のことを指すのか、粒子検出器が反応した時点なのか、毒ガスが発生した時点か、それを猫が見た時点か、箱が空けられた時点か、箱を開けた人が猫を見た時点か...、といったどの時点で観測が成立するのかは標準解釈では決まっていない。どの時点で観測が起きるのか、どこまでを量子系とするのかは、測定者が任意に設定できる。
一方で、アインシュタインは「量子力学では記述されていないが、実際にその状態を実現させた変数が存在するはずである」と主張した(局所的な隠れた変数理論)。隠れた変数理論は数学的に成り立たないことがフォン・ノイマンによって証明されたが、後に、その証明に使われた仮定に誤りがあることが分かった。ただし局所的な隠れた変数理論は、量子力学とは異なる結論を出すことがベルの不等式によって示され、実験検証によって棄却された。量子力学と同じ結論を出す、隠れた変数理論は存在するが、非局所的である(クラスター分解性を持たない)。
計算機中の信号媒体の状態は、本来量子力学的に記述されるはずであり、0 または 1 の2値(1ビット)ではなく、 0 と 1 がそれぞれの確率で重ねあわされた途中の値を持つことがありうる。この量子論的な状態を1量子ビット (qubit) と呼ぶ。ここで複数のqubitを量子もつれ状態にすることにより、様々な数を表す状態がそれぞれの確率で重ね合わされた状態を実現することができる。量子もつれを壊さないユニタリー変換を活用してそれぞれの確率の重みを変化させることで演算を行うと、特定の問題について古典計算機では実現し得ない計算速度を実現できる。
この中には素因数分解も含まれており、Shorのアルゴリズムにより素因数分解を多項式時間で解けることが証明されている。RSA暗号は大きな桁数の素因数分解が事実上不可能である事を前提として成立しているため、楕円曲線暗号と離散対数問題も含めた前提を量子コンピュータが崩すことになっている。