The class #BQP consists of functions counting the dimension of the accepting-witness subspace of a polynomial-time quantum verifier, and is exact-counting-equivalent to #P under polynomial-time reductions. The source paper (Rhodes, Slezak, Chowdhury, Subasi; arXiv:2411.02602, v1 titled 'On additive error approximations to #BQP') completely characterizes additive-error approximations to #BQP and explicitly leaves open the multiplicative regime: the complexity of returning relative-error approximations to #BQP is stated to fall 'somewhere between QMA and #P', and determining its precise complexity is an open problem. Follow-up work has mapped the boundary but not resolved it: Anshu, Haferkamp, Hwang, and Nguyen gave a quantum oracle relative to which the quantum approximate counting class QXC is not contained in QMA^QMA (ruling out a black-box quantum analogue of Stockmeyer's approximate counting algorithm); Chia, Hasegawa, Le Gall, and Shen proved conditional fine-grained hardness under the Quantum Strong Exponential-Time Hypothesis (QSETH) of constant-relative-error quantum partition function approximation; Gharibian and Kamminga placed a multiplicative partition-function approximation in qq-QAM (a quantum analogue of the classical proof class AM). No unconditional containment, hardness, or separation closes the gap, so the problem remains open.

Background

Counting complexity studies function classes that count accepting witnesses. #P is the class of functions counting accepting paths of polynomial-time verifiers; GapP is its closure under subtraction. #BQP is the quantum analogue introduced in connection with the quantum density-of-states problem: a #BQP relation is described by a uniform family of quantum verifier circuits Vr,(n)V_{r,(n)} acting on w(n)w(n) witness qubits and a(n)a(n) ancilla qubits, and the counted quantity is the normalized dimension #r(x)=2−wdim⁡Pacc(x)\#r(x)=2^{-w} \dim P_{\mathrm{acc}}(x) of the subspace of witnesses accepted with high probability. QMA is the quantum analogue of NP (bounded-error verification of quantum proofs); PP is the class of decision problems decidable with unbounded-error probabilistic computation. Although #BQP, #P and GapP are polynomial-time equivalent for exact computation, their behavior under approximation differs sharply. For relative (multiplicative) error: any #P function can be multiplicatively approximated by a randomized algorithm with an NP oracle (Stockmeyer's classical approximate counting), whereas multiplicatively approximating GapP functions is #P-hard, since a multiplicative estimate preserves signs and enables binary search. For #BQP the corresponding question is unresolved: multiplicatively estimating the count forces one to decide whether the accepting subspace is empty (D=0D=0) or not, which is QMA-complete, giving a QMA lower bound; and the equivalence with #P gives an upper bound at the level of P#P\mathrm{P}^{\mathrm{\#P}}. Bravyi, Chowdhury, Gosset and Wocjan (quantum partition functions and free energy of local Hamiltonians, 2022) and Bravyi, Chowdhury, Gosset, Havlicek and Zhu (PRX Quantum 2024) formalized this quantum approximate counting task as the class QXC — given a QMA verification circuit and thresholds, estimate the accepting-witness-subspace dimension DD with multiplicative error ε≥1/poly(n)\varepsilon \ge 1/\mathrm{poly}(n) — and showed that relative approximation of representation-theoretic quantities such as Kronecker coefficients (multiplicities of symmetric-group representations in tensor products) reduces to it; the precise complexity of QXC was left open. DQC1, the class of problems solvable with one clean qubit plus maximally mixed qubits, captures additive-error estimation of related quantities such as the trace of a unitary or the density of states. The source paper settled the additive-error side: additive approximations at normalization u=2wu = 2^{w} (error εu\varepsilon u) are polynomial-time equivalent to BQP, any smaller normalization 2cw2^{cw} with c<1c<1 is #BQP-hard, classical additive approximations exist only at a much larger normalization that depends on the verifier's gate counts, and for relations with only logarithmically many ancilla qubits the 2w2^{w}-normalized additive approximation is DQC1-complete. Its Discussion section then states explicitly that for #BQP 'the complexity of returning relative-error approximations is an open problem, with the complexity falling somewhere between QMA and #P', attributing the bracket to the two Bravyi et al. works. This is the question recorded here.

