Quantum Approximate Counting with Additive Error: Hardness and Optimality
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
Quantum counting is the task of determining the dimension of the subspace of states that are accepted by a quantum verifier circuit. It is the quantum analog of counting the number of valid solutions to NP problems -- a problem well-studied in theoretical computer science with far-reaching implications in computational complexity. The complexity of solving the class #BQP of quantum counting problems, either exactly or within suitable approximations, is related to the hardness of computing many-body physics quantities arising in algebraic combinatorics. Here, we address the complexity of quantum approximate counting under additive error. First, we show that computing additive approximations to #BQP problems to within an error exponential in the number of witness qubits in the corresponding verifier circuit is as powerful as polynomial-time quantum computation. Next, we show that returning an estimate within error that is any smaller is #BQP-hard. Finally, we show that additive approximations to a restricted class of #BQP problems are equivalent in computational hardness to the class DQC1. Our work parallels results on additively approximating #P and GapP functions.