はじめに
量子コンピュータは、いざ学ぼうとすると初学者のハードルが高い分野であると思います。
抽象的な概念を少しでも直感的に掴むため、Fundamentals of quantum algorithms: 量子アルゴリズムの基礎 学習サイトの内容をもとに、生成AIを活用して自分用の図解と解説動画を作成しました。
個人の勉強記録ではありますが、同じように学習の糸口を探している方のご参考になれば幸いです。
※AI生成コンテンツを含んでいるため、厳密な定義については必ず公式教材を併せてご参照ください。
The query model of comutation
(要約)
1.クエリ計算モデルとは
- 定義: 入力データ全体を直接読み取るのではなく、「オラクル」と呼ばれるブラックボックス（隠された関数 $f$）に質問（クエリ）を投げ、その応答から関数の性質を導き出すモデルです。
- 評価基準: 実行速度やメモリ量ではなく、「何回オラクルに問い合わせたか（クエリ数）」をコストとして重視します。
2.なぜこのモデルが重要か
- 量子計算が古典計算に対してどこで優位性（量子超越性）を持つのかを、情報アクセスの観点から明確に比較できるためです。
- 現実の複雑な実装を排除し、「情報を何回取得すれば問題を解けるか」という本質に集中できます。
3.量子クエリゲートの仕組み
- 可逆性の維持: 量子計算はユニタリ（可逆）である必要があるため、単に入力 $x$ を 出力 $f(x)$ で上書きすることはできません。
- 標準的な構成: 入力レジスタ $|x\rangle$ はそのまま保持し、別の補助レジスタ $|y\rangle$ に結果を書き込む形式（$|x\rangle|y \oplus f(x)\rangle$）をとることで、情報を破壊せずに計算を行います。
4.具体的な問題例
- OR問題: $f(x)=1$ となる入力が一つでもあるか？
- パリティ問題: $f(x)=1$ となる入力の個数が偶数か奇数か？
- 最小値探索・1位探索: 最も小さい値を出す入力や、唯一の正解を探す。
結論
クエリモデルを学ぶことで、量子コンピューターを単なる「高速な計算機」ではなく、「情報へのアクセス方法そのものを変える新しい計算原理」として理解できるようになります。これが、サイモンのアルゴリズムやショアのアルゴリズムといった発展的な手法を理解する土台となります。
Deutsch's Algorithm: Theory, Analysis, and Qiskit Implementation
(要約)
1. Deutsch's Algorithm とは
定義:
Deutsch のアルゴリズムは、1ビット入力の関数 ( f(x) ) が 定数関数 か バランス関数 かを判定する量子アルゴリズムです。
定数関数:
( f(0) ) と ( f(1) ) が同じ値になる関数です。
バランス関数:
( f(0) ) と ( f(1) ) が異なる値になる関数です。
2. なぜ重要か
Deutsch のアルゴリズムは、量子計算が古典計算と異なる方法で情報を取り出せることを示す、最も基本的な例です。
古典計算では、通常 ( f(0) ) と ( f(1) ) の両方を確認する必要があります。
一方、量子計算では、重ね合わせと干渉を使うことで、1回の問い合わせで関数の性質を判定できます。
3. アルゴリズムの仕組み
まず、2つの量子ビットを用意し、アダマールゲートで重ね合わせ状態を作ります。
次に、オラクルを使って関数 ( f(x) ) の情報を量子状態に反映させます。
その後、再びアダマールゲートを適用して測定すると、関数が定数かバランスかを判定できます。
4. 何がすごいのか
重要なのは、個別の値 ( f(0) ) や ( f(1) ) を知ることではありません。
量子アルゴリズムでは、関数全体の性質、つまり
[
f(0) = f(1) \quad \text{か} \quad f(0) \neq f(1)
]
を直接取り出します。
ここに、量子重ね合わせと干渉の本質があります。
5. 他のアルゴリズムとの関係
Deutsch のアルゴリズムは、Deutsch-Jozsa アルゴリズムの最も単純な形です。
また、後に学ぶ Bernstein-Vazirani アルゴリズムや Simon のアルゴリズムでも、同じように「オラクルから関数の隠れた性質を取り出す」という考え方が使われます。
結論
Deutsch のアルゴリズムは、量子コンピューターが関数の値を一つずつ調べるのではなく、関数全体の性質を干渉によって取り出せることを示す基本的なアルゴリズムです。
この考え方は、より発展的な量子アルゴリズムを理解するための出発点になります。
Deutsch-Jozsa algorithm
量子アルゴリズムの威力と比較
(要約)
1. ドイチュのアルゴリズムとは
定義:
ドイチュのアルゴリズムは、ある関数 ( f(x) ) が 定数関数 か バランス関数 かを判定する量子アルゴリズムです。
定数関数:
どの入力に対しても同じ値を返す関数です。
バランス関数:
入力によって 0 と 1 の両方を返す関数です。
ポイント:
古典計算では複数回の確認が必要になる場合がありますが、量子計算では重ね合わせを使うことで、1回の問い合わせで判定できます。
2. なぜ重要か
ドイチュのアルゴリズムは、量子コンピューターが古典コンピューターとは異なる方法で情報を取り出せることを示す、最も基本的な例です。
単に速く計算するのではなく、関数全体の性質を一度に調べる という考え方が重要です。
3. ベルンシュタイン・ヴァジラニの問題とは
定義:
ベルンシュタイン・ヴァジラニ問題は、関数の中に隠されたビット列 ( a ) を見つける問題です。
関数は次のような形で表されます。
[
f(x) = a \cdot x \mod 2
]
ここで ( a ) が、見つけたい隠れたビット列です。
目的:
オラクルに問い合わせながら、この隠れたビット列 ( a ) を求めます。
4. アルゴリズムの仕組み
まず、アダマールゲートを使って、すべての入力の重ね合わせを作ります。
次に、オラクルを通して関数 ( f(x) ) の情報を位相として反映させます。
最後に、もう一度アダマールゲートを適用すると、隠れたビット列 ( a ) が測定結果として現れます。
5. サイモンのアルゴリズムとの関係
ドイチュのアルゴリズムやベルンシュタイン・ヴァジラニのアルゴリズムは、量子アルゴリズムの基本的な考え方を学ぶ入口です。
サイモンのアルゴリズムでは、この考え方がさらに発展し、関数に隠れた周期構造を見つける問題へ進みます。
結論
ドイチュのアルゴリズムとベルンシュタイン・ヴァジラニのアルゴリズムは、量子コンピューターが重ね合わせと干渉を使って、関数の性質や隠れた情報を効率よく取り出せることを示す基本例です。
これらを理解すると、サイモンのアルゴリズムや Shor のアルゴリズムで使われる「隠れた構造を見つける」という考え方が、より自然に理解できるようになります。
Simon's algorithm
サイモンのアルゴリズム
(要約)
1. サイモンの問題とは
定義:
サイモンの問題は、ブラックボックス関数 ( f(x) ) に隠されたビット列 ( s ) を見つける問題です。
関数には次の性質があります。
[
f(x) = f(x \oplus s)
]
つまり、ある入力 ( x ) と、隠れたビット列 ( s ) を XOR した入力は、同じ出力になります。
2. なぜ重要か
サイモンのアルゴリズムは、量子コンピューターが古典コンピューターより少ない問い合わせ回数で問題を解けることを示した重要な例です。
古典計算では、同じ出力になる入力のペアを探す必要があります。
一方、量子計算では、重ね合わせと干渉を使って、隠れた構造を効率よく取り出せます。
3. アルゴリズムの仕組み
まず、アダマールゲートで入力全体の重ね合わせを作ります。
次に、オラクルを使って ( f(x) ) を計算します。
その後、測定と再度のアダマール変換により、隠れたビット列 ( s ) に関する条件式を得ます。
得られる式は次の形です。
[
y \cdot s = 0 \mod 2
]
4. 答えの求め方
1回の実行で ( s ) が直接出るわけではありません。
得られるのは、( s ) を絞り込むための条件式です。
アルゴリズムを複数回実行し、十分な数の式を集めます。
最後に、それらを連立方程式として解くことで、隠れたビット列 ( s ) を求めます。
5. 他のアルゴリズムとの関係
サイモンのアルゴリズムは、関数に隠れた周期構造を見つけるアルゴリズムです。
この考え方は、後の Shor のアルゴリズムにもつながります。
Shor のアルゴリズムも、周期を見つけることを利用して素因数分解を行います。
結論
サイモンのアルゴリズムは、関数の中に隠された XOR の周期 ( s ) を、量子重ね合わせ・干渉・測定によって効率よく見つける手法です。
量子コンピューターが、単に速い計算機ではなく、問題に隠れた構造を取り出す新しい計算モデルであることを示す重要なアルゴリズムです。
おわりに
量子情報の用語と世界観に慣れるための学習目的で記載しております。
掲載しているビジュアル素材は、IBM Quantum Learningの教材を参考にさせていただき、自身の理解を深めるためにAIで書き起こしたものです。
正確性、厳密さについては、公式の教材と照らし合わせてご確認ください。
一個人の学習ノートとしてご参照いただけますと幸いです。