論文の概要: The Complexity of Translationally Invariant Problems beyond Ground State
Energies
- arxiv url: http://arxiv.org/abs/2012.12717v1
- Date: Wed, 23 Dec 2020 14:44:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-19 19:49:51.373689
- Title: The Complexity of Translationally Invariant Problems beyond Ground State
Energies
- Title(参考訳): 基底状態エネルギーを超えた翻訳不変問題の複雑性
- Authors: James D. Watson, Johannes Bausch, Sevag Gharibian
- Abstract要約: 地元のハミルトンに関する3つの基本的な質問は、$mathsfQMA$-hard、$mathsfPmathsfQMA[log]$-hard、$mathsfQCMA$-hardである。
我々は,APX-SIMとGSCONの両方の翻訳不変バージョンが難易度を保っていることを示す。
- 参考スコア(独自算出の注目度): 6.445605125467574
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: It is known that three fundamental questions regarding local Hamiltonians --
approximating the ground state energy (the Local Hamiltonian problem),
simulating local measurements on the ground space (APX-SIM), and deciding if
the low energy space has an energy barrier (GSCON) -- are $\mathsf{QMA}$-hard,
$\mathsf{P}^{\mathsf{QMA}[log]}$-hard and $\mathsf{QCMA}$-hard, respectively,
meaning they are likely intractable even on a quantum computer. Yet while
hardness for the Local Hamiltonian problem is known to hold even for
translationally-invariant systems, it is not yet known whether APX-SIM and
GSCON remain hard in such "simple" systems. In this work, we show that the
translationally invariant versions of both APX-SIM and GSCON remain
intractable, namely are $\mathsf{P}^{\mathsf{QMA}_{\mathsf{EXP}}}$- and
$\mathsf{QCMA}_{\mathsf{EXP}}$-complete, respectively. Each of these results is
attained by giving a respective generic "lifting theorem" for producing
hardness results. For APX-SIM, for example, we give a framework for "lifting"
any abstract local circuit-to-Hamiltonian mapping $H$ (satisfying mild
assumptions) to hardness of APX-SIM on the family of Hamiltonians produced by
$H$, while preserving the structural and geometric properties of $H$ (e.g.
translation invariance, geometry, locality, etc). Each result also leverages
counterintuitive properties of our constructions: for APX-SIM, we "compress"
the answers to polynomially many parallel queries to a QMA oracle into a single
qubit. For GSCON, we give a hardness construction robust against highly
non-local unitaries, i.e. even if the adversary acts on all but one qudit in
the system in each step.
- Abstract(参考訳): 地平線エネルギー(局所ハミルトン問題)の近似、地平線上の局所測定(APX-SIM)のシミュレーション、低エネルギー空間がエネルギー障壁(GSCON)を持つかどうかの決定という3つの基本的な質問は、$\mathsf{QMA}$-hard, $\mathsf{P}^{\mathsf{QMA}[log]}$-hardと$\mathsf{QCMA}$-hardである。
しかし、局所ハミルトン問題に対する硬さは、翻訳的不変なシステムでも成り立つことが知られているが、APX-SIM と GSCON がそのような「単純な」システムでは困難であるかどうかはまだ分かっていない。
本稿では、APX-SIM と GSCON の翻訳不変バージョンが、それぞれ$\mathsf{P}^{\mathsf{QMA}_{\mathsf{EXP}}}$-および$\mathsf{QCMA}_{\mathsf{EXP}}$-complete であることを示す。
これらの結果のそれぞれは、硬度結果を生成するための「リフトング定理」をそれぞれ与えることで達成される。
例えば、APX-SIM に対して、$H$ で生成されるハミルトニアンの族上の APX-SIM の硬さに対して、$H$ の構造的および幾何学的性質(例えば、変換不変性、幾何学的、局所性など)を保ちながら、抽象的な局所回路-ハミルトン写像を "リフト" する枠組みを与える。
apx-simでは、qma oracleに対する多項式的に多くの並列クエリに対する答えを1つのキュービットに「圧縮」します。
GSCON に対して、高度に非局所的なユニタリに対して頑健な構成を与える。
関連論文リスト
- The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳(メタデータ) (2024-02-29T01:35:46Z) - A polynomial-time quantum algorithm for solving the ground states of a
class of classically hard Hamiltonians [4.828791769306579]
古典的ハードハミルトニアン群の基底状態を解くための量子アルゴリズムを提案する。
ハミルトンの$Ldag L$は、LMEのシミュレーションが難しいと信じている場合、古典的なコンピュータでは難しいことが保証されている。
論文 参考訳(メタデータ) (2024-01-25T05:01:02Z) - Nonlocality under Computational Assumptions [51.020610614131186]
相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。
ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
論文 参考訳(メタデータ) (2023-03-03T16:53:30Z) - Guidable Local Hamiltonian Problems with Implications to Heuristic
Ans\"atze State Preparation and the Quantum PCP Conjecture [0.0]
我々は最近定義されたガイドド局所ハミルトン問題における「マーリン化」バージョンについて検討する。
これらの問題には、入力の一部として提供される指針状態はなく、単に存在するという約束が伴うだけである。
誘導状態の両クラスに対する誘導可能な局所ハミルトン問題は、逆多項式の精度設定において$mathsfQCMA$-completeであることを示す。
論文 参考訳(メタデータ) (2023-02-22T19:00:00Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳(メタデータ) (2022-11-10T00:40:37Z) - Complexity of the Guided Local Hamiltonian Problem: Improved Parameters
and Extension to Excited States [0.0]
いわゆるガイド付き局所ハミルトニアン問題は、ハミルトニアンが 2-局所であるとき、BQP完全であることを示す。
この結果を改善するために、(i)ハミルトニアンが2-局所であること、(i)誘導状態と目標固有状態の重なりが最大1.99ドルであることを示す。
論文 参考訳(メタデータ) (2022-07-20T18:00:02Z) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。
密度行列 $rho$ は可観測物の期待値から決定できると仮定される。
アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文 参考訳(メタデータ) (2021-12-14T16:29:53Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳(メタデータ) (2021-11-09T18:49:48Z) - Computational Complexity of the Ground State Energy Density Problem [0.0]
本研究では, 局所ハミルトニアンの基底状態エネルギー密度を, 無限格子サイズの熱力学的極限の格子上に求める複雑さについて検討する。
2次元正方格子上の古典的、翻訳不変な近傍ハミルトン群に対して、$mathsfPmathsfNEEXPsubseteqmathsfEXPmathsfGSEDsubseteq MathsfEXPmathsfNEXP$, and for quantum Hamiltonians $mathsfPmathsfNEEXPsubseteqmathsfEXPmath。
論文 参考訳(メタデータ) (2021-07-11T14:52:43Z) - Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
我々は、$mathcal N=2 $ 超対称性を持つフェルミオンハミルトニアンの文脈における局所ハミルトニアン問題の複雑さを考える。
これを研究する主な動機は、超対称系の基底状態エネルギーがちょうどゼロであることと、あるコホモロジー群が非自明であることである。
論文 参考訳(メタデータ) (2021-06-30T18:00:01Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳(メタデータ) (2021-06-25T17:03:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。