論文の概要: Resource-efficient formulations of the Knapsack problem for quantum computing
- arxiv url: http://arxiv.org/abs/2611.06797v1
- Date: Wed, 04 Nov 2026 17:14:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-06 03:25:58.213524
- Title: Resource-efficient formulations of the Knapsack problem for quantum computing
- Title(参考訳): 量子コンピューティングにおけるKnapsack問題の資源効率の定式化
- Abstract要約: 不等式制約のある問題の正準例であるKnapsack問題のQUBO定式化について検討する。
我々は、クナプサックをQUBOとして定式化するための、より資源効率の良い3つのアプローチについて検討する。
このスラックレス法は、比較的小さな問題のサイズであっても、数桁の桁数で成功確率を増大させる。
- 参考スコア(独自算出の注目度): 0.19573380763700712
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum computing has emerged as a new tool for solving combinatorial optimization problems. Quantum optimization approaches usually operate on the subclass of Quadratic Unconstrained Binary Optimization (QUBO) problems. Many optimization problems can be reformulated in this form, though there are often multiple ways to do so. The choice of formulation can considerably affect the performance of QUBO solvers in practice. In this work, we study QUBO formulations of the Knapsack problem, a canonical example of a problem with inequality constraints. In the standard formulation these constraints are converted into penalty terms, which requires additional slack variables. Here, we investigate three more resource-efficient approaches for formulating the Knapsack as a QUBO. The first two modify the standard formulation, either by deriving a smaller penalty constant or by reducing the number of slack variables. The third approach is a wholly different method, which avoids the use of slack variables entirely. All three approaches increase the probability of finding the optimal solution, both in simulations of the linear ramp Quantum Approximate Optimization Algorithm (LR-QAOA) and on a D-Wave quantum annealer. The slackless method performs best, increasing success probabilities by several orders of magnitude even for relatively small problem sizes.
- Abstract(参考訳): 組合せ最適化問題を解決する新しいツールとして量子コンピューティングが登場した。
量子最適化のアプローチは、通常、準非拘束バイナリ最適化(QUBO)問題のサブクラスで動作する。
多くの最適化問題は、この形式で再定義できるが、しばしば複数の方法が存在する。
定式化の選択はQUBOソルバの性能に大きく影響する。
本研究では,不等式制約のある問題の正則例であるKnapsack問題のQUBO定式化について検討する。
標準的な定式化では、これらの制約はペナルティ項に変換され、追加のスラック変数が必要となる。
ここでは、KnapsackをQUBOとして定式化するための、より資源効率の良い3つのアプローチについて検討する。
最初の2つは、より小さいペナルティ定数を導出するか、スラック変数の数を減らすことによって、標準定式化を変更する。
第3のアプローチは,スラック変数の使用を完全に回避する,まったく異なるメソッドである。
これら3つのアプローチは、線形ランプ量子近似最適化アルゴリズム(LR-QAOA)とD-Wave量子アニールのシミュレーションの両方において、最適解を見つける確率を高める。
このスラックレス法は、比較的小さな問題のサイズであっても、数桁の桁数で成功確率を増大させる。
関連論文リスト
- 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 Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (2022-11-25T06:05:18Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳(メタデータ) (2022-03-01T19:47:16Z) - 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) - Solving Quadratic Unconstrained Binary Optimization with
divide-and-conquer and quantum algorithms [0.0]
分割・対数手法を用いて、元の問題を小さな問題の集合に還元する。
この手法は任意のQUBOインスタンスに適用でき、全古典的またはハイブリッドな量子古典的アプローチにつながる。
論文 参考訳(メタデータ) (2021-01-19T19:00:40Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳(メタデータ) (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。