論文の概要: Experimental analysis of quantum annealers and hybrid solvers using
benchmark optimization problems
- arxiv url: http://arxiv.org/abs/2202.08939v1
- Date: Thu, 17 Feb 2022 23:46:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-25 12:41:01.444145
- Title: Experimental analysis of quantum annealers and hybrid solvers using
benchmark optimization problems
- Title（参考訳）: ベンチマーク最適化問題を用いた量子アニールとハイブリッドソルバの実験解析
- Authors: Evangelos Stogiannos and Christos Papalitsas and Theodore Andronikos
- Abstract要約: 本稿では、D-Waveの量子システムにおけるハミルトンサイクル問題(HCP)とトラベリングセールスマン問題(TSP)について検討する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies the Hamiltonian Cycle Problem (HCP) and the Traveling
Salesman Problem (TSP) on D-Wave's quantum systems. Initially, motivated by the
fact that most libraries present their benchmark instances in terms of
adjacency matrices, we develop a novel matrix formulation for the HCP and TSP
Hamiltonians, which enables the seamless and automatic integration of benchmark
instances in quantum platforms. our extensive experimental tests have led us to
some interesting conclusions. D-Wave's {\tt Advantage\_system4.1} is more
efficient than {\tt Advantage\_system1.1} both in terms of qubit utilization
and quality of solutions. Finally, we experimentally establish that D-Wave's
Hybrid solvers always provide a valid solution to a problem, without violating
the QUBO constraints, even for arbitrarily big problems, of the order of $120$
nodes. When solving TSP instances, the solutions produced by the quantum
annealer are often invalid, in the sense that they violate the topology of the
graph. To address this use we advocate the use of \emph{min-max normalization}
for the coefficients of the TSP Hamiltonian. Finally, we present a thorough
mathematical analysis on the precise number of constraints required to express
the HCP and TSP Hamiltonians. This analysis, explains quantitatively why,
almost always, running incomplete graph instances requires more qubits than
complete instances. It turns out that incomplete graph require more quadratic
constraints than complete graphs, a fact that has been corroborated by a series
of experiments.
- Abstract（参考訳）: 本稿では、D-Waveの量子システムにおけるハミルトンサイクル問題(HCP)とトラベリングセールスマン問題(TSP)について検討する。
当初、ほとんどのライブラリが隣接行列でベンチマークインスタンスを提示するという事実に動機付けられて、量子プラットフォームにおけるベンチマークインスタンスのシームレスかつ自動統合を可能にする、HCPおよびTSPハミルトニアンの新しい行列定式化を開発した。
大規模な実験の結果 興味深い結論が得られました
D-Wave の {\tt Advantage\_system4.1} は、量子ビット利用とソリューションの品質の両方において、 {\tt Advantage\_system1.1} よりも効率的である。
最後に、D-WaveのHybridソルバがQUBO制約に違反することなく、任意の大問題に対して120ドルノードの順序で常に有効なソリューションを提供することを実験的に確立する。
tspインスタンスを解くとき、量子アニーラーによって生成される解はしばしば、グラフのトポロジーに違反しているという意味で無効である。
この用途に対処するために、TSPハミルトニアンの係数に対する \emph{min-max normalization} の使用を提唱する。
最後に, hcp と tsp のハミルトニアンを表現するのに必要な制約の正確な数を数学的に解析する。
この分析は、不完全なグラフインスタンスを実行するのに完全インスタンスよりもクビットを必要とする理由を定量的に説明している。
不完全グラフは完備グラフよりも二次的な制約を必要とすることが判明し、これは一連の実験で裏付けられている。
関連論文リスト
- 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) - Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
量子計算カラーブルーを用いて解くのに適した二次非拘束バイナリ最適化(QUBO)問題を定式化する。
この定式化は、最大自己充足力とそれらの間を流れる最小限のパワーを持つコミュニティを見つけることを目的としている。
D-Waveのハイブリッド量子古典解法、古典解法、分枝結合解法などである。
論文 参考訳（メタデータ） (2024-07-09T11:44:58Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Quantum Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
行列乗法重み付けアルゴリズムの量子化'''は、古典的アルゴリズムよりも2次的に高速なSDPの近似解が得られることを示す。
この量子アルゴリズムを改良し、ギブス状態サンプリング器を熱純量子(TPQ)状態に置き換えることで、同様のスピードアップが得られることを示す。
論文 参考訳（メタデータ） (2023-10-11T18:00:53Z) - A Hybrid Quantum-Classical Approach to the Electric Mobility Problem [0.8796261172196743]
NP-hard Electric Vehicle Fleet Charging and Allocation Problemのためのハイブリッド量子古典ルーチンを提案する。
分解法の性能を古典的・量子的メタヒューリスティックスで評価する。
提案手法の主な利点は、多くの不等式制約のある現実的な問題に対して量子ベースの方法を可能にすることである。
論文 参考訳（メタデータ） (2023-10-04T12:14:56Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳（メタデータ） (2022-11-22T18:54:48Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳（メタデータ） (2022-03-11T17:19:26Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。