Table of contents

1. 第2章 量子アルゴリズム入門
   1. NISQアルゴリズムとLong-termアルゴリズム
      1. NISQアルゴリズム
         1. NISQ(ニスク)とは
         2. NISQアルゴリズムの概要
         3. Long-termアルゴリズム
   2. アダマールテスト
      1. アダマールテストの動作
   3. 量子乱数生成
      1. 物理乱数
      2. 擬似乱数
      3. 安価な実験で量子乱数を実現
         1. 光のショットノイズ
         2. 原子核のα崩壊
      4. 信頼できない量子デバイスで量子乱数生成
         1. 手順
   4. 量子フーリエ変換
      1. 定義
      2. 回路構成
      3. コラム: 計算量について
   5. 位相推定アルゴリズム(入門)
      1. アダマールテストを改良する
      2. 概要
      3. 構成
      4. 結言
      5. 具体例
      6. コラム: (素因数分解と位相推定)
      7. 応用例
2. 参考文献(というよりこれを見て勉強中)

第2章 量子アルゴリズム入門

欲しい答え(状態)が高確率で得られるように設計された量子コンピュータ専用のアルゴリズムが不可欠 -> 量子アルゴリズム
e.g. ) Shorの素因数分解アルゴリズム、Groverの探索アルゴリズムなど。

1. NISQデバイスで実行可能(と思われる)なアルゴリズム
2. 量子誤り訂正ありの真の量子コンピュータでしか実行できない

の2つに大別される。

NISQアルゴリズムとLong-termアルゴリズム

この用語は一般的でない、かつ解きたい問題の大きさや技術の進歩によって移変わる。

	NISQ	Long-term
入門	VQE, QAOA, QCLなど	Hadamard test, QFT, QPEなど
発展		Grover, HHLなど

VQE: Variational Quantum Eigensolver
QAOA: Quantum Approximate Optimization Algorithm
QCL: Quantum Circuit Learning
QFT: Quantum Fourier Transform
QPE: Quantum Phyase Estimation

NISQアルゴリズム

NISQ(ニスク)とは

Noisy Intermediate-Scale Quantum devices.量子誤り訂正機能を持たない。

NISQアルゴリズムの概要

ノイズは計算が長ければ長いほど(アルゴリズムが複雑になるほど)蓄積していき、最終的な出力結果をデタラメなものにしてしまう。ShorやGroverのアルゴリズムは回路が複雑で操作回数が多いため、エラー耐性の低いNISQではパワー不足で実行が困難。
化学反応のシミュレーションなどでは、NISQが古典コンピュータを上回る可能性が示唆されている。NISQは量子スプレマシーの担い手となった(Googleの研究発表より)。
一般に量子計算は、量子ビット数が多く量子演算回数が多くなるほど、エラーの影響を受けやすくなる。よってNISQアルゴリズムは浅い量子回路(少ない量子ゲート数)で行う必要がある。このような背景から、NISQアルゴリズムの研究では、量子コンピュータの得意な部分のみを量子計算機に任せ、残りは古典コンピュータで処理する「量子-古典ハイブリッドアルゴリズム」というアプローチが主流。

Long-termアルゴリズム

多数の量子ビットが利用可能かつ誤り訂正が可能という仮定のもとで実現可能。基本的に全てのアルゴリズムはLong-termアルゴリズムであり、その一部がNISQデバイスでも実行可能なアルゴリズムと考えるのが良いかもしれない。

アダマールテスト

第1量子ビットは$$\left

0 \right>\(、第2量子ビット以降は\)\left

\psi \right>$$に初期化されている。まず第1量子ビットにアダマールゲートをかける。そして全体に制御ユニタリ演算子を作用させて、再び第1量子ビットにアダマールゲートをかける。最後にその第1量子ビットを測定する。

制御ユニタリ演算は以下のように、第1量子ビットが$$\left

0 \right>\(の場合には何もせず、\)\left

1 \right>$$の場合にはUを作用させるユニタリ演算。

\[\Lambda (U) = \left| 0 \right>\left< 0 \right| \otimes I + \left| 1 \right>\left< 1 \right| \otimes U\]

1つ目の量子ビットが$$\left

0 \right>\(or\)\left

1 \right>$$によって条件分岐して、何もしないorUを作用させるという演算が実行される。量子コンピュータでは状態の重ね合わせを利用して条件分岐を同時並列的に実行することができる。

アダマールテストの動作

簡単のため、量子状態$$\left

\psi \right>\(がユニタリ演算Uの固有値\)e^{i\lambda}$$の固有状態(固有ベクトル)である場合を考える。

\[U\left| \psi \right> = e^{i\lambda} \left| \psi \right>\]

第1量子ビットにアダマール演算Hを作用させることで

\[\left| 0 \right> \otimes \left| \psi \right> \rightarrow \frac{1}{\sqrt{2}} (\left| 0 \right> + \left| 1 \right>) \otimes \left| \psi \right> = \frac{1}{\sqrt{2}} \left| 0 \right> \otimes \left| \psi \right> + \frac{1}{\sqrt{2}} \left| 1 \right> \otimes \left| \psi \right>\]

そこに制御U演算を作用させると、固有値\(e^{i\lambda}\)が第1量子ビットの相対位相として得られる(これを位相キックバックと呼ぶ)

\[\frac{1}{\sqrt{2}} \left| 0 \right> \otimes \left| \psi \right> + \frac{1}{\sqrt{2}} \left| 1 \right> \otimes \left| \psi \right> \rightarrow \frac{1}{\sqrt{2}} \left| 0 \right> \otimes \left| \psi \right> + \frac{1}{\sqrt{2}} \left| 1 \right> \otimes U \left| \psi \right> = \frac{1}{\sqrt{2}} \left| 0 \right> \otimes \left| \psi \right> + \frac{1}{\sqrt{2}} \left| 1 \right> \otimes e^{i\lambda} \left| \psi \right> = \frac{1}{\sqrt{2}} (\left| 0 \right> + e^{i\lambda} \left| 1 \right>) \otimes \left| \psi \right>\]

