論文の概要: A comparison between D-wave and a classical approximation algorithm and
a heuristic for computing the ground state of an Ising spin glass
- arxiv url: http://arxiv.org/abs/2105.00537v1
- Date: Sun, 2 May 2021 19:18:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-01 19:50:32.759290
- Title: A comparison between D-wave and a classical approximation algorithm and
a heuristic for computing the ground state of an Ising spin glass
- Title（参考訳）: D波と古典近似アルゴリズムの比較とイジングスピングラスの基底状態計算のためのヒューリスティック
- Authors: Ran Yaacoby, Nathan Schaar, Leon Kellerhals, Oren Raz, Danny Hermelin
and Rami Pugatch
- Abstract要約: 断熱量子コンピュータD-waveは、キメラグラフ上のIsing-spinガラスの基底状態の近似を計算するのに特に適している。
本稿では,D-wave コンピュータに対する有界次数グラフ上でのイジングスピンガラス問題の解法について,最近開発された近似アルゴリズムの性能比較を行った。
- 参考スコア（独自算出の注目度）: 2.6787357840625257
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Finding the ground state of an Ising-spin glass on general graphs belongs to
the class of NP-hard problems, widely believed to have no efficient
polynomial-time algorithms for solving them. An approach developed in computer
science for dealing with such problems is to devise approximation algorithms
that run in polynomial time, and provide solutions with provable guarantees on
their quality in terms of the optimal unknown solution. Recently, several
algorithms for the Ising-spin glass problem on a graph that provide different
approximation guarantees were introduced albeit without implementation. Also
recently, D-wave company constructed a physical realization of an adiabatic
quantum computer, and enabled researchers to access it. D-wave is particularly
suited for computing an approximation for the ground state of an Ising spin
glass on its chimera graph -- a graph with bounded degree. In this work, we
compare the performance of a recently developed approximation algorithm for
solving the Ising spin glass problem on graphs of bounded degree against the
D-wave computer. We also compared a heuristic tailored specifically to handle
the fixed D-wave chimera graph. D-wave computer was able to find better
approximations to all the random instances we studied. Furthermore the
convergence times of D-wave were also significantly better. These results
indicate the merit of D-wave computer under certain specific instances. More
broadly, our method is relevant to other performance comparison studies. We
suggest that it is important to compare the performance of quantum computers
not only against exact classical algorithms with exponential run-time scaling,
but also to approximation algorithms with polynomial run-time scaling and a
provable guarantee on performance.
- Abstract（参考訳）: 一般グラフ上のイジン・スピンガラスの基底状態を見つけることは、NPハード問題のクラスに属し、それらの解法に効率的な多項式時間アルゴリズムが存在しないと広く信じられている。
このような問題に対処するためにコンピュータサイエンスで開発されたアプローチは、多項式時間で実行される近似アルゴリズムを考案し、最適な未知解の観点でその品質の証明可能な保証を提供する。
近年、異なる近似保証を提供するグラフ上のイジングスピングラス問題に対するいくつかのアルゴリズムが実装なしで導入された。
最近では、D波会社が断熱型量子コンピュータの物理的実現を開発し、研究者がアクセスできるようにした。
D波は特に、そのキメラグラフ上のイジングスピンガラスの基底状態(有界グラフ)の近似を計算するのに適している。
本研究では,d-waveコンピュータと有界次数グラフ上のイジングスピングラス問題を解くために最近開発した近似アルゴリズムの性能を比較する。
また、固定D波キメラグラフを扱うためのヒューリスティックな調整も行った。
d-waveコンピュータは、研究したすべてのランダムなインスタンスに対するより良い近似を見つけることができた。
さらにD波の収束時間も有意に改善した。
これらの結果は、特定の特定の事例下でのD波コンピュータの利点を示している。
より広範に、本手法は他の性能比較研究と関係がある。
我々は,量子コンピュータの性能を,古典的アルゴリズムと指数関数的実行時のスケーリングに加えて,多項式実行時のスケーリングと性能保証を備えた近似アルゴリズムと比較することが重要であることを示唆する。
関連論文リスト
- Imaginary Hamiltonian variational ansatz for combinatorial optimization problems [3.14105061893604]
パラメタライズド量子ゲートのツリー配置を導入し、1ラウンド$i$HVAを用いて任意のツリーグラフを正確に解けるようにする。
我々のアンサッツは、最大24ノードと$D leq 5$のグラフに対して、MaxCutを正確に解く。
論文 参考訳（メタデータ） (2024-08-17T03:34:17Z) - A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。
汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。
MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
論文 参考訳（メタデータ） (2024-07-19T08:29:12Z) - GPU Based Differential Evolution: New Insights and Comparative Study [7.5961910202572644]
この研究は、GPUベースの微分進化アルゴリズムの文献における主要なアーキテクチャ選択についてレビューする。
新しいGPUベースの数値最適化ベンチマークを導入し、GPUベースのDEMアルゴリズムを評価し比較する。
論文 参考訳（メタデータ） (2024-05-26T12:40:39Z) - Quantum Hamiltonian Algorithms for Maximum Independent Sets [6.772902928686719]
PKアルゴリズムと呼ばれる別のアルゴリズムは、独立集合が創発的PXPモデルの非アーベルゲージ行列によって支配されるメディアグラフ上で拡散することを明らかにする。
2つのアルゴリズムは数学的に等価であるが、PKアルゴリズムはより効率的でリソース節約性能を示す。
論文 参考訳（メタデータ） (2023-10-23T04:00:34Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Efficient and Accurate Optimal Transport with Mirror Descent and
Conjugate Gradients [15.128885770407132]
本研究では, エントロピー的最適輸送, ミラー降下, 共役勾配の文献から, 最適輸送のための新しいアルゴリズムを設計する。
我々のスケーラブルでGPU並列化可能なアルゴリズムは、ワッサースタイン距離を極端精度で計算することができ、数値安定性の問題なく相対誤差レート10～8ドルに達することができる。
論文 参考訳（メタデータ） (2023-07-17T14:09:43Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳（メタデータ） (2021-11-23T18:10:48Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳（メタデータ） (2021-11-19T12:35:26Z) - A Fast PC Algorithm with Reversed-order Pruning and A Parallelization
Strategy [22.31288740171446]
PCアルゴリズムは観測データに基づく因果構造発見のための最先端のアルゴリズムである。
条件付き独立テストが実行された場合、最悪の場合、計算コストがかかる可能性がある。
これにより、タスクが数百から数千のノードを含む場合、アルゴリズムは計算的に難解になる。
本稿では、2つのノードを独立にレンダリングする条件セットが非特異であり、特定の冗長ノードを含む場合、結果の精度を犠牲にしない、という批判的な観察を提案する。
論文 参考訳（メタデータ） (2021-09-10T02:22:10Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。