論文の概要: The Entangled Quantum Polynomial Hierarchy Collapses
- arxiv url: http://arxiv.org/abs/2401.01453v1
- Date: Tue, 2 Jan 2024 22:25:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-04 15:47:45.463748
- Title: The Entangled Quantum Polynomial Hierarchy Collapses
- Title（参考訳）: 量子多面体階層崩壊の絡み合い
- Authors: Sabee Grewal and Justin Yirka
- Abstract要約: 絡み合った量子量子階層$mathsfQEPH$が第2レベルに崩壊することを示す。
また、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算力を増大させることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce the entangled quantum polynomial hierarchy $\mathsf{QEPH}$ as
the class of problems that are efficiently verifiable given alternating quantum
proofs that may be entangled with each other. We prove $\mathsf{QEPH}$
collapses to its second level. In fact, we show that a polynomial number of
alternations collapses to just two. As a consequence, $\mathsf{QEPH} =
\mathsf{QRG(1)}$, the class of problems having one-turn quantum refereed games,
which is known to be contained in $\mathsf{PSPACE}$. This is in contrast to the
unentangled quantum polynomial hierarchy $\mathsf{QPH}$, which contains
$\mathsf{QMA(2)}$.
We also introduce a generalization of the quantum-classical polynomial
hierarchy $\mathsf{QCPH}$ where the provers send probability distributions over
strings (instead of strings) and denote it by $\mathsf{DistributionQCPH}$.
Conceptually, this class is intermediate between $\mathsf{QCPH}$ and
$\mathsf{QPH}$. We prove $\mathsf{DistributionQCPH} = \mathsf{QCPH}$,
suggesting that only quantum superposition (not classical probability)
increases the computational power of these hierarchies. To prove this equality,
we generalize a game-theoretic result of Lipton and Young (1994) which says
that the provers can send distributions that are uniform over a polynomial-size
support. We also prove the analogous result for the polynomial hierarchy, i.e.,
$\mathsf{DistributionPH} = \mathsf{PH}$. These results also rule out certain
approaches for showing $\mathsf{QPH}$ collapses.
Finally, we show that $\mathsf{PH}$ and $\mathsf{QCPH}$ are contained in
$\mathsf{QPH}$, resolving an open question of Gharibian et al. (2022).
- Abstract（参考訳）: 交叉量子多項式階層 $\mathsf{QEPH}$ を、互いに絡み合うかもしれない交互量子証明を効率的に検証できる問題のクラスとして導入する。
我々は、$\mathsf{QEPH}$崩壊を第二レベルに証明する。
実際、交替の多項式数が2に崩壊することを示す。
その結果、$\mathsf{QEPH} = \mathsf{QRG(1)}$は、1ターンの量子参照ゲームを持つ問題のクラスであり、$\mathsf{PSPACE}$に含まれることが知られている。
これは、非絡み合いの量子多項式階層$\mathsf{QPH}$とは対照的であり、$\mathsf{QMA(2)}$を含む。
また、量子古典多項式階層 $\mathsf{QCPH}$ の一般化を導入し、(弦の代わりに)文字列上の確率分布を送り、$\mathsf{DistributionQCPH}$ で表す。
概念的には、このクラスは$\mathsf{QCPH}$と$\mathsf{QPH}$の間にある。
我々は、$\mathsf{DistributionQCPH} = \mathsf{QCPH}$を証明し、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算能力を高めることを示唆する。
この等式を証明するために、Pipton and Young (1994) のゲーム理論の結果を一般化し、プローバーは多項式サイズのサポートに対して一様である分布を送れることを述べる。
また、多項式階層に対する類似の結果、すなわち $\mathsf{DistributionPH} = \mathsf{PH}$ も証明する。
これらの結果は、$\mathsf{QPH}$崩壊を示すいくつかのアプローチも除外する。
最後に、$\mathsf{ph}$ と $\mathsf{qcph}$ が$\mathsf{qph}$ に含まれることが示され、gharibian et al. (2022) の公然とした疑問が解決される。
関連論文リスト
- Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。
驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。
約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
論文 参考訳（メタデータ） (2024-11-01T18:00:56Z) - Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。
十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
論文 参考訳（メタデータ） (2024-08-29T09:40:55Z) - Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower
bounds [1.3927943269211591]
本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。
まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。
我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
論文 参考訳（メタデータ） (2024-01-03T09:12:25Z) - A polynomial quantum computing algorithm for solving the dualization
problem [75.38606213726906]
2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。
本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-08-28T18:12:54Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - 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) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。
密度行列 $rho$ は可観測物の期待値から決定できると仮定される。
アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文 参考訳（メタデータ） (2021-12-14T16:29:53Z) - The Acrobatics of BQP [1.7136832159667206]
量子時間(mathsfBQP$)の挙動をブラックボックスで設定すると、$mathsfNP$のような古典的な複雑性クラスと著しく分離できることが示される。
また、独立した関心を持つかもしれない新しいツールも導入します。
ランダム制限法の「量子対応」バージョン、$mathsfAC0$回路のブロック感度に対する集中定理、スパースオークスに対するアーロンソン・アンバイニス・コンジェクチャの(証明可能な)アナログを含む。
論文 参考訳（メタデータ） (2021-11-19T19:40:05Z) - On the complexity of zero gap MIP* [0.11470070927586014]
クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。
特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
論文 参考訳（メタデータ） (2020-02-24T19:11:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。