重ね合わせ

複数の状態の線形結合も、また状態である。

$$|\psi ⟩=\alpha |0⟩+\beta |1⟩,|\alpha {|}^2+|\beta {|}^2=1$$

線形性からの帰結#

これは特別な現象ではなく、 状態空間がベクトル空間であることの直接の帰結。 シュレディンガー方程式が 線形なので、 重ね合わせは時間発展しても重ね合わせのまま保たれる。

「同時に両方」ではない#

よくある説明「0 と 1 を同時に取る」は誤解を招く。 より正確には、測定するまでどちらでもない別の状態にある。

測定すれば必ず 0 か 1 のどちらかが出る。 $2^n$ 個の値を同時に持っていても、 測定で取り出せるのは 1 つだけ。

だから並列計算ではない#

$n$ ビットの重ね合わせは $2^n$ 個の振幅を持つが、 それをすべて読み出すことはできない。

量子アルゴリズムの設計とは、 干渉を使って欲しい答えの振幅だけを大きくしてから測ること。 Grover が $𝒪(\sqrt{N})$ で済むのも、 $N$ 個を並列に調べているからではなく、 振幅増幅という別の仕組みによる。

「量子コンピュータは全部の可能性を同時に試す」は 広く流布した誤解で、Aaronson が繰り返し指摘している。

参考文献#

• Michael A. Nielsen, Isaac L. Chuang. Quantum Computation and Quantum Information, 10th Anniversary Edition. Cambridge University Press, 2010. https://doi.org/10.1017/CBO9780511976667
• Scott Aaronson. Quantum Computing Since Democritus. Cambridge University Press, 2013. https://doi.org/10.1017/CBO9780511979309
• John Preskill. Quantum Computation Lecture Notes (Caltech Ph219/CS219) https://www.preskill.caltech.edu/ph219/