なぜ量子コンピューターを使うと組合せ爆発に対応できる可能性があるのでしょうか。 　それは、量子コンピューターでは量子力学的な特性を生かした並列処理が可能なためです。 　従来型のコンピューターの情報の基本単位はビットです。ビットは「0」か「1」の値をとります、ビットを複数並べることで数を表していきます（2進法）。 　Excel風に表現すると2ビットで表すことのできる4つのデータ(00,01,10,11)を保管するには4行必要です。 ◆2ビットで表現できるデータ 1行目 : 00 2行目 : 01 3行目 : 10 4行目 : 11 　データを処理する時は、1行ごとに処理していきますので、2ビットで「表現可能な全ての候補」を処理するために必要な処理ステップは4となります。 「表現可能な全ての候補」の数は桁数（ビット数）が増えるごとに2倍と加速的に（指数的に）増加して、処理するために必要な処理ステップは膨大になっていきます。これが組合せ爆発です。 ◆ビット数と表現可能な全ての候補数 2ビット : 4 3ビット : 8 4ビット : 16 53ビット : 9,007,199,254,740,990 54ビット : 18,014,398,509,482,000 100ビット : 1,267,650,600,228,230,000,000,000,000,000 　一方、量子コンピューターの情報の基本単位は量子ビットです。 　量子ビットは「0」「1」を同時に取ることができます。これを重ね合わせ状態と呼びます。 　ここは直感的に理解出来ないと思いますが心配いりません。この世の誰も直感的に理解できない、それが量子の世界です。そういうものだと思って受け入れてください。 　Excel風に表現すると「表現可能な全ての候補」を1行に重ね合わせ状態で保管できます。 ◆2量子ビットで表現できるデータ 1行目 φφ (00,01,10,11の重ね合わせ状態) 　データを処理する時は、重ね合わせ状態になった1行に「表現可能な全ての候補」が存在するので、短いステップで処理が完了できる可能性があります。これは桁数（量子ビット数）が増えても変わらないため、組合せ爆発は発生しません。 　但し、短いステップで目的の処理を完了させるためには、用途に合わせた「うまいアルゴリズム」が必須です。 　重ね合わせ状態は外から隔絶された量子の世界でのみ存在します。外からデータを取り出そうとするとその状態は崩れ、重ね合わせになっていたうちの1つのデータが出てきます。何もしないとどのデータが出てくるかは完全にランダムになるため、何の役にも立ちません。 　処理目的に応じた「うまいアルゴリズム」を作り量子の世界で動作させることで、目的に応じた正解データを取り出せる（アルゴリズムによっては高い確率で取り出せる）ようにすることが出来ます。 　現時点でいくつかの「うまいアルゴリズム」が考案されています。一番最初に作られたドイチュ-ジョサのアルゴリズム、データ検索を行うためのグローバーのアルゴリズム、因数分解を行うためのショアのアルゴリズムなどが有名ですが、その他色々なアルゴリズムが考案されています。 　量子コンピューターは、その特性を生かせる一部の処理で高い性能が期待できますが、既存のコンピューターを完全に凌駕する存在ではありません。将来的に実用段階に入ったとしても、既存のコンピューターと共存することになるでしょう。 　大きな可能性を秘めた量子コンピューターですが、まだ実用段階には至っていません。それは一定規模以上の量子コンピューターを作るのがとても難しいからです。 　量子コンピューターはノイズに弱いなどの技術的な特性のため、扱える量子ビットを増やしていくのが非常に難しい課題となっています。量子コンピューターで扱える量子ビットが増えれば、従来型のコンピューターでは計算の爆発で処理が困難なケースを扱えるのは論理的には明白なのですが、少ない量子ビット数しか実装できない状態では既存のコンピューターとの差を実証することができない状況でした。 　そんな中「論理的には可能だが、その論理を実装して従来型のコンピューターを大きく上回る性能を出すことが本当にできるのか？」「その実現は『とても、とても難しい（でも可能性はある）』のか「『馬鹿げたくらい難しい（実現不可能）』なのか？」という懸念が生まれていました。 　それを見極めるための一つの指標として考えられたのが「量子超越性」です。「現実世界で役に立たない処理でもいいから、一般のコンピューターを上回る性能を実証することができたら、それは一つのステップになるだろう」という考え方です。 　Googleはこの「量子超越性」を実証するためのシナリオとして「ランダム量子回路サンプリング」という処理を選択し、53量子ビットの量子コンピューター「Sycamore」で「量子超越性」を実証したと発表しました。従来型のコンピューターでは1万年以上かかる処理を200秒で完了したとしています。 　Googleによる「量子超越性」の実証は量子コンピューターの実用化に向けた大きなステップですが、「ランダム量子回路サンプリング」自体は「量子超越性」のために選択された「現実世界で役立たない処理」であり、直近で実世界にインパクトを与える実装を生むものではありません。 「量子超越性」を考えたJohn Preskill氏は、”Googleによる「量子超越性」は大きなステップである、しかし実用化への道のりはまだ遠い、これから数年は限られた量子ビット数（~100）とエラー耐性の低い実装で可能なことを考え進んでいくことになるだろう”と述べています。 　以上が量子超越性の概要です。