この記事は以下の記事の続きとなります。
「Shorのアルゴリズムをじっくり読んでみる (Abstract編)」
https://qiita.com/galo/items/18581e5930a4fef1e287
Shorのアルゴリズム 論文
Shorのアルゴリズムの論文[1]の2章「Quantum computation」を解説していきたいと思います。
取り扱う量子計算
量子計算の分野として
- 量子ゲート配列・量子非循環回路
- 量子チューリングマシン
- 量子セルオートマトン
といったものがありますが、ここでは量子ゲート配列・量子非循環回路について取り扱うものとします。
量子非循環回路
量子非循環回路（Quantum acyclic circuit）は、量子コンピューターにおいて、一連の量子ゲートを順番に適用することで任意の量子状態を作り出すために使用される回路です。
量子非循環回路は、ある特定の量子状態を作り出すために必要な最小限の量子ゲートを使って、効率的に演算を行うことができます。これは、量子コンピューターがエラー耐性が低く、大規模な回路の実行が難しいことを考慮すると、非常に重要です。
量子非循環回路は、DAG（有向非循環グラフ）として表現することができます。各ノードは量子ゲートを表し、各エッジは量子ビット間の相互作用を表します。このように表現することで、回路の視覚的な理解が容易になります。
量子非循環回路は、量子アルゴリズムや量子エラー訂正など、さまざまな分野で使用されます。量子コンピューターがより大規模かつ信頼性の高いものになるにつれ、量子非循環回路の使用はますます重要になることでしょう。
量子チューリングマシン
量子チューリングマシン（Quantum Turing Machine, QTM）とは、量子コンピュータの理論的な基礎となるモデルの一つで、アラン・チューリングが提唱した古典的なチューリングマシンを量子力学的に拡張したものです。
QTMは、入力として与えられた量子状態を受け取り、一連の量子演算を適用して計算を行います。QTMの計算モデルは、古典的なチューリングマシンと非常によく似ていますが、量子状態を処理することができるという点で異なります。
QTMでは、量子状態を表すために、量子ビットの重ね合わせ状態やエンタングルメントなど、古典的なチューリングマシンでは扱えない量子力学的な概念が使用されます。また、QTMでは量子演算子を使用することで、同時に複数の演算を行うことができます。
QTMは、量子アルゴリズムの理論的な解析や、量子コンピュータの設計や実装において重要な役割を果たしています。ただし、現在の技術では、QTMを実際に構築することは非常に困難であり、量子コンピュータはまだ限定的な規模でしか構築されていません。
量子セルオートマトン
量子セルオートマトン（Quantum Cellular Automaton, QCA）は、量子力学的な観点からセルオートマトンを一般化したもので、量子ビットを用いた離散的な時間と空間での計算モデルです。
QCAは、離散的な空間を規則的なセルに分割し、量子状態を記述するために量子ビットを使用します。QCAは、各セルの量子状態が、周囲のセルの状態に依存して時間発展することで計算を行います。
QCAは、一般的に、量子ビットのエンタングルメントや相互作用に基づく複雑な量子力学的な現象を利用して、並列的な計算を行います。QCAによって解決できる問題には、量子検索、量子シミュレーション、量子化学、量子暗号化などがあります。
QCAは、量子コンピューティングの分野において、量子アルゴリズムの実装や量子エラー訂正、量子シミュレーションなど、さまざまな応用が期待されています。しかし、現在のところ、QCAの実際的な実装や効率的なアルゴリズムの開発には、多くの課題が残されています。
量子コンピューティングには様々なモデルが提案されていますが、現在でも主流になっているのは量子非循環回路でしょう。というのはこれが一番技術的に実現可能性が高く、これが先に実行できなければ後の二つは議論するにはまだハードルが高いからでしょう。
まずは循環などがないあらかじめ決めたオペレーションを上から下(左から右)に実行する回路を考える必要があるということでしょう。
量子回路[2]
量子と古典のビット記述の違いについて考えます。
n個のコンポーネントがあり、それぞれのコンポーネントは2つの状態を取ることができるとき、古典の記述方法では、nビットあれば任意の状態を記述することができます。
それに対し量子の記述方法では、$2^n-1$の複素数が必要になります。
これを表に表すと以下になります。
| コンピュータ | n個のコンポーネントの自由度 |
|---|---|
| 古典 | n個のブール値(0か1) |
| 量子 | $2^n-1$個の複素数 |
簡単のために2個のコンポーネントの記述を考えましょう。
古典ではXYはXが0か1か、Yが0が1かを考えるだけで済みます。
量子では$|XY>=a|00>+b|01>+c|10>+d|11>$
(a,b,c,dは複素数 $|a|^2+|b|^2+|c|^2+|d|^2=1$)
といった記述になります。同じ2個のコンポーネントでも格納できる情報量が全然違うことが分かりますね。特に大事なことは量子はnが指数部にあることで、ここが量子計算が指数加速を可能にします。
また、量子回路では量子力学の法則によりユニタリ変換の操作のみが許されています。ユニタリ変換とは共役転置が逆行列と等しい行列のことをいいます。
古典的な電気回路のビルディングブロックとしてAND、OR、NOTゲートがありますが、これの代わりとなる量子回路のビルディングブロックはX、Z、Hのような1量子ビットゲートとCNOTのような2量子ビットゲートとなります。
ユニタリ変換の操作の例として、例えば以下のような変化を発生させる操作を考えたとき
行列表示は以下のように表されます。
このように、量子ゲートの操作は行列やベクトルを介して表現されることとなります。
多数の量子ゲートを作用させることで量子計算を実現するわけですが、それには二つの制約があります。
- ゲート配列の設計は多項式時間（古典的）計算によって生成される
- 各エントリーの最初のlog nビットは、nに対して多項式時間で古典的に計算可能であるべき
といったものです。一つ目は解こうとする問題に対し、どのように量子ゲートを作用させるかを決める処理は多項式時間で終わらせることを要求しています。
もう一つは、最初に初期化し、設定する量子ビットの状態というのは多項式時間で計算して決められることを要求しています。
要するに、量子計算の準備は古典計算機で行うわけですが、この前処理に指数時間かかってはいけませんよということだと取れます。
まとめると
- 量子非循環回路について議論する
- X,H,CNOTなどの量子ゲート操作を行列計算の形で計算する
- 量子操作の前準備は古典計算機で多項式時間で完了するという前提とする
ということでした。
次回は来週2023/4/16更新予定です。
さらに深い議論に踏み込んでいきます。リアクション頂けるとやる気が出ます
[1]https://arxiv.org/pdf/quant-ph/9508027.pdf
[2]https://qiskit.org/documentation/locale/pt_UN/apidoc/circuit.html