最後に第1量子ビットにアダマール演算を行う。

\[\frac{1}{\sqrt{2}} (\left| 0 \right> + e^{i\lambda} \left| 1 \right>) \otimes \left| \psi \right> \rightarrow \frac{1}{\sqrt{2}} (\frac{1}{\sqrt{2}} (\left| 0 \right> + \left| 1 \right>) + \frac{e^{i\lambda}}{\sqrt{2}} (\left| 0 \right> - \left| 1 \right>)) \otimes \left| \psi \right> = (\frac{1}{2} (1+e^{i\lambda}) \left| 0 \right> + \frac{1}{2} (1-e^{i\lambda}) \left| 1 \right>) \otimes \left| \psi \right>\]

となる。第1量子ビットを測定すると、測定結果として状態0, 1を得る確率\(p_0, p_1\)は

\[p_m = \left| \frac{1+(-1)^m e^{i\lambda}}{2}\right|^2 = \frac{1+ (-1)^m\cos \lambda}{2}\]

$$\left

\psi \right>, \left< \psi \right

\(はそれぞれ\)2^n\(次元の列ベクトルと行ベクトル、そしてUは\)2^n \times 2^n\(行列。よってこのアダマールテストを古典コンピュータで愚直に計算すると指数的に大きなメモリの確保と演算回数が必要になる。一方、量子コンピュータでは確率分布\)p_m\(のもとでmがサンプルされる。\)\cos \lambda\(をある誤差\)\epsilon\(で推定したい場合、その逆数\)1/\epsilon$$の多項式回程度サンプルすれば良いことがわかる。

同じ計算を必ずしも固有状態とは限らない、一般の入力に対して行う。測定前の状態は

\[\left| 0 \right> \otimes \frac{I+U}{2} \left| \psi \right> + \left| 1 \right> \otimes \frac{I-U}{2} \left| \psi \right>\]

0, 1が得られる確率は

\(p_0 = \frac{1+{\text Re}\left< \psi \right| U \left| \psi \right>}{2}\) \(p_1 = \frac{1-{\text Re}\left< \psi \right| U \left| \psi \right>}{2}\)

よって量子コンピュータ上でアダマールテストを実行すれば、その測定結果のサンプル平均を取ることで**ベクトル$$ \left

\psi \right>$$でユニタリ行列Uを挟んだ値を推定することができる**。同じ値を古典コンピュータで求めようとした場合、量子ビット数nが大きくなりにつれて、ベクトルや行列の次元は指数的に大きくなる。よって古典コンピュータでは指数的に時間を要する。

第1量子ビットを測定した後の第2量子ビットの状態は、測定結果m=0, 1に応じて以下の状態になる(規格化因子は省略)

\[\left| \psi_0 \right> = \frac{I+U}{2} \left| \psi \right>, \ \left| \psi_1 \right> = \frac{I-U}{2} \left| \psi \right>\]

ここで、Uが第1量子ビットのユニタリ演算でかつその固有値が\(\pm 1\)であるような場合を考える。固有値\(\pm 1\)に対応する固有状態$$\left

u_1 \right>, \left

u_{-1} \right>\(を用いて\)\left

\psi \right> = c_1 \left

u_1 \right> + c_{-1} \left

u_{-1} \right>\(と展開し代入することで、測定後の状態\)\left

\psi_0 \right>, \left

\psi_1 \right>\(はそれぞれ固有値\)\pm 1\(に対応する固有状態であることがわかる。固有値が\)\pm 1$$でない場合も、アダマールテストの出力を入力として繰り返すとUの固有状態に状態が収束していく。

量子乱数生成

より基本的な技術で実現可能な量子情報処理の応用が考えられている。その三つが量子乱数生成、量子センシング、量子暗号。

乱数に要請される性質は0, 1の出現に関してバイアスがないこと、そして以前に生成した乱数との相関がないこと。このような理想的な性質をもつ乱数を真正乱数と呼ぶ。現実には生成困難なので、通常の計算機では物理乱数や擬似乱数が用いられている。

物理乱数

物理乱数とは一般に予測が困難な計算機の物理的な情報をモニタリングし、その情報からバイアスや相関を取り去ることで生成する乱数。例えばCPUや通信機器のノイズ情報が用いられる。こうして得られた乱数はエントロピープールと呼ばれる箇所に蓄積される。そして、物理乱数はプログラムが使用するたびに消費される。

1. 物理乱数の利点は予測が困難なこと
2. 物理乱数の欠点は生成がデバイスのノイズに依存するため概して生成が遅いことと、予測は困難であっても理論上不可能ではないこと

例えばCPUの熱ノイズを遠くにいる攻撃者が正確に予測することは現実的には困難だが、攻撃者が計算機の近くにいる場合、計算機の本体から漏れ出る情報をモニタリングすることで、計算機の使用者が想定した以上の情報が外に漏れ出てしまうという可能性はある。理論上の話をすれば、古典力学的に扱える物理系は初期状態とダイナミクスが定まれば理論上は完全に予測可能。

擬似乱数

疑似乱数とは、ある秘密の「状態」を指定し、これを決定論的に遷移させることで、遷移に際して現在の「状態」を知らない人にとって乱数と区別がつかないと期待される数列を得ること。例として、線形合同法、xorshift、メルセンヌツイスタのようなアルゴリズムが代表的。 疑似乱数の特徴は物理乱数と相補的。

1. 利点は高速であること
2. 欠点は現在の「状態」が外部に漏れると以降の数列がすべて予測されてしまうこと

以上より、暗号鍵生成のような安全性が重視される場面では物理乱数が、物理シミュレーションのような高速性が重視される場面では初期状態として物理乱数を用いて以降は疑似乱数を用いることが多い。

