論文の概要: Solving Large Break Minimization Problems in a Mirrored Double
Round-robin Tournament Using Quantum Annealing
- arxiv url: http://arxiv.org/abs/2110.07239v1
- Date: Thu, 14 Oct 2021 09:08:09 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-15 15:12:09.456780
- Title: Solving Large Break Minimization Problems in a Mirrored Double
Round-robin Tournament Using Quantum Annealing
- Title（参考訳）: 量子アニーリングを用いたミラーリングダブルラウンドロビントーナメントにおける大破れ最小化問題の解法
- Authors: Michiya Kuramata, Ryota Katsuki, Kazuhide Nakata
- Abstract要約: 量子異方体は, 実用的な最適化問題の解法として利用できることを示す。
量子異方体の性能を、最も洗練された数学的最適化解法の一つと比較する。
結果: 20チームで問題が発生した場合、QAは0.05秒で正確なソリューションを決定できた。
- 参考スコア（独自算出の注目度）: 0.5156484100374059
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum annealing (QA) has gained considerable attention because it can be
applied to combinatorial optimization problems, which have numerous
applications in logistics, scheduling, and finance. In recent years, research
on solving practical combinatorial optimization problems using them has
accelerated. However, researchers struggle to find practical combinatorial
optimization problems, for which quantum annealers outperform other
mathematical optimization solvers. Moreover, there are only a few studies that
compare the performance of quantum annealers with one of the most sophisticated
mathematical optimization solvers, such as Gurobi and CPLEX. In our study, we
determine that QA demonstrates better performance than the solvers in the break
minimization problem in a mirrored double round-robin tournament (MDRRT). We
also explain the desirable performance of QA for the sparse interaction between
variables and a problem without constraints. In this process, we demonstrate
that the break minimization problem in an MDRRT can be expressed as a 4-regular
graph. Through computational experiments, we solve this problem using our QA
approach and two-integer programming approaches, which were performed using the
latest quantum annealer D-Wave Advantage, and the sophisticated mathematical
optimization solver, Gurobi, respectively. Further, we compare the quality of
the solutions and the computational time. QA was able to determine the exact
solution in 0.05 seconds for problems with 20 teams, which is a practical size.
In the case of 36 teams, it took 84.8 s for the integer programming method to
reach the objective function value, which was obtained by the quantum annealer
in 0.05 s. These results not only present the break minimization problem in an
MDRRT as an example of applying QA to practical optimization problems, but also
contribute to find problems that can be effectively solved by QA.
- Abstract（参考訳）: 量子アニール(QA)は、物流、スケジューリング、ファイナンスに多くの応用がある組合せ最適化問題に適用できるため、注目されている。
近年,それらを用いた組合せ最適化問題を解く研究が加速されている。
しかし、研究者たちは実用的な組合せ最適化問題を見つけるのに苦労しており、量子アニーラーは他の数学的最適化解法よりも優れている。
さらに、量子アニーラーの性能を、gurobiやcplexのような最も洗練された数学的最適化解法の一つと比較する研究はごくわずかである。
そこで本研究では,ミラーリングラウンドロビントーナメント(MDRRT)におけるブレーク最小化問題において,QAが解法よりも優れた性能を示した。
また,変数間の疎相互作用と制約のない問題に対するQAの望ましい性能についても説明する。
本稿では,MDRRTにおけるブレーク最小化問題を4正規グラフとして表現できることを実証する。
計算実験により,最新の量子アニーラーD-WaveAdvantageと高度な数学的最適化解法であるGurobiを用いて,QA法と2整数プログラミング法を用いてこの問題を解く。
さらに,解の質と計算時間を比較する。
QAは20チームでの問題に対して0.05秒で正確なソリューションを決定できた。
36チームの場合、整数プログラミング法が目的関数値に達するのに84.8秒かかり、これは0.05秒の量子アニールによって得られた。
これらの結果は, MDRRTにおけるブレーク最小化問題を, 実用的な最適化問題にQAを適用した例として提示するだけでなく, QAによって効果的に解ける問題を見つけるためにも貢献する。
関連論文リスト
- Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems [0.0]
ゲートモデル量子コンピュータにおける二項最適化問題に対する包括的量子解法を提案する。
最大127キュービットの問題の正しい解を一貫して提供する。
我々は、古典的に非自明な2進最適化問題に対して、IBM量子コンピュータ上でこの解法をベンチマークする。
論文 参考訳（メタデータ） (2024-06-03T19:08:01Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - Multiobjective variational quantum optimization for constrained
problems: an application to Cash Management [45.82374977939355]
本稿では,変分量子アルゴリズムを用いた制約付き最適化問題の解法を提案する。
我々は、キャッシュマネジメント問題という、金融の極めて関連性の高い現実世界の問題について、我々の提案を検証した。
実験の結果, 実現したソリューションのコスト, 特に局所最小値の回避に関して, 大幅な改善が見られた。
論文 参考訳（メタデータ） (2023-02-08T17:09:20Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Efficient Use of Quantum Linear System Algorithms in Interior Point
Methods for Linear Optimization [0.0]
線形最適化問題を解くために、非現実的な量子内点法を開発した。
また、量子ソルバの過度な時間なしで、反復リファインメントによって正確な解を得る方法についても論じる。
論文 参考訳（メタデータ） (2022-05-02T21:30:56Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
車両ルーティング問題(VRP)はNPハード最適化問題である。
この研究は、変数 ANSATZ 上の変分量子固有解法を用いて、3 と 4 の都市に基本的な VRP ソリューションを構築する。
論文 参考訳（メタデータ） (2021-12-28T10:20:42Z) - A case study of variational quantum algorithms for a job shop scheduling
problem [0.0]
我々は、IBMの超伝導量子プロセッサ上で動作する4つの変分量子アルゴリズムをジョブショップスケジューリング問題に適用する。
5量子ビットの比較により、最近のフィルタリング変分量子固有解法(F-VQE)はより高速に収束することが示された。
F-VQEは、エラー軽減後処理なしで、ハードウェア上で最大23キュービットの問題を容易に解決する。
論文 参考訳（メタデータ） (2021-09-08T16:05:50Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Larger Sparse Quadratic Assignment Problem Optimization Using Quantum
Annealing and a Bit-Flip Heuristic Algorithm [0.4125187280299248]
線形制約は、量子アニールで表現できる問題のサイズを減らす。
オーゼキ法により得られた解に対して,後処理ビットフリップアルゴリズムを適用し,スパースQAPの解法を提案する。
D-Wave Advantage を用いて,D-Wave Advantage を用いた QAP の高精度化に成功した。
論文 参考訳（メタデータ） (2020-12-18T09:48:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。