量子コンピュータで速く解ける問題の種類は、わずかしかわかっていない。その他の問題については、今のコンピュータでも量子コンピュータでも互角である。

量子コンピュータで計算が速くなるとは、必要な計算の回数を減らすことである。量子コンピュータの並列計算は「量子」のミクロな世界特有の「重ね合わせ」という現象を使う。並列計算したたくさんの結果の候補の中から取捨選択して、欲しい計算結果だけを絞り込んでいくような工夫が必要になる。この欲しい計算結果を絞り込める「特別な用途」の場合に、量子コンピュータは速く計算することができる。特別な用途の代表例には、何通りもあるパターンの中から、最も良いパターンを1つ選び出すという「最適化問題」がある。これは新素材や薬の開発といった用途に影響を及ぼすと予想される。

量子コンピュータはたくさんのパターンを重ね合わせて、その重ね合わせ具合をうまくコントロールしながら問題を解く。1つずつ計算を行う代わりに、何通りもの計算を重ね合わせて同時に行った後に、干渉によって「当たり」に相当する計算パターンだけを探し当てる。干渉にはかなり工夫が必要だが、うまくいくと「当たり」を探す手間を圧倒的に減らせる場合がある。

原子1個や電子1個などのミクロな世界は、量子力学に従い、重ね合わせや干渉が起こる。一方、日常的に目にする比較的大きな物質は、多数の原子や電子の集合体だが、こうした現象は起こらない。正確な答えはわかっていないが、重ね合わせや干渉を起こす波の性質は、周囲からの影響によって壊れてしまうと考えられている。

量子コンピュータでは、計算の途中で、重ね合わせを生み出す波の性質ができるだけ損なわれないよう、どのように周囲からの影響をなくすかが鍵を握る。

量子コンピュータは、量子の性質を用い「0と1の重ね合わせ」を情報の単位に使う。これを量子ビットという。量子ビットは、ただ「0」と「1」の情報が重ね合わさって同時に存在するだけでなく、その2つの「重ね合わせ具合」によって情報を表現している。たくさんの波を操って「重ね合わせ具合」をうまくコントロールしながら計算を行う。量子ビットは、2つの波の大きさの比に応じた確率でランダムに「0」か「1」が決まる。量子ビットがn個あり、2n個のパターンの情報が重ね合わさっている場合も、測定して読み出す際にはどれか1パターンだけが選ばれる。つまり、量子コンピュータは大量のパターンの情報を並列に処理できるという強みがある一方で、最後に計算結果として取り出せる情報は1パターンだけという厳しい制約がある。この制約を理解した上で、計算の仕方を工夫する必要がある。