量子乱数は物理系の持つ予測の難しさを利用するという意味では物理乱数の一種であるが、初期状態を攻撃者が把握していても原理的に未来に生成される乱数が予測が不可能であるという点で熱ノイズなどを用いた乱数とは異なる。量子乱数の最も基本的なアイデアは、量子状態を$$\left

+ \right>$$に初期化し、これをZ基底で測定するものである。

$$\left

+ \right>$$を用意してZ基底で測定する操作は、一見すると熱ノイズなどを扱う物理乱数とあまり変わらないように思える。しかし乱数生成の背景を攻撃者が完全に知っていたとしてもどういった値が出るのか理論上予測できないという点で物理乱数とは大きく異なる。完ぺきに調整された信頼できる量子乱数源は、たとえ攻撃者がその初期状態を知っていたとしても真正乱数となる。

量子乱数生成の研究の目的は、上記のような理想的な状況をより現実に近い制約の下で実現すること。

安価な実験で量子乱数を実現

イオンや超伝導素子は、理想的な量子ビットを生成するためには良い物質。しかしその準備には光源/マイクロ波源や冷却機構などの高度な技術と高価な装置が必要。しかし現実的な問題として、乱数を生成するためだけに希釈冷凍機や真空チャンバを購入することは殆どの場合割に合わない。このため、いかに安価な実験装置でも量子乱数を生成できるかというテーマは応用上重要。一見すると単なる物理乱数に見えるが、実は初期状態を攻撃者が完全に把握していたとしても予測が出来ない量子乱数となっている例として以下の２つがある。

光のショットノイズ

発振したレーザーから放出される微弱な光を高精度な光強度検出器で観測すると、ショットノイズと呼ばれるノイズが不可避に乗ることが知られている。これは、発振したレーザーから放出されるパルスは光子数分布がポアソン分布と整合するコヒーレント状態と呼ばれる純粋状態となるために、その光子数の期待値は一定であっても、光子数の射影測定によって得られる光子の数がばらついてしまうことによる。このばらつきのことをショットノイズと呼ぶ。光の強度に対するショットノイズの大きさは光の強度が小さくなればなるほど大きくなる。
通常、こうしたばらつきは精密な撮像などでSN比向上のために排除するべきノイズ。一方、量子乱数の文脈では純粋状態に対する射影測定の結果生じる確率的な挙動であるから量子乱数として用いることができる。検出される光子数は0,1で等確率ではないし2光子が検出されることもあるため、適切な補正が必要となる。当然ながら測定器やレーザーの電流値揺らぎによるノイズは量子乱数とはみなせず、現実的なレーザー光の光子数には時間的な相関も存在する。このため、実際にこのシステムで量子乱数を構成するにはショットノイズ以外の古典的ノイズの要因が無視できる程度にシステムが安定している必要がある。

原子核のα崩壊

原子核のアルファ粒子は原子核のポテンシャルに閉じ込められているが、トンネル効果のために一定の確率でポテンシャルを通り抜けて原子核外に放出される。トンネル効果によって波動関数がポテンシャル内側と外側に分かれるという操作はユニタリな操作である。よってこれは透過率が小さなミラーに光子を当て、透過したか否かを射影測定することと現象としては等価である。 従って、適切なレートでアルファ粒子を放出する原子集団を準備し、検知器の検知タイミングに適切な補正を施すことで量子乱数源とすることができる。なお原子核のふるまいのエネルギースケールは室温ノイズのエネルギースケールよりはるかに大きいため、上記の観測は室温でも行える。

信頼できない量子デバイスで量子乱数生成

もしチップのベンダに悪意があり、CPUの熱ノイズを取得する関数がメルセンヌツイスタに従う疑似乱数を生成していたとしても、それを我々が検定することは困難である。従って、CPUの熱ノイズを物理乱数として用いるとき、自身がCPUの中身を検査する能力を持たない限りはCPUのベンダが用意した命令の挙動を暗黙に信頼していることになる。現実にはCPUやチップのこうした挙動は最終的に会社の信頼度によって担保されていると思われる。
同様に、もし「量子乱数生成装置」なるものが販売されていたとして、その中身がブラックボックスとなっているとき、この装置を使うことは量子乱数生成のベンダを信頼していることを前提とする。 量子乱数生成器のベンダが社会的信頼をまだ勝ち得ていない場合、デバイスの信頼性の欠如は物理乱数を利用すること以上のリスクとなるため、販売における大きな障害となる。
保証あり量子乱数生成(Certified Quantum Random Number Generation)の研究とは、何らかの現実的な仮定をおくことで信頼できないベンダによる量子乱数生成装置から信頼できる量子乱数を生成する手法を模索する分野。この中で最も有名なものは、量子操作を行える離れた二つの信頼できないサーバ、信頼できる古典計算機、シードとなる少量の乱数を用いて、信頼できる量子乱数を生成する手法である[S. Pironio, et al., Nature 464, 1021 (2010)]。この手法ではBell不等式の破れを二つの敵対的な量子計算サーバによって検証することで、保証された量子乱数を得るといったものである。Bell不等式の上界に古典と量子で差が出る理由は、Bell不等式の量子演算子に対し整合的なjoint probaility distributionを定義できないことに依存する。従って、Bell不等式が破れている状況では、その測定結果に不可避なランダムネスが生じているということである。以下の手法はBell不等式におけるこの性質を利用している。

手順

二つの離れたサーバをA,B, 乱数を生成するプレイヤーをPとする。この時、登場人物はA,P,Bの順番に一次元に並んでおり、それぞれLだけ距離が離れているとする。物理定数として光速をcとする。この時、以下の手順を行う。

