The Entangled Quantum Polynomial Hierarchy Collapses

• URL: http://arxiv.org/abs/2401.01453v1
• Date: Tue, 2 Jan 2024 22:25:56 GMT
• Title: The Entangled Quantum Polynomial Hierarchy Collapses
• Authors: Sabee Grewal and Justin Yirka
• Abstract summary: We show that the entangled quantum quantum hierarchy $mathsfQEPH$ collapses to its second level. We also show that only quantum superposition (not classical probability) increases the computational power of these hierarchies.
• Score: 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).

Related papers

• Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
  We generalize quantum-classical PCPs to allow for $q$ quantum queries to a classical proof. Surprisingly, this shows that we can amplify the promise gap from inverse to constant for constant query quantum-classicals. Even though we can achieve promise gap, our result also gives strong evidence that there exists no constant query quantum-classical PCP for $mathsfQCMA$.
  arXiv  Detail & Related papers  (2024-11-01T18:00:56Z)
• Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
  We study classes of constant-depth circuits with bounds that compute restricted threshold functions. For large enough values of $mathsfbPTFC0[k]$, $mathsfbPTFC0[k] contains $mathsfTC0[k].
  arXiv  Detail & Related papers  (2024-08-29T09:40:55Z)
• Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds [1.3927943269211591]
  This work studies three quantum-verifier based generalizations of $mathsfPH$. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for $mathsfQCPH$. We show one-sided error reduction for $mathsfpureQPH$, as well as the first bounds relating these quantum variants of $mathsfPH$.
  arXiv  Detail & Related papers  (2024-01-03T09:12:25Z)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  Given two monotone prime functions $f:0,1n to 0,1$ and $g:0,1n to 0,1$ the dualization problem consists in determining if $g$ is the dual of $f$. We present a quantum computing algorithm that solves the decision version of the dualization problem in time.
  arXiv  Detail & Related papers  (2023-08-28T18:12:54Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Monogamy of entanglement between cones [68.8204255655161]
  We show that monogamy is not only a feature of quantum theory, but that it characterizes the minimal tensor product of general pairs of convex cones. Our proof makes use of a new characterization of products of simplices up to affine equivalence.
  arXiv  Detail & Related papers  (2022-06-23T16:23:59Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  The observables associated with a quantum system $S$ form a non-commutative algebra $mathcal A_S$. It is assumed that a density matrix $rho$ can be determined from the expectation values of observables. Abelian algebras do not have inner automorphisms, so the measurement apparatus can determine mean values of observables.
  arXiv  Detail & Related papers  (2021-12-14T16:29:53Z)
• The Acrobatics of BQP [1.7136832159667206]
  We show that in the black-box setting the behavior of quantum-time ($mathsfBQP$) can be remarkably decoupled from that of classical complexity classes like $mathsfNP$. We also introduce new tools that might be of independent interest. These include a "quantum-aware" version of the random restriction method, a concentration theorem for the block sensitivity of $mathsfAC0$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.
  arXiv  Detail & Related papers  (2021-11-19T19:40:05Z)
• On the complexity of zero gap MIP* [0.11470070927586014]
  We show that the class $mathsfMIP*$ is equal to $mathsfRE$. In particular this shows that the complexity of approximating the quantum value of a non-local game $G$ is equivalent to the complexity of the Halting problem.
  arXiv  Detail & Related papers  (2020-02-24T19:11:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.