論文の概要: Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower
bounds
- arxiv url: http://arxiv.org/abs/2401.01633v1
- Date: Wed, 3 Jan 2024 09:12:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-05 16:46:26.524722
- Title: Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower
bounds
- Title（参考訳）: 量子多項式階層 : Karp-Lipton,エラー低減,下界
- Authors: Avantika Agarwal, Sevag Gharibian, Venkata Koppula, Dorian Rudolph
- Abstract要約: 本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。
まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。
我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
- 参考スコア（独自算出の注目度）: 1.3927943269211591
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Polynomial-Time Hierarchy ($\mathsf{PH}$) is a staple of classical
complexity theory, with applications spanning randomized computation to circuit
lower bounds to ''quantum advantage'' analyses for near-term quantum computers.
Quantumly, however, despite the fact that at least \emph{four} definitions of
quantum $\mathsf{PH}$ exist, it has been challenging to prove analogues for
these of even basic facts from $\mathsf{PH}$. This work studies three
quantum-verifier based generalizations of $\mathsf{PH}$, two of which are from
[Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings
($\mathsf{QCPH}$) and quantum mixed states ($\mathsf{QPH}$) as proofs, and one
of which is new to this work, utilizing quantum pure states
($\mathsf{pureQPH}$) as proofs. We first resolve several open problems from
[GSSSY22], including a collapse theorem and a Karp-Lipton theorem for
$\mathsf{QCPH}$. Then, for our new class $\mathsf{pureQPH}$, we show one-sided
error reduction for $\mathsf{pureQPH}$, as well as the first bounds relating
these quantum variants of $\mathsf{PH}$, namely $\mathsf{QCPH}\subseteq
\mathsf{pureQPH} \subseteq \mathsf{EXP}^{\mathsf{PP}}$.
- Abstract（参考訳）: 多項式時間階層 (\mathsf{ph}$) は、ランダム化計算から回路下限まで、短期量子コンピュータの'量子長所'解析にまたがる、古典的複雑性理論の要点である。
しかしながら、量子$\mathsf{PH}$ の少なくとも \emph{four} の定義が存在するという事実にもかかわらず、$\mathsf{PH}$ の基本的な事実の類似性を証明することは困難である。
本研究は、[Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] の量子検証に基づく3つの一般化を研究し、古典弦(\mathsf{QCPH}$)と量子混合状態(\mathsf{QPH}$)を証明として、量子純状態(\mathsf{pureQPH}$)を証明として利用する。
まず、[GSSSY22] から、崩壊定理と $\mathsf{QCPH}$ に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。
すると、新しいクラス $\mathsf{pureQPH}$ に対して、$\mathsf{pureQPH}$ と $\mathsf{pureQPH}$ のこれらの量子不変量に関連する最初の境界、すなわち $\mathsf{QCPH}\subseteq \mathsf{pureQPH} \subseteq \mathsf{EXP}^{\mathsf{PP}}$ の一方的な誤差削減を示す。
関連論文リスト
- Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。
驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。
約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
論文 参考訳（メタデータ） (2024-11-01T18:00:56Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
絡み合った量子量子階層$mathsfQEPH$が第2レベルに崩壊することを示す。
また、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算力を増大させることを示す。
論文 参考訳（メタデータ） (2024-01-02T22:25:56Z) - Nonlocality under Computational Assumptions [51.020610614131186]
相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。
ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
論文 参考訳（メタデータ） (2023-03-03T16:53:30Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Monogamy of entanglement between cones [68.8204255655161]
モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。
我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
論文 参考訳（メタデータ） (2022-06-23T16:23:59Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - The Acrobatics of BQP [1.7136832159667206]
量子時間(mathsfBQP$)の挙動をブラックボックスで設定すると、$mathsfNP$のような古典的な複雑性クラスと著しく分離できることが示される。
また、独立した関心を持つかもしれない新しいツールも導入します。
ランダム制限法の「量子対応」バージョン、$mathsfAC0$回路のブロック感度に対する集中定理、スパースオークスに対するアーロンソン・アンバイニス・コンジェクチャの(証明可能な)アナログを含む。
論文 参考訳（メタデータ） (2021-11-19T19:40:05Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - On the complexity of zero gap MIP* [0.11470070927586014]
クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。
特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
論文 参考訳（メタデータ） (2020-02-24T19:11:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。