1. 二つの離れたサーバA, BかんでBell状態を共有させる
2. Pは\(\mathcal{O}(\sqrt{n})\)ビットの乱数をエントロピープールから消費し、所定の手順でこの乱数から2nビットの数列を作る
3. Pは2nビットのうちnビットをAに、nビットをBに送信する
4. A, Bは指定されたビットに従った基底で、事前に共有したBell状態の片割れを測定し、その結果をPに返却する
5. Pは3の送信から4の返却までに4L/c秒以上かかっていた場合、プロトコルを破棄し、1からやり直す
6. PはAとBが確実に測定したと仮定し、演算子の期待値からBell不等式の破れを検証する。Bell不等式を破っている度合いに応じて受け取った2nビットを縮小し、その結果を乱数とする。

上記のプロトコルではA,Bが誠実である場合、Pは\(\mathcal{O}(n)\)ビットを得る。 A,Bが不誠実であった場合、例えば与えられた指示を無視した基底でベル状態を測定したり、Pに隠れてA,B間で通信を行って共謀してPをだまそうとする。 しかし、A,B間の通信に上記の時間制約があり、かつベル不等式が確かに破れている場合、上記のようなズルではPが乱数を得ることは妨害できない。 従って、「Pは乱数だと思って乱数を続けるが、実はその乱数はAやBによって操作された数列である」という可能性をなくすことができる。

返却までに時間がかかったり、Bell不等式を破らない返答をすることは可能である。この場合PはA,Bが不審であると考え、乱数生成のプロトコル自体を破棄することになる。あくまで「Pが乱数だと思っているものが、実は乱数ではなかった」というケースを排除するプロトコルであって、悪意あるサーバA,Bの妨害を防ぐことができるものではない。
また、このプロトコルを開始するには\(\mathcal{O}(\sqrt{n})\)の量子乱数が開始に必要となる。このため、このプロトコルは純粋な意味での量子乱数生成ではなく、正しくは量子乱数増幅である点にも注意が必要である。

量子フーリエ変換

定義

\(2^n\)成分の配列\(\{x_j\}(j=0,1, \cdots, 2^n-1)\)に対して、その離散フーリエ変換である配列\(\{ y_k\}\)を

\[y_k = \frac{1}{\sqrt{2^n}} \sum^{2^n-1}_{j=0} x_j e^{i\frac{2\pi k j}{2^n}}\]

で定義する。ここで\(k=0, 1, \cdots, 2^n-1\)。配列\(\{x_j\}(j=0,1, \cdots, 2^n-1)\)は

\[\sum_{j=0}^{2^n-1} |x_j|^2 = 1\]

のように規格化されているとする。
量子フーリエ変換のアルゴリズムは、入力の量子状態

\[\left| x\right> = \sum_{j=0}^{2^n-1} x_j \left| j \right> \space (1)\]

を

\[\left| y \right> = \sum_{k=0}^{2^n-1} y_k \left| k\right> \space {2}\]

となるように変換する量子アルゴリズムである。ここで$$\left

j \right>\(は整数jの2進数表示\)i_1 i_2 \cdots i_n \ (i_m = 0, 1)\(に対応する量子状態\)\left

i_1 i_2 \cdots i_n \right>\(の略記です。例えば\)\left

2\right> = \left

00\cdots010\right>, \left

7\right> = \left

00\cdots 0111\right>$$などである。

ここで(1)を(2)に代入すると

\[|y\rangle =\frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^{n}-1} \sum_{j=0}^{2^{n}-1} x_{j} e^{i \frac{2 \pi k j}{2^{n}}}|k\rangle =\sum_{j=0}^{2^{n}-1} x_{j}\left(\frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^{n}-1} e^{i \frac{2 \pi k j}{2^{n}}}|k\rangle\right)\]

よって、量子フーリエ変換では

\[\left| j\right> \rightarrow \frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^{n}-1} e^{i \frac{2 \pi k j}{2^{n}}}|k\rangle\]

を行う量子回路(変換)Uを見つければ良いことがわかる。この式はさらに式変形できて

\[\sum_{k=0}^{2^{n}-1} e^{i \frac{2 \pi k j}{2^{n}}}|k\rangle \underbrace{=}_{和を2進数に変換} \sum_{k_1 = 0}^{1} \cdots \sum_{k_n = 0}^1 e^{2\pi i\frac{k_1 2^{n-1} \cdots k_n 2^0}{2^n} j } \left| k_1 \cdots k_n \right> = \sum_{k_1 = 0}^{1} \cdots \sum_{k_n = 0}^1 e^{2\pi i(k_1 2^{-1} +\cdots +k_n 2^{-n})j } \left| k_1 \cdots k_n \right>\]

因数分解し、全体をテンソル積で書き直すと

\[\begin{align} \sum_{k=0}^{2^{n}-1} e^{i \frac{2 \pi k j}{2^{n}}}|k\rangle &= \left( \sum_{k_1=0}^1 e^{i 2\pi j k_1 2^{-1}} \left| k_1\right>\right) \otimes \cdots \otimes \left( \sum_{k_m=0}^1 e^{i 2\pi j k_m 2^{-m}} \left| k_m\right>\right) \otimes \cdots \otimes \left( \sum_{k_n=0}^1 e^{i 2\pi j k_n 2^{-n}} \left| k_1\right>\right) \\ &= ( \left| 0\right> + e^{i 2\pi j 2^{-1}} \left| 1\right>) \otimes \cdots \otimes ( \left| 0\right> + e^{i 2\pi j 2^{-m}} \left| 1\right>) \otimes \cdots \otimes ( \left| 0\right> + e^{i 2\pi j 2^{-n}} \left| 1\right>) \end{align}\]

ここで

\[0.j_\ell \cdots j_n := \frac{j_\ell}{2} + \frac{j_{\ell -1}}{2} + \cdots + \frac{j_n}{2^{n-\ell + 1}}\]

は2進少数を使う。\(j=j_1j_2\cdots j_n\)のように、整数jを10進数に変換する。10進数において\(10^{-1}\)をかける(10で割る)と小数点が一つ左にズレるのと同じように、jを2で割ると、その2進数表記では小数点が一つ左にズレて

