論文の概要: Exponential Speed-ups for Structured Goemans-Williamson relaxations via Quantum Gibbs States and Pauli Sparsity

• arxiv url: http://arxiv.org/abs/2510.08292v1
• Date: Thu, 09 Oct 2025 14:44:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:15.138784
• Title: Exponential Speed-ups for Structured Goemans-Williamson relaxations via Quantum Gibbs States and Pauli Sparsity
• Title（参考訳）: 量子ギブズ状態とパウリ空間による構造ゲーマン-ウィリアムソン緩和の指数速度アップ
• Authors: Haomu Yuan, Daniel Stilck França, Ilia Luchnikov, Egor Tiunov, Tobias Haug, Leandro Aolita,
• Abstract要約: 我々は,Guemans-Williamson SDPを既存手法よりも指数関数的に高速に近似する量子および量子インスピレーション付きアルゴリズムを開発した。 また,多対数時間でQUBOの実現可能な点のエネルギーを抽出し,ランダム化されたラウンドリング手順の手法についても検討する。
• 参考スコア（独自算出の注目度）: 2.4359597250214517
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quadratic Unconstrained Binary Optimization (QUBO) problems are prevalent in various applications and are known to be NP-hard. The seminal work of Goemans and Williamson introduced a semidefinite programming (SDP) relaxation for such problems, solvable in polynomial time that upper bounds the optimal value. Their approach also enables randomized rounding techniques to obtain feasible solutions with provable performance guarantees. In this work, we identify instances of QUBO problems where matrix multiplicative weight methods lead to quantum and quantum-inspired algorithms that approximate the Goemans-Williamson SDP exponentially faster than existing methods, achieving polylogarithmic time complexity relative to the problem dimension. This speedup is attainable under the assumption that the QUBO cost matrix is sparse when expressed as a linear combination of Pauli strings satisfying certain algebraic constraints, and leverages efficient quantum and classical simulation results for quantum Gibbs states. We demonstrate how to verify these conditions efficiently given the decomposition. Additionally, we explore heuristic methods for randomized rounding procedures and extract the energy of a feasible point of the QUBO in polylogarithmic time. While the practical relevance of instances where our methods excel remains to be fully established, we propose heuristic algorithms with broader applicability and identify Kronecker graphs as a promising class for applying our techniques. We conduct numerical experiments to benchmark our methods. Notably, by utilizing tensor network methods, we solve an SDP with $D = 2^{50}$ variables and extract a feasible point which is certifiably within $0.15\%$ of the optimum of the QUBO through our approach on a desktop, reaching dimensions millions of times larger than those handled by existing SDP or QUBO solvers, whether heuristic or rigorous.
• Abstract（参考訳）: 二次非拘束バイナリ最適化(QUBO)問題は、様々なアプリケーションで広く使われており、NPハードであることが知られている。 ゲーマンとウィリアムソンのセミナルな研究は、そのような問題に対して半定値プログラミング(SDP)緩和を導入し、上限値が最適値である多項式時間で解けるようにした。 また、ランダム化されたラウンドリング技術により、証明可能な性能保証を備えた実現可能なソリューションを得ることもできる。 本研究では,行列乗算重み法が量子および量子インスパイアされたアルゴリズムに導かれるQUBO問題の例を同定する。 このスピードアップは、ある代数的制約を満たすパウリ弦の線形結合として表現された場合、QUBOコスト行列がスパースであると仮定され、量子ギブス状態に対する効率的な量子および古典シミュレーション結果を利用することができる。 本研究では,これらの条件を効率的に検証する方法を示す。 さらに,ランダム化されたラウンドリング手順のヒューリスティック手法を探索し,多対数時間でQUBOの実現可能な点のエネルギーを抽出する。 提案手法が完全に確立されていない場合の実際的関連性については,より広範な適用性を持つヒューリスティックアルゴリズムを提案し,Kroneckerグラフを我々の手法を適用するための有望なクラスとして同定する。 我々は手法をベンチマークするために数値実験を行う。 特に、テンソルネットワークの手法を用いて、D = 2^{50}$変数を用いてSDPを解き、デスクトップ上でのアプローチにより、QUBOの最適値の0.15 %以内で、ヒューリスティックか厳密かにかかわらず、既存のSDPやQUBOソルバよりも数百万倍の精度で、実現可能な点を抽出する。

関連論文リスト

• Quantum Framework for Simulating Linear PDEs with Robin Boundary Conditions [0.6144680854063939]
  一般線形偏微分方程式(PDE)を数値シミュレーションするための明示的でオラクルのない量子フレームワークを提案する。 我々のアプローチは、一般的な有限差分法による離散化から始まり、結果の系をユニタリ量子進化を認めるものに変換するためにシュロディンガー化法を適用する。
  論文  参考訳（メタデータ） (2025-06-25T14:23:38Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer [0.157286095422595]
  いくつかの量子SDOソルバは、低精度な状態において高速化を提供する。 この事実を利用してアルゴリズムの精度への依存を指数関数的に改善する。 我々のアルゴリズムの量子実装は、$mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$の最悪の実行時間を示す。
  論文  参考訳（メタデータ） (2023-01-10T23:12:05Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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