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

Chapman & Hall/CRC eBooks

Background on computational complexity

István Miklós

Published Feb 21, 2019• 0 citations
Publisher

Abstract

In computational complexity theory, we distinguish decision, optimization, counting and sampling problems. Although this book is about the computational complexity of counting and sampling, counting and sampling problems are related to decision and optimization problems. Counting problems are always at least as hard as their decision counterparts. Indeed, if we can tell, say, the number of perfect matchings in a graph G , then naturally we can tell if there exists a perfect matching in G : G contains a perfect matching if and only if the number of perfect matchings in G is at least 1.

DOI
10.1201/b22024-1

Related papers

The complexity of approximate counting

Larry J. Stockmeyer

There are several computational problems that can be formulated as problems of counting the number of objects having a certain property. Valiant [22] has introduced the class #P which includes a variety of counting problems such as counting the number of perfect matchings in a graph, computing the permanent of a matrix [22], finding the size of a backtrack search tree [14], and computing the probability that a network remains connected when links can fail with a certain probability [23].

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1983•222 citations

Near-Optimal Parallel Approximate Counting via Sampling

David G. Harris, Vladimir Kolmogorov, H.W. Liu +2 more

The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is based on simulated annealing. In this approach, the counting problem is formulated as estimating the ratio Q = Z(βmax)/Z(βmin) between partition functions Z(β) = Σx∈Ω exp(βH(x)) of Gibbs distributions μβ over Ω with Hamiltonian H, given access to a sampling oracle for μβ at any β ∈ [βmin, βmax]. The sample complexity (measured by the number of oracle calls) is typically expressed in terms of q and h, which respectively bound ln Q and H. The best upper bound achieved by known annealing algorithms with relative error ε is O(qε−2 log h). However, all known algorithms attaining this near-optimal complexity are inherently sequential, or adaptive: the queried parameters β depend on previous samples.

arXiv:2604.01263•ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)•Jul 6, 2026•1 citation

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

Gaussian boson sampling for perfect matchings of arbitrary graphs

Kamil Brádler, Pierre-Luc Dallaire-Demers, Patrick Rebentrost +2 more

A famously hard graph problem with a broad range of applications is computing the number of perfect matchings, that is, the number of unique and complete pairings of the vertices of a graph. We propose a method to estimate the number of perfect matchings of undirected graphs based on the relation between Gaussian boson sampling and graph theory. The probability of measuring zero or one photons in each output mode is directly related to the hafnian of the adjacency matrix, and thus to the number of perfect matchings of a graph. We present encodings of the adjacency matrix of a graph into a Gaussian state and show strategies to boost the sampling success probability for the studied graphs. With our method, a Gaussian boson sampling device can be used to estimate the number of perfect matchings significantly faster and with lower-energy consumption compared to a classical computer.

arXiv:1712.06729•Physical Review A•Sep 10, 2018•105 citations

Computational Complexity for Physicists

Stephan Mertens

These lecture notes are an informal introduction to the theory of computational complexity and its links to quantum computing and statistical mechanics.

arXiv:cond-mat/0012185•Dec 11, 2000•6 citations

Computational complexity for physicists

Stephan Mertens

The theory of computational complexity has some interesting links to physics, in particular to quantum computing and statistical mechanics. The article contains an informal introduction to this theory and its links to physics.

Computing in Science & Engineering•Jan 1, 2002•63 citations
In computational complexity theory, we distinguish decision, optimization, counting and sampling problems. Although this book is about the computational complexity of counting and sampling, counting and sampling problems are related to decision and optimization problems. Counting problems are always at least as hard as their decision counterparts. Indeed, if we can tell, say, the number of perfect matchings in a graph G , then naturally we can tell if there exists a perfect matching in G : G contains a perfect matching if and only if the number of perfect matchings in G is at least 1.
The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is based on simulated annealing. In this approach, the counting problem is formulated as estimating the ratio Q = Z(βmax)/Z(βmin) between partition functions Z(β) = Σx∈Ω exp(βH(x)) of Gibbs distributions μβ over Ω with Hamiltonian H, given access to a sampling oracle for μβ at any β ∈ [βmin, βmax]. The sample complexity (measured by the number of oracle calls) is typically expressed in terms of q and h, which respectively bound ln Q and H. The best upper bound achieved by known annealing algorithms with relative error ε is O(qε−2 log h). However, all known algorithms attaining this near-optimal complexity are inherently sequential, or adaptive: the queried parameters β depend on previous samples.
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.
A famously hard graph problem with a broad range of applications is computing the number of perfect matchings, that is, the number of unique and complete pairings of the vertices of a graph. We propose a method to estimate the number of perfect matchings of undirected graphs based on the relation between Gaussian boson sampling and graph theory. The probability of measuring zero or one photons in each output mode is directly related to the hafnian of the adjacency matrix, and thus to the number of perfect matchings of a graph. We present encodings of the adjacency matrix of a graph into a Gaussian state and show strategies to boost the sampling success probability for the studied graphs. With our method, a Gaussian boson sampling device can be used to estimate the number of perfect matchings significantly faster and with lower-energy consumption compared to a classical computer.