\[j 2^{-1} := j_1 j_2 \cdots j_{n-1}. j_n\]

となる。よってこれをより一般的に

\[j 2^{-\ell} := j_1 j_2 \cdots j_{n-\ell}.j_{n-\ell + 1} \cdots j_n\]

と書く。これを位相部分に代入すると

\[e^{i 2\pi j 2^{-\ell}} = e^{i2\pi j_1 \cdots j_{n-\ell}. j_{n-\ell +1} \cdots j_{n}} = 1\cdot e^{i 2\pi 0.j_{n-\ell+1} \cdots j_{n}}\]

となるので、最終的に

\[\sum_{k=0}^{2^{n}-1} e^{i \frac{2 \pi k j}{2^{n}}}|k\rangle = ( \left| 0\right> + e^{i 2\pi 0.j_n} \left| 1\right>) \otimes ( \left| 0\right> + e^{i 2\pi 0.j_{n-1} j_n} \left| 1\right>) \otimes \cdots \otimes ( \left| 0\right> + e^{i 2\pi 0.j_{n-(m-1)} \cdots j_n } \left| 1\right>) \otimes \cdots \otimes ( \left| 0\right> + e^{i 2\pi 0.j_1\cdots j_n} \left| 1\right>) \tag{*}\]

回路構成

次のアダマールゲートHについての等式

\[H \left| m\right> = \frac{ \left| 0\right> + e^{i2\pi 0.m} \left| 1\right> }{\sqrt{2}} \ (m = 0, 1)\]

と角度\(2\pi/2^\ell\)の一般位相ゲート

\[R_\ell = \left( \begin{array}{cc} 1 & 0 \\ 0 & e^{i 2\pi / 2^\ell} \end{array} \right)\]

を用いる。ここで\(0.m\)は2進少数である。

まず、状態$$ \left

0\right> + e^{i2\pi 0.j_1 j_2 \cdots j_n}\left

1\right> \(を作る。第1量子ビット\) \left

j_1\right> $$にアダマールゲートをかける。

\[\left| j_1 j_2 \cdots j_n \right> \rightarrow \frac{1}{\sqrt{2}} ( \left| 0\right> + e^{i 2\pi 0.j_1} \left| 1\right> ) \otimes \left| j_2 \cdots j_n \right>\]

となる。ここで第2量子ビット$$ \left

j_2 \right> \(を制御ビットとする一般位相ゲート\)R_2\(を第1量子ビットにかける。\)j_2 = 0\(のときは何もせず、\)j_2 = 1\(のときのみ第1量子ビットの\) \left

1\right> \(の部分に位相\)2\pi/2^2 = 0.01$$(2進少数)が付与される。この位相ゲートの意味は制御ビットに

\[i 2\pi \times 0.\underbrace{00\cdots j_k}_{\ell桁} \cdots\]

のように2進少数第\(\ell\)桁目に$$\left

j_k \right>$$の情報を書き込むことである。

\[\frac{1}{\sqrt{2}} ( \left| 0\right> + e^{i 2\pi 0.j_1} \left| 1\right> ) \otimes \left| j_2 \cdots j_n \right> \rightarrow \frac{1}{\sqrt{2}} ( \left| 0\right> + e^{i 2\pi 0.j_1j_2} \left| 1\right> ) \otimes \left| j_2 \cdots j_n \right>\]

以下、\(\ell\)番目の量子ビット$$\left

j_\ell \right>\(を制御ビットとする一般位相ゲート\)R_\ell (\ell = 3, \cdots , n)$$を順番にかけていくと、最終的に

\[\frac{1}{\sqrt{2}} ( \left| 0\right> + e^{i 2\pi 0.j_1j_2\cdots j_n} \left| 1\right> ) \otimes \left| j_2 \cdots j_n \right>\]

次に状態$$\left

0\right> + e^{i2\pi 0.j_2\cdots j_n} \left

1\right>\(の部分を作る。先ほどと同様に第2量子ビットに\)\left

j_2\right>$$にアダマールゲートを作用させれば

\[\frac{1}{\sqrt{2}} ( \left| 0\right> + e^{i 2\pi 0.j_1j_2\cdots j_n} \left| 1\right> ) \otimes \frac{1}{\sqrt{2}} (\left| 0\right> + e^{i 2\pi 0.j_2} \left| 1\right>) \otimes \left| j_2 \cdots j_n \right>\]

再び第3量子ビットを制御ビット$$\left

j_3\right> \(とする位相ゲート\)R_2$$を作用させれば

\[\frac{1}{\sqrt{2}} ( \left| 0\right> + e^{i 2\pi 0.j_1j_2\cdots j_n} \left| 1\right> ) \otimes \frac{1}{\sqrt{2}} (\left| 0\right> + e^{i 2\pi 0.j_2 j_3} \left| 1\right>) \otimes \left| j_2 \cdots j_n \right>\]

これを\(R_{n-1}\)まで繰り返して

\[\frac{1}{\sqrt{2}} ( \left| 0\right> + e^{i 2\pi 0.j_1j_2\cdots j_n} \left| 1\right> ) \otimes \frac{1}{\sqrt{2}} (\left| 0\right> + e^{i 2\pi 0.j_2 j_3 \cdots j_n} \left| 1\right>) \otimes \left| j_2 \cdots j_n \right>\]

を得る。同様の手順で第\(\ell\)量子ビット$$\left

j_\ell \right>\(にアダマールゲートと制御位相ゲート\)R_2, R_{3}, \cdots R_{n-\ell+1} \ (\ell = 1, \cdots ,n-1)$$を順番に作用させていく。最終的に

