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• 200 citations
Publisher
DOI
10.1007/s00453-003-1073-y

Related papers

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

Dean Doron, Amnon Ta‐Shma

Information Processing Letters•Mar 23, 2015•3 citations

On approximate counting

Philippe Flajolet

•Jul 1, 1982•4 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•1 citation

Approximate counting with uniform constant depth circuits

Miklós Ajtai

DIMACS series in discrete mathematics and theoretical computer science•Oct 25, 1993•56 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 arXiv:1811.03126 [cs.CC]. 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 previously known FPRASable region, we show that computing the partition function can be reduced to (with or without approximation) counting perfect matchings. 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 of this kind.

arXiv:1904.10493•Leibniz international proceedings in informatics•Apr 23, 2019•7 citations

The Weakness of CTC Qubits and the Power of Approximate Counting

Ryan O’Donnell, A. C. Cem Say

We present results in structural complexity theory concerned with the following interrelated topics: computation with postselection/restarting, closed timelike curves (CTCs), and approximate counting. The first result is a new characterization of the lesser known complexity class BPP path in terms of more familiar concepts. Precisely, BPP path is the class of problems that can be efficiently solved with a nonadaptive oracle for the approximate counting problem. Similarly, PP equals the class of problems that can be solved efficiently with nonadaptive queries for the related approximate difference problem. Another result is concerned with the computational power conferred by CTCs, or equivalently, the computational complexity of finding stationary distributions for quantum channels. Using the preceding characterization of PP, we show that any poly( n )-time quantum computation using a CTC of O (log n ) qubits may as well just use a CTC of 1 classical bit. This result essentially amounts to showing that one can find a stationary distribution for a poly( n )-dimensional quantum channel in PP.

ACM Transactions on Computation Theory•May 23, 2018•7 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 arXiv:1811.03126 [cs.CC]. 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 previously known FPRASable region, we show that computing the partition function can be reduced to (with or without approximation) counting perfect matchings. 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 of this kind.
We present results in structural complexity theory concerned with the following interrelated topics: computation with postselection/restarting, closed timelike curves (CTCs), and approximate counting. The first result is a new characterization of the lesser known complexity class BPP path in terms of more familiar concepts. Precisely, BPP path is the class of problems that can be efficiently solved with a nonadaptive oracle for the approximate counting problem. Similarly, PP equals the class of problems that can be solved efficiently with nonadaptive queries for the related approximate difference problem. Another result is concerned with the computational power conferred by CTCs, or equivalently, the computational complexity of finding stationary distributions for quantum channels. Using the preceding characterization of PP, we show that any poly( n )-time quantum computation using a CTC of O (log n ) qubits may as well just use a CTC of 1 classical bit. This result essentially amounts to showing that one can find a stationary distribution for a poly( n )-dimensional quantum channel in PP.