幾何学的な量子アルゴリズム生成問題における距離の評価 *中島孝雄（学籍番号200821668）

研究指導教員：鎮目浩輔
副研究指導教員：松本紳つまり、単位行列 I と計算に対応する Unitary

１．研究背景量子計算は量子力学に基づく新しい計算手法

行列 W を結ぶ qubit 数 n の多項式曲線が得られであり、ある種の問題を古典計算よりも効率的にれば、その曲線を基に必要なゲート数が n の多解くことが可能だと言われている。

項式で増える効率的な量子アルゴリズムを生成

量子計算とは spin と呼ばれる物理量の状態をできることを示した。従って I と W を結ぶ最短曲線

磁場や相互作用のコントロールで変化させ、計が得られれば、最も効率の良い量子アルゴリズム

算作業に対応するような時間的変化を起こすことが作れる。しかし二点間を結ぶ最短曲線の具体である。量子計算では spin のことを qubit と呼ぶ。

的な探索方法はいまだ不明である。

数学的には qubit は複素列ベクトルで表され、状ま た 、 Nielsen 等 は ゲ ー ト 数 G(W) と 距 離態の変化はその列ベクトルにある Unitary 行列をD(I,W)(最短曲線の長さ)の間に以下の関係があかけることで表される。

ることを示した。

複雑な計算では複数の qubit を相互作用させD(I,W)≦G(W)て状態を変化させることが必要であるが、それをこれは曲線の長さが実際に必要なゲート数以一度に行うことは難しいため、あらかじめ決めら上だった場合には、その曲線は最短ではないこれた数種類の量子ゲート（一つの qubit のみに磁とを意味する。

場をかけるか、二つの qubit に CNOT と呼ばれる

2.2 Time complexity and gate complexity [2]相互作用をさせる操作）を逐次的に qubit に施す。

Koike 等は時間をコストとした Unitary 行列生

この量子ゲートを qubit に逐次的に施す順番のこ成問題に最適制御分野で知られている Krotovとを量子アルゴリズムと呼ぶ。数学的には計算作法[3]を適用し、次のことを示した。(1)量子フーリ業に対応する複雑な Unitary 行列 W を量子ゲー

エ変換 QFT の時間コストは n の多項式。(2)多重トでの変化に対応する単純な行列 gi の積として制御 NOT Cn-1NOT の時間コストは n の指数関数。

分解することを意味する。

(3)量子フーリエ変換 QFT の 2qubit Hamiltonian

W=gmgm-1gm-2…g2g1
量子アルゴリズムが効率的であるためには、W成分は対称性を持つ。

３．研究概要が与えられたとき W の構築に必要なゲート数の本研究では、Krotov 法を Nielsen 等の最短曲増加が qubit 数 n の多項式で済むことが要求さ線探索問題に適用し、指定した二点間を結ぶ測れる。W の量子アルゴリズムを生成する一般的な地線を探索する手法を開発した。測地線とは長方法は存在するが、この条件を満たすことは困さが極値をとる曲線で、最短曲線の候補となるも難である。のである。そして、開発した測地線探索手法を用

２．先行研究いて次のことを行った。(1)2qubit における Krotov

2.1 Quantum Computation as Geometry [1]法の漸化式の働きの可視化。(2) 単位行列 I と量この問題に対し、Nielsen 等は行列空間上に子フーリエ変換 QFT(n=3,4,5)を結ぶ測地線の探長さを定義しアルゴリズム生成問題を幾何学の索およびその長さの計算。(3) 単位行列 I と多重曲線探索問題に作り変えた。

制御 NOTCn-1NOT(n=3)を結ぶ測地線の探索およ び そ の 長 さ の 計 算 。 (4) 得 ら れ た 測 地 線 の* “Estimations of distances of the geometry ofquantum computation” by Takao NAKAJIMA

Hamiltonian の成分の調査。

等の長さは 25.2 であり、構築に必要な量子ゲ

４．シミュレーション結果

ート数 16 よりも多く Nielsen 等の不等式を満4.1 2qubit における Krotov 法の漸化式の可視化たしていない。

Gu 等[4]は Nielsen 等の長さの定義の下で開発した手法を用いて、単位行列 I と多重2qubit における距離の近似式を導出した。こ制御 NOT C3-1NOT を結ぶ測地線を探索し、そのの近似式は三次元ユークリッド空間として可長さを計算した結果、Nielsen 等の不等式を満視化することができるため、可視化によってたす測地線を得た。その長さは 1.8 である。

Krotov 法の漸化式がどのように働くかを調べ5．結論た。その結果次のことが分かった(1)漸化式を5.1 考察

繰り返し解くことによって得られる曲線は新今回得られた測地線は最短とは言い切れなしいものほど終点が W に近づき、同時に曲線いが、全て Nielsen 等の不等式を満たす。ま

自体が測地線に収束する。(2)曲線の長さが距た、QFT(3)では 43-1 個の初期曲線を取ったが離よりも長い場合は測地線に収束せず曲線は全て同じ結果となった。これらは本研究で開たるむ。

発した手法が最短測地線を探す手法である可能性を示唆していると考えられる。
量子フーリエ変換の長さが n の多項式であることや、Hamiltonian の対称性は Koike 等の時間をコストとした最適解の性質と同等であることから、ゲート計算量と時間計算量との間に密接な関係があることが考えられる。
5.2 課題開発した手法は n に対して指数関数的に計算時間がかかるため改良が必要である。

図 1:Krotov 法の漸化式による測地線探索。

U0(t)、U1(t)、U2(t)と新しい曲線ほど終点がW に近付く。最終的には I と W を結ぶ線分(測地線)に収束する。
4.2 単 位 行 列 I と 量 子 フ ー リ エ 変 換QFT(n),n=3,4,5 を結ぶ測地線の探索とその長さ開発した手法を用いて、単位行列 I と量子フーリエ変換 QFT(n),n=3,4,5 を結ぶ測地線を探索し、その長さを計算した結果次のことが分かった。(1)測地線の長さは n の多項式でゲート計算量と時間計算量の関係を調べるため、qubit 数を増やして Cn-1NOT の長さの計算を行うことが必要である。これは n の指数関数で増えると予想される。また、他のUnitary 行列(例えば置換)に対してシミュレーションを行うことも考えられる。
さらに得られた測地線の最短性を調べる必要がある。例えば幾何学のツール CutPoint を計算する機能を追加することが挙げられる。

文献増加する。(2)測地線の長さはゲート数の 1/4[1]Nielsen,Dowling,Gu,Doherty.QuantumCompu倍以下であり、Nielsen 等の不等式を満たし

tation as Geometry.Science311,p1133(2007)ている。(3)2qubit Hamiltonian は対称性を[2]Koike,Okudaira.Time complexity and gate持つ。

complexity.quant-ph/0910.5587v1(2009)

4.3 単位行列 I と多重制御 NOT C3-1NOT を結ぶ[3]Krotov,Global Methods in Optimal Control

測地線の探索とその長さ
本研究で多重制御 NOT Cn-1NOT の厳密解の一つを見出した。但し、n=3 の場合の Nielsen

theory.Marcel Dekker Inc(1995)[4]Gu.Quantum control via geometry:An explicit
example.PRA78,032327(2008)