論文の概要: The classical limit of Quantum Max-Cut
- arxiv url: http://arxiv.org/abs/2401.12968v1
- Date: Tue, 23 Jan 2024 18:53:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-24 14:46:02.899571
- Title: The classical limit of Quantum Max-Cut
- Title（参考訳）: 量子マックスカットの古典的極限
- Authors: Vir B. Bulchandani, Stephen Piddock
- Abstract要約: 我々は、大きな量子スピンの極限$S$は半古典的極限として理解されるべきであることを示した。
半定値プログラムの出力をブロッホコヒーレント状態の積に丸め、$mathrmQMaxCut_S$に対する古典近似アルゴリズムの2つのファミリを示す。
- 参考スコア（独自算出の注目度）: 0.18416014644193066
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: It is well-known in physics that the limit of large quantum spin $S$ should
be understood as a semiclassical limit. This raises the question of whether
such emergent classicality facilitates the approximation of computationally
hard quantum optimization problems, such as the local Hamiltonian problem. We
demonstrate this explicitly for spin-$S$ generalizations of Quantum Max-Cut
($\mathrm{QMaxCut}_S$), equivalent to the problem of finding the ground state
energy of an arbitrary spin-$S$ quantum Heisenberg antiferromagnet
($\mathrm{AFH}_S$). We prove that approximating the value of $\mathrm{AFH}_S$
to inverse polynomial accuracy is QMA-complete for all $S$, extending previous
results for $S=1/2$. We also present two distinct families of classical
approximation algorithms for $\mathrm{QMaxCut}_S$ based on rounding the output
of a semidefinite program to a product of Bloch coherent states. The
approximation ratios for both our proposed algorithms strictly increase with
$S$ and converge to the Bri\"et-Oliveira-Vallentin approximation ratio
$\alpha_{\mathrm{BOV}} \approx 0.956$ from below as $S \to \infty$.
- Abstract（参考訳）: 物理学では、大きな量子スピン $s$ の極限は半古典的極限として理解されるべきである。
これは、そのような創発的古典性が局所ハミルトン問題のような計算上難しい量子最適化問題の近似を促進するかどうかという問題を引き起こす。
量子マックスカットのスピン-$s$一般化(\mathrm{qmaxcut}_s$)は、任意のスピン-$s$量子ハイゼンベルク反強磁性体の基底状態エネルギー(\mathrm{afh}_s$)を見つける問題と同値である。
逆多項式の精度に$\mathrm{AFH}_S$の値を近似することは、すべての$S$に対してQMA完全であることを証明する。
また、半定値プログラムの出力をブロッホコヒーレント状態の積に丸めることに基づいて、$\mathrm{qmaxcut}_s$ の古典近似アルゴリズムの2つの異なる族を示す。
提案する2つのアルゴリズムの近似比は厳密に$s$ で増加し、bri\"et-oliveira-vallentin近似比 $\alpha_{\mathrm{bov}} \approx 0.956$ に収束する。
関連論文リスト
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature
and Bayesian Optimization [51.533164528799084]
小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。
関数評価がノイズである場合でも,このパターンは真であることがわかった。
論文 参考訳（メタデータ） (2024-01-11T07:45:09Z) - Product states optimize quantum $p$-spin models for large $p$ [2.594420805049218]
量子$p$局所スピングラスランダムハミルトニアンの最大エネルギーを推定する問題を考察する。
我々の結果は、ランダムな局所ハミルトンの極低温状態が非無視的な絡み合いを示すべきであるという物理学における一般的な信念に挑戦する。
論文 参考訳（メタデータ） (2023-09-21T01:10:50Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳（メタデータ） (2023-08-16T06:46:37Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum Speedups of Optimizing Approximately Convex Functions with
Applications to Logarithmic Regret Stochastic Convex Bandits [8.682187438614296]
量子アルゴリズムは、$F(x*)-min_xincal K F(x)leqepsilon$が$tildeO(n3)$が$F$となるような$x*incal K$を求める。
応用として、ゼロ階凸包帯に対して $tildeO(n5log2 T)$ regret の量子関数アルゴリズムを与える。
論文 参考訳（メタデータ） (2022-09-26T03:19:40Z) - The Quantum and Classical Streaming Complexity of Quantum and Classical
Max-Cut [0.07614628596146598]
グラフストリーミング問題であるMax-Cutとその量子アナログQuantum Max-Cutの空間複雑性について検討する。
我々の研究は、$textrmo(n)$ space を用いて量子および古典マックスキュートの量子的および古典的近似性を解決する。
論文 参考訳（メタデータ） (2022-06-01T03:40:56Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality [6.621324975749854]
関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。
我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
論文 参考訳（メタデータ） (2021-11-01T20:45:42Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。