論文の概要: Sparse QUBO Formulation for Efficient Embedding via Network-Based Decomposition of Equality and Inequality Constraints

• arxiv url: http://arxiv.org/abs/2601.18108v1
• Date: Mon, 26 Jan 2026 03:40:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-27 15:23:08.653304
• Title: Sparse QUBO Formulation for Efficient Embedding via Network-Based Decomposition of Equality and Inequality Constraints
• Title（参考訳）: ネットワークによる平等・不平等制約の分解による効率的な埋め込みのためのスパースQUBOの定式化
• Authors: Kohei Suda, Soshun Naito, Yoshihiko Hasegawa,
• Abstract要約: 等式制約と不等式制約に対して,かなりスペーサーな論理QUBOモデルを構築する手法を提案する。 特定のネットワーク構造に基づいて補助変数を追加することにより、本手法は元の制約をより小さく、より管理しやすい制約に分解する。 D-Waveのハードウェア上での実験結果から,我々の定式化は埋め込みに必要な量子ビット数を大幅に削減することを示した。
• 参考スコア（独自算出の注目度）: 0.35331503620315147
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum annealing is a promising approach for solving combinatorial optimization problems. However, its performance is often limited by the overhead of additional qubits required for embedding logical QUBO models onto quantum annealers. This overhead becomes severe when logical QUBO models have dense connectivity. Such dense structures frequently arise when formulating equality and inequality constraints. To address this issue, we propose a method to construct a significantly sparser logical QUBO model for these constraints. By adding auxiliary variables based on specific network structures, our approach decomposes the original constraint into smaller, more manageable constraints. We demonstrate that this method reduces the number of edges (quadratic terms) from $O(N^2)$ to $O(N)$ for the one-hot constraint and to $O(N\log N)$ in the worst case for general equality constraints, where $N$ is the number of variables. Experimental results on D-Wave's hardware show that our formulation leads to substantial reductions in the number of qubits required for embedding, shorter average chain lengths, lower chain break rates, and higher feasible solution rates compared to conventional methods. This work provides a practical tool for efficiently solving constrained optimization problems on current and future quantum annealers.
• Abstract（参考訳）: 量子アニールは組合せ最適化問題の解決に有望なアプローチである。 しかし、その性能は論理的QUBOモデルを量子アンニールに埋め込むのに必要な追加の量子ビットのオーバーヘッドによって制限されることが多い。 このオーバーヘッドは、論理的QUBOモデルが密接な接続性を持つ場合、深刻になる。 そのような高密度構造は、等式と不等式制約を定式化するときにしばしば生じる。 この問題に対処するために、これらの制約に対してかなりスペーサーな論理QUBOモデルを構築する方法を提案する。 特定のネットワーク構造に基づいて補助変数を追加することにより、本手法は元の制約をより小さく、より管理しやすい制約に分解する。 この方法では, 1ホット制約に対して$O(N^2)$から$O(N)$, 一般等式制約では$O(N\log N)$, 変数数では$N$となる。 D-Wave のハードウェア上での実験結果から,我々の定式化は,埋め込みに必要な量子ビット数,平均鎖長の短縮,チェーン切断率の低減,従来手法よりも実現可能な解率の向上につながることが示された。 この研究は、現在の量子アニーラーと将来の量子アニーラーの制約付き最適化問題を効率的に解くための実用的なツールを提供する。

関連論文リスト

• MPQ-DMv2: Flexible Residual Mixed Precision Quantization for Low-Bit Diffusion Models with Temporal Distillation [74.34220141721231]
  我々は,textbfMixed textbfPrecision textbfQuantizationフレームワークを改良したMPQ-DMv2を提案する。
  論文  参考訳（メタデータ） (2025-07-06T08:16:50Z)
• Quantum-Classical Hybrid Quantized Neural Network [8.382617481718643]
  本稿では、任意のアクティベーションと損失関数の使用を可能にする、量子化されたニューラルネットワークトレーニングのための新しい擬似バイナリ最適化(QBO)モデルを提案する。 我々はQCBO問題を直接解くために量子コンピューティングを利用するQCGD(Quantum Gradient Conditional Descent)アルゴリズムを用いる。
  論文  参考訳（メタデータ） (2025-06-23T02:12:36Z)
• 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)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Advanced unembedding techniques for quantum annealers [0.0]
  本研究は4つの重要なNPハード問題に対するアンエンベディング手法について述べる。 我々の手法は単純であり、解決される問題の構造的特性を生かしている。
  論文  参考訳（メタデータ） (2020-09-10T17:49:43Z)

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

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