Quantum complexity hierarchy collapse linked to nonuniform circuit collapse
Nonuniform QCPH Collapse Implies QCPH Collapse
Computational Complexity
Summary
The authors studied a quantum version of a classical computer science concept called the Polynomial-Time Hierarchy, which organizes problems based on how hard they are to solve. They introduced a new quantum hierarchy that allows for extra advice bits (nonuniformity) and found this hierarchy collapses if and only if the original quantum hierarchy does. This means the complexity levels in the quantum hierarchy behave similarly whether or not extra advice is allowed. They also connect this collapse to a relationship between two quantum complexity classes called coQCMA and QCMA with advice.
What this means in practice
- •For quantum algorithm designers: Understand structural limits on quantum complexity classes which impact the design of quantum verification protocols.
- •For quantum complexity theorists: Use equivalences between uniform and nonuniform quantum hierarchies to guide complexity class separations or collapses.
A theory result. No direct application yet.
Authors
Jeremy Ahrens Huang
Abstract
Despite the importance of the non-uniform Polynomial-Time Hierarchy (PH/poly) in classical complexity understanding the collapse conditions of the Polynomial-Time Hierarchy (PH), a quantum equivalent of PH/poly has yet to be studied in the literature. We introduce the non-uniform computational Quantum Polynomial-Time Hierarchy (QCPH/mpoly), the quantum equivalent of PH/poly, and show that it collapses if and only if QCPH, the quantum equivalent of PH introduced by Gharibian et al. (comput. complex. 2022), also collapses. We also show that QCPH collapses if coQCMA is contained in QCMA/mpoly. These results are analogous to those of Yap (TCS 1983) commonly used to invoke the collapse of PH in classical complexity. QCPH/mpoly is analogous to QCPH with non-uniform quantum verifier circuits.