\[\left| j_1 j_2 \cdots j_n \right> \rightarrow \frac{ \left| 0\right> + e^{i 2\pi 0.j_1j_2\cdots j_n} \left| 1\right>}{\sqrt{2}}\otimes \frac{ \left| 0\right> + e^{i 2\pi 0.j_2j_3 \cdots j_n} \left| 1\right>}{\sqrt{2}}\otimes \cdots \otimes \frac{ \left| 0\right> + e^{i 2\pi 0.j_n} \left| 1\right>}{\sqrt{2}} \tag{**}\]

となる。(**)と(*)では量子ビットの順番が反転している。よって最後に量子ビットの順番をSWAPゲートで反転させれば量子フーリエ変換を実行する回路が構成できたことになる。

コラム: 計算量について

「量子コンピュータは高速に計算を行うことができる」、この意味を考える。

量子フーリエ変換を行うために必要なゲート操作の回数は第1量子ビットにn回、第2量子ビットにn-1回、…、そして第n量子ビットに1回、の合計n(n-1)/2回である。さらに最後にSWAP操作が約n/2回あるから、全て合わせると計算量は\(\mathcal{O}(n^2)\)となる。
一方で古典コンピュータでフーリエ変換を行う高速フーリエ変換は同じ計算で\(\mathcal{O}(n2^n)\)の計算量を必要とする。この意味で量子フーリエ変換は高速。 しかし、フーリエ変換した結果\(\{ y_k\}\)は量子フーリエ変換後の状態\(\left| y\right>\)の確率振幅として埋め込まれているが、この振幅を素直に読み出そうとすると、結局は指数関数的な回数の観測を繰り返さなくてはならない。さらにそもそも入力\(\left| x\right>\)を用紙する方法も簡単でなく、やはり素直にやると指数関数的な時間がかかる。
このように量子コンピュータや量子アルゴリズムを実用するのは簡単ではなく、様々な工夫と技術発展が必要。

位相推定アルゴリズム(入門)

ユニタリ行列の固有値を求める位相推定アルゴリズムについてのメモ。

アダマールテストを改良する

ユニタリ演算Uの固有値\(e^{i\lambda}\)を求める問題を考える。アダマールテストでは、固有値の位相\(\lambda\)はテストの測定結果の確率分布に反映され、測定結果をたくさんサンプルすることで\(\lambda\)を推定した。これを工夫することで、測定結果から位相の情報を直接的に取り出す。

下準備として\(\lambda/(2\pi)\)を2進展開する。

\[\frac{\lambda}{2\pi} = \frac{j_1}{2^1} + \frac{j_2}{2^2} + \cdots + \frac{j_k}{2^k} + \cdots\]

\(j_k\)は0or1の値をとる(古典)ビット。\(\lambda\)は\(e^{i\lambda}\)の形で出てくるため、\(0\leq \lambda < 2\pi\)としても一般性を失わない。この2進展開を以下のように書く。

\[\lambda := 2\pi \times 0.j_1 j_2 \cdots j_k \cdots\]

以下では簡単のため、\(\lambda /(2\pi)\)は小数点以下n桁でかけるものとする。

\[\lambda := 2\pi \times 0.j_1 j_2 \cdots j_k \cdots j_n\]

アダマールテストでは制御ユニタリ演算として\(\Lambda (U)\)を用いたが、ここではそれを変形して\(\Lambda(U^{2^k})\)としてみる。以前と同様に$$\left

\psi \right>$$がUの固有状態であることを仮定。制御ユニタリ演算を行なった後の状態は

\[\frac{1}{\sqrt{2}}(\left| 0 \right> + e^{i2^{k} \lambda }\left|1 \right>) \otimes \left| \psi \right>\]

上述の2進展開を用いて

\[2^k \lambda = 2\pi \times j_1 j_2 \cdots j_k.j_{k+1} \cdots j_n\]

より\(e^{i2\pi j_1j_2\cdots j_k} = 1\)より

\[\frac{1}{\sqrt{2}}(\left| 0 \right> +e^{i2\pi \times 0.j_{k+1}\cdots j_n} \left|1 \right>) \otimes \left| \psi \right>\]

となる。k=n-1のとき

\[\frac{1}{\sqrt{2}}(\left| 0 \right> +e^{i2\pi \times 0.j_n} \left|1 \right>) \otimes \left| \psi \right>\]

よりこれの第1量子ビットにアダマールゲートを作用させると

\[\frac{1}{\sqrt{2}}(\left| 0 \right> +e^{i2\pi \times 0.j_n} \left|1 \right>) \otimes \left| \psi \right> \rightarrow \left| j_n \right> \otimes \left| \psi \right>\]

のように、\(\lambda\)の2進少数表示のn番目のビット\(j_n = \pm 1\)に対応した状態に変換できる。
k=n-2のときは状態は

\[\frac{1}{\sqrt{2}}(\left| 0 \right> +e^{i2\pi \times 0.j_{n-1}j_n} \left|1 \right>) \otimes \left| \psi \right>\]

\(j_n\)は先ほど調べてあるので、\(j_n=0\)のときは何もせず、\(j_n = 1\)のときは一般位相ゲートのエルミート演算

\[R^\dagger_\ell = \left( \begin{array}{cc} 1 & 0\\ 0 & e^{-i2\pi / 2^\ell} \end{array}\right)\]

の\(R^\dagger_2\)を作用させると

\[\frac{1}{\sqrt{2}}(\left| 0 \right> +e^{i2\pi \times 0.j_{n-1}j_n} \left|1 \right>) \otimes \left| \psi \right> \rightarrow \frac{1}{\sqrt{2}}(\left| 0 \right> +e^{i2\pi \times 0.j_{n-1}} \left|1 \right>) \otimes \left| \psi \right>\]

となる。そしてアダマールゲートをかければ

\[\frac{1}{\sqrt{2}}(\left| 0 \right> +e^{i2\pi \times 0.j_{n-1}} \left|1 \right>) \otimes \left| \psi \right> \rightarrow \left| j_{n-1} \right>\]

