論文の概要: Combinatorial NLTS From the Overlap Gap Property

• arxiv url: http://arxiv.org/abs/2304.00643v4
• Date: Mon, 11 Nov 2024 20:59:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-13 13:16:48.711674
• Title: Combinatorial NLTS From the Overlap Gap Property
• Title（参考訳）: オーバーラップギャッププロパティからの Combinatorial NLTS
• Authors: Eric R. Anschuetz, David Gamarnik, Bobak Kiani,
• Abstract要約: Anshu, Breuckmann, and Nirkhe [ABN22] は、フリードマンとヘイスティングスによるいわゆる "No Low-Energy Trivial State conjecture" を肯定的に解決した。 この予想は、基底状態が浅い(対数深度)回路で生成できないn量子ビット系上の線形サイズの局所ハミルトニアンの存在を仮定した。
• 参考スコア（独自算出の注目度）: 2.594420805049218
• License:
• Abstract: In an important recent development, Anshu, Breuckmann, and Nirkhe [ABN22] resolved positively the so-called No Low-Energy Trivial State (NLTS) conjecture by Freedman and Hastings. The conjecture postulated the existence of linear-size local Hamiltonians on n qubit systems for which no near-ground state can be prepared by a shallow (sublogarithmic depth) circuit. The construction in [ABN22] is based on recently developed good quantum codes. Earlier results in this direction included the constructions of the so-called Combinatorial NLTS -- a weaker version of NLTS -- where a state is defined to have low energy if it violates at most a vanishing fraction of the Hamiltonian terms [AB22]. These constructions were also based on codes. In this paper we provide a "non-code" construction of a class of Hamiltonians satisfying the Combinatorial NLTS. The construction is inspired by one in [AB22], but our proof uses the complex solution space geometry of random K-SAT instead of properties of codes. Specifically, it is known that above a certain clause-to-variables density the set of satisfying assignments of random K-SAT exhibits an overlap gap property, which implies that it can be partitioned into exponentially many clusters each constituting at most an exponentially small fraction of the total set of satisfying solutions. We establish a certain robust version of this clustering property for the space of near-satisfying assignments and show that for our constructed Hamiltonians every combinatorial near-ground state induces a near-uniform distribution supported by this set. Standard arguments then are used to show that such distributions cannot be prepared by quantum circuits with depth o(log n). Since the clustering property is exhibited by many random structures, including proper coloring and maximum cut, we anticipate that our approach is extendable to these models as well.
• Abstract（参考訳）: 最近の重要な発展の中で、Anshu, Breuckmann, and Nirkhe [ABN22] は、フリードマンとヘイスティングスによるいわゆるNo Low-Energy Trivial State (NLTS)予想を肯定的に解決した。 この予想は、基底状態が浅い(対数深度)回路で生成できないn量子ビット系上の線形サイズの局所ハミルトニアンの存在を仮定した。 ABN22]の構成は、最近開発された良い量子符号に基づいている。 この方向の初期の結果には、いわゆる Combinatorial NLTS - NLTSの弱いバージョン - の構成が含まれていた。 これらの構造は法典にも基づいていた。 本稿では,Y Combinatorial NLTSを満たすハミルトニアンのクラスを「非コード」構築する。 この構成は [AB22] 内の 1 に着想を得たものであるが、我々の証明はコードの性質の代わりにランダム K-SAT の複素解空間幾何を用いる。 具体的には、ある節から変数の密度を超えると、ランダムな K-SAT の充足した割り当ての集合が重なり合うギャップ性を示すことが知られており、このことは、充足する解全体の集合の少なくとも指数的に小さな部分集合を構成するように、指数的に多くのクラスターに分割できることを示唆している。 我々は、このクラスタリング特性のある種のロバストバージョンを、ほぼ満足な割り当ての空間に対して確立し、構築されたハミルトニアンに対して、すべての組合せ的近傍状態が、この集合によって支えられるほぼ一様分布を誘導することを示す。 標準的な議論は、そのような分布が深さ o(log n) の量子回路では準備できないことを示すために使われる。 クラスタリング特性は、適切な色付けや最大カットを含む多くのランダムな構造で示されるので、これらのモデルにも我々のアプローチが拡張可能であることを期待する。

