論文の概要: Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization
- arxiv url: http://arxiv.org/abs/2604.21123v1
- Date: Wed, 22 Apr 2026 22:26:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-24 14:40:06.199866
- Title: Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization
- Title（参考訳）: 量子最適化のためのグラフ分割問題の量子効率およびゲート効率符号化
- Authors: Tristan Zaborniak, Prashanti Priya Angara, Vikram Khipple Mulligan, Hausi Müller, Ulrike Stege,
- Abstract要約: グラフ分割問題に対して、量子ビットおよびゲート効率の高い高次非制約バイナリ最適化(HUBO)符号化を導入する。
これは量子環境でこれらの問題の最適化バージョンに対処する最初の試みである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We introduce a qubit- and gate-efficient higher-order unconstrained binary optimization (HUBO) encoding for graph partitioning problems requiring label-count minimization. This widely applicable class of problems includes minimum graph coloring, minimum $k$-cut, and community detection. To the best of our knowledge, this is the first work to address the optimization versions of these problems in a quantum setting, rather than only their decision counterparts. Our construction encodes each $k$-valued vertex variable using $\lceil \log_2 k \rceil$ bits and employs a novel lexicographic penalty system that implicitly minimizes partition count without requiring dedicated indicator variables. We derive provably sufficient conditions on all penalty coefficients, including those arising from Rosenberg quadratization, guaranteeing feasibility and optimality of the lowest-energy solution. Analogous conditions are derived for a one-hot encoding to enable controlled comparison. We also show that our encoding reduces two-qubit gate count per QAOA layer from $Θ(|V||k|^2 + |E||k|)$ for the one-hot encoding to $Θ(|E| \cdot |k| \lceil\log_2 |k|\rceil)$. Benchmarking on a quantum annealer demonstrates that our logarithmic encoding significantly improves solution quality and time-to-solution for minimum graph coloring relative to one-hot encoding, with greater advantage as problem size increases.
- Abstract（参考訳）: ラベル数最小化を必要とするグラフ分割問題に対して、qubit- and gate- efficient higher-order unconstrained binary optimization (HUBO) 符号化を導入する。
この広く適用可能な問題のクラスには、最小グラフ彩色、最小$k$-cut、コミュニティ検出が含まれる。
私たちの知る限りでは、これはこれらの問題の最適化バージョンを量子環境で解決する最初の試みであり、その決定だけではありません。
我々の構成では、$\lceil \log_2 k \rceil$ bitsを使用して各$k$値の頂点変数をエンコードし、専用の指標変数を必要とせずにパーティションカウントを暗黙的に最小化する新しい語彙ペナルティシステムを採用している。
ローゼンバーグの二次化から生じるものを含め、全てのペナルティ係数について十分な条件を導出し、最低エネルギー解の実現可能性と最適性を保証する。
制御された比較を可能にするワンホット符号化のために、アナログ条件が導出される。
また、この符号化により、QAOA層当たりの2量子ゲート数(英語版)を、(|V||k|^2 + |E||k|)$から(|E| \cdot |k| \lceil\log_2 |k|\rceil)$へ還元することを示す。
量子アニーラー上でのベンチマークにより、我々の対数エンコーディングは、問題のサイズが大きくなるにつれて、より有利な1ホットエンコーディングに対する最小グラフ彩色における解の質と解法を著しく改善することを示した。
関連論文リスト
- EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
既存の技術は情報損失のコストで量子ビットの削減に依存しており、計算性能は劣化している。
等価保存量子ビット効率QAOAを提案し、性能を劣化させることなく必要なキュービット数を著しく削減する。
完全独立変数を持つ非制約問題を除いて,大規模最適化問題に広く適用可能であることを示す。
論文 参考訳（メタデータ） (2026-04-20T13:57:49Z) - Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut [0.8084252698425037]
グラフ上の整数問題に適用された量子近似最適化アルゴリズム(QAOA)について検討する。
任意の大きさの高次$d$正則グラフ上で、深さ-p$QAOA予想に対する一般的な反復公式を導出する。
その結果、二進法から整数最適化問題への移動は、量子的優位性のために新しい道を開くことができることを示した。
論文 参考訳（メタデータ） (2026-02-05T18:11:18Z) - Hierarchical divide and conquer quantum approach to combinatorial optimization problems with tunable reduction [0.6117371161379209]
我々は、最適化問題をより小さな量子プロセッサ上で表現できる部分グラフに分割する分割と征服のアプローチを導入する。
このアプローチにより、$sim |mathcalV| / 4$ qubits 上の $|mathcalV|=40$ 個の離散変数を持つ重み付き3つの正則グラフ上の最適化問題を解けるが、近似比は $sim99.9%$ である。
論文 参考訳（メタデータ） (2025-12-20T18:36:10Z) - Verifiable Quantum Advantage via Optimized DQI Circuits [2.149968465453488]
Decoded Quantum Interferometry (DQI) はスーパーポリノミカル量子スピードアップのためのフレームワークを提供する。
DQIをリードソロモン(Reed-Solomon, RS)コードである最適多項式区間(OPI)問題に適用する。
我々は、OPIのDQIが、最適スピードアップによる検証可能な量子優位性の最初の候補であることを示す。
論文 参考訳（メタデータ） (2025-10-13T03:19:28Z) - Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables [0.7015624626359264]
トラベリングパーソン販売問題(TSP)の例を用いて、最適化問題に対するより量子効率の高い回路構成を示す。
特定の冗長性を取り除いた場合、上記の従来の符号化に比べて、必要量子ビットの数は線形因子によって減少することができる。
実験の結果, 提案した符号化法と同等に精度が向上する一方, 必要な古典的反復回数はわずかに増加することがわかった。
論文 参考訳（メタデータ） (2024-12-10T12:12:34Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳（メタデータ） (2022-11-25T06:05:18Z) - 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) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。