論文の概要: Solving Larger Optimization Problems Using Parallel Quantum Annealing

• arxiv url: http://arxiv.org/abs/2205.12165v1
• Date: Tue, 24 May 2022 15:56:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-11 21:53:48.835346
• Title: Solving Larger Optimization Problems Using Parallel Quantum Annealing
• Title（参考訳）: 並列量子アニーリングによる大規模最適化問題の解法
• Authors: Elijah Pelofske, Georg Hahn, Hristo N. Djidjev
• Abstract要約: 並列量子アニールとグラフ分解を組み合わせたハイブリッドアプローチにより、より大規模な最適化問題を正確に解けることを示す。 最大傾き問題を最大120ノードと6395エッジのグラフに適用する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum annealing has the potential to find low energy solutions of NP-hard problems that can be expressed as quadratic unconstrained binary optimization problems. However, the hardware of the quantum annealer manufactured by D-Wave Systems, which we consider in this work, is sparsely connected and moderately sized (on the order of thousands of qubits), thus necessitating a minor-embedding of a logical problem onto the physical qubit hardware. The combination of relatively small hardware sizes and the necessity of a minor-embedding can mean that solving large optimization problems is not possible on current quantum annealers. In this research, we show that a hybrid approach combining parallel quantum annealing with graph decomposition allows one to solve larger optimization problem accurately. We apply the approach on the Maximum Clique problem on graphs with up to 120 nodes and 6395 edges.
• Abstract（参考訳）: 量子アニールは2次非制約二元最適化問題として表されるNPハード問題の低エネルギー解を見つけることができる。 しかし、我々が本研究で検討しているd-waveシステムによって製造される量子アニーラーのハードウェアは、(数千キュービットのオーダーで)疎結合であり、適度にサイズが小さいため、論理的な問題を物理キュービットハードウェアに小さな組み込む必要がある。 比較的小さなハードウェアサイズとマイナーエンベディングの必要性の組み合わせは、現在の量子アニールでは大きな最適化問題を解くことができないことを意味する。 本研究では,並列量子アニーリングとグラフ分解を組み合わせることによって,より大きな最適化問題を正確に解くことができることを示す。 このアプローチを最大120ノードと6395エッジのグラフ上の最大クライク問題に適用する。

関連論文リスト

• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems [0.0]
  ゲートモデル量子コンピュータにおける二項最適化問題に対する包括的量子解法を提案する。 最大127キュービットの問題の正しい解を一貫して提供する。 我々は、古典的に非自明な2進最適化問題に対して、IBM量子コンピュータ上でこの解法をベンチマークする。
  論文  参考訳（メタデータ） (2024-06-03T19:08:01Z)
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization [0.0]
  本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。 目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
  論文  参考訳（メタデータ） (2023-05-23T16:17:57Z)
• Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer [0.0]
  NPハード問題は、一般時間アルゴリズムで正確に解けるとは考えられていない。 本稿では,問題のサイズに応じて対数的にスケールする独自手法を構築した。 これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。
  論文  参考訳（メタデータ） (2023-01-17T16:03:33Z)
• 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)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Parallel Quantum Annealing [0.0]
  D-Wave Systems, Inc. の量子アニールは、NPハード問題の高品質な解を計算する効率的な方法を提供する。 本稿では,利用可能な量子ビットをよりよく活用するための並列量子アニール法を提案する。 本手法は,最大傾き問題の解法として,TTS(Time-to-Solution)を用いて劇的な高速化を実現することができることを示す。
  論文  参考訳（メタデータ） (2021-11-11T00:10:44Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Advanced unembedding techniques for quantum annealers [0.0]
  本研究は4つの重要なNPハード問題に対するアンエンベディング手法について述べる。 我々の手法は単純であり、解決される問題の構造的特性を生かしている。
  論文  参考訳（メタデータ） (2020-09-10T17:49:43Z)

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

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