論文の概要: Limitations of tensor network approaches for optimization and sampling: A comparison against quantum and classical Ising machines

• arxiv url: http://arxiv.org/abs/2411.16431v1
• Date: Mon, 25 Nov 2024 14:35:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-26 14:18:44.421816
• Title: Limitations of tensor network approaches for optimization and sampling: A comparison against quantum and classical Ising machines
• Title（参考訳）: テンソルネットワークによる最適化とサンプリングの限界:量子および古典的イジングマシンとの比較
• Authors: Anna Maria Dziubyna, Tomasz Śmierzchalski, Bartłomiej Gardas, Marek M. Rams, Masoud Mohseni,
• Abstract要約: 相互作用グラフを用いたIsingスピングラスシステムの低エネルギースペクトルを明らかにするアルゴリズムを開発した。 我々の決定論的アプローチは、分岐と境界の探索戦略と、辺辺の近似計算を組み合わせたものである。 ペガサスグラフとゼファーグラフで定義されたランダムな問題に対して、最大数千スピンのアプローチをベンチマークする。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Optimization problems pose challenges across various fields. In recent years, quantum annealers have emerged as a promising platform for tackling such challenges. To provide a new perspective, we develop a heuristic tensor-network-based algorithm to reveal the low-energy spectrum of Ising spin-glass systems with interaction graphs relevant to present-day quantum annealers. Our deterministic approach combines a branch-and-bound search strategy with an approximate calculation of marginals via tensor-network contractions. Its application to quasi-two-dimensional lattices with large unit cells of up to 24 spins, realized in current quantum annealing processors, requires a dedicated approach that utilizes sparse structures in the tensor network representation and GPU hardware acceleration. We benchmark our approach on random problems defined on Pegasus and Zephyr graphs with up to a few thousand spins, comparing it against the D-Wave Advantage quantum annealer and Simulated Bifurcation algorithm, with the latter representing an emerging class of classical Ising solvers. Apart from the quality of the best solutions, we compare the diversity of low-energy states sampled by all the solvers. For the biggest considered problems with over 5000 spins, the state-of-the-art tensor network approaches lead to solutions that are $0.1\%$ to $1\%$ worse than the best solutions obtained by Ising machines while being two orders of magnitude slower. We attribute those results to approximate contraction failures. While all three methods can output diverse low-energy solutions, e.g., differing by at least a quarter of spins with energy error below $1\%$, our deterministic branch-and-bound approach finds sets of a few such states at most. On the other hand, both Ising machines prove capable of sampling sets of thousands of such solutions.
• Abstract（参考訳）: 最適化問題は様々な分野にまたがって問題を引き起こす。 近年、量子アニールはこのような課題に対処するための有望なプラットフォームとして出現している。 そこで本研究では,Ising スピングラスシステムの低エネルギースペクトルと,現在の量子アニーラーに関連する相互作用グラフを明らかにするために,ヒューリスティックなテンソルネットワークに基づくアルゴリズムを開発した。 我々の決定論的アプローチは、分枝探索戦略とテンソルネットワークの収縮による辺縁の近似計算を組み合わせたものである。 現在の量子アニールプロセッサで実現されている最大24スピンの単位セルを持つ準二次元格子への応用には、テンソルネットワーク表現とGPUハードウェアアクセラレーションのスパース構造を利用する専用のアプローチが必要である。 我々はペガサスグラフとゼファーグラフで定義されたランダムな問題を最大数千スピンでベンチマークし、これをD-Waveアドバンテージ量子アニールとシミュレートされた分岐アルゴリズムと比較した。 最良の解の質は別として、すべての解法によってサンプリングされた低エネルギー状態の多様性を比較する。 5000以上のスピンを持つ最大の問題に対して、最先端のテンソルネットワークアプローチは、イジングマシンが2桁遅いときに得られる最良の解よりも0.1\%から1\%悪い解をもたらす。 これらの結果は、およその収縮失敗によるものとみなす。 これら3つの方法はいずれも、エネルギー誤差が1\%以下であるスピンの少なくとも4分の1が異なる多様な低エネルギー解を出力できるが、決定論的分岐結合法は、少なくともそのような状態の集合を見つける。 一方、どちらのイジングマシンも数千のそのような解の集合をサンプリングできることを証明している。

関連論文リスト

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。 この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
  論文  参考訳（メタデータ） (2024-11-04T20:21:16Z)
• Quantum Circuit Simulation with Fast Tensor Decision Diagram [10.24745264727704]
  テンソル決定図を利用してオーバヘッドを排除し,大幅な高速化を実現する,新たなオープンソースフレームワークを提案する。 本稿では,テンソル決定ダイアグラム演算のための線形複雑度ランク単純化アルゴリズム,テトリス,エッジ中心データ構造を提案する。
  論文  参考訳（メタデータ） (2024-01-21T01:24:29Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Validation and benchmarking of quantum annealing technology [0.0]
  この論文は、量子アニールのベンチマークと検証の問題に焦点を当てている。 実世界の問題を解くための2つのアルゴリズムを提案し、それらが現在の世代の量子アニール上でどのように機能するかをテストする。
  論文  参考訳（メタデータ） (2023-12-06T14:56:45Z)
• Block belief propagation algorithm for two-dimensional tensor networks [0.0]
  本稿では,2次元テンソルネットワークを縮小し,2D$システムの基底状態を近似するためのブロック信念伝搬アルゴリズムを提案する。 応用として、我々のアルゴリズムを用いて2D$HeisenbergとTransverse Isingモデルを調べ、この手法の精度が最先端の結果と同等であることを示す。
  論文  参考訳（メタデータ） (2023-01-14T07:37:08Z)
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems [1.0878040851638]
  我々は3世代にわたるD-Wave量子アニールのベンチマークを報告する。 イジングあるいは等価なQUBOは、これらの問題の定式化は順序の減少のために補助変数を必要としない。
  論文  参考訳（メタデータ） (2023-01-08T10:02:56Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• 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)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。 この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。 GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
  論文  参考訳（メタデータ） (2022-04-18T21:45:13Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。 私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。 実際の量子コンピュータを用いて得られた結果について述べる。
  論文  参考訳（メタデータ） (2022-01-25T05:59:24Z)
• Sampling diverse near-optimal solutions via algorithmic quantum annealing [0.3506539188356145]
  主要な開問題の1つは、典型的なモンテカルロ解法に対するエルゴディディティの欠如、あるいはモード崩壊である。 本稿ではNP-hard最適化問題に対する独立近似解の数を定量化する新しい多様性尺度を提案する。
  論文  参考訳（メタデータ） (2021-10-20T13:33:37Z)

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

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