欠損の無い単一原子アレー形成の為の最適経路探索プログラムの開発
中川研究室 学部 4 年 西本捺美
1. 研究背景のある原子アレーが作成され、目的の位置に原子を極低温まで冷却すると原子は量子的原子が全てローディングされるまで時間がかな性質を現す。その性質は量子情報処理に応かるという問題が起きる。この問題に対し、用でき、現在様々な研究が行われている。量短時間で欠損のない原子アレーを作成するた子情報処理の一例として、量子シミュレーシ

めにローディングした原子を欠損位置に光ピョンが挙げられる。量子シミュレーションは、ンセットを用いてこのように再配置するとい計算機では解析困難な物理系を他の量子系をう方法に着目する。原子の初期位置ごとに原用いて再現するというものである。結晶や磁子の輸送経路をパターン化し、データを保存性体、超伝導など多数の原子が存在する系でしておくことですぐに再配置を完了できるよは計算量が指数関数的に増加するため、物性うにする。トラップからの原子の拡散をなるを解析するのは難しい。例えば最もシンプルべく防止するため、出来るだけ少ない手順やなイジングモデルを考えると、原子が５０個衝突を避けた経路での原子の輸送パターンをある系を仮定するとそれぞれのスピンの向き作成する必要がある。本研究では、原子の欠を考えるため、250 通りの状態が存在するこ損につながるような要因である、輸送距離やとになり、計算機での計算は困難である。こ原子を動かす手数などを輸送コストとして考の問題に対し、冷却原子を並べることで目的え、輸送コストの少ない原子とターゲットのの物理系を実験室で再現、観測可能にする試

輸送経路を選ぶアルゴリズムの選択とプログみが行われている。我々の研究室ではこのよ

ラムの開発を目的として研究を行った。

うな量子シミュレーションの実現を目指して、計算機で計算困難かつ実験室で再現可能である、５０～１００個ほどの原子からなる原子アレーの作成を目標としている。

2. 研究目的

3. 総当り法
まず、考えうる全ての組み合わせを検索し最適な解を求めるという総当たり法を利用したプログラムを作成した。ある原子𝑎𝑖 を、ターゲット𝑡𝑗 へ輸送する時にかかるコストを𝑑𝑖𝑗 と単一原子アレー形成において課題が存在す表す。全てのコストを距離行列Dとして表し、る。目的の形に並べた光双極子トラップによコストの合計𝑑𝑡𝑜𝑡𝑎𝑙 が最小となる𝑎と𝑡の組みり原子をローディングし原子アレーを形成す合わせ𝑓: 𝑇 → 𝐴を求める。(T = {𝑡𝑖 |1 ≤ 𝑖 ≤ 𝑁},

るが、１つのトラップに原子がローディング

𝐴 = {𝑎𝑗 |1 ≤ 𝑗 ≤ 𝑁𝐴 }, 𝑁:ターゲットの総数,𝑁𝐴 :される確率は 1/2 であるため、n 個のトラッ原子の総数)

プがある場合全てのトラップに原子が充填される確率は(1/2)50 となり、50 個の原子があ𝑑𝑖,𝑓(𝑖) = |𝑡𝑖 − 𝑓(𝑡𝑖 )|(1)

𝑑𝑡𝑜𝑡𝑎𝑙 = ∑𝑖 𝑑𝑖,𝑓(𝑖)(2)る場合、1 回のローディングには 100 ms の時間を要するため、全ての原子がローディングされるまで約 357 万年かかる計算になる。よって、何度ローディングを繰り返しても欠損

D=𝑑1 1𝑑2 1⋮𝑑1 2𝑑2 2[𝑑25 1𝑑25 2⋯

𝑑1 25⋮⋱⋯

𝑑25 25 ]

=05
⋮

50⋯

28.3⋮

⋱

