論文の概要: Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations

• arxiv url: http://arxiv.org/abs/2209.02715v3
• Date: Sun, 30 Apr 2023 16:38:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-02 19:38:33.204100
• Title: Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
• Title（参考訳）: 量子状態に対する濃度境界と多項式近似からのQAOA上の極限
• Authors: Anurag Anshu, Tony Metger
• Abstract要約: i) 浅い量子回路の出力状態、 [DPMRF22] からのオープン質問に答える、 (ii) 射影行列積状態、 [DPMRF22] からのオープン質問に答える、 (iii) 密なハミルトン進化の出力状態、すなわち、$eiota H(p) cdots eiota H(1) |psirangle for any $n$-qubit product state $|psirangle$。
• 参考スコア（独自算出の注目度）: 17.209060627291315
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove concentration bounds for the following classes of quantum states: (i) output states of shallow quantum circuits, answering an open question from [DPMRF22]; (ii) injective matrix product states; (iii) output states of dense Hamiltonian evolution, i.e. states of the form $e^{\iota H^{(p)}} \cdots e^{\iota H^{(1)}} |\psi_0\rangle$ for any $n$-qubit product state $|\psi_0\rangle$, where each $H^{(i)}$ can be any local commuting Hamiltonian satisfying a norm constraint, including dense Hamiltonians with interactions between any qubits. Our proofs use polynomial approximations to show that these states are close to local operators. This implies that the distribution of the Hamming weight of a computational basis measurement (and of other related observables) concentrates. An example of (iii) are the states produced by the quantum approximate optimisation algorithm (QAOA). Using our concentration results for these states, we show that for a random spin model, the QAOA can only succeed with negligible probability even at super-constant level $p = o(\log \log n)$, assuming a strengthened version of the so-called overlap gap property. This gives the first limitations on the QAOA on dense instances at super-constant level, improving upon the recent result [BGMZ22].
• Abstract（参考訳）: 量子状態の次のクラスに対する濃度境界を証明する。 (i)[DPMRF22]からのオープン質問に応答する浅い量子回路の出力状態 (ii) 射出行列生成物 (iii)密ハミルトン進化の出力状態、すなわち、任意のn$-量子ビット積状態に対して、{e^{\iota h^{(p)}} \cdots e^{\iota h^{(1)}} |\psi_0\rangle$、すなわち各$h^{} の形の状態。 i)$ はノルム制約を満たす任意の局所通勤ハミルトニアンであり、任意のクビット間の相互作用を持つ高密度ハミルトニアンを含む。 我々の証明は多項式近似を用いてこれらの状態が局所作用素に近いことを示す。 これは、計算基底測定(および他の関連する観測可能量)のハミング重みの分布が集中していることを意味する。 一例 (iii)は量子近似最適化アルゴリズム(QAOA)によって生成される状態である。 これらの状態に対する集中結果を用いて、ランダムスピンモデルでは、QAOAは、いわゆるオーバーラップギャップ特性の強化バージョンを仮定して、超コンスタントレベル$p = o(\log \log n)$でも無視可能な確率でしか成功できないことを示す。 これにより、超定常レベルでの高密度インスタンスに対するQAOAの最初の制限が得られ、最近の結果 [BGMZ22] により改善される。

関連論文リスト

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。 この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
  論文  参考訳（メタデータ） (2024-11-04T20:21:16Z)
• Quasi-quantum states and the quasi-quantum PCP theorem [0.21485350418225244]
  準量子状態上の$k$-局所ハミルトニアンを解くことは、古典的な$k$-局所CSP上の代入の分布を最適化することと同値であることを示す。 我々の主な結果は、準量子状態上の$k$-局所ハミルトニアンに対するPCP定理である。
  論文  参考訳（メタデータ） (2024-10-17T13:43:18Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Analysis of sum-of-squares relaxations for the quantum rotor model [0.0]
  非可換和-二乗階層は、非局所ゲームにおける量子値の近似のための半定値プログラミング緩和の列として、Navascu'es-Pironio-Ac'iによって導入された。 最近の研究は、地元のハミルトンの基底エネルギーを近似するための階層構造の分析を始めている。
  論文  参考訳（メタデータ） (2023-11-15T14:53:22Z)
• 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)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)
• Matrix Product Density Operators: when do they have a local parent Hamiltonian? [59.4615582291211]
  準局所親ハミルトニアンのギブス状態として行列積密度演算子(MPDO)を書けるかを検討する。 我々は、これが一般的なMPDOのケースであり、証拠を裏付けるものであると推測する。
  論文  参考訳（メタデータ） (2020-10-28T00:30:07Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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