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

Springer eBooks

Approximate Counting

Russ Bubley

Published Jan 1, 2001• 0 citations
Publisher
DOI
10.1007/978-1-4471-0695-1_3

Related papers

Approximate counting : an alternative approach

Peter Kirschenhofer, Helmut Prodinger

Approximate counting : an alternative approach

RAIRO - Theoretical Informatics and Applications•Jan 1, 1991•20 citations

On approximate counting

Philippe Flajolet

•Jul 1, 1982•4 citations

QMA Lower Bounds for Approximate Counting.

William Kretschmer

Electronic colloquium on computational complexity•Jan 1, 2019•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 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

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting

Sevag Gharibian, Jonas Kamminga

What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $Θ(n)$ queries to an NP oracle to compute a witness to a given SAT formula, quantumly $Θ(\log n)$ queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires $Ω(\log n)$ queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires $Ω(\log n)$ queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making $o(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.

arXiv:2401.03943•Leibniz international proceedings in informatics•Jan 1, 2024•3 citations

Approximate Methods

Florian Gebhard

Springer tracts in modern physics•Jan 1, 1997•1 citation
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.
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n)Θ(n)Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(log⁡n)Θ(\log n)Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(log⁡n)Ω(\log n)Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(log⁡n)Ω(\log n)Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn)o(log n)o(logn) NP queries, then BPPNP[o(n)]\text{BPP}^{\text{NP}[o(n)]}BPPNP[o(n)] contains a PNP\text{P}^{\text{NP}}PNP-complete problem if the algorithm is classical and FBQPNP[o(n)]\text{FBQP}^{\text{NP}[o(n)]}FBQPNP[o(n)] contains an FPNP\text{FP}^{\text{NP}}FPNP-complete problem if the algorithm is quantum.