論文の概要: Quasi-quantum states and the quasi-quantum PCP theorem

• arxiv url: http://arxiv.org/abs/2410.13549v1
• Date: Thu, 17 Oct 2024 13:43:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-18 13:18:20.601112
• Title: Quasi-quantum states and the quasi-quantum PCP theorem
• Title（参考訳）: 準量子状態と準量子PCP定理
• Authors: Itai Arad, Miklos Santha,
• Abstract要約: 準量子状態上の$k$-局所ハミルトニアンを解くことは、古典的な$k$-局所CSP上の代入の分布を最適化することと同値であることを示す。 我々の主な結果は、準量子状態上の$k$-局所ハミルトニアンに対するPCP定理である。
• 参考スコア（独自算出の注目度）: 0.21485350418225244
• License:
• Abstract: We introduce $k$-local quasi-quantum states: a superset of the regular quantum states, defined by relaxing the positivity constraint. We show that a $k$-local quasi-quantum state on $n$ qubits can be 1-1 mapped to a distribution of assignments over $n$ variables with an alphabet of size $4$, which is subject to non-linear constraints over its $k$-local marginals. Therefore, solving the $k$-local Hamiltonian over the quasi-quantum states is equivalent to optimizing a distribution of assignment over a classical $k$-local CSP. We show that this optimization problem is essentially classical by proving it is NP-complete. Crucially, just as ordinary quantum states, these distributions lack a simple tensor-product structure and are therefore not determined straightforwardly by their local marginals. Consequently, our classical optimization problem shares some unique aspects of Hamiltonian complexity: it lacks an easy search-to-decision reduction, and it is not clear that its 1D version can be solved with dynamical programming (i.e., it could remain NP-hard). Our main result is a PCP theorem for the $k$-local Hamiltonian over the quasi-quantum states in the form of a hardness-of-approximation result. The proof suggests the existence of a subtle promise-gap amplification procedure in a model that shares many similarities with the quantum local Hamiltonian problem, thereby providing insights on the quantum PCP conjecture.
• Abstract（参考訳）: 我々は、正の量子状態のスーパーセットである$k$-local quasi-quantum状態を導入し、正の制約を緩和することによって定義される。 我々は、$n$ qubits上の$k$-local quasi-quantum状態が、$k$-local marginalsの非線型制約である4$のアルファベットを持つ$n$変数上の代入の分布に1-1でマッピング可能であることを示す。 したがって、準量子状態上の$k$-局所ハミルトニアンを解くことは、古典的な$k$-局所CSP上の割り当ての分布を最適化することと同値である。 この最適化問題はNP完全であることを証明することによって本質的に古典的であることを示す。 重要なことに、通常の量子状態と同様に、これらの分布は単純なテンソル積構造を持たず、したがって局所的な辺縁によって直接決定されない。 その結果、我々の古典的な最適化問題はハミルトンの複雑性のいくつかの特異な側面を共有している: 簡単な探索と決定の還元が欠如しており、その1Dバージョンが動的プログラミング(つまりNPハードのまま)で解決できるかどうかは不明である。 我々の主な結果は、準量子状態上の$k$-局所ハミルトニアンに対するPCP定理である。 この証明は、量子局所ハミルトン問題と多くの類似点を共有するモデルに微妙な公約ギャップ増幅法が存在することを示唆し、量子PCP予想に関する洞察を与える。

関連論文リスト

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。 この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
  論文  参考訳（メタデータ） (2024-11-04T20:21:16Z)
• 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 quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  我々は最近提案された量子ハミルトニアン(QHD)アルゴリズムが、このファミリーから$d$Dのクエリを解くことができることを証明した。 一方、総合的な実証研究により、最先端の古典的アルゴリズム/解法はそのような問合せを解決するのにスーパーポリノミカルな時間を必要とすることが示唆されている。
  論文  参考訳（メタデータ） (2023-11-01T19:51:00Z)
• Nonlocality under Computational Assumptions [51.020610614131186]
  相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。 ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
  論文  参考訳（メタデータ） (2023-03-03T16:53:30Z)
• Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture [0.0]
  我々は最近定義されたガイドド局所ハミルトン問題における「マーリン化」バージョンについて検討する。 これらの問題には、入力の一部として提供される指針状態はなく、単に存在するという約束が伴うだけである。 誘導状態の両クラスに対する誘導可能な局所ハミルトン問題は、逆多項式の精度設定において$mathsfQCMA$-completeであることを示す。
  論文  参考訳（メタデータ） (2023-02-22T19:00:00Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。 本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。 位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
  論文  参考訳（メタデータ） (2023-02-07T10:57:36Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Reconstructing the whole from its parts [0.0]
  我々は、多人数シナリオにおいて、広範囲の自己整合性辺縁還元から大域量子状態を解析的に決定する。 我々は, 分極チャネルを通過した後に, 自己整合した多重粒子の辺縁還元は, 大域量子状態の存在と相容れないことを示した。
  論文  参考訳（メタデータ） (2022-09-28T15:04:22Z)
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations [17.209060627291315]
  i) 浅い量子回路の出力状態、 [DPMRF22] からのオープン質問に答える、 (ii) 射影行列積状態、 [DPMRF22] からのオープン質問に答える、 (iii) 密なハミルトン進化の出力状態、すなわち、$eiota H(p) cdots eiota H(1) |psirangle for any $n$-qubit product state $|psirangle$。
  論文  参考訳（メタデータ） (2022-09-06T18:00:02Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)

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

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