Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

CVRPに対する量子アニーリング方式の決定変数削減

Akiyoshi Wakatani

Published Jul 31, 2024• 0 citations
Publisher

Abstract

量子コンピューティングの方式のひとつとして量子アニーリング方式が注目され, 組合せ最適化問題へ実用的な利用が進んでいる, 量子アニーリングはイジングモデル上のスピングラス問題を 解くものであるが, 昨今は, その手法を起源としたデジタルマシンも多く考案され, 本稿で用いたGPUベースのFixstars Amplify Annealing Engineもその一つである. 本稿では, 組合せ最適化問題の一つである容量制約つき運搬経路問題に対して, 最適解探索に用いる決定変数を削減するための2個の手法で実装し, 性能を評価した. ルート数を考慮して決定変数を削減する場合に, 決定変数の一部の値を固定化して削減する方法と決定変数の生成自体を削減する方法を評価し, 前者の方法は決定変数削減による高速化の効果は限定的であるが, 後者の方法は, 訪問都市数に依存するものの,概ね2倍程度の高速化が達成できた.

DOI
10.14990/0002000465

Related papers

物流問題に対する量子アニーリングによる実装と制約条件の影響

Akiyoshi Wakatani

次世代の計算方式として量子コンピューティングが注目されている. その実現方式の一つである量子アニーリングは組合せ最適化の分野で実用レベルでのアプリケーションが扱われ, 特に既存デバイスを用いた疑似的量子アニーリングマシンは多数の提案と実稼働がされている. 一方で, 働き方の改革に起因する物流業界の効率化が急がれており, 移動コストと人件費コストの最小化は大きな課題である. 本稿では, Fixstars Amplify Annealing Engineを用いて物流問題の最適化の実装を行い, その制約条件の増加と最適解を求める実行時間の関係と, 実行時間を削減するための効率化について述べる. 丁寧な最適化を求めるためには制約条件は複雑になるが, それによる求解時間の増加は顕著であり, 決定変数の初期化により制約条件を減少することにより求解時間を削減できることを実験的に確認した.

•Aug 8, 2025•0 citations

[技術・研究報告] 組合せ最適化問題に対する量子アニーリング方式の試用と考察

彰良 若谷, Wakatani Akiyoshi

近年, 量子計算が注目されている. 量子計算には量子ゲート方式と量子アニーリング方式があるが, 実用的に利用されているいるのは後者であり, デジタル方式のものも含め複数の実機が発表されている. しかし, 実問題をイジングモデルの相互作用とバイアスに変換することは煩雑であり, 自動的にイジング最適化を行なうソフトウェアの利用が重要である. 本稿では, そのためのソフトウェアの一つであるFixstars Amplify を用いて巡回セールスマン問題をFixstars Amplify Annealing Engine上で実行し, 古典的ソルバーのGLPK (GNU Linear Programming Kit) のオンプレミスのLinux マシン上での実行結果との比較を行い, その試用を通して実用性の考察を行なう.

•Jul 30, 2022•0 citations

スタッフ配置制約を含む物流最適化問題に対する量子アニーリングを用いた実装

Akiyoshi Wakatani

ムーアの法則の限界が指摘される中,次世代の計算方式として量子計算が注目されている.その関連手法である量子アニーリングは,擬似的な実現方式を含め,数理最適化分野において実用レベルのアプリケーションが利用されている.一方,引越し業界をはじめとする物流業界でも効率化が急務となっており,移動コストおよび人件費コストの最小化は重要な課題である.このような課題に対し,量子アニーリングを用いた最適化は有効な解決策となり得る.本稿では,FixstarsAmplifyAnnealingEngineを用いて物流最適化問題を実装し,スタッフ間の相性や教育関係を考慮した配置制約に着目する.これらの制約条件の増加が最適解探索の実行時間に与える影響を評価するとともに,実行時間削減のための効率化手法を検討する.その結果,決定変数の扱いを工夫することで,追加の制約を導入することなく同等の最適化が可能となり,求解時間を短縮できることを確認した.

•Sep 11, 2026•0 citations

Combinatorial Optimization by Quantum Neural Networks and Its Applications

