はじめに

　こんにちは、量子研究所の量子アプリCPJの猪谷です。2025年3月28日にFujitsu Uvance Kawasaki Towerで開催されたFujitsu Quantum Day (FQD) 2025 Japanでポスター発表を行いました。今回は、この発表内容をFujitsu Tech Blogの方でも紹介させていただきます。なお、発表した技術自体は、2024年11月17日-22日に米国アトランタで開催されたSC24で発表されたものです [1]。技術の詳細はIEEE QSW24での発表 [2]もご覧下さい。

　今回のFQDでは「Multi-node Decision Diagram-based Quantum Circuit Simulator with Ring Communication and Auto SWAP Insertion」というタイトルで発表しました。決定グラフ型量子回路シミュレータの研究は、約3年前から東京大学と共同で行ってきました。この決定グラフ型量子回路シミュレータは、決定グラフというデータ構造を使って量子状態や量子ゲートを表現して、ノイズの影響のない理想的な量子コンピュータを古典計算機上で模擬して計算します。詳細は、以前このFujitsu Tech Blog記事 [3]でも公開されていますので参照ください。今回の記事では、決定グラフ型量子回路シミュレータのマルチノード化と、ノード間通信の削減方式技術について報告します。

マルチ計算ノードによる決定グラフ型量子回路シミュレータ

　スパコン環境では、たくさんの計算ノードが通信し合いながら協調して計算を進めます。決定グラフ型量子回路シミュレータの場合、状態ベクトルを均等に分割して複数のノードに配分することにしました。図1に示すように、例えば、8つの要素からなる状態ベクトルを、4つのノードで計算する場合、1ノードに2つの要素を割り当てて、決定グラフに変換してデータを扱います。また、1ノードを2プロセスでマルチプロセス計算する場合は、使用するノードは2つとして、1ノードに4つの要素を割り当てます。したがって、マルチノード化することで計算を並列処理して高速化が期待できる一方、ノード毎に保有するデータが異なり、ノード間通信が必要になることから、通信オーバーヘッドに気を付ける必要があります。

リング状通信と自動スワップゲート挿入

　マルチノードによる決定グラフ型量子回路シミュレータの高速化を実現するために、ノード間通信を削減して通信オーバーヘッドを減らすることを目指します。下記の2つ技術を適用することでシミュレーションの高速化を図りました。

リング状通信
自動スワップゲート挿入

リング状通信

　はじめに、ある量子状態に対して量子ゲートを作用させた後に新たに得られる量子状態を求める行列ベクトル積のマルチノード計算について説明します。例えば、4つのノードにおける乗算は式(1)で表すことができます。各ノードのサブベクトルは $v1, v2, v3, v4$ で、量子ゲートのサブ行列は $w11, …, w44$ です。このとき、 $v'2, v'3, v'4$ を計算するには、全て $v1$ が必要です。よって、この $v1$ を各ノードに伝達する必要があります。図2の中の赤色の矢印はノード間通信を表しており、左側の図は一般的なノード間通信方式を示しています。ノード $i$ が持つサブベクトル $v_{i}$ は、他のすべてのノードとノード間通信を行います。一方、右側の図はリング型通信方式を示しています。左側の図と比べて、赤色の矢印の数が減っていることが分かるかと思います。ノードをリング状に接続しており、ノード $i$ が持つサブベクトル $v_{i}$ は、隣接するノード $v_{i+1}$ とのみノード間通信を行います。最終的な計算結果はどちらも同じで、ノード間通信方式のみが異なります。ノード間通信が減ることで、通信オーバーヘッドが減り、並列計算を高速化できます。

自動スワップゲート挿入

　図3は、3量子ビットの回路の第1量子ビットと第3量子ビットにそれぞれHゲートを作用させたときの計算式です。4つのノードで計算する場合、Hゲートを第1量子ビットに作用させた場合は、各ノードが持つ要素のみで計算できます。例えば、Node1では $a$ と $b$ のみ、Node2は $c$ と $d$ のみで計算できます。一方、Hゲートを第3量子ビットに作用させた場合は、他のノードが持つ要素も必要になります。例えば、Node1では $a$ と $b$ に加えて、Node3が持つ $e$ と $f$ も必要です。同様に、他のノードでも、自身以外の他のノードが持つ要素が必要です。つまり、Hゲートを第3量子ビットに作用させた場合は、ノード間通信が必要になります。一般的に表すと、 $2^{M}$ 個のノードを使って $N$ 量子ビットの回路を計算する場合、最初の $N-M$ 量子ビットに作用する量子ゲートは、各ノード内が持つ要素のみで計算できるが、最後のM量子ビットに作用するゲートは、他のノードが持つ要素が必要になるため、ノード間通信が必要です。よって、ゲートは最初の $N-M$ 量子ビットに作用させることが望まれます。