となるので、\(j_{n-1}\)もこの状態を1回測定するだけで決定できる。以下同様に\(k=n-3, \cdots , 0\)とすれば、下の方のけたから順に\(j_{k+1}\)を決定していくことが可能である。
このようにしてアダマールテストを少し変形することで固有値の位相を1桁ずつ(確定した)量子ビットの状態として取り出すことが可能。この手続きを量子回路でいっぺんに行うのが、以下に説明する位相推定アルゴリズムである。

概要

上述のアルゴリズムの測定側の量子ビットを拡張し、QFTを組み合わせたものが、Kitaevによって提案された位相推定アルゴリズムである。どのような操作ができるアルゴリズムなのかを紹介する。

Uを量子回路として構成できる一般的なユニタリ行列とする。Uの固有状態を$$\left

{\text eigen}\ell \right>\(として、対応する固有値を\)e^{i\lambda\ell}\(とする。一般的な量子状態\)\left

\psi \right>$$が与えられたとすると、これは必ず固有状態で展開できる。

\[\left| \psi \right> = \sum_\ell c_\ell \left| {\text eigen}_\ell \right>\]

このとき位相推定アルゴリズムは、n個の補助量子ビットを用いて、入力状態

\[\left| 00\cdots 0\right> \otimes \left| \psi \right>\]

を

\[\sum_\ell c_\ell \left| \lambda_\ell \right>\left| {\text eigen}_\ell \right>\]

へと変換するアルゴリズムのこと。ここで$$\left	\lambda_\ell \right>\(の固有値は位相\)\lambda_\ell\(の2進少数表示\)\lambda_\ell = 2\pi \times 0.j_1^{(\ell)} j_2^{(\ell)} \cdots j_n^{(\ell)}\(に対応する量子状態\)\left	j_1^{(\ell)} j_2^{(\ell)} \cdots j_n^{(\ell)} \right>$$である。
すなわち位相推定アルゴリズムは$$\left	\psi \right>$$の重ね合わせの中にあるそれぞれの固有ベクトルに対応した固有値をn個の補助量子ビットへと取り出すアルゴリズムのこと。この状態に対して補助量子ビットを測定すると、確率

\[p_\ell = |c_\ell|^2\]

で、どれか一つの固有ベクトル$$\left

{\text eigen}\ell \right>\(とその固有値が\)\lambda\ell$$がランダムに選択される。このアルゴリズムは、素因数分解や量子化学アルゴリズム(分子などのエネルギー計算)、そしてその他多くのアルゴリズムのサブルーチンとして利用されており、量子コンピュータが従来の古典コンピュータよりも指数的に高速に解を得ることができる(と期待されている)もっとも重量な例の一つ。

構成

以下では、入力状態$$\left

\psi \right>\(を固有状態\)\left

{\text eigen} \right>\(とその固有値\)\lambda$$に限定して、位相推定アルゴリズムを説明する。入力状態が固有状態の重ね合わせの場合でも、全く同じ議論ができるため、一般性は失われません。アダマールテストでは1つしか測定用の量子ビットを用いなかった。しかし、位相推定では測定用の補助量子ビットとしてn個の量子ビットを確保する。

再び、ユニタリ演算Uの固有値\(e^{i\lambda}\)の位相\(\lambda\)をnビットの2進少数を用いて

\[\lambda = 2\pi \times 0.j_1 j_2 \cdots j_n\]

と書くことにする(\(\lambda\)の2進少数表示がn桁で終わると仮定する: 終わらない場合は最後の測定の際に若干のエラーが生じるが、測定を繰り返せばこのエラーは克服できる(Nielsen-Chuang参照))。

1. まず、$$\left

   0 \right>\(に初期化されたn個の量子ビットのそれぞれに、アダマールテストと同様にアダマールゲートと制御ユニタリ演算を作用させる。ただしk番目(k=1, ..., n)の補助量子ビットには制御\)U^{2^{k-1}}\(演算をすることになる。\)U \left

   {\text eigen} \right> = e^{i2\pi \lambda} \left

   {\text eigen} \right>\(より、k番目の補助量子ビットには\)e^{i\lambda 2^k}$$の位相が獲得される(位相キックバック)ので

\[\frac{\left| 0 \right> + e^{i2\pi \times 0.j_1 j_2 \cdots j_n} \left| 1 \right>}{\sqrt{2}} \otimes \frac{\left| 0 \right> + e^{i2\pi \times 0.j_2 \cdots j_n} \left| 1 \right>}{\sqrt{2}} \otimes \cdots \otimes \frac{\left| 0 \right> + e^{i2\pi \times 0.j_n} \left| 1 \right>}{\sqrt{2}} \otimes \left| {\text eigen} \right>\]

という状態が得られます。すなわち、固有値の位相を2進少数表示で1ビットずつシフトしたものが各補助量子ビットの位相に格納されることになる。

1. n個の補助量子ビットの状態はQFTの結果の式と全く同じ形をしている。よって逆量子フーリエ変換(\({\text QFT}^\dagger\))をこれらの補助量子ビットに作用させることで

\[\frac{\left| 0 \right> + e^{i2\pi \times 0.j_1 j_2 \cdots j_n} \left| 1 \right>}{\sqrt{2}} \otimes \frac{\left| 0 \right> + e^{i2\pi \times 0.j_2 \cdots j_n} \left| 1 \right>}{\sqrt{2}} \otimes \cdots \otimes \frac{\left| 0 \right> + e^{i2\pi \times 0.j_n} \left| 1 \right>}{\sqrt{2}} \otimes \left| {\text eigen} \right> \rightarrow \left| j_1 j_2 \cdots j_n \right> \otimes \left| {\text eigen} \right>\]

となる。よってこの段階で補助量子ビットの測定を行えば、100%の確率で\(j_1, j_2, \cdots, j_n\)が得られ、Uの固有値の位相\(\lambda\)が求められる。

