Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Algorithmica

The Relative Complexity of Approximate Counting Problems

Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum

Published Dec 10, 2003• 196 citations
Publisher
DOI
10.1007/s00453-003-1073-y

Related papers

The Complexity of Approximate Counting (Preliminary Version)

Larry J. Stockmeyer

•Jan 1, 1983•12 citations

On the de-randomization of space-bounded approximate counting problems

Dean Doron, Amnon Ta‐Shma

Information Processing Letters•Mar 23, 2015•3 citations

Quantum Approximate Counting with Additive Error: Hardness and Optimality

Mason L. Rhodes, Sam Slezak, Anirban Ch Narayan Chowdhury +1 more

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.

arXiv:2411.02602•Nov 4, 2024•0 citations

Counting Perfect Matchings and the Eight-Vertex Model

Jin‐Yi Cai, Tianyu Liu

We study the approximation complexity of the partition function of the eight-vertex model on general 4-regular graphs. For the first time, we relate the approximability of the eight-vertex model to the complexity of approximately counting perfect matchings, a central open problem in this field. Our results extend those in [Jin-Yi Cai et al., 2018]. In a region of the parameter space where no previous approximation complexity was known, we show that approximating the partition function is at least as hard as approximately counting perfect matchings via approximation-preserving reductions. In another region of the parameter space which is larger than the region that is previously known to admit Fully Polynomial Randomized Approximation Scheme (FPRAS), we show that computing the partition function can be reduced to counting perfect matchings (which is valid for both exact and approximate counting). Moreover, we give a complete characterization of nonnegatively weighted (not necessarily planar) 4-ary matchgates, which has been open for several years. The key ingredient of our proof is a geometric lemma. We also identify a region of the parameter space where approximating the partition function on planar 4-regular graphs is feasible but on general 4-regular graphs is equivalent to approximately counting perfect matchings. To our best knowledge, these are the first problems that exhibit this dichotomic behavior between the planar and the nonplanar settings in approximate counting.

•Jan 1, 2020•1 citation

On approximate counting

Philippe Flajolet

•Jul 1, 1982•4 citations

Approximate counting with uniform constant depth circuits

Miklós Ajtai

DIMACS series in discrete mathematics and theoretical computer science•Oct 25, 1993•49 citations
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.
We study the approximation complexity of the partition function of the eight-vertex model on general 4-regular graphs. For the first time, we relate the approximability of the eight-vertex model to the complexity of approximately counting perfect matchings, a central open problem in this field. Our results extend those in [Jin-Yi Cai et al., 2018]. In a region of the parameter space where no previous approximation complexity was known, we show that approximating the partition function is at least as hard as approximately counting perfect matchings via approximation-preserving reductions. In another region of the parameter space which is larger than the region that is previously known to admit Fully Polynomial Randomized Approximation Scheme (FPRAS), we show that computing the partition function can be reduced to counting perfect matchings (which is valid for both exact and approximate counting). Moreover, we give a complete characterization of nonnegatively weighted (not necessarily planar) 4-ary matchgates, which has been open for several years. The key ingredient of our proof is a geometric lemma. We also identify a region of the parameter space where approximating the partition function on planar 4-regular graphs is feasible but on general 4-regular graphs is equivalent to approximately counting perfect matchings. To our best knowledge, these are the first problems that exhibit this dichotomic behavior between the planar and the nonplanar settings in approximate counting.