はじめに

始める前に、この短いコース前アンケートにご回答ください。このアンケートは、コンテンツの改善とユーザーエクスペリエンスの向上に役立てるための重要なものです。

このコースの最初のレッスンでは、クエリモデルとして知られるシンプルなアルゴリズムの枠組みを定式化し、この枠組みの中で量子コンピューターが提供する優位性を探ります。

クエリモデルによる計算は、量子アルゴリズムのアイデアを育てるペトリ皿のようなものです。 実際に私たちが一般的に関心を持つ計算問題を正確に表現していないという意味では、硬直的で不自然なものですが、それでも量子アルゴリズムの技術を発展させるためのツールとして非常に有用であることが証明されています。 これには、整数因数分解のためのShorのアルゴリズムなど、最もよく知られた量子アルゴリズムを支える技術も含まれています。 クエリモデルはまた、量子アルゴリズムの技術を説明するための非常に有用な枠組みでもあります。

クエリモデル自体を紹介した後、発見された最初の量子アルゴリズムであるDeutschのアルゴリズムと、そのDeutschのアルゴリズムを拡張したDeutsch-Jozsaアルゴリズムについて解説します。 これらのアルゴリズムは、クエリモデルの文脈において、量子コンピューターが古典コンピューターに対して持つ定量的な優位性を示しています。 次に、Simonのアルゴリズムと呼ばれる量子アルゴリズムについて解説します。このアルゴリズムは、古典的な計算に対する量子の優位性をより堅牢かつ納得のいく形で示しており、その理由については該当箇所で詳しく説明します。

レッスン動画

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