はじめに

量子アルゴリズムは、クエリ計算モデルにおいて古典アルゴリズムに対して証明可能な優位性を持っています。 しかし、より標準的な計算モデル、つまり問題の入力がオラクルやブラックボックスの形式ではなく明示的に与えられる場合はどうでしょうか？ これは答えるのがはるかに難しい問いであり、これに取り組むためにはまず調査の基盤となる確固たる土台を築かなければなりません。 本レッスンの主な目的はまさにここにあります。

まず、古典計算と量子計算の双方における計算コストについて、そしてそれをどのように測定するかについて説明します。 これはさまざまな計算問題に適用できる一般的な概念ですが、わかりやすくするために、主に計算数論という観点から考察します。計算数論とは、基本的な算術、最大公約数の計算、整数の素因数分解など、多くの読者にとって馴染み深い計算タスクを扱う分野です。 計算数論は応用範囲が限られていますが、これらの問題は基本的な課題をよく示しており（また、次のレッスンとも深く関連しています）、説明に適しています。

私たちが注目するのは、アルゴリズムが実行されるハードウェアの性能向上ではなく、アルゴリズムそのものです。 それに対応して、特定の計算に何秒・何分・何時間かかるかよりも、アルゴリズムが処理する問題インスタンスのサイズが大きくなるにつれて実行コストがどのようにスケールするかを重視します。 この観点に着目するのは、アルゴリズムが本質的な重要性を持ち、技術の発展とともに高速かつ信頼性の高いハードウェアを用いてより大規模な問題インスタンスに自然と適用されていくという事実を認識しているからです。

最後に、非常に重要なタスク、すなわち量子コンピューター上で古典計算を実行することについて説明します。 このタスクが重要な理由は、古典コンピューターを量子コンピューターで置き換えることを期待しているからではありません。そのようなことが近い将来に実現する可能性は極めて低いと思われますし、もしかすると永遠に実現しないかもしれません。むしろ、量子アルゴリズムに多くの興味深い可能性をもたらすからです。 具体的には、量子コンピューター上で動作する古典計算がサブルーチンとして利用できるようになり、量子計算的優位性の追求において古典アルゴリズムに関する数十年にわたる研究開発の成果を効果的に活用できるようになります。

レッスン動画

以下の動画では、John Watrous が量子アルゴリズムの基礎に関するこのレッスンの内容を解説しています。別のウィンドウでこのレッスンの YouTube 動画 を開くこともできます。このレッスンのスライドをダウンロードすることもできます。