Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds

• URL: http://arxiv.org/abs/2401.01633v1
• Date: Wed, 3 Jan 2024 09:12:25 GMT
• Title: Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
• Authors: Avantika Agarwal, Sevag Gharibian, Venkata Koppula, Dorian Rudolph
• Abstract summary: 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$.
• Score: 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}}$.

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)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
  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.
  arXiv  Detail & Related papers  (2024-01-02T22:25:56Z)
• Nonlocality under Computational Assumptions [51.020610614131186]
  A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations. We show that there exist (efficient) local producing measurements that cannot be reproduced through randomness and quantum-time computation.
  arXiv  Detail & Related papers  (2023-03-03T16:53:30Z)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• 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)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
  arXiv  Detail & Related papers  (2020-12-03T14:03:20Z)
• 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.