Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
By: Kartik Anand, Kabgyun Jeong, Junseo Lee
Potential Business Impact:
Simplifies how computers prove things using quantum rules.
We investigate the structure of quantum proof systems by establishing collapse results that reveal simplifications in their complexity landscape. By extending classical theorems such as the Karp-Lipton theorem to quantum settings and analyzing uniqueness in quantum-classical PCPs, we clarify how various constraints influence computational power. Our main contributions are: (1) We show that restricting quantum-classical PCPs to unique proofs does not reduce their power: $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ under $\mathsf{BQ}$-operator and randomized reductions. This parallels the known $\mathsf{UniqueQCMA} = \mathsf{QCMA}$ result, indicating robustness of uniqueness even in quantum PCP-type systems. (2) We prove a non-uniform quantum analogue of the Karp-Lipton theorem: if $\mathsf{QMA} \subseteq \mathsf{BQP}/\mathsf{qpoly}$, then $\mathsf{QPH} \subseteq \mathsf{Q\Sigma}_2/\mathsf{qpoly}$. This conditional collapse suggests limits on quantum advice for $\mathsf{QMA}$-complete problems. (3) We define a bounded-entanglement version of the quantum polynomial hierarchy, $\mathsf{BEQPH}$, and prove that it collapses above the fourth level. We also introduce the separable hierarchy $\mathsf{SepQPH}$ (zero entanglement), for which the same collapse result holds. These collapses stem not from entanglement, as in prior work, but from the convex structure of the protocols, which renders higher levels tractable. Collectively, these results offer new insights into the structure of quantum proof systems and the role of entanglement, uniqueness, and advice in defining their complexity.
Similar Papers
On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
Quantum Physics
Makes quantum computers solve harder problems.
Derandomised tensor product gap amplification for quantum Hamiltonians
Quantum Physics
Makes hard computer problems easier to solve.
Fine-Grained Complexity via Quantum Natural Proofs
Quantum Physics
Makes computers harder to trick with quantum computers.