論文の概要: Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks

• arxiv url: http://arxiv.org/abs/2507.12159v2
• Date: Thu, 17 Jul 2025 06:09:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-18 11:36:41.101314
• Title: Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks
• Title（参考訳）: Slackをカットする: Y CombinatorialベンチマークのためのSlackフリーメソッドによる量子最適化
• Authors: Monit Sharma, Hoong Chuin Lau,
• Abstract要約: 制約処理は、量子最適化における重要なボトルネックである。 量子シミュレータやハードウェア上での制約問題を解くために,ラグランジアンに基づく一連の最適化手法について検討する。 この結果は,QUBOのペナライゼーションに代わるスケーラブルな代替手段として,ラグランジアン定式化の柔軟性を強調した。
• 参考スコア（独自算出の注目度）: 4.266376725904727
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constraint handling remains a key bottleneck in quantum combinatorial optimization. While slack-variable-based encodings are straightforward, they significantly increase qubit counts and circuit depth, challenging the scalability of quantum solvers. In this work, we investigate a suite of Lagrangian-based optimization techniques including dual ascent, bundle methods, cutting plane approaches, and augmented Lagrangian formulations for solving constrained combinatorial problems on quantum simulators and hardware. Our framework is applied to three representative NP-hard problems: the Travelling Salesman Problem (TSP), the Multi-Dimensional Knapsack Problem (MDKP), and the Maximum Independent Set (MIS). We demonstrate that MDKP and TSP, with their inequality-based or degree-constrained structures, allow for slack-free reformulations, leading to significant qubit savings without compromising performance. In contrast, MIS does not inherently benefit from slack elimination but still gains in feasibility and objective quality from principled Lagrangian updates. We benchmark these methods across classically hard instances, analyzing trade-offs in qubit usage, feasibility, and optimality gaps. Our results highlight the flexibility of Lagrangian formulations as a scalable alternative to naive QUBO penalization, even when qubit savings are not always achievable. This work provides practical insights for deploying constraint-aware quantum optimization pipelines, with applications in logistics, network design, and resource allocation.
• Abstract（参考訳）: 制約処理は、量子組合せ最適化における重要なボトルネックである。 slack-variable-based encodingsは単純だが、量子ビット数と回路深度を大幅に増加させ、量子ソルバのスケーラビリティに挑戦する。 本研究では,2重積法,バンドル法,切断面アプローチ,量子シミュレータとハードウェア上の制約付き組合せ問題を解くための拡張ラグランジアン定式化など,ラグランジアンに基づく最適化手法の組について検討する。 本稿では,トラベリングセールスマン問題(TSP),多次元クナップサック問題(MDKP),最大独立集合(MIS)の3つの問題に適用する。 MDKP と TSP は不等式や等級制約のある構造であり,スラックフリーな再構成が可能であり,性能を損なうことなく大幅な量子ビット保存が可能であった。 対照的に、MISは本質的にはスラック除去の恩恵を受けないが、原則化されたラグランジアン更新によって実現可能性と客観的品質が向上している。 古典的なハードなインスタンスにまたがってこれらの手法をベンチマークし、キュービット使用率、実現可能性、最適性ギャップのトレードオフを分析する。 この結果から,量子ビット保存が必ずしも達成できない場合でも,ラグランジアン定式化の柔軟性はQUBOペナリゼーションに代わるスケーラブルな代替手段として強調される。 この研究は、ロジスティクス、ネットワーク設計、リソース割り当てといった制約を意識した量子最適化パイプラインをデプロイするための実践的な洞察を提供する。

関連論文リスト

• Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems [4.266376725904727]
  最適化問題のQUBO定式化における変数数と制約を減らすために,グラフ縮小に基づく古典量子ハイブリッドフレームワークを提案する。 提案手法は, ソリューションの実現性の向上, 修理の複雑さの低減, ハードウェア限定インスタンスの量子最適化品質の向上を実現する。
  論文  参考訳（メタデータ） (2025-06-17T07:11:48Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers [4.266376725904727]
  変分量子アルゴリズム(VQA)は、通常、ペナルティ法を用いて制約のない問題として再構成されるように制約付き問題を要求する。 一般的なアプローチでは、不等式制約を扱うためにQUBOの定式化においてスラック変数と二次罰則を導入する。 我々は、カスタムペナルティ関数を使って不等式制約を直接エンコードするスラックフリーな定式化について検討する。 これらのステップのような罰則は、追加の量子ビットを導入するか、微調整された重みを必要とすることなく、実現不可能な解を抑える。
  論文  参考訳（メタデータ） (2025-04-17T03:20:02Z)
• A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems [4.266376725904727]
  本稿では,NP-hard問題に対する量子最適化手法の評価を目的とした,包括的なベンチマークフレームワークを提案する。 本フレームワークは,多次元クナップサック問題(MDKP),最大独立集合(MIS),二次割当問題(QAP),市場シェア問題(MSP)など,主要な課題に重点を置いている。
  論文  参考訳（メタデータ） (2025-03-15T13:02:22Z)
• Reconfigurable Intelligent Surface (RIS)-Assisted Entanglement Distribution in FSO Quantum Networks [62.87033427172205]
  自由空間光(FSO)量子チャネルに依存する量子ネットワーク(QN)は、光ファイバー基盤の確立が困難でコストがかかる環境における量子アプリケーションをサポートすることができる。 エンタングルメント分布のための仮想視線を提供する費用効率の高いフレームワークとして,再構成可能なインテリジェントサーフェス(RIS)を用いたFSOベースのQNを提案する。
  論文  参考訳（メタデータ） (2024-01-19T17:16:40Z)
• Achieving Constraints in Neural Networks: A Stochastic Augmented Lagrangian Approach [49.1574468325115]
  DNN(Deep Neural Networks)の正規化は、一般化性の向上とオーバーフィッティングの防止に不可欠である。 制約付き最適化問題としてトレーニングプロセスのフレーミングによるDNN正規化に対する新しいアプローチを提案する。 我々はAugmented Lagrangian (SAL) 法を用いて、より柔軟で効率的な正規化機構を実現する。
  論文  参考訳（メタデータ） (2023-10-25T13:55:35Z)
• 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)
• Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization [7.541345730271882]
  一般に、そのような制約は回路内で容易に符号化することができず、量子回路の測定結果が制約を尊重することが保証されない。 本稿では,制約付き最適化問題に対する非実装型量子アンサテイズによる新しい解法を提案する。 シミュレータや量子ハードウェア上での高速なプロトタイピングのために,QiskitとインターフェースするPythonパッケージであるQVoiceで実装した。
  論文  参考訳（メタデータ） (2022-11-13T20:58:00Z)
• Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
  量子ゼノダイナミクスを用いて、不等式を含む複数の任意の制約で最適化問題を解く手法を提案する。 量子最適化のダイナミクスは、フォールトトレラントな量子コンピュータ上の制約内部分空間に効率的に制限できることを示す。
  論文  参考訳（メタデータ） (2022-09-29T18:00:40Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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