Problem Statement

Determine the precise computational complexity of returning relative-error (multiplicative) approximations to #BQP functions. Formally, given a #BQP relation r described by a uniform family of quantum verifier circuits, estimate the accepting-witness-subspace count #r(x)\#r(x) (equivalently, up to the known normalization factor 2w(n)2^{w(n)}, the accepting dimension D of a QMA verifier — the task captured by the class QXC) to multiplicative error ε≥1/poly(∣x∣)\varepsilon \ge 1/\mathrm{poly}(|x|), including correct detection of the D=0D = 0 case. It is known that this task is QMA-hard (positivity of the count is QMA-complete) and that it lies at the level of P#P\mathrm{P}^{\mathrm{\#P}} via the equivalence of #BQP with classical counting classes and classical approximate counting; the source paper states the complexity falls 'somewhere between QMA and #P' and that determining its precise complexity is open. A resolution is, for example: an unconditional improved containment (an explicit polynomial-time or oracle protocol placing the task in a strictly smaller named class, quantum or classical); an unconditional hardness or completeness result for a class strictly above QMA (such as QMA^QMA-hardness or #P-hardness); or an unconditional separation from a named class such as QMAQMA\mathrm{QMA}^{\mathrm{QMA}} or BPPNP\mathrm{BPP}^{\mathrm{NP}}. The question concerns all #BQP relations without restriction; results restricted to specific witness-counting families (e.g. particular partition functions) address it only insofar as they pin the complexity of the general task.

References

  1. Mason L. Rhodes, Sam Slezak, Anirban Chowdhury, Yiğit Subaşı, 'Quantum Approximate Counting with Additive Error: Hardness and Optimality' (v1, 2024, titled 'On additive error approximations to #BQP'; v2, 2025), arXiv:2411.02602, DOI 10.48550/arxiv.2411.02602, https://arxiv.org/abs/2411.02602
  2. Anurag Anshu, Jonas Haferkamp, Yeongwoo Hwang, Quynh T. Nguyen, 'On the complexity of unique quantum witnesses and quantum approximate counting', arXiv:2410.23811 (2024; v2 revised September 2025), DOI 10.48550/arxiv.2410.23811, https://arxiv.org/abs/2410.23811
  3. Sergey Bravyi, Anirban Chowdhury, David Gosset, Pawel Wocjan, 'On the complexity of quantum partition functions', arXiv:2110.15466, DOI 10.48550/arxiv.2110.15466, https://arxiv.org/abs/2110.15466 (published as 'Quantum Hamiltonian complexity in thermal equilibrium', Nature Physics 18, 1367-1370, 2022, DOI 10.1038/s41567-022-01742-5, https://doi.org/10.1038/s41567-022-01742-5)
  4. Sergey Bravyi, Anirban Chowdhury, David Gosset, Vojtěch Havlíček, Guanyu Zhu, 'Quantum Complexity of the Kronecker Coefficients', PRX Quantum 5, 010329 (2024), DOI 10.1103/PRXQuantum.5.010329, https://doi.org/10.1103/PRXQuantum.5.010329 (preprint arXiv:2302.11454)
  5. Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen, 'Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions', arXiv:2602.14379 (2026), DOI 10.48550/arxiv.2602.14379, https://arxiv.org/abs/2602.14379 (supersedes arXiv:2510.07495)
  6. Sevag Gharibian, Jonas Kamminga, 'On the complexity of estimating ground state entanglement and free energy', arXiv:2510.06796 (2025; revised through May 2026), DOI 10.48550/arxiv.2510.06796, https://arxiv.org/abs/2510.06796
  7. Larry Stockmeyer, 'The complexity of approximate counting', Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC), 1983, DOI 10.1145/800061.808740, https://doi.org/10.1145/800061.808740