論文の概要: Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders

• arxiv url: http://arxiv.org/abs/2610.03670v1
• Date: Fri, 02 Oct 2026 17:40:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.534483
• Title: Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders
• Title（参考訳）: 密度展開器上の二部量子マックスカットの古典的アルゴリズム
• Abstract要約: 量子マックス・カット(英: Quantum Max-Cut)は、二部体の場合の古典的複雑性が依然として開であるような、よく研究された局所ハミルトン問題である。 スピン磁性12$反強磁性ハイゼンベルクモデルに対する時空の古典的ランダム化アルゴリズム、すなわち量子マックスキュート(Quantum Max-Cut)を高密度に平衡したバイパルタイト展開器に与える。
• 参考スコア（独自算出の注目度）: 39.564326983693704
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum Max-Cut is a well-studied local Hamiltonian problem for which the classical complexity of the bipartite case remains open. We give a polynomial-time classical randomized algorithm for the spin-$\tfrac12$ antiferromagnetic Heisenberg model, equivalently Quantum Max-Cut, on dense balanced bipartite expanders. This class includes $G(n,n,p)$ with high probability for every fixed $p>0$. The algorithm estimates the ground energy and any ground state edge correlation to additive error $\varepsilon$ in time polynomial in $n$ and $1/\varepsilon$. We construct a Markov chain on perfect matchings of the complete bipartite graph, each matching representing a product of singlets, that converges to the ground state, and use the expansion of the graph to show that polynomially many steps and samples of this chain suffice.
• Abstract（参考訳）: 量子マックス・カット(英: Quantum Max-Cut)は、二部体の場合の古典的複雑性が依然として開であるような、よく研究された局所ハミルトン問題である。 我々は、高密度バランスのバイパルタイト展開器上で、スピン-$\tfrac12$反強磁性ハイゼンベルクモデルに対する多項式時間古典的ランダム化アルゴリズム(Quantum Max-Cut)を与える。 このクラスは、固定された$p>0$に対して高い確率を持つ$G(n,n,p)$を含む。 このアルゴリズムは、基底エネルギーと任意の基底状態のエッジ相関を、加算誤差$\varepsilon$の時間多項式$n$と$/\varepsilon$の1/\varepsilon$と見積もる。 完全二部グラフの完全マッチングの上にマルコフ連鎖を構築し、各マッチングは一重項の積を表し、基底状態に収束し、グラフの拡張を用いて、この連鎖の多項式的な多くのステップとサンプルを示す。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Classical and Quantum Computing of Shear Viscosity for $2+1D$ SU(2) Gauge Theory [0.0]
  我々は、$(2+1)$-dimensional SU(2)ゲージ理論に対するせん断粘度の非摂動計算を行う。 せん断粘度とエントロピー密度$fracetas$の比は、よく知られたホログラフィック結果と一致している。 本研究では,グリーン関数の量子計算法を開発し,計算の系統的特徴を解析する。
  論文  参考訳（メタデータ） (2024-02-06T18:25:41Z)
• The classical limit of Quantum Max-Cut [0.16385815610837165]
  我々は、大きな量子スピンの極限$S$は半古典的極限として理解されるべきであることを示した。 半定値プログラムの出力をブロッホコヒーレント状態の積に丸め、$mathrmQMaxCut_S$に対する古典近似アルゴリズムの2つのファミリを示す。
  論文  参考訳（メタデータ） (2024-01-23T18:53:34Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  我々は最近提案された量子ハミルトニアン(QHD)アルゴリズムが、このファミリーから$d$Dのクエリを解くことができることを証明した。 一方、総合的な実証研究により、最先端の古典的アルゴリズム/解法はそのような問合せを解決するのにスーパーポリノミカルな時間を必要とすることが示唆されている。
  論文  参考訳（メタデータ） (2023-11-01T19:51:00Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  量子Max-$d$-Cut問題(Quantum Max-$d$-Cut problem)は、プロジェクターに付随する期待エネルギーを、全ての局所相互作用上の2つの$d$-dimensional quditsの非対称部分空間に最大化する量子状態を見つけることである。 我々は,非自明な性能保証を実現するために,有界な純度を持つ混合状態の積状態解を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-09-19T22:53:17Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。 我々はモンテカルロ法と量子ウォークの量子アナログを利用する。 また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
  論文  参考訳（メタデータ） (2022-10-12T19:10:43Z)

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

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