論文の概要: Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers

• arxiv url: http://arxiv.org/abs/2504.12611v1
• Date: Thu, 17 Apr 2025 03:20:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-18 14:36:24.869044
• Title: Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers
• Title（参考訳）: ゲートベース量子コンピュータにおけるQUBOのためのSlackフリーカスタムペナルティ関数の実装
• Authors: Xin Wei Lee, Hoong Chuin Lau,
• Abstract要約: 変分量子アルゴリズム(VQA)は、通常、ペナルティ法を用いて制約のない問題として再構成されるように制約付き問題を要求する。 一般的なアプローチでは、不等式制約を扱うためにQUBOの定式化においてスラック変数と二次罰則を導入する。 我々は、カスタムペナルティ関数を使って不等式制約を直接エンコードするスラックフリーな定式化について検討する。 これらのステップのような罰則は、追加の量子ビットを導入するか、微調整された重みを必要とすることなく、実現不可能な解を抑える。
• 参考スコア（独自算出の注目度）: 4.266376725904727
• License:
• Abstract: Solving NP-hard constrained combinatorial optimization problems using quantum algorithms remains a challenging yet promising avenue toward quantum advantage. Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE), typically require constrained problems to be reformulated as unconstrained ones using penalty methods.A common approach introduces slack variables and quadratic penalties in the QUBO formulation to handle inequality constraints. However, this leads to increased qubit requirements and often distorts the optimization landscape, making it harder to find high-quality feasible solutions. To address these issues, we explore a slack-free formulation that directly encodes inequality constraints using custom penalty functions, specifically the exponential function and the Heaviside step function. These step-like penalties suppress infeasible solutions without introducing additional qubits or requiring finely tuned weights. Inspired by recent developments in quantum annealing and threshold-based constraint handling in gate-based algorithms, we implement and evaluate our approach on the Multiple Knapsack Problem (MKP). Experimental results show that the step-based formulation significantly improves feasibility and optimality rates compared to unbalanced penalization, while reducing overall qubit overhead.
• Abstract（参考訳）: NP-harded constrained combinatorial optimization problem using quantum algorithm を解くことは、量子優位性への挑戦的かつ有望な道である。 変分量子固有解法 (VQA) のような変分量子アルゴリズム (VQA) は、通常、不等式制約を扱うために、不等式制約を扱うために、スラック変数と二次罰則を導入する。 しかし、これは量子ビット要求の増加をもたらし、しばしば最適化の展望を歪ませ、高品質な実現可能なソリューションを見つけるのが難しくなる。 これらの問題に対処するために、カスタムペナルティ関数、特に指数関数とヘビサイドステップ関数を用いて不等式制約を直接符号化するスラックフリーな定式化について検討する。 これらのステップのような罰則は、追加の量子ビットを導入するか、微調整された重みを必要とすることなく、実現不可能な解を抑える。 ゲートベースアルゴリズムにおける近年の量子アニーリングとしきい値に基づく制約処理に着想を得て,MKP(Multiple Knapsack Problem)のアプローチを実装し,評価した。 実験結果から,ステップベースの定式化は,不均衡なペナル化よりも実現可能性と最適性率を著しく向上し,全体の量子ビットオーバーヘッドを低減させることがわかった。

関連論文リスト

• Non-Variational Quantum Random Access Optimization with Alternating Operator Ansatz [3.5773675235837974]
  量子ランダムアクセス最適化(QRAO)は、量子最適化の空間要求を減らすために提案されている。 インスタンスに依存しない'固定'パラメータは優れた性能を示し、変分パラメータ最適化の必要性を排除した。 本研究は,早期のフォールトトレラント量子コンピュータ上でのQRAOの実践的実行の道を開くものである。
  論文  参考訳（メタデータ） (2025-02-06T18:25:31Z)
• Inequality constraints in variational quantum circuits with qudits [1.0923877073891446]
  量子最適化は、短期量子デバイスの能力を利用するための重要な候補として浮上している。 本稿では,QAOAアルゴリズムにおける不等式制約をQudit-SUMゲートを用いて直接実装する手法を提案する。 不平等な罰則の直接的実装はスラック変数法を著しく上回り、特に実世界において多くの制約を課した問題を研究する場合に顕著である。
  論文  参考訳（メタデータ） (2024-10-10T07:32:38Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。 本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。 また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
  論文  参考訳（メタデータ） (2024-04-17T11:00:12Z)
• 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)
• 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)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  余分なスラック変数を必要としない代替手法を提案する。 我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。 この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
  論文  参考訳（メタデータ） (2022-11-25T06:05:18Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• 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)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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