関連論文リスト

• LDPC stabilizer codes as gapped quantum phases: stability under graph-local perturbations [0.025206105035672277]
  我々は、ブラヴィイ、ハスティングス、ミチャラキスによる位相秩序の安定性の証明を、低密度パリティチェック符号に対応するハミルトン群に一般化する。 LDPC符号は、非ユークリッド設定においても、一般に安定なギャップ付き量子位相を定義する。
  論文  参考訳（メタデータ） (2024-11-04T18:52:44Z)
• Unextendibility, uncompletability, and many-copy indistinguishable ensembles [77.34726150561087]
  本研究では,不拡張性,不コンパイル性について検討し,多くのコピー不識別アンサンブルへの接続を解析する。 混合度を減少させて局所的不識別性を増大させる多部構成の多部構成の多部構成不識別アンサンブルについて報告する。
  論文  参考訳（メタデータ） (2023-03-30T16:16:41Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。 本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。 位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
  論文  参考訳（メタデータ） (2023-02-07T10:57:36Z)
• Quantum Pseudoentanglement [4.3053817709507]
  エンタングルメント(英: Entanglement)は、古典計算におけるランダムネスに類似した量子資源である。 カット毎に$log n$ に近い絡み合いエントロピーを持つ擬アンタングル状態の構成を与える。 本稿では, マトリックス製品状態試験, エンタングルメント蒸留, およびAdS/CFT対応の複雑さへの応用について論じる。
  論文  参考訳（メタデータ） (2022-11-01T21:04:49Z)
• 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)
• A construction of Combinatorial NLTS [22.539300644593936]
  NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [2014] posits that the family of Hamiltonians with all low energy state with high complexity。 ここでは、NLTSと呼ばれるより弱いバージョンを証明し、局所項の(小さい)定数数に反する状態に対して量子回路の下限が示される。
  論文  参考訳（メタデータ） (2022-06-06T16:55:34Z)
• Proofs of network quantum nonlocality aided by machine learning [68.8204255655161]
  我々は[DOI40103/PhysRevLett.123.140]の量子三角形分布の族が、元の証明よりも広い範囲の三角形局所モデルを認めていないことを示した。 我々は、独立な利害関係を持つ二項結果を持つ三角形のシナリオに対して、ネットワークベルの不等式を大量に収集する。
  論文  参考訳（メタデータ） (2022-03-30T18:00:00Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)
• Geometry of Banach spaces: a new route towards Position Based Cryptography [65.51757376525798]
  我々は幾何学的機能解析の観点から位置ベース量子暗号(PBQC)について検討し,その量子ゲームとの関係について考察した。 私たちが関心を持っている主な質問は、PBQCプロトコルのセキュリティを損なうために、攻撃者の連合が共有しなければならない、最適な絡み合いの量を求めることです。 より複雑なバナッハ空間の型プロパティの理解は、仮定を捨て、我々のプロトコルを攻撃するのに使用されるリソースに条件のない低い境界をもたらすことを示します。
  論文  参考訳（メタデータ） (2021-03-30T13:55:11Z)
• Models of zero-range interaction for the bosonic trimer at unitarity [91.3755431537592]
  ゼロ範囲の2体相互作用によって相互に結合された同一ボソンからなる3体系に対する量子ハミルトニアンの構成について述べる。 プレゼンテーションの大部分では、無限の散乱長が考慮される。
  論文  参考訳（メタデータ） (2020-06-03T17:54:43Z)
• A new approach to the construction of Schur-Weyl states [0.0]
  シュル=ワイル状態は、2つのヤング・アンド・ワイル・タドーによって記述される対称性を持つ特別な状態のクラスに属する。 スピン鎖系表現におけるシュル=ワイル状態構築の新しい方法を提案する。
  論文  参考訳（メタデータ） (2020-04-30T14:10:14Z)

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

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