Mikio Hasegawa

近年，イジングハミルトニアンのエネルギー最小化を利用した最適化問題の解法が検討されている（S. Utsunomiya et al., Optics Express 19, 2011）．また，そのような手法を大規模に実装する技術の研究も進んでいる（T. Inagaki et al., Science, 234, 2016）．本稿では，このようなハードウェアで実現する量子ニューラルネットワークを用いた組合せ最適化アルゴリズムを検討する．対象とする組合せ最適化問題の目的関数は，イジングスピンの相互結合に実装することとなる．相互作用によるエネルギー最小化を用いた最適化問題の解法は，Hopfield-Tank Neural Network を用いた従来研究において様々な組合せ最適化問題に適用されてきた．本稿では，Hopfield-Tank Neural Network を用いた巡回セールスマン問題の解法を，量子ニューラルネットワークで動作させる方法を説明する．シミュレーション結果を示しながら，提案手法の有効性を示す．

IEICE ESS FUNDAMENTALS REVIEW•Jan 1, 2017•0 citations

強相関電子系の有限温度計算手法の開発と励起子絶縁体への応用

コウダイ スギモト, K. Sugimoto, 高大 杉本

電子が互いに強く相互作用する強相関電子系を対象に、有限温度の計算手法の開発と具体的問題への適用を目的とする研究を行った。有限温度においてはフェルミオン対がボーズ凝縮するよりも高温でプリフォームド対が出現したり、幾何学的フラストレーションを有する系において金属・絶縁体転移が生じたりするなどの興味深い物理現象が実験において多数観測されており、理論的に有限温度の計算手法を確立させることは極めて重要である。 従来から有限温度計算によく使用されている量子モンテカルロ法では、電子のようなフェルミオン系において「負符号問題」により特殊な例を除いて計算が実行できなくなることが知られており、その普遍的解決策は見つかっていない。そこで、本研究では有限サイズのクラスターの状態を求め、その結果を無限系へと接続する変分クラスター法(VCA)に注目した。またこの手法の特徴として、平均場を導入することにより有限温度の相転移を議論することも可能である。クラスター内の状態を求める際、素朴には厳密対角化(ED)によって得られた固有状態を使ってカノニカル平均をとることで有限温度での性質を調べることができるが、クラスターのサイズが著しく制限されてしまう。これを解決するため、熱的純粋量子(TPQ)状態を用いた有限温度計算を提案した。この手法はEDに比べて比較的大きなサイズのクラスターを扱うことができ、EDで顕著に現れる有限サイズ効果の抑制につながる。 VCAとTPQ状態を組み合わせた手法の妥当性を調べるために、2次元正方格子上のハバード模型に適用した。有限温度における平均場秩序変数、熱力学量、励起スペクトルの温度依存性の計算に成功し、その有用性を示すことができた、今後はこの手法を元にして、励起子絶縁体の有限温度におけるプリフォームド励起子対生成に伴う物理現象の解明を目指す。 I developed a numerical method to investigate finite-temperature properties of strongly correlated electron systems, and applied it to some problems. At finite temperatures, many intriguing physical phenomena have been observed in experiments, such as the appearance of preformed pairs above the transition temperature of the Bose-Einstein condensation and the metal-insulator transition in geometrically frustrated systems. Therefore, it is quite important to establish a theoretical method to calculate the physical properties at finite temperatures. In quantum Monte Carlo methods, which are often used for finite-temperature calculations, it is well known that a "negative sign problem" disrupts calculations of fermionic systems, except for several special cases. In this study, I focus on the variational-cluster approach (VCA), which an infinite-system state is constructed from the state of a small-size cluster. In addition, we are also able to discuss a finite-temperature phase transition by introducing a mean-field term. Although we can in principle obtain the physical quantities of the cluster at finite temperatures by taking the canonical-ensemble average with the eigenstates obtained from the exact-diagonalization (ED) method, the size of the cluster is severely restricted. To solve this problem, we make use of the method based on thermal-pure-quantum (TPQ) state. This method can treat a relatively large cluster compared to the ED method, and thus it can suppress the finite-size effect that often appears in ED method. I investigated the validity of the method combining VCA and TPQ states. I succeeded in calculating the temperature dependence of the mean-field order parameters, the thermodynamic quantities, and the single-particle excitation spectra of the Hubbard model on a two-dimensional square lattice with this method. The result clearly shows the usefulness of this method. I am going to investigate the physical properties of the excitonic preformed pairs above the transition temperature of the excitonic-insulator phase in the future.

