論文の概要: Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers

• arxiv url: http://arxiv.org/abs/2503.10302v1
• Date: Thu, 13 Mar 2025 12:24:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-14 15:50:51.057658
• Title: Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
• Title（参考訳）: 確率コンピュータによるハードコンビネーション最適化における量子アドバンテージの境界
• Authors: Shuvro Chowdhury, Navid Anjum Aadit, Andrea Grimaldi, Eleonora Raimondo, Atharva Raut, P. Aaron Lott, Johan H. Mentink, Marek M. Rams, Federico Ricci-Tersenghi, Massimo Chiappini, Luke S. Theogarajan, Tathagata Srimani, Giovanni Finocchio, Masoud Mohseni, Kerem Y. Camsari,
• Abstract要約: 確率コンピュータ(p-コンピュータ)がモンテカルロアルゴリズムを実装可能であることを示す。 これらのアルゴリズムは、成熟した半導体技術のおかげで、現代のハードウェアで容易に実装可能であることを示す。 本結果は,pコンピュータをスケーラブルでエネルギー効率のよいハードウェアとして,最適化における実用的な量子優位性の概念に挑戦するものである。
• 参考スコア（独自算出の注目度）: 0.4969640751053581
• License:
• Abstract: Recent demonstrations on specialized benchmarks have reignited excitement for quantum computers, yet whether they can deliver an advantage for practical real-world problems remains an open question. Here, we show that probabilistic computers (p-computers) when co-designed with hardware to implement powerful Monte Carlo algorithms surpass state-of-the-art quantum annealers [\href{https://www.nature.com/articles/s41586-023-05867-2}{King et al., Nature (2023)}] in solving hard optimization problems. We focus on two key algorithms: discrete-time simulated quantum annealing (DT-SQA) and adaptive parallel tempering (APT), both applied to 3D spin glasses. For DT-SQA, we find that increasing the number of replicas improves residual energy scaling, while parallelizing fewer replicas across independent runs also achieves comparable scaling. Both strategies align with the theoretical expectations from extreme value theory. In addition, APT outperforms DT-SQA when supported by non-local isoenergetic cluster moves. Finite-size scaling analysis suggests a universal behavior that explains the superior performance of APT over both DT-SQA and quantum annealing. We show that these algorithms are readily implementable in modern hardware thanks to the mature semiconductor technology. Unlike software simulations, replicas can be monolithically housed on a single chip and a large number of spins can be updated in parallel and asynchronously, similar to a quantum annealer. We project that custom Field Programmable Gate Arrays (FPGA) or specialized chips leveraging massive parallelism can further accelerate these algorithms by orders of magnitude, while drastically improving energy efficiency. Our results challenge the notion of a practical quantum advantage in optimization and present p-computers as scalable, energy-efficient hardware for real-world optimization problems.
• Abstract（参考訳）: 特殊なベンチマークに関する最近の実証は、量子コンピュータの興奮を再燃させたが、現実の現実的な問題に利点をもたらすことができるかどうかはまだ未解決のままである。 ここでは,モンテカルロアルゴリズムをハードウェアと共同設計して実装した確率コンピュータ(pコンピュータ)が,ハード最適化問題の解法において,最先端の量子アンネラ [\href{https://www.nature.com/articles/s41586-023-05867-2}{King et al , Nature (2023)}] を超えていることを示す。 離散時間型量子アニール (DT-SQA) と適応並列テンパリング (APT) の2つの重要なアルゴリズムを3次元スピングラスに適用した。 DT-SQAの場合、レプリカ数の増加は余剰エネルギーのスケーリングを改善する一方、独立した実行にまたがるレプリカの並列化も同等のスケーリングを実現する。 どちらの戦略も極値理論からの理論的な期待と一致している。 さらに、APTは非局所アイソエネルゲティッククラスタ移動によって支持されたとき、DT-SQAより優れる。 有限サイズスケーリング解析は、DT-SQAと量子アニールの両方に対してAPTの優れた性能を説明する普遍的な挙動を示唆している。 これらのアルゴリズムは、成熟した半導体技術のおかげで、現代のハードウェアで容易に実装可能であることを示す。 ソフトウェアシミュレーションとは異なり、レプリカは単一チップ上にモノリシックに格納することができ、多数のスピンを並列かつ非同期に更新することができる。 FPGA(Field Programmable Gate Array)や,大規模並列性を利用した専用チップは,これらのアルゴリズムを桁違いに高速化し,エネルギー効率を大幅に向上させる。 本研究は,実世界の最適化問題に対して,pコンピュータをスケーラブルでエネルギー効率のよいハードウェアとして,実用的な量子優位性の概念に挑戦するものである。

関連論文リスト

• Codesigned counterdiabatic quantum optimization on a photonic quantum processor [6.079051215256144]
  我々は,このアルゴリズムをフォトニック量子プロセッサ上で実装するための符号付きアプローチを用いて,逆断熱プロトコルに焦点を当てた。 我々は,高次多体相互作用項に対処して,最適化された反断熱的手法を開発し,実装する。 フォトニックプラットフォーム上での量子コンピューティングにおける反断熱量子力学の符号付きマッピングの利点を実験的に実証した。
  論文  参考訳（メタデータ） (2024-09-26T15:08:19Z)
• Hardware-efficient variational quantum algorithm in trapped-ion quantum computer [0.0]
  本研究では, トラップイオン量子シミュレータ, HEA-TI に適したハードウェア効率の変動量子アルゴリズムアンサッツについて検討する。 我々は、全てのイオン間のプログラム可能な単一量子ビット回転と大域スピンスピン相互作用を活用し、従来のゲートベース手法における資源集約型2量子ビットゲートへの依存を減らす。
  論文  参考訳（メタデータ） (2024-07-03T14:02:20Z)
• Towards Quantum Computational Mechanics [1.530480694206666]
  本稿では、量子コンピューティングを用いて、計算ホモジェナイゼーションにおける代表要素体積(RVE)問題を解く方法について述べる。 我々の量子RVE解法は古典解法に対して指数加速度を得る。
  論文  参考訳（メタデータ） (2023-12-06T12:53:02Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  テンソルネットワーク(TN)アルゴリズムは、パラメタライズド量子回路(PQC)にマッピングできる 本稿では,現実的な量子回路を用いてTN状態を近似する新しいプロトコルを提案する。 その結果、量子回路の逐次的な成長と最適化を含む1つの特定のプロトコルが、他の全ての手法より優れていることが明らかとなった。
  論文  参考訳（メタデータ） (2022-09-01T17:08:41Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。 この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。 GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
  論文  参考訳（メタデータ） (2022-04-18T21:45:13Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Fragmented imaginary-time evolution for early-stage quantum signal processors [0.0]
  QITE(Quantum imaginary-time Evolution)のシミュレーションは、量子計算の大きな可能性である。 我々の主な貢献は、新しい世代の決定論的高精度QITEアルゴリズムである。 複雑化に優れたQITE回路サブルーチンを2つ提案する。
  論文  参考訳（メタデータ） (2021-10-25T18:02:24Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  変分量子アルゴリズム(VQA)は、特定の計算上の利点を得るために、短期量子マシンを利用する可能性がある。 現代のVQAは、巨大なデータを扱うために単独の量子プロセッサを使用するという伝統によって妨げられている、計算上のオーバーヘッドに悩まされている。 ここでは、この問題に対処するため、効率的な分散最適化手法であるQUDIOを考案する。
  論文  参考訳（メタデータ） (2021-06-24T08:18:42Z)
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization [0.14755786263360526]
  最小限のフォールトトレラント量子コンピュータで試すのに、最適化のための量子アルゴリズムが最も実用的であるかを探る。 この結果から,2次高速化のみを実現する量子最適化が,古典的アルゴリズムよりも有利であるという考えが否定される。
  論文  参考訳（メタデータ） (2020-07-14T22:54:04Z)

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

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