[28.3 25⋯

4. ハンガリー法(3)n 人の人に n 個の仕事を割り当てる時、それぞれの人がそれぞれの仕事をする為にかか0 ]るコストを最小にするような割り当てを考える問題がある。ハンガリー法はこの割当問題を簡単に解くことができるアルゴリズムであるが、n 個の原子に n 個のターゲットを割り当てる問題として置き換えハンガリー法を利用する。それぞれのターゲットに対する原子の輸送コストを表 1 のように表す。今回は簡単のため原子とターゲット間の直線距離を輸
図1

原子とターゲットの位置例(𝑖) 𝑑1 6 + 𝑑2 7 = 5 + 5{(𝑖𝑖) 𝑑2 6 + 𝑑1 7 = 7.1 + 7.1

𝑑𝑡𝑜𝑡𝑎𝑙 = 10𝑑𝑡𝑜𝑡𝑎𝑙 = 14.2

送コストとした。これを行列として書き表し(4)たものがコスト行列である。𝑡1 －𝑎4 、𝑡2 －𝑎5 、𝑡3 －𝑎6 という割り当てを順列 σ = 〈4,5,6〉 と輸送コストの値は簡単のために、原子とタ表し、コスト行列が C のとき順列σに対応しーゲット間の直線距離とした。例として𝑑1 6 のて割り当てたときの総コストを C(σ)で表す

値は図 1 より 5 μmである。この場合、原子とことにする。C(σ)を最小にするσを求めるこターゲット間の直線距離の合計が最小であるとに問題は帰着される。

組み合わせが最適解として求められ、図 2.2 の場合の問題を考えると原子とターゲットの組
み合わせは①𝑎1 →𝑡6 、𝑎2 →𝑡7 ②𝑎1 →𝑡7 、𝑎2 →𝑡6の 2 通り存在し、式(4)より𝑎1 を𝑡6 へ輸送しさらに𝑎2 を𝑡7 へ輸送する組み合わせが解である。
この方法では全ての組み合わせを計算する

表1

輸送コスト(単位：μm)

為、原子やターゲットの数が多くなるにつれて組み合わせの総数が爆発的に増加するとい具体的な解き方を表 2 を例として説明する。

う問題がある。我々の研究室では将来的に７

手順 1：各行の各要素からその行の最小値を×７個のトラップ内に５×５個の大きさの原引き、さらに各列の各要素からその列の最小子アレーを作成したいと考えているが、例え値を引く(図２)。

ばその範囲の中で原子 40 個に対してターゲ

手順 2：0 を各行各列から一つずつ選ぶことがット 25 個の総当たりを考えるとすると、組みできれば、その 0 の位置の組が割り当て案と合わせの総数はなる。出来なければ次の手順に進む。

40 𝑃25通り、つまり約6.24 ×10 通りとなり計算は不可能に近い。よって、

手順 3：全ての 0 をできるだけ少ない数の縦総当り法は比較的小さい範囲の原子アレーをか横の線で覆う(図 3)。

作成する場合に有用な手法だと言える。また

手順 4：線で覆われていない要素から、それら最適な解を求めることが出来るため、他のアの最小値を引き、縦横の線の重なっている要ルゴリズムにより求めた解と比較しその解が素に加える(図４)。手順 2 に戻り割り当て案最適かどうかの指標として利用することが出が完成するまで手順 3～4 を繰り返す。

35

来る。

○5×5 正方格子 原子 6 個、ターゲット 3 個の場合の例

表 2 コスト表

図 2 手順１

図 7 総当り法 1 解①

図 8 総当り法 1 解②

図 7、8 のように総当り法のプログラムでは、等価な解は全て表示されるようにした。この
図３ 手順３図 4 手順 4場合

6 𝑃3 = 120通りの組み合わせから、総輸送距離が最小である解が 2 つ選ばれたことを示す。
○７×７正方格子 原子 9 個、ターゲット 9 個の場合の例
図５ 割り当て案１

図 6 割り当て案 2

コスト行列は 1：1 の組を作り出すので正方行列でなくてはならないが、原子とターゲッ
トの数に差異があった場合、ダミーのターゲットを増やし正方行列にする必要がある。ハンガリー法は、アルゴリズムの計算量がO(𝑛3 )で表されるように総当り法O(n!)と比較し計

図9

総当り法 2算が簡単である。原子やターゲットの個数により総当り法では計算が不可能である場合で9 𝑃9 = 362880通りの中で総輸送距離が最小も、ハンガリー法であれば計算が可能になるな解が１つのみ求められたことを示す。と考えられる。

○様々な形の原子アレー例

5. 総当り法を利用したプログラム
プログラムは MATLAB により作成した。
原子とターゲット間の直線距離を輸送コストとして、最適な原子とターゲットのペアを矢印で結び表示させる。以下にプログラムによって表示された図を載せる。黒丸がトラップの位置、青丸が原子の初期位置、赤丸がターゲットの位置である。トラップの配列は正方格子以外にも座標を変えて様々な形に配置させた。

図 10 リング型
図 10 では

図 11 ハチの巣型

10 𝑃5 = 30240通り、図 11 では

6 𝑃6 = 720通りの中からそれぞれ最適解が１つ求められたことを示す。

6. ハンガリー法を利用したプログラム
前記のプログラムとは異なり、等価な解があったとしてもプログラム上で最初に求められた解だけを表示する仕様である。
○原子 13 個、ターゲット 13 個の場合の例○原子 20 個、ターゲット 20 個の場合の例

ットの数が 9 個以下の範囲でハンガリー法は最適な解を求めることを評価できた。
7. 結論
原子輸送経路の検索に適したアルゴリズム
から 2 つのプログラムを作成し、経路を原子とターゲットを結ぶ線として表示することが出来た。総当り法とハンガリー法の結果が比較する限り等しくなったことから、少なくとも原子やターゲットの数が少ない場合でのハンガリー法の最適性が示された。またその計算量の少なさから、ハンガリー法は輸送経路

図 12 ハンガリー法１

図 13 ハンガリー法２をあらかじめ計算しデータとして保存するという最終的な目的にも使用できるアルゴリズ

上記の結果から、1 回の動作で総当り法より多くの原子やターゲット数の計算が可能であった。

ムとして現実的であると考えられる。
今回は輸送経路の計算に使用するアルゴリズムを考え、それらを使ったプログラムの開また、原子とターゲットを同様に配置し、2つのプログラムで結果に差異が出るか比較することでハンガリー法の解の最適さを検証した。以下が比較した結果である。

発と簡単な条件の場合の下でのシミュレーシ
ョンを行った。それらの結果から考えられる
今後の研究の課題として、まず当初の目的としていた 50 個程度の原子の場合に計算が可能になるよう、コスト行列を解く際に発生するプログラムのエラーを取り除くことが挙げられる。また、実際に実験に応用できるようなプログラムにすることを目指し、様々な条件に対応可能な仕様を実装することが挙げられる。例として、輸送コストの値の検証である。経路として避けたいトラップの位置や優先的に選びたい位置を輸送コストの重みとして値に反映することによって、より柔軟な場面に対応できると考えられる。さらに、
図 14総当り法(左)とハンガリー法(右)の比較

図 14 の左側が総当り法による計算結果、今回の結果のみでは原子の数が 9 個以上だった場合のハンガリー法の最適性が評価できなかったため、輸送コストの値を変えることで右側がハンガリー法による計算結果である。

評価する必要がある。

隣同士の結果を比較すると、全く同じ解が求

8. 参考文献

められたことがわかる。総当たり法で求めら

Woojun Lee, Hyosub Kim, and Jaewook Ahn.Defect-free

れた結果は最適解であるので、原子やターゲ

atomic array formation using Hungarian matchingalgorithm.Phys.Rev. A, 053424 (2017)