論文の概要: Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
- arxiv url: http://arxiv.org/abs/2301.03009v4
- Date: Wed, 23 Oct 2024 21:40:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-25 12:48:49.851066
- Title: Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
- Title（参考訳）: 最小組込み組合せ最適化問題に対する3世代D波量子アニールの比較
- Authors: Elijah Pelofske,
- Abstract要約: 我々は3世代にわたるD-Wave量子アニールのベンチマークを報告する。
イジングあるいは等価なQUBOは、これらの問題の定式化は順序の減少のために補助変数を必要としない。
- 参考スコア（独自算出の注目度）: 1.0878040851638
- License:
- Abstract: Quantum annealing is a novel type of analog computation that aims to use quantum mechanical fluctuations to search for optimal solutions of Ising problems. Quantum annealing in the Transverse Ising model, implemented on D-Wave QPUs, are available as cloud computing resources. In this article we report concise benchmarks across three generations of D-Wave quantum annealers, consisting of four different devices, for the NP-Hard combinatorial optimization problems unweighted maximum clique and unweighted maximum cut on random graphs. The Ising, or equivalently QUBO, formulation of these problems do not require auxiliary variables for order reduction, and their overall structure and weights are not highly complex, which makes these problems simple test cases to understand the sampling capability of current D-Wave quantum annealers. All-to-all minor embeddings of size $52$, with relatively uniform chain lengths, are used for a direct comparison across the Chimera, Pegasus, and Zephyr device topologies. A grid search over annealing times and the minor embedding chain strengths is performed in order to determine the level of reasonable performance for each device and problem type. Experiment metrics that are reported are approximation ratios for non-broken chain samples and chain break proportions. How fairly the quantum annealers sample optimal maximum cliques, for instances which contain multiple maximum cliques, is also quantified using entropy of the measured ground state distributions. The newest generation of quantum annealing hardware, which has a Zephyr hardware connectivity, performed the best overall with respect to approximation ratios and chain break frequencies.
- Abstract（参考訳）: 量子アニーリング(quantum annealing)は、量子力学的揺らぎを用いてイジング問題の最適解を探すことを目的とした、新しいタイプのアナログ計算である。
D-Wave QPU上に実装されたTransverse Isingモデルにおける量子アニールは、クラウドコンピューティングリソースとして利用可能である。
本稿では、NP-Hard組合せ最適化問題に対して、4つの異なるデバイスからなるD-Wave量子アニールの3世代にわたる簡潔なベンチマークを報告する。
アイシング(QUBO)は、これらの問題の定式化は順序の減少のために補助変数を必要とせず、その全体構造と重みは非常に複雑ではないため、これらの問題は現在のD-Wave量子アニールのサンプリング能力を理解するための単純なテストケースである。
キメラ、ペガサス、ゼファーのデバイストポロジーを直接比較するために、長さが比較的均一な5,2$の全ての小さな埋め込みが用いられる。
各装置の合理的性能と問題種別を判定するために、アニール時間と小さな埋め込みチェーン強度を網羅探索する。
報告されている実験指標は、非破壊鎖サンプルの近似比と連鎖破壊比である。
測定された基底状態分布のエントロピーを用いて、複数の最大傾きを含む場合において、量子異方体が最適な最大傾きをいかに正確にサンプリングするかを定量化する。
最新世代の量子アニールハードウェアは、Zephyrのハードウェア接続を備えており、近似比とチェーン破断周波数に関して、全体として最高の性能を発揮した。
関連論文リスト
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking [1.6385815610837167]
我々は,多数の小さな離散係数スピングラスイジングモデルを融合させることにより,ポジフォーム植込みQUBOを計算的に困難にすることを検討する。
3つのD-Wave超伝導量子アニーリングプロセッサの性能をベンチマークする。
D-Wave QPUの地中サンプリング成功率は、我々が採用するランダムQUBOのサイズに対して変化しないことがわかった。
論文 参考訳（メタデータ） (2024-11-06T02:46:33Z) - Optimizing random local Hamiltonians by dissipation [44.99833362998488]
簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。
この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
論文 参考訳（メタデータ） (2024-11-04T20:21:16Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Posiform Planting: Generating QUBO Instances for Benchmarking [2.7624021966289605]
本稿では,任意のサイズのランダムQUBOインスタンスを既知の最適解で生成する,posform plantingと呼ばれる新しい手法を提案する。
実験では,最大5,627ドルキュービットの最適化問題の最適植込み解をサンプリングするD-Wave量子アニールの能力を実証した。
論文 参考訳（メタデータ） (2023-08-10T21:23:41Z) - Trainable Variational Quantum-Multiblock ADMM Algorithm for Generation
Scheduling [0.0]
本稿では、量子コンピューティング、機械学習、分散最適化による生成スケジューリングのための2ループ量子解アルゴリズムを提案する。
この目的は、実用的な電力系統の問題を解決するために、限られた量子ビット数を持つ短期量子機械の雑音を緩和することである。
論文 参考訳（メタデータ） (2023-03-28T21:31:39Z) - Importance sampling for stochastic quantum simulations [68.8204255655161]
我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。
サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。
格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
論文 参考訳（メタデータ） (2022-12-12T15:06:32Z) - Noise Dynamics of Quantum Annealers: Estimating the Effective Noise
Using Idle Qubits [0.0]
我々は、D-Waveデバイスに解の質の長期的傾向があり、使用されていない量子ビットは、量子システムの現在のノイズレベルを測定するのに使用できることを示した。
そこで本研究では,チップの未使用部分にQUBOを組み込んで解決する手法を提案する。
論文 参考訳（メタデータ） (2022-09-12T23:06:51Z) - Sampling Frequency Thresholds for Quantum Advantage of Quantum
Approximate Optimization Algorithm [0.7046417074932257]
量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。
古典的解法は線形時間複雑性において高品質な近似解を生成することができる。
異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
論文 参考訳（メタデータ） (2022-06-07T20:59:19Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。