論文の概要: Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms

• arxiv url: http://arxiv.org/abs/2211.13914v4
• Date: Fri, 7 Jun 2024 05:52:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-10 23:14:33.767092
• Title: Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
• Title（参考訳）: 不均衡ペナル化:量子最適化アルゴリズムにおける組合せ問題の不等式制約をエンコードする新しいアプローチ
• Authors: Alejandro Montanez-Barrera, Dennis Willsch, Alberto Maldonado-Romo, Kristel Michielsen,
• Abstract要約: 余分なスラック変数を必要としない代替手法を提案する。 我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。 この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
• 参考スコア（独自算出の注目度）: 42.29248343585333
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving combinatorial optimization problems of the kind that can be codified by quadratic unconstrained binary optimization (QUBO) is a promising application of quantum computation. Some problems of this class suitable for practical applications such as the traveling salesman problem (TSP), the bin packing problem (BPP), or the knapsack problem (KP) have inequality constraints that require a particular cost function encoding. The common approach is the use of slack variables to represent the inequality constraints in the cost function. However, the use of slack variables considerably increases the number of qubits and operations required to solve these problems using quantum devices. In this work, we present an alternative method that does not require extra slack variables and consists of using an unbalanced penalization function to represent the inequality constraints in the QUBO. This function is characterized by larger penalization when the inequality constraint is not achieved than when it is. We evaluate our approach on the TSP, BPP, and KP, successfully encoding the optimal solution of the original optimization problem near the ground state cost Hamiltonian. Additionally, we employ D-Wave Advantage and D-Wave hybrid solvers to solve the BPP, surpassing the performance of the slack variables approach by achieving solutions for up to 29 items, whereas the slack variables approach only handles up to 11 items. This new approach can be used to solve combinatorial problems with inequality constraints with a reduced number of resources compared to the slack variables approach using quantum annealing or variational quantum algorithms.
• Abstract（参考訳）: 二次的非制約バイナリ最適化(QUBO)によって符号化できる種類の組合せ最適化問題を解くことは、量子計算の有望な応用である。 このクラスのいくつかの問題は、旅行セールスマン問題(TSP)、ビンパッキング問題(BPP)、クナップサック問題(KP)など、特定のコスト関数の符号化を必要とする不等式制約がある。 一般的なアプローチは、コスト関数の不等式制約を表現するためにslack変数を使用することである。 しかし、スラック変数の使用は量子デバイスを用いてこれらの問題を解決するのに必要なキュービットの数と演算を著しく増加させる。 本研究では、余分なスラック変数を必要とせず、QUBOの不等式制約を表現するために不均衡なペナル化関数を使用する方法を提案する。 この関数は、不等式制約が時よりも達成されない場合に、より大きなペナル化を特徴とする。 我々は、TSP、BPP、KPに対する我々のアプローチを評価し、基底状態コストのハミルトニアンに近い最適化問題の最適解の符号化に成功した。 さらに、最大29項目の解を求めることで、スラック変数アプローチの性能を上回り、スラック変数アプローチでは最大11項目しか処理できないのに対し、D-Wave AdvantageとD-Waveハイブリッドソルバを用いてBPPを解く。 この新しいアプローチは、量子アニール法や変分量子アルゴリズムを用いたスラック変数アプローチと比較して、リソース数の削減による不等式制約の組合せ問題を解くために使用できる。

関連論文リスト

• Inequality constraints in variational quantum circuits with qudits [1.0923877073891446]
  量子最適化は、短期量子デバイスの能力を利用するための重要な候補として浮上している。 本稿では,QAOAアルゴリズムにおける不等式制約をQudit-SUMゲートを用いて直接実装する手法を提案する。 不平等な罰則の直接的実装はスラック変数法を著しく上回り、特に実世界において多くの制約を課した問題を研究する場合に顕著である。
  論文  参考訳（メタデータ） (2024-10-10T07:32:38Z)
• Improving Performance in Combinatorial Optimization Problems with Inequality Constraints: An Evaluation of the Unbalanced Penalization Method on D-Wave Advantage [0.0]
  非バランスなペナル化と呼ばれる新しい手法が、スラック変数の使用を避けるために提案されている。 本研究は、旅行セールスマン問題(TSP)に対するD-Wave Advantage上の実量子ハードウェアを用いた不均衡ペナル化法をテストする。 その結果、不均衡なペナル化法はスラック変数を用いた解よりも優れていた。
  論文  参考訳（メタデータ） (2023-05-30T05:40:50Z)
• Quantum annealing with inequality constraints: the set cover problem [0.0]
  本稿では,複数の不等式制約を持つ集合被覆問題を量子アニール上で解くための2つの新しい手法を提案する。 第1の方法は拡張ラグランジアン法を用いて制約を表現し、第2の方法は高階バイナリ最適化(HUBO)を用いる。 どちらのアプローチも、D-Wave量子アニールの不等式制約の問題を解くために、スラック変数で標準的なアプローチより優れている。
  論文  参考訳（メタデータ） (2023-02-22T07:39:51Z)
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management [45.82374977939355]
  本稿では,変分量子アルゴリズムを用いた制約付き最適化問題の解法を提案する。 我々は、キャッシュマネジメント問題という、金融の極めて関連性の高い現実世界の問題について、我々の提案を検証した。 実験の結果, 実現したソリューションのコスト, 特に局所最小値の回避に関して, 大幅な改善が見られた。
  論文  参考訳（メタデータ） (2023-02-08T17:09:20Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• 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)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。