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

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.

ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)•Jul 6, 2026•0 citations

Computing: The Turing way

Massimiliano Di Ventra

Abstract This Chapter introduces the Turing paradigm of computation and computational complexity classes. It discusses the algorithmic way combinatorial optimization problems are traditionally solved and explains why some of them are particularly difficult to solve with algorithms. It anticipates the need for non-perturbative approaches to the solution of such problems.

•Feb 21, 2022•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•5 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•96 citations

Randomized Computation

Thomas Watson

This chapter discusses randomized algorithms, which produce correct output with high probability. The chapter covers some classic randomized algorithms, complexity classes, and useful tools from probability theory. It also introduces the topic of efficient derandomization (turning randomized algorithms into non-randomized ones) in the time- and space-bounded settings.

Cambridge University Press eBooks•Oct 9, 2026•0 citations

Computation Models and Computational Complexity

Radhika Vathsan

Now that we have the laws for qubits, we need to develop a system for meaningfully manipulating them. Much of the current paradigm for quantum computing is motivated by classical computation theory, especially the circuit model for computation. In this chapter, we will briefly overview the classical model of Boolean circuit theory, and also some of the theoretical concepts involved in classifying the computational complexity of problems. Roger Penrose [53] has a beautiful account of the history of the theory of computation. Another wonderful book on similar lines is that of Douglas Hofstadter [41], both of which will stimulate you to think along the lines of a computer scientist.

CRC Press eBooks•Jul 21, 2015•1 citation
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.
Now that we have the laws for qubits, we need to develop a system for meaningfully manipulating them. Much of the current paradigm for quantum computing is motivated by classical computation theory, especially the circuit model for computation. In this chapter, we will briefly overview the classical model of Boolean circuit theory, and also some of the theoretical concepts involved in classifying the computational complexity of problems. Roger Penrose [53] has a beautiful account of the history of the theory of computation. Another wonderful book on similar lines is that of Douglas Hofstadter [41], both of which will stimulate you to think along the lines of a computer scientist.