•Jan 1, 2019•0 citations

2次元複合符号について

輝暁 鈴木, 今井 秀樹

ランダム誤りを訂正する符号として，複合符号がある．本稿では，複合符号を2次元に拡張した2次元複合符号について論ずる．

•Aug 1, 1979•0 citations
量子コンピューティングの方式のひとつとして量子アニーリング方式が注目され, 組合せ最適化問題へ実用的な利用が進んでいる, 量子アニーリングはイジングモデル上のスピングラス問題を 解くものであるが, 昨今は, その手法を起源としたデジタルマシンも多く考案され, 本稿で用いたGPUベースのFixstars Amplify Annealing Engineもその一つである. 本稿では, 組合せ最適化問題の一つである容量制約つき運搬経路問題に対して, 最適解探索に用いる決定変数を削減するための2個の手法で実装し, 性能を評価した. ルート数を考慮して決定変数を削減する場合に, 決定変数の一部の値を固定化して削減する方法と決定変数の生成自体を削減する方法を評価し, 前者の方法は決定変数削減による高速化の効果は限定的であるが, 後者の方法は, 訪問都市数に依存するものの,概ね2倍程度の高速化が達成できた.
次世代の計算方式として量子コンピューティングが注目されている. その実現方式の一つである量子アニーリングは組合せ最適化の分野で実用レベルでのアプリケーションが扱われ, 特に既存デバイスを用いた疑似的量子アニーリングマシンは多数の提案と実稼働がされている. 一方で, 働き方の改革に起因する物流業界の効率化が急がれており, 移動コストと人件費コストの最小化は大きな課題である. 本稿では, Fixstars Amplify Annealing Engineを用いて物流問題の最適化の実装を行い, その制約条件の増加と最適解を求める実行時間の関係と, 実行時間を削減するための効率化について述べる. 丁寧な最適化を求めるためには制約条件は複雑になるが, それによる求解時間の増加は顕著であり, 決定変数の初期化により制約条件を減少することにより求解時間を削減できることを実験的に確認した.
近年, 量子計算が注目されている. 量子計算には量子ゲート方式と量子アニーリング方式があるが, 実用的に利用されているいるのは後者であり, デジタル方式のものも含め複数の実機が発表されている. しかし, 実問題をイジングモデルの相互作用とバイアスに変換することは煩雑であり, 自動的にイジング最適化を行なうソフトウェアの利用が重要である. 本稿では, そのためのソフトウェアの一つであるFixstars Amplify を用いて巡回セールスマン問題をFixstars Amplify Annealing Engine上で実行し, 古典的ソルバーのGLPK (GNU Linear Programming Kit) のオンプレミスのLinux マシン上での実行結果との比較を行い, その試用を通して実用性の考察を行なう.
ムーアの法則の限界が指摘される中,次世代の計算方式として量子計算が注目されている.その関連手法である量子アニーリングは,擬似的な実現方式を含め,数理最適化分野において実用レベルのアプリケーションが利用されている.一方,引越し業界をはじめとする物流業界でも効率化が急務となっており,移動コストおよび人件費コストの最小化は重要な課題である.このような課題に対し,量子アニーリングを用いた最適化は有効な解決策となり得る.本稿では,FixstarsAmplifyAnnealingEngineを用いて物流最適化問題を実装し,スタッフ間の相性や教育関係を考慮した配置制約に着目する.これらの制約条件の増加が最適解探索の実行時間に与える影響を評価するとともに,実行時間削減のための効率化手法を検討する.その結果,決定変数の扱いを工夫することで,追加の制約を導入することなく同等の最適化が可能となり,求解時間を短縮できることを確認した.
近年，イジングハミルトニアンのエネルギー最小化を利用した最適化問題の解法が検討されている（S. Utsunomiya et al., Optics Express 19, 2011）．また，そのような手法を大規模に実装する技術の研究も進んでいる（T. Inagaki et al., Science, 234, 2016）．本稿では，このようなハードウェアで実現する量子ニューラルネットワークを用いた組合せ最適化アルゴリズムを検討する．対象とする組合せ最適化問題の目的関数は，イジングスピンの相互結合に実装することとなる．相互作用によるエネルギー最小化を用いた最適化問題の解法は，Hopfield-Tank Neural Network を用いた従来研究において様々な組合せ最適化問題に適用されてきた．本稿では，Hopfield-Tank Neural Network を用いた巡回セールスマン問題の解法を，量子ニューラルネットワークで動作させる方法を説明する．シミュレーション結果を示しながら，提案手法の有効性を示す．
電子が互いに強く相互作用する強相関電子系を対象に、有限温度の計算手法の開発と具体的問題への適用を目的とする研究を行った。有限温度においてはフェルミオン対がボーズ凝縮するよりも高温でプリフォームド対が出現したり、幾何学的フラストレーションを有する系において金属・絶縁体転移が生じたりするなどの興味深い物理現象が実験において多数観測されており、理論的に有限温度の計算手法を確立させることは極めて重要である。 従来から有限温度計算によく使用されている量子モンテカルロ法では、電子のようなフェルミオン系において「負符号問題」により特殊な例を除いて計算が実行できなくなることが知られており、その普遍的解決策は見つかっていない。そこで、本研究では有限サイズのクラスターの状態を求め、その結果を無限系へと接続する変分クラスター法(VCA)に注目した。またこの手法の特徴として、平均場を導入することにより有限温度の相転移を議論することも可能である。クラスター内の状態を求める際、素朴には厳密対角化(ED)によって得られた固有状態を使ってカノニカル平均をとることで有限温度での性質を調べることができるが、クラスターのサイズが著しく制限されてしまう。これを解決するため、熱的純粋量子(TPQ)状態を用いた有限温度計算を提案した。この手法はEDに比べて比較的大きなサイズのクラスターを扱うことができ、EDで顕著に現れる有限サイズ効果の抑制につながる。 VCAとTPQ状態を組み合わせた手法の妥当性を調べるために、2次元正方格子上のハバード模型に適用した。有限温度における平均場秩序変数、熱力学量、励起スペクトルの温度依存性の計算に成功し、その有用性を示すことができた、今後はこの手法を元にして、励起子絶縁体の有限温度におけるプリフォームド励起子対生成に伴う物理現象の解明を目指す。 I developed a numerical method to investigate finite-temperature properties of strongly correlated electron systems, and applied it to some problems. At finite temperatures, many intriguing physical phenomena have been observed in experiments, such as the appearance of preformed pairs above the transition temperature of the Bose-Einstein condensation and the metal-insulator transition in geometrically frustrated systems. Therefore, it is quite important to establish a theoretical method to calculate the physical properties at finite temperatures. In quantum Monte Carlo methods, which are often used for finite-temperature calculations, it is well known that a "negative sign problem" disrupts calculations of fermionic systems, except for several special cases. In this study, I focus on the variational-cluster approach (VCA), which an infinite-system state is constructed from the state of a small-size cluster. In addition, we are also able to discuss a finite-temperature phase transition by introducing a mean-field term. Although we can in principle obtain the physical quantities of the cluster at finite temperatures by taking the canonical-ensemble average with the eigenstates obtained from the exact-diagonalization (ED) method, the size of the cluster is severely restricted. To solve this problem, we make use of the method based on thermal-pure-quantum (TPQ) state. This method can treat a relatively large cluster compared to the ED method, and thus it can suppress the finite-size effect that often appears in ED method. I investigated the validity of the method combining VCA and TPQ states. I succeeded in calculating the temperature dependence of the mean-field order parameters, the thermodynamic quantities, and the single-particle excitation spectra of the Hubbard model on a two-dimensional square lattice with this method. The result clearly shows the usefulness of this method. I am going to investigate the physical properties of the excitonic preformed pairs above the transition temperature of the excitonic-insulator phase in the future.