論文の概要: Set-Packing and Sequence-Pair QUBOs for the 2D Cutting Stock Problem on Quantum Annealing Hardware
- arxiv url: http://arxiv.org/abs/2609.20853v1
- Date: Wed, 26 Aug 2026 07:28:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-05 14:48:16.099815
- Title: Set-Packing and Sequence-Pair QUBOs for the 2D Cutting Stock Problem on Quantum Annealing Hardware
- Title（参考訳）: 量子アニーリングハードウェアにおける2次元カットストック問題に対するセットパッキングとシーケンスペアQUBO
- Abstract要約: 2次元カットストック問題(2D-CSP)は、製造業と物流に直接的な経済的・環境的影響を与えるNPハード問題である。
我々は、その固定プレートの変種を、フリーピースの繰り返しと完全な非オーバーラップ制約と封じ込め制約でエンコードする。
反対の符号化パラダイムからの2つの定式化を比較し、境界相互作用次数の座標自由QUBOが2次元封じ込めの幾何学的に実現可能な基底状態を持たないことを証明した。
- 参考スコア（独自算出の注目度）: 0.1565870461096057
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The two-dimensional Cutting Stock Problem (2D-CSP) is an NP-hard problem with direct economic and environmental impacts on manufacturing and logistics. We encode its fixed-plate variant, with free piece repetition and full non-overlap and containment constraints, as a Quadratic Unconstrained Binary Optimization (QUBO) problem for quantum annealing and compare two formulations from opposite encoding paradigms. The first was a coordinate-based set-packing model with one binary variable per candidate placement. Its variable count grows linearly with plate area and resolution, but its ground state is, by construction, a geometrically feasible maximum-area packing. The second is a coordinate-free sequence-pair model whose variable count is independent of plate resolution and size. We prove that this compactness has a structural limit: no coordinate-free QUBO of bounded interaction degree whose penalties vanish on every geometrically feasible layout can have a geometrically feasible ground state for 2D containment, because containment is a longest-path constraint that bounded-degree penalties cannot enforce on chains longer than their interaction order. We evaluate both formulations under multi-seed simulated annealing, simulated quantum annealing, and an exact integer-programming baseline. Hardware experiments include D-Wave minor embedding, a calibrated direct-QPU sweep, and Leap hybrid solvers in both penalty and constraint-native form, across a six-instance campaign with per-instance calibration. The hybrid solver returns our certificate configuration, tying its energy to thirteen decimal places while overflowing the plate. We claim no quantum speedup. Our contribution is an impossibility result characterizing the limits of compact packing QUBOs, and a practical rule for choosing between the two formulations.
- Abstract（参考訳）: 2次元カットストック問題(2D-CSP)は、製造業と物流に直接的な経済的・環境的影響を与えるNPハード問題である。
量子アニーリングのための擬似非制約二元最適化(QUBO)問題として,自由部分繰り返しと完全非オーバーラップおよび包含制約を伴う固定板変種をエンコードし,反対の符号化パラダイムから2つの定式化を比較する。
1つは座標ベースのセットパッキングモデルで、候補の配置毎に1つのバイナリ変数を持つ。
その変動数は、プレート面積と分解能とともに直線的に増加するが、その基底状態は、構造上、幾何学的に可能な最大領域パッキングである。
2つ目は、プレートの解像度とサイズに依存しない可変数を持つ座標自由シーケンスペアモデルである。
このコンパクト性には構造的限界があることを証明している: 任意の幾何学的に実現可能なレイアウトで罰則が消える有界相互作用次数 QUBO は2次元封じ込めの幾何学的に実現可能な基底状態を持つことができない。
マルチシード・シミュレート・アニール法,シミュレート・量子アニール法,および正確な整数プログラミングベースライン下での2つの定式化を評価する。
ハードウェア実験には、D-Waveのマイナー埋め込み、キャリブレーションされたダイレクトQPUスイープ、およびLeapハイブリッドソルバのペナルティと制約ネイティブの両方で、インスタンスごとのキャリブレーションを含む6インスタンスのキャンペーンがある。
ハイブリッドソルバは認証設定を返却し、プレートをオーバーフローしながらエネルギーを13個の10個の場所に結び付ける。
量子スピードアップは行いません。
コントリビューションはコンパクトパッキングQUBOの限界を特徴づける不可能な結果であり、この2つの定式化を選択するための実践的ルールである。
関連論文リスト
- PMosFM: Preconditioned Manifold Matching for One-Step Physics-Constrained Generation [47.34605477768213]
textbf Preconditioned textbfManifold textbfone-textbfstep textbfFlow textbfMatching (textbfPMosFM) は1ステップの物理制約付き生成のための事前条件付き多様体マッチングフレームワークである。
多様体デコーダの制約を符号化することにより、PMosFMは残留損失と終端残差を分離することなく固有座標の輸送を学習する。
論文 参考訳（メタデータ） (2026-09-30T17:48:21Z) - Vehicle-Routing Clustering by Sparse Quantum Relaxation [1.8262547855491453]
本稿では,時間窓を用いた容量化ピックアップ・アンド・デリバリ問題に対するクラスタ・ファースト・ルート秒割当分解法について検討する。
我々は,スパース化対象のみを符号化し,丸め後の修復による1ホット,キャパシティ,クラスタ時間予算の実現性を確保することで,ハミルトンスパースを維持している。
論文 参考訳（メタデータ） (2026-09-17T02:05:02Z) - Hardware-Aware QUBO Reformulation of Constrained Binary Optimization via the Walsh-Fourier Transform [1.3423094548772225]
本稿では,制約付きバイナリ最適化を準拘束型バイナリ最適化(QUBO)として再構成する新しいフレームワークを提案する。
このハードウェアネイティブサロゲートは、厳密な近似空間から引き出されたにもかかわらず、より高密度な全対射影よりも優れていることを示す。
この利点は量子アニーラーにQUBOが埋め込まれてサンプル化されると、不均衡なペナル化やハードウェアブラインドによる全ての2次項への投射と比較して、最悪のケースと平均的な客観的なギャップを持つサンプルが得られる。
論文 参考訳（メタデータ） (2026-07-28T23:45:18Z) - When the Learning With Errors Problem Meets the Coherent Ising Machine: A Penalty-Free Algorithm-Hardware Co-Design [0.0]
LWE問題(Learning With Errors)はポスト量子暗号(PQC)の数学的基礎を構成する
CIM-BDDは,LWEを厳密な不規則二項最適化(QUBO)問題に還元するハイブリッド境界距離復号法である。
このフレームワークをTU Darmstadt LWE Challengeで検証し、Coherent Ising Machine CPQC-550上で40$Dのインスタンスを検索と決定の両方でエンドツーエンドでデモする。
論文 参考訳（メタデータ） (2026-06-22T04:39:32Z) - Quantum optimal control of the Dicke manifold in dipolar Rydberg atom arrays [0.0]
我々は,多体系の量子状態を設計し,制御する能力について検討する。
N$ qubits のレジスタに対して、ヒルベルト空間次元は指数関数的に 2N$ になる。
局所アドレスをほとんどあるいは全く持たない制御方式に勾配上昇パルス工学(GrAPE)を実装した。
論文 参考訳（メタデータ） (2026-06-01T14:06:14Z) - A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
分散量子最適化のための構造認識フレームワークを提案する。
検索スペースが$N$の場合、我々のフレームワークはプロセッサやセパレータに依存した要素に対して$O(sqrtN)$クエリ複雑性を達成する。
構造を考慮した分解は、量子ネットワーク上でのスケーラブルな分散量子最適化に実践的な道をもたらすことを示す。
論文 参考訳（メタデータ） (2026-03-08T15:15:52Z) - BPDQ: Bit-Plane Decomposition Quantization on a Variable Grid for Large Language Models [56.504879072674015]
本稿では,ビットプレーンとスカラー係数による可変量子化グリッドを構成するビットプレーン分解量子化(BPDQ)を提案する。
BPDQは、1つのGTX 3090上でQwen2.5-72Bを83.85%のGSM8Kの精度で提供できる(ただし16ビットでは90.83%)。
論文 参考訳（メタデータ） (2026-02-04T02:54:37Z) - Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary
Optimization [44.96576908957141]
本稿では,量子コンピュータ上での2次線形反復問題を解くために,フランク・ウルフアルゴリズム(Q-FW)に基づく古典量子ハイブリッドフレームワークを提案する。
論文 参考訳（メタデータ） (2022-03-23T18:00:03Z) - Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable
Approach for Continuous Markov Random Fields [53.31927549039624]
断片的な離散化は既存の離散化問題と矛盾しないことを示す。
この理論を2つの画像のマッチング問題に適用する。
論文 参考訳（メタデータ） (2021-07-13T12:31:06Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。