論文の概要: Improving Performance in Combinatorial Optimization Problems with
Inequality Constraints: An Evaluation of the Unbalanced Penalization Method
on D-Wave Advantage
- arxiv url: http://arxiv.org/abs/2305.18757v1
- Date: Tue, 30 May 2023 05:40:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 18:10:00.773035
- Title: Improving Performance in Combinatorial Optimization Problems with
Inequality Constraints: An Evaluation of the Unbalanced Penalization Method
on D-Wave Advantage
- Title（参考訳）: 不等式制約による組合せ最適化問題の性能向上:D波アドバンテージの不均衡化手法の評価
- Authors: J. A. Montanez-Barrera, Pim van den Heuvel, Dennis Willsch, Kristel
Michielsen
- Abstract要約: 非バランスなペナル化と呼ばれる新しい手法が、スラック変数の使用を避けるために提案されている。
本研究は、旅行セールスマン問題(TSP)に対するD-Wave Advantage上の実量子ハードウェアを用いた不均衡ペナル化法をテストする。
その結果、不均衡なペナル化法はスラック変数を用いた解よりも優れていた。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Combinatorial optimization problems are one of the target applications of
current quantum technology, mainly because of their industrial relevance, the
difficulty of solving large instances of them classically, and their
equivalence to Ising Hamiltonians using the quadratic unconstrained binary
optimization (QUBO) formulation. Many of these applications have inequality
constraints, usually encoded as penalization terms in the QUBO formulation
using additional variables known as slack variables. The slack variables have
two disadvantages: (i) these variables extend the search space of optimal and
suboptimal solutions, and (ii) the variables add extra qubits and connections
to the quantum algorithm. Recently, a new method known as unbalanced
penalization has been presented to avoid using slack variables. This method
offers a trade-off between additional slack variables to ensure that the
optimal solution is given by the ground state of the Ising Hamiltonian, and
using an unbalanced heuristic function to penalize the region where the
inequality constraint is violated with the only certainty that the optimal
solution will be in the vicinity of the ground state. This work tests the
unbalanced penalization method using real quantum hardware on D-Wave Advantage
for the traveling salesman problem (TSP). The results show that the unbalanced
penalization method outperforms the solutions found using slack variables and
sets a new record for the largest TSP solved with quantum technology.
- Abstract（参考訳）: 組合せ最適化問題は、主にその産業的関連性、それらの大規模インスタンスを古典的に解くことの難しさ、および二次的非制約二元最適化(QUBO)の定式化を用いたイジング・ハミルトニアンの同値性から、現在の量子技術のターゲットの1つである。
これらのアプリケーションの多くは不等式制約を持ち、通常、slack変数として知られる追加変数を使用してquboの定式化においてペナルティ化項としてエンコードされる。
slack変数には2つの欠点がある。
(i)これらの変数は最適および準最適解の探索空間を広げ、
(ii)変数は量子アルゴリズムに余分な量子ビットと接続を追加する。
近年,slack変数の使用を避けるために,unbalanced penalizationと呼ばれる新しい手法が提案されている。
この方法は、最適解がイジングハミルトニアンの基底状態によって与えられることを保証し、不均衡なヒューリスティック関数を用いて不等式制約が違反している領域をペナルティ化し、最適解が基底状態の近傍にあることを保証するための追加のslack変数間のトレードオフを提供する。
本研究は,実量子ハードウェアを用いた非平衡ペナリゼーション法を,旅行セールスマン問題 (tsp) に対する d-wave advantage 上でテストする。
その結果,非平衡ペナリゼーション法はslack変数を用いた解を上回り,量子技術で解く最大のtspの新記録を樹立した。
関連論文リスト
- Inequality constraints in variational quantum circuits with qudits [1.0923877073891446]
量子最適化は、短期量子デバイスの能力を利用するための重要な候補として浮上している。
本稿では,QAOAアルゴリズムにおける不等式制約をQudit-SUMゲートを用いて直接実装する手法を提案する。
不平等な罰則の直接的実装はスラック変数法を著しく上回り、特に実世界において多くの制約を課した問題を研究する場合に顕著である。
論文 参考訳（メタデータ） (2024-10-10T07:32:38Z) - Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。
2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
論文 参考訳（メタデータ） (2024-06-11T19:59:05Z) - Neural Time-Reversed Generalized Riccati Equation [60.92253836775246]
ハミルトン方程式は、コストテートとして知られる補助変数を通して最適性の解釈を提供する。
本稿では,前向きに作業することを目的とした,新しいニューラルベースによる最適制御手法を提案する。
論文 参考訳（メタデータ） (2023-12-14T19:29:37Z) - QSlack: A slack-variable approach for variational quantum semi-definite
programming [5.0579795245991495]
量子コンピュータは、最もよく知られた古典的アルゴリズムのスピードアップを提供することができる。
半定値および線形プログラムを含む最適化問題の解法を示す。
これらの問題に対する予備問題と双対問題の両方の実装が、基礎的真理に近づいていることが示される。
論文 参考訳（メタデータ） (2023-12-06T19:00:01Z) - Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳（メタデータ） (2022-11-25T06:05:18Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。
我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。
提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
論文 参考訳（メタデータ） (2022-11-14T21:54:31Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳（メタデータ） (2022-11-01T07:52:47Z) - Modeling Linear Inequality Constraints in Quadratic Binary Optimization
for Variational Quantum Eigensolver [0.0]
本稿では, 変分量子固有解法における配向型変分形式の利用について紹介する。
通常、いくつかの最適化問題に現れる4つの制約がモデル化されている。
提案手法の主な利点は、変分形式のパラメータの数が一定であることである。
論文 参考訳（メタデータ） (2020-07-26T23:36:22Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。