論文の概要: Hierarchical divide and conquer quantum approach to combinatorial optimization problems with tunable reduction

• arxiv url: http://arxiv.org/abs/2512.18464v1
• Date: Sat, 20 Dec 2025 18:36:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-23 18:54:32.350091
• Title: Hierarchical divide and conquer quantum approach to combinatorial optimization problems with tunable reduction
• Title（参考訳）: チューナブル還元を伴う組合せ最適化問題に対する階層的分割と量子アプローチの克服
• Authors: Mathias Schmid, Naeimeh Mohseni, Michael J. Hartmann,
• Abstract要約: 我々は、最適化問題をより小さな量子プロセッサ上で表現できる部分グラフに分割する分割と征服のアプローチを導入する。 このアプローチにより、$sim |mathcalV| / 4$ qubits 上の $|mathcalV|=40$ 個の離散変数を持つ重み付き3つの正則グラフ上の最適化問題を解けるが、近似比は $sim99.9%$ である。
• 参考スコア（独自算出の注目度）: 0.6117371161379209
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization is considered a promising class of problems in which quantum computers can show significant advantages. However, problems of practical relevance typically have more variables than current or foreseeable quantum computers have qubits. Here we introduce a divide and conquer approach that partitions the optimization problem into subgraphs that can be represented on smaller quantum processors. We then find all states of the subgraphs that can possibly be part of the solution to the entire problem by determining the cost or energy ranges in which the local subgraph energies of these states must be contained. This allows us to reduce the problem by only considering the subspace spanned by these states. We then recombine the system using a binary encoding for each subgraph with a local energy ordering. This process can be iterated until no further reduction is possible. We also find that the number of necessary qubits can be reduced further when only retaining states in a fraction of the relevant energy range at very little expense in terms of approximation ratio to the global ground state. In numerical simulations, we find that our approach allows us to solve combinatorial optimization problems on weighted random 3-regular graphs with $|\mathcal{V}|=40$ discrete variables on $\sim |\mathcal{V}| / 4$ qubits while retaining a possible approximation ratio of $\sim99.9\%$. We also observe an increasing reduction with larger system sizes.
• Abstract（参考訳）: 組合せ最適化は、量子コンピュータが大きな優位性を示す可能性のある、有望な問題のクラスであると考えられている。 しかし、実用関連性の問題は通常、現在の量子コンピュータや予測可能な量子コンピュータよりも多くの変数を持つ。 ここでは、最適化問題をより小さな量子プロセッサ上で表現できる部分グラフに分割する分割と征服のアプローチを導入する。 次に、これらの状態の局所的な部分グラフエネルギーを含まなければならないコストまたはエネルギー範囲を決定することによって、問題全体の解の一部となる可能性のある部分グラフのすべての状態を見つける。 これにより、これらの状態にまたがる部分空間のみを考慮すれば問題を減らすことができる。 次に,各サブグラフのバイナリエンコーディングを局所的なエネルギー順序付けで再結合する。 このプロセスは、これ以上の削減が不可能になるまで繰り返すことができる。 また、地球基底状態に対する近似比において、関連するエネルギー範囲のごく一部の状態のみを非常に少ない費用で保持する場合、必要な量子ビットの数を減らせることも見出した。 数値シミュレーションにおいて、我々の手法は、$\sim |\mathcal{V}| / 4$ qubits 上の $|\mathcal{V}|=40$ 離散変数を持つ重み付きランダムな3つの正則グラフ上の組合せ最適化問題を解けるが、その近似比は $\sim99.9\%$ である。 また,システムサイズが大きくなるにつれて減少する傾向が見られた。

関連論文リスト

• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  本稿では,QUBO行列におけるテクステミシンメトリの概念を紹介する。 提案アルゴリズムは結合数と回路深さを最大45%削減することを示した。
  論文  参考訳（メタデータ） (2024-12-18T12:05:18Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  余分なスラック変数を必要としない代替手法を提案する。 我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。 この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
  論文  参考訳（メタデータ） (2022-11-25T06:05:18Z)
• Reconstructing the whole from its parts [0.0]
  我々は、多人数シナリオにおいて、広範囲の自己整合性辺縁還元から大域量子状態を解析的に決定する。 我々は, 分極チャネルを通過した後に, 自己整合した多重粒子の辺縁還元は, 大域量子状態の存在と相容れないことを示した。
  論文  参考訳（メタデータ） (2022-09-28T15:04:22Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。 我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
  論文  参考訳（メタデータ） (2022-02-10T18:59:52Z)
• Computational Overhead of Locality Reduction in Binary Optimization Problems [0.0]
  本稿では,2つの局所的(二次的)コスト関数のみに対応可能な解法の大部分に必要な局所性低減の効果について論じる。 Microsoft Azure Quantumのモンテカルロ並列解法を用いて、2つの局所表現へのポスト還元により、問題の解決がかなり困難になることを示す。
  論文  参考訳（メタデータ） (2020-12-17T15:49:55Z)
• Advanced unembedding techniques for quantum annealers [0.0]
  本研究は4つの重要なNPハード問題に対するアンエンベディング手法について述べる。 我々の手法は単純であり、解決される問題の構造的特性を生かしている。
  論文  参考訳（メタデータ） (2020-09-10T17:49:43Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)

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

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