結言

まとめると、測定用の各量子ビットを制御ビットとする制御\(U^{2^k}\)演算を行い、固有値の位相の情報を補助量子ビットに転写した後、逆量子フーリエ変換で位相の値を取り出す。これが位相推定アルゴリズムである。

具体例

以下のような行列Uの固有値を求めてみよう。

\[U = \left( \begin{array}{cccc} 1 & & & {\mathbf 0} \\ & e^{i\pi/4}& & \\ & & i& \\ {\mathbf 0} & & & ie^{i \pi/4} \end{array} \right)\]

この行列はすでに対角化されているので、固有値の位相は\(\lambda\)は\(0, \pi/4, \pi/2, 3\pi/4\)です。その2進小数表示は\(2\pi \times 0.0, 2\pi \times 0.001, 2\pi \times 0.01, 2\pi \times 0.011\)となります。位相が2進小数3桁で表されているので、これらを誤差なく測定するためには3つの補助量子ビットが必要です。

まずはアダマールゲートを全ての補助量子ビットに作用させる。

次に制御ユニタリをそれぞれ1回, 2回, 4回と作用させる。

すると入力量子ビット$$\left

\psi \right>\(が、\)\left

11 \right>\(のときは対応する固有値\)e^{i3\pi/4}\(に対して補助ビットは011となり、確かに\)\lambda = 3\pi/4\(の2進小数0.011が得られている。同様に\)\left

00 \right>\(なら出力は000、\)\left

10 \right>\(なら出力は010、\)\left

01 \right>$$なら出力は001となる。

コラム: (素因数分解と位相推定)

位相推定の重要な応用例として、素因数分解アルゴリズムをメモ。素因数分解問題はn桁の整数Nが与えられたときに、Nの1ではない約数を見つける問題である。従来のコンピュータでは多項式時間で解けるアルゴリズムは見つかっていない。現在のベストアルゴリズムの計算コストは

\[\mathcal{O}\left( \exp \left[ \frac{64}{9} n (\log n)^2 \right] \right)\]

であり、準指数的な計算時間がかかる。このような素因数分解問題の難しさを利用したRSA暗号などが日常的にも使われている。

ショアは1994年に量子コンピュータを用いることによって素因数分解問題が桁数nに対して多項式時間で解くことができることを示した。これがいわゆるショアの素因数分解アルゴリズムである。

Nを素因数分解したい整数だとしよう。まず、Nと互いに素な整数xを見つけてくる(xはユークリッドの互除法で簡単に見つけることができる。適当にxを取ってきて、ユークリッドの互除法でNとxの最大公約数を計算し、それが1以外の整数であればNの非自明な約数が見つかったことになり、(素)因数分解が完了する。1しかなければxはNと互いに素な整数であることになる)。このときxのNに関する位数rを考えよう。位数rとは

\[x^r \equiv 1 \ ({\text mod} \ N)\]

を満たす最小の整数であり、ランダムにxを選ぶと高い確率でrは偶数になることが知られている。rが偶数であると、上式は

\[(x^{r/2}+1)(x^{r/2}-1) \equiv 0 \ ({\text mod} \ N)\]

のように変形することができる。これはつまり\(x^{r/2} \pm 1 \equiv 0 \ ({\text mod} \ N)\)であるか、\(x^{r/2} + 1\)と\(x^{r/2}-1\)がNと非自明な公約数(Nの因数)を持つかのどちらかであることを意味する。実は、xがランダムに選ばれているとき、後者の確率が十分に高いことも示すことができる。よって\(x^{r/2}+1\)か\(x^{r/2}-1\)とNとの公約数をユークリッドの互除法で用いることにより、最終的に非自明なNの因数が見つかることになる。これを繰り返していくことによってNをどんどん小さな因数へと分解していくことができる。よって最終的に素因数分解が達成される。

そして、素因数分解の鍵となる位数rは、実は入力yをmod Nの素でx倍するという、古典計算に対応したユニタリ行列

\[U_x = \sum_y \left| yx \ {\text mod } \ N \right> \left< y \right|\]

の固有値を求めることによって決定することができる。実際、固有状態のラベル\(0\geq s \geq r-1\)を用いて、固有ベクトルは

\[\left|u_{s}\right\rangle=\frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} e^{-2 \pi i(s / r) k}\left|x^{k}(\bmod N)\right\rangle\]

と書き下すことができ、これは

\[U_x \left| u_s \right> = e^{2\pi i (s/r) } \left| u_s \right>\]

を満たす。すなわちU_xの固有値の位相推定から\(s/r\)を求め、その分母としてrを得ることができる。そして、その位数rから上述の手順でNの素因数分解ができる。これがいわゆるショアによる素因数分解アルゴリズム(キタエフの位相推定を利用したバージョン)である。

応用例

特に位相推定アルゴリズムは量子コンピュータを使いこなす上で非常に大切なもので、様々な応用がある。

1. 素因数分解問題：上記コラムで見たように、位相推定アルゴリズムを用いて位数という数を推定することによって素因数分解を行うことができる。
2. 量子系のエネルギー計算：量子力学において、エネルギーはハミルトニアンと呼ばれる行列の固有値によって与えられる。もっとも安定的な状態のエネルギーはもっとも小さい値の固有値、安定な状態は対応する固有ベクトルで与えられる。ハミルトニアン自体はユニタリー行列ではないものの、行列の指数関数で定義される時間発展に対応するユニタリ行列\(e^{-iHt}\)に対して位相推定を行うことによって、エネルギーを計算することができる。
3. 連立一次方程式\(A x = b\)の求解：位相推定を使って求めた固有値・固有ベクトルを用いることにより、連立一次方程式の解を求めることができる。また、その機械学習への応用も研究されている。

参考文献(というよりこれを見て勉強中)

Quantum Native Dojo