「量子チューリング・マシンを用いると因数分解と離散対数問題が非常に小さな誤り確率で高速に解ける」、

ことを証明した1994年以後からである。因数分解問題Factoring problemとは、ある整数に対して、掛けるとこの数になるような素数の組を求める問題である。離散対数Order-finding問題とは、「素数と２つの整数と（mod）が与えられている時、となるを求めよ」という問題である。離散対数問題を高速に解くアルゴリズムは因数分解問題も解くことができるという意味で、両者は同等の問題だと言える。ショアの方法は、シモンD.R. Simonによって考案された（２段、離散）量子フーリエ変換という方法を応用したものである。

計算の章でも述べたように、P, NP完全など、現在の計算機で計算困難な問題は他にも沢山ある。量子計算でも、組み合わせや探索など、多くの問題が研究されている。また量子チューリング・マシンは、任意の物理系を効率的にシミュレーションできることが示されている。

量子暗号Quantum cryptography

　量子計算機が期待どおり大きな数の素因数分解を実行できるとすれば、現在の公開鍵は破られてしまうことになる。興味深いことに量子情報計算は、新しい暗号方式の可能性をも提示している。そのもとになったのは、ウィズナーStephen Wiesnerの「量子のお金Quantum Money」というアイデアである。彼は、水平、垂直、対角という３方向に偏光した光子を連続して送信することで、ある種の暗号がつくれることを思いついた。彼はこのアイデアをベネットに話し、ベネットはこれをある長さの信号を、秘密鍵方式で送信する方法に拡張した。この方式では、誰かが送信内容を傍受（盗み見ようと）すると、そのことが分かるようになっている。

量子テレポーテーション

量子テレポテーションQuantum Transportationとは、受信者が遠方にいる送信者に依頼して、ある量子状態を瞬時に受信者側に送ってもらうことである。ただし、厳密に言えばこれは「送信」するのではなく、送信したい(量子)状態を受けた側に「出現」させる方法である。量子状態の瞬時の出現を可能にする仕組みは、送信者と受信者が、エンタングルメントしている粒子を共有していることである。エンタングルメントEntanglementとは、複数の物理系の量子状態が絡み合っていることを意味する。一般に、２つの物理系が相互