有意思的是，量子纏結最初在物理界引起關注，不是在於它的巨大潛在應用價值，而是被愛因斯坦、波多斯基（boris podolsky）和羅森（nathan rosen）作為質疑量子力學完備性的悖論於1935年提出的（epr理論）。他們認為量子纏結態的存在，似乎破壞了在物理學上非常基本的定域性原理，因而應該存在一種可以涵蓋所有量子力學結論的更完備的“定域隱變量”理論（或曰“定域實在論”，即定域論與實在論相結合的產物）。30年後，貝爾（john bell）提出了一個著名的思想實驗——貝爾實驗，在此實驗中，定域隱變量理論和量子理論會得出明顯不同的結果。自1972年以來，貝爾實驗被實際進行了很多次，精確度也越來越高，所有的結果都指向量子理論優於定域隱變量理論。
對傳統計算機來說，信息是由一係列位元（0/1）合成的編碼，這些位元經過特定組合的布爾邏輯門一步接一步地進行處理，從而得出最終結果。量子計算機則是通過量子位元和量子門對信息進行處理。在這點上量子計算機與傳統計算機並沒有本質區別。所以從理論上講，傳統計算機可以模擬任何量子計算機。但另一方麵量子計算機與傳統計算機又有著本質的不同。其中最重要的有兩點。一是存在疊加態，300個處於疊加態的量子位元所能承載的信息量是2300，這比整個宇宙中基本粒子數量的總和都大得多，是傳統計算機根本不可能處理的。二是量子纏結，它使相互纏結的量子位元間的信息傳遞可以以連鎖反應的形式在瞬間完成。這些特性決定了當處理某些種類的計算問題時，不論是速度還是效率，傳統計算機都無法與和量子計算機相提並論。一個典型的例子是整數的因數分解（將一個整數分解成若幹個質數的乘積）。理論上，量子計算機可以在幾秒鍾內分解一個10200數量級的整數，這對傳統計算機來說是根本不可能完成的任務。由秀爾（peter shor）在1994年提出的第一個應用於在量子計算機的算法——秀爾算法，針對的就是整數分解問題。秀爾算法不僅僅是為量子計算提供了一個可行的運算模型，同時還顯示出量子計算巨大無比的潛在應用價值。互聯網如今已經是人類社會不可分割的一個重要部分，而互聯網的安全幾乎完全取決於加密技術。在公鑰加密和電子商業中被廣泛使用的rsa加密算法所依仗的，就是對極大整數作因數分解的困難程度。它原本被認為是不可破解的，但在量子計算機麵前卻可能不堪一擊。