論文の概要: Circuit complexity lower bounds for quantum spin glasses
- arxiv url: http://arxiv.org/abs/2607.14384v2
- Date: Tue, 21 Jul 2026 14:30:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-22 14:48:36.184548
- Title: Circuit complexity lower bounds for quantum spin glasses
- Title（参考訳）: 量子スピングラスの回路複雑性低境界
- Authors: Omar Al-Ghattas, David Gamarnik,
- Abstract要約: 標準多体モデルから生じる状態の回路複雑性について検討する。
積状態ギャップを閉じるために必要な絡み合いは浅い深さでは発生できないことを示す。
我々の結果は、自由とヘイスティングスの低エネルギー三元問題(arXiv:1301.1363)の精神に障害を与える。
- 参考スコア（独自算出の注目度）: 1.2604738912025477
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum $p$-spin glasses, random Hamiltonians whose interactions act on $p$-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement. We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with $n$, we prove that, for all sufficiently large fixed $p$, any circuit preparing an $n$-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth $Ω_p(\log n)$. In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed $D$, a sufficiently large degree prefactor rules out depth-$D$ preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits. Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.
- Abstract（参考訳）: 量子情報理論における中心的な問題は、標準的な多体モデルから生じる状態の回路複雑性である。
この問題は、パウリ弦を介して量子ビットの$p$-tuplesに作用するランダムハミルトニアンである量子$p$-spinグラスに対して研究される。
アンシュエツ、ガマルニク、キアニ(arXiv:2404.07231)は、最適エネルギーが生成物の状態によって達成可能な最高のエネルギーから分離されることを示した。
これにより、浅い回路がギャップを塞ぐことができるかどうかが明らかになる。
積状態ギャップを閉じるために必要な絡み合いは浅い深さでは発生できないことを示す。
平均相互作用次数が$n$で大きくなると、十分大きな固定$p$に対して、正規化されたエネルギーが最適値の固定正定数内にある$n$-qubit状態を作る回路は深さ$Ω_p(\log n)$でなければならない。
有界平均度系では、固定深度障害(英語版)を証明し、固定深度D$に対して、十分大きなプレファクターが深度D$の準基底状態の準備を行う。
どちらの結果も任意の数のアンシラ量子ビットを持つ回路上を均一に保持する。
この結果は、自由マン・ヘイスティングス(arXiv:1301.1363)の非低エネルギー三元状態問題(arXiv:1301.1363)の精神に障害を与えるが、アンシュ、ブリュックマン、ニハーヘ(arXiv:2206.13228)のような符号に基づくハミルトニアンよりもランダムな量子スピングラス(arXiv:2206.13228)の基底状態は多項式サイズの準備回路を許容する。
この設定は NLTS のような問題に対する確率的経路を開く: 浅い回路でインデックス付けされたガウス過程の均一制御として、ランダム量子ハミルトニアンに対する状態準備の下限を再放送する。
関連論文リスト
- Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure [52.51019642214249]
我々は,カットのエントロピーを量子時間で推定できない2次元局所定数深さ量子回路の族を構築する。
定深量子回路は特定の多くの量子サンプルから学習できるので、結果として得られる擬似絡み状態は暗黙的に公鍵であり、擬似ランダムではない。
論文 参考訳（メタデータ） (2026-05-29T15:43:00Z) - SpinGQE: A Generative Quantum Eigensolver for Spin Hamiltonians [42.007194397302825]
基底状態探索は量子コンピューティングの中心である。
我々は、生成量子固有ソルバフレームワークをスピンハミルトニアンに拡張したSpinGQEを提案する。
我々は、低エネルギー状態を生成する量子回路について学ぶために、トランスフォーマーベースのデコーダを用いる。
論文 参考訳（メタデータ） (2026-03-25T13:38:15Z) - Average-case quantum complexity from glassiness [45.57609001239456]
グラスネス(Glassiness)は、物理学において、不安定な自由エネルギーの風景を特徴とする現象であり、安定な古典的アルゴリズムの難しさを意味する。
レプリカ対称性の破れに基づく標準的な量子ガラス性の概念は、ギブスサンプリングのための安定な量子アルゴリズムを妨げていることを証明している。
論文 参考訳（メタデータ） (2025-10-09T17:37:33Z) - Limitations of Noisy Geometrically Local Quantum Circuits [0.2039123720459736]
ノイズが分散した雑音量子回路は、$omega(log n)$ depthで均一分布に収束し、$n$は量子ビットの数である。
我々は、我々の境界はまだゆるいものであり、$Theta(1)$-depthしきい値がパーコレーション効果によるシミュラビリティに十分であると予想する。
論文 参考訳（メタデータ） (2025-10-07T18:08:23Z) - Fault-tolerant fermionic quantum computing [39.58317527488534]
我々は、このオーバーヘッドを完全に除去するフレームワークであるフェルミオン型フォールトトレラント量子コンピューティングを導入する。
我々は、我々のフレームワークを中性原子でどのように実装できるかを示し、非数保存ゲートを実装するために中性原子が明らかに不可能であることを克服する。
論文 参考訳（メタデータ） (2024-11-13T19:00:02Z) - Optimizing random local Hamiltonians by dissipation [44.99833362998488]
簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。
この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
論文 参考訳（メタデータ） (2024-11-04T20:21:16Z) - On verifiable quantum advantage with peaked circuit sampling [9.551919087634522]
このような回路から1/textpoly(n)$のピーク値を得るには、圧倒的な確率で$tau_p = Omega(tau_r/n)0.19)$が必要である。
また、このモデルでは非自明なピーク性も可能であるという数値的な証拠を与える。
論文 参考訳（メタデータ） (2024-04-22T18:00:06Z) - Sparse random Hamiltonians are quantumly easy [105.6788971265845]
量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。
本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。
位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
論文 参考訳（メタデータ） (2023-02-07T10:57:36Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。
この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
論文 参考訳（メタデータ） (2021-02-03T09:20:32Z) - Approximate unitary $t$-designs by short random quantum circuits using
nearest-neighbor and long-range gates [0.0]
ply(t)cdot n1/D$-depth local random quantum circuits with two qudit Near-ighbor gates are almost $t$-designs in various measures。
また,異なるモデルを用いた深度O(log(n)loglog(n)において,反濃縮が可能であることを証明した。
論文 参考訳（メタデータ） (2018-09-18T22:28:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。