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

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

彰良 若谷, Wakatani Akiyoshi

Published Jul 30, 2022• 0 citations
Publisher

Abstract

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

DOI
10.14990/00004374

Related papers

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

Akiyoshi Wakatani

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

•Aug 8, 2025•0 citations

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

Akiyoshi Wakatani

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

•Jul 31, 2024•0 citations

ダイアグラム展開に基づく連続時間量子モンテカルロ法

Hiroaki Kusunose, Junya Otsuki

近年,多体摂動論に基づく連続時間量子モンテカルロ法のアルゴリズムが提出され,強相関電子系の動的平均場近似における有力な不純物(クラスター)ソルバーとして広く用いられるようになってきた.本稿では,不純物Anderson模型を主な題材として,相互作用および混成(運動エネルギー)項に関する展開アルゴリズムを解説する.また,実際にプログラムを作成する際の注意点や計算効率について述べる.電子-格子相互作用系への適用など,最近の発展についても簡単に紹介する.

•Jul 5, 2010•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

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

Akiyoshi Wakatani

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

•Sep 11, 2026•0 citations

素因数分解とデータベース検索に対する量子アルゴリズム

KEISUKE TANAKA

•Jan 1, 2000•0 citations
近年, 量子計算が注目されている. 量子計算には量子ゲート方式と量子アニーリング方式があるが, 実用的に利用されているいるのは後者であり, デジタル方式のものも含め複数の実機が発表されている. しかし, 実問題をイジングモデルの相互作用とバイアスに変換することは煩雑であり, 自動的にイジング最適化を行なうソフトウェアの利用が重要である. 本稿では, そのためのソフトウェアの一つであるFixstars Amplify を用いて巡回セールスマン問題をFixstars Amplify Annealing Engine上で実行し, 古典的ソルバーのGLPK (GNU Linear Programming Kit) のオンプレミスのLinux マシン上での実行結果との比較を行い, その試用を通して実用性の考察を行なう.
次世代の計算方式として量子コンピューティングが注目されている. その実現方式の一つである量子アニーリングは組合せ最適化の分野で実用レベルでのアプリケーションが扱われ, 特に既存デバイスを用いた疑似的量子アニーリングマシンは多数の提案と実稼働がされている. 一方で, 働き方の改革に起因する物流業界の効率化が急がれており, 移動コストと人件費コストの最小化は大きな課題である. 本稿では, Fixstars Amplify Annealing Engineを用いて物流問題の最適化の実装を行い, その制約条件の増加と最適解を求める実行時間の関係と, 実行時間を削減するための効率化について述べる. 丁寧な最適化を求めるためには制約条件は複雑になるが, それによる求解時間の増加は顕著であり, 決定変数の初期化により制約条件を減少することにより求解時間を削減できることを実験的に確認した.
量子コンピューティングの方式のひとつとして量子アニーリング方式が注目され, 組合せ最適化問題へ実用的な利用が進んでいる, 量子アニーリングはイジングモデル上のスピングラス問題を 解くものであるが, 昨今は, その手法を起源としたデジタルマシンも多く考案され, 本稿で用いたGPUベースのFixstars Amplify Annealing Engineもその一つである. 本稿では, 組合せ最適化問題の一つである容量制約つき運搬経路問題に対して, 最適解探索に用いる決定変数を削減するための2個の手法で実装し, 性能を評価した. ルート数を考慮して決定変数を削減する場合に, 決定変数の一部の値を固定化して削減する方法と決定変数の生成自体を削減する方法を評価し, 前者の方法は決定変数削減による高速化の効果は限定的であるが, 後者の方法は, 訪問都市数に依存するものの,概ね2倍程度の高速化が達成できた.
近年,多体摂動論に基づく連続時間量子モンテカルロ法のアルゴリズムが提出され,強相関電子系の動的平均場近似における有力な不純物(クラスター)ソルバーとして広く用いられるようになってきた.本稿では,不純物Anderson模型を主な題材として,相互作用および混成(運動エネルギー)項に関する展開アルゴリズムを解説する.また,実際にプログラムを作成する際の注意点や計算効率について述べる.電子-格子相互作用系への適用など,最近の発展についても簡単に紹介する.
近年，イジングハミルトニアンのエネルギー最小化を利用した最適化問題の解法が検討されている（S. Utsunomiya et al., Optics Express 19, 2011）．また，そのような手法を大規模に実装する技術の研究も進んでいる（T. Inagaki et al., Science, 234, 2016）．本稿では，このようなハードウェアで実現する量子ニューラルネットワークを用いた組合せ最適化アルゴリズムを検討する．対象とする組合せ最適化問題の目的関数は，イジングスピンの相互結合に実装することとなる．相互作用によるエネルギー最小化を用いた最適化問題の解法は，Hopfield-Tank Neural Network を用いた従来研究において様々な組合せ最適化問題に適用されてきた．本稿では，Hopfield-Tank Neural Network を用いた巡回セールスマン問題の解法を，量子ニューラルネットワークで動作させる方法を説明する．シミュレーション結果を示しながら，提案手法の有効性を示す．
ムーアの法則の限界が指摘される中,次世代の計算方式として量子計算が注目されている.その関連手法である量子アニーリングは,擬似的な実現方式を含め,数理最適化分野において実用レベルのアプリケーションが利用されている.一方,引越し業界をはじめとする物流業界でも効率化が急務となっており,移動コストおよび人件費コストの最小化は重要な課題である.このような課題に対し,量子アニーリングを用いた最適化は有効な解決策となり得る.本稿では,FixstarsAmplifyAnnealingEngineを用いて物流最適化問題を実装し,スタッフ間の相性や教育関係を考慮した配置制約に着目する.これらの制約条件の増加が最適解探索の実行時間に与える影響を評価するとともに,実行時間削減のための効率化手法を検討する.その結果,決定変数の扱いを工夫することで,追加の制約を導入することなく同等の最適化が可能となり,求解時間を短縮できることを確認した.