　この要望を満たすために、スワップゲートを挿入することでノード間通信を削減しました。図4の左側の回路では、最後の量子ビットに4つのゲートが作用しているため、ゲート分のノード間通信が発生します。この回路に対して、4つのゲートの前後にスワップゲートを挿入します。これによって、計算して得られる結果は同じですが、ノード間通信は2つのswapゲートに対してのみ必要になります。swapゲートが増えることで必要な計算は増えますが、ノード間通信が減少するため、全体的な実行時間を短縮することができます。

実験結果

　はじめに、Shorのアルゴリズムを対象に、ノード数を1～256個として実行時間を求めて、その結果を表1に示しました。また、決定グラフ (DD)型だけではなく、参考として状態ベクトル (SV)型の結果も記しました。511を素因数分解した場合において、1ノードで1391秒要していましたが、256ノードで計算することで137秒に短縮しており、約10倍高速化できました。また、SV型では、1ノードと256ノードの実行時間を比較すると、約88倍高速化していました。よって、マルチノードによる高速化の効果はSV型のほうが大きかったです。ただし、実行時間自体はDD型の方が短く、1～256個のノードにおいて、数十倍～1000倍程度高速に計算できました。ShorアルゴリズムではDD型の使用が推奨されます。

表1　DD型とSV型の実行時間

Simulator	Number	nQubits	nGates	# Nodes & run-time (sec)
Simulator	Number	nQubits	nGates	1	2	4	8	16	32	64	128	256
DD	511	38	400,123	1,391	403	366	251	212	187	172	145	137
DD	253	34	204,223	2406	1420	892	636	525	530	356	331	326
DD	123	30	118,005	68	63	54	48	39	38	35	35	46
DD	57	26	51,123	39	30	21	17	14	14	15	16	24
SV	57	26	51,123	48,039	24,714	12,706	7,242	3,705	2,097	1,315	845	548

　次に、1ノード当たりのプロセス数を1、2、4として実行時間を比較した結果を表2に示しました。例えばプロセス数が2048で4process/nodeの場合は、512ノードが使用されて、各ノード内では4プロセスで計算します。その結果、プロセス数が同じ場合は、1ノード当たりのプロセス数が少ない方が実行時間が短くなりやすいことが分かりました。また、同じ計算ノード数でプロセス数を増減させても、実行時間は大きく変わらないことが分かりました。しかし、この傾向は256プロセスまでで、512プロセス以上では、1ノード数当たりのプロセス数を増やした方が実行時間が短くなっていました。原因として通信オーバーヘッドが考えられます。1ノード内で複数のプロセスを立ち上げる場合、CPUの計算リソースやメモリ帯域はプロセス間通信にも利用されます。その結果、隣合う計算ノードと通信するだけですむ1プロセスの時よりも実行時間が長くなってしまうと考えられます。なお、上で述べたように、512プロセス以上では、1ノード数当たりのプロセス数を増やした方が実行時間が短くなっていました。この原因は、ラック間通信のオーバーヘッドと考えられます。使用したシステムは1つのラックに最大384計算ノードが収められています。よって、256ノードまではラック内通信で計算を完了させることができます。しかし512ノード以上ではラック間通信が必要となるため、実行時間が大幅に増加してしまうと考えられます。ラック間通信を避けつつ、基本的には1ノードあたり1プロセスでシミュレーションすることが望ましいことが分かりました。

表2　マルチプロセスによるDD型の実行時間

Process	1	2	4	8	16	32	64	128	256	512	1,024	2,048
1 process/node	1,391	403	366	251	212	187	172	145	137	167	161	441
2 process/node		1,387	405	371	253	213	193	166	145	146	164	232
4 process/node			1,392	410	372	251	213	189	165	147	142	159

おわりに

　本記事では、2025年3月28日に開催されたFQDでポスター発表した内容を、このFujitsu Tech Blogの方で紹介させていただきました。実際のポスター発表では、1時間という短い時間でしたが、共同研究しているお客様や研究者、学生の方など多様な人々との議論を通じて意見交換でき、SV型と比べてDD型が圧倒的に高速であること興味を持っていただきました。どのようなアルゴリズムでも同じ効果が得られるのか、どのような応用が期待できるかなど、DD型シミュレータ研究への期待を実感できました。今後も引き続き、富士通の量子研究に少しでも貢献できるよう努めていきたいと考えています。

参考文献

[1] Kimura, Y., Koyama, J., Li, S., Sato, H., & Fujita, M. QDD: Multi-node Implementation of Decision Diagram-based Quantum Circuit Simulator with Ring Communication and Auto SWAP Insertion. SC24 Poster
[2] Kimura, Y., Li, S., Sato, H., & Fujita, M. (2024, July). Accelerating Decision Diagram-based Multi-node Quantum Simulation with Ring Communication and Automatic SWAP Insertion. In 2024 IEEE International Conference on Quantum Software (QSW) (pp. 107-115). IEEE.
[3] 決定グラフ型量子シミュレータのご紹介 - fltech - 富士通研究所の技術ブログ