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

arXiv:1611.01706

Self-reducible with easy decision version counting problems admit additive error approximation. Connections to counting complexity, exponential time complexity, and circuit lower bounds

Eleni Bakali

Published Nov 5, 2016• 3 citations
arXivHTMLPDF

Abstract

We consider the class of counting problems,i.e. functions in $\#$P, which are self reducible, and have easy decision version, i.e. for every input it is easy to decide if the value of the function $f(x)$ is zero. For example, $\#$independent-sets of all sizes, is such a problem, and one of the hardest of this class, since it is equivalent to $\#$SAT under multiplicative approximation preserving reductions. Using these two powerful properties, self reducibility and easy decision, we prove that all problems/ functions $f$ in this class can be approximated in probabilistic polynomial time within an absolute exponential error $ε\cdot 2^{n'}, \forallε>0$, which for many of those problems (when $n'=n+$constant) implies additive approximation to the fraction $f(x)/2^n$. (Where $n'$ is the amount of non-determinism of some associated NPTM). Moreover we show that for all these problems we can have multiplicative error to the value $f(x)$, of any desired accuracy (i.e. a RAS), in time of order $2^{2n'/3}poly(n)$, which is strictly smaller than exhaustive search. We also show that $f(x)

DOI
10.48550/arxiv.1611.01706

Related papers

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

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

Deterministic Approximate Counting for Degree-222 Polynomial Threshold Functions

De, Anindya, Diakonikolas, Ilias, Rocco A. Servedio

We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$ polynomial threshold function. Given a degree-2 input polynomial $p(x_1,\dots,x_n)$ and a parameter $\eps > 0$, the algorithm approximates \[ \Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0] \] to within an additive $\pm \eps$ in time $\poly(n,2^{\poly(1/\eps)})$. Note that it is NP-hard to determine whether the above probability is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. This is the first deterministic algorithm for this counting problem in which the running time is polynomial in $n$ for $\eps= o(1)$. For "regular" polynomials $p$ (those in which no individual variable's influence is large compared to the sum of all $n$ variable influences) our algorithm runs in $\poly(n,1/\eps)$ time. The algorithm also runs in $\poly(n,1/\eps)$ time to approximate $\Pr_{x \sim N(0,1)^n}[p(x) \geq 0]$ to within an additive $\pm \eps$, for any degree-2 polynomial $p$. As an application of our counting result, we give a deterministic FPT multiplicative $(1 \pm \eps)$-approximation algorithm to approximate the $k$-th absolute moment $\E_{x \sim \{-1,1\}^n}[|p(x)^k|]$ of a degree-2 polynomial. The algorithm's running time is of the form $\poly(n) \cdot f(k,1/\eps)$.

arXiv:1311.7105•Nov 27, 2013•5 citations

Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method

Albert Lin, Han-Hsuan Lin

We study the two-weight decision version of quantum approximate counting: given oracle access to $x\in\{0,1\}^N$, distinguish $|x|=M$ from $|x|=M+Δ$ with success probability $1/2+ζ$. Using the multiplicative adversary method, we prove $Ω\left(\max\left\{ζ\sqrt{(N-M)(M+Δ)}/Δ,\sqrt{ζN/Δ}\right\}\right)$. The same parameter dependence follows from the polynomial-method characterization of the two-layer symmetric function by Podder, Yao, and Ye. Our contribution is a multiplicative-adversary derivation that tracks the progress produced by individual oracle queries. For the first term, after complementing the input if necessary, we assume $M+Δ\le N-M$. We use the Hamming-layer subspaces from the eigenspace method of Ambainis, Spalek, and de Wolf and compose their adjacent-layer unitary maps to relate the two nonadjacent promise layers. After fixing the queried coordinate, the analysis block-diagonalizes into four-dimensional subspaces. An exact calculation of the one-query progress ratio gives the first lower bound. The same estimate also implies $\left\|(I-\widehatΠ_{\mathrm{bad}})\lvertΨ^T\rangle\right\|^2=O\left(T^2Δ^2/((N-M)(M+Δ))\right)$ for the coherent input superposition used in the adversary argument. For the second term, we prove directly using a three-eigenvalue multiplicative adversary that unique OR on $n$ bits with success probability $1/2+ζ$ requires $Ω(\sqrt{ζn})$ queries, and then reduce unique OR to the two-weight counting problem.

quant-pharXiv:2609.09804•Sep 10, 2026•0 citations

Efficiently Approximable Real-Valued Functions

Valentine Kabanets, Charles Rackoff, Stephen A Cook

We consider a class, denoted APP, of real-valued functions f : f0; 1g n ! [0; 1] such that f can be approximated, to within any ffl ? 0, by a probabilistic Turing machine running in time poly(n; 1=ffl). We argue that APP can be viewed as a generalization of BPP, and show that APP contains a natural complete problem: computing the acceptance probability of a given Boolean circuit; in contrast, no complete problems are known for BPP. We observe that all known complexity-theoretic assumptions under which BPP is easy (i.e., can be efficiently derandomized) imply that APP is easy; on the other hand, we show that BPP may be easy while APP is not, by constructing an appropriate oracle. 1 Introduction The complexity class BPP is traditionally considered a class of languages that can be efficiently decided with the help of randomness. While it does contain some natural problems, the "semantic" nature of its definition (on every input, a BPP machine must have either at least 3=4 or at...

Electronic colloquium on computational complexity•Jan 1, 2000•14 citations

No Size-Preserving Amplification with Quantum Advice

Shih-Han Hung, Han-Hsuan Lin

Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particular, we present decision problems for which even a vanishing additive error reduction requires longer advice. More precisely, for every polynomially bounded advice length $m(n)=ω(1)$ and every error bound $\varepsilon(n)$ that stays below $1/2$ by at least an inverse polynomial, there is a positive function $δ$ with $δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)$ such that $\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}m$; for constant $\varepsilon$ the gap is $O(\sqrt{\log m/m})$. Here, $\mathsf{BQP}_\varepsilon/\mathsf{q}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a polynomial-time quantum algorithm with an $m(n)$-qubit advice state that only depends on the input length $n$. We show this by proving a stronger separation $\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} m$, where $\mathsf{P}_{\varepsilon}/\mathsf{r}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a deterministic polynomial-time algorithm with an $m(n)$-bit advice string sampled from a distribution that depends only on $n$.

quant-pharXiv:2610.03377•Oct 5, 2026•0 citations
We consider the class of counting problems,i.e. functions in #\##P, which are self reducible, and have easy decision version, i.e. for every input it is easy to decide if the value of the function f(x)f(x)f(x) is zero. For example, #\##independent-sets of all sizes, is such a problem, and one of the hardest of this class, since it is equivalent to #\##SAT under multiplicative approximation preserving reductions. Using these two powerful properties, self reducibility and easy decision, we prove that all problems/ functions fff in this class can be approximated in probabilistic polynomial time within an absolute exponential error ε⋅2n′,∀ε>0ε\cdot 2^{n'}, \forallε>0ε⋅2n′,∀ε>0, which for many of those problems (when n′=n+n'=n+n′=n+constant) implies additive approximation to the fraction f(x)/2nf(x)/2^nf(x)/2n. (Where n′n'n′ is the amount of non-determinism of some associated NPTM). Moreover we show that for all these problems we can have multiplicative error to the value f(x)f(x)f(x), of any desired accuracy (i.e. a RAS), in time of order 22n′/3poly(n)2^{2n'/3}poly(n)22n′/3poly(n), which is strictly smaller than exhaustive search. We also show that $f(x)
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.
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 give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-222 polynomial threshold function. Given a degree-2 input polynomial p(x1,…,xn)p(x_1,\dots,x_n)p(x1​,…,xn​) and a parameter $\eps > 0$, the algorithm approximates Pr⁡x∼{−1,1}n[p(x)≥0] \Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0] Prx∼{−1,1}n​[p(x)≥0] to within an additive $\pm \eps$ in time $\poly(n,2^{\poly(1/\eps)})$. Note that it is NP-hard to determine whether the above probability is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. This is the first deterministic algorithm for this counting problem in which the running time is polynomial in nnn for $\eps= o(1)$. For "regular" polynomials ppp (those in which no individual variable's influence is large compared to the sum of all nnn variable influences) our algorithm runs in $\poly(n,1/\eps)$ time. The algorithm also runs in $\poly(n,1/\eps)$ time to approximate Pr⁡x∼N(0,1)n[p(x)≥0]\Pr_{x \sim N(0,1)^n}[p(x) \geq 0]Prx∼N(0,1)n​[p(x)≥0] to within an additive $\pm \eps$, for any degree-2 polynomial ppp. As an application of our counting result, we give a deterministic FPT multiplicative $(1 \pm \eps)$-approximation algorithm to approximate the kkk-th absolute moment $\E_{x \sim \{-1,1\}^n}[|p(x)^k|]$ of a degree-2 polynomial. The algorithm's running time is of the form $\poly(n) \cdot f(k,1/\eps)$.
We study the two-weight decision version of quantum approximate counting: given oracle access to x∈{0,1}Nx\in\{0,1\}^Nx∈{0,1}N, distinguish ∣x∣=M|x|=M∣x∣=M from ∣x∣=M+Δ|x|=M+Δ∣x∣=M+Δ with success probability 1/2+ζ1/2+ζ1/2+ζ. Using the multiplicative adversary method, we prove Ω(max⁡{ζ(N−M)(M+Δ)/Δ,ζN/Δ})Ω\left(\max\left\{ζ\sqrt{(N-M)(M+Δ)}/Δ,\sqrt{ζN/Δ}\right\}\right)Ω(max{ζ(N−M)(M+Δ)​/Δ,ζN/Δ​}). The same parameter dependence follows from the polynomial-method characterization of the two-layer symmetric function by Podder, Yao, and Ye. Our contribution is a multiplicative-adversary derivation that tracks the progress produced by individual oracle queries. For the first term, after complementing the input if necessary, we assume M+Δ≤N−MM+Δ\le N-MM+Δ≤N−M. We use the Hamming-layer subspaces from the eigenspace method of Ambainis, Spalek, and de Wolf and compose their adjacent-layer unitary maps to relate the two nonadjacent promise layers. After fixing the queried coordinate, the analysis block-diagonalizes into four-dimensional subspaces. An exact calculation of the one-query progress ratio gives the first lower bound. The same estimate also implies ∥(I−Π^bad)∣ΨT⟩∥2=O(T2Δ2/((N−M)(M+Δ)))\left\|(I-\widehatΠ_{\mathrm{bad}})\lvertΨ^T\rangle\right\|^2=O\left(T^2Δ^2/((N-M)(M+Δ))\right)​(I−Πbad​)∣ΨT⟩​2=O(T2Δ2/((N−M)(M+Δ))) for the coherent input superposition used in the adversary argument. For the second term, we prove directly using a three-eigenvalue multiplicative adversary that unique OR on nnn bits with success probability 1/2+ζ1/2+ζ1/2+ζ requires Ω(ζn)Ω(\sqrt{ζn})Ω(ζn​) queries, and then reduce unique OR to the two-weight counting problem.
We consider a class, denoted APP, of real-valued functions f : f0; 1g n ! [0; 1] such that f can be approximated, to within any ffl ? 0, by a probabilistic Turing machine running in time poly(n; 1=ffl). We argue that APP can be viewed as a generalization of BPP, and show that APP contains a natural complete problem: computing the acceptance probability of a given Boolean circuit; in contrast, no complete problems are known for BPP. We observe that all known complexity-theoretic assumptions under which BPP is easy (i.e., can be efficiently derandomized) imply that APP is easy; on the other hand, we show that BPP may be easy while APP is not, by constructing an appropriate oracle. 1 Introduction The complexity class BPP is traditionally considered a class of languages that can be efficiently decided with the help of randomness. While it does contain some natural problems, the "semantic" nature of its definition (on every input, a BPP machine must have either at least 3=4 or at...
Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particular, we present decision problems for which even a vanishing additive error reduction requires longer advice. More precisely, for every polynomially bounded advice length m(n)=ω(1)m(n)=ω(1)m(n)=ω(1) and every error bound ε(n)\varepsilon(n)ε(n) that stays below 1/21/21/2 by at least an inverse polynomial, there is a positive function δδδ with δ(n)=O(min⁡{(log⁡m/m)1/4, log⁡m/m /(1/2−ε(n))})δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)δ(n)=O(min{(logm/m)1/4, logm/m​/(1/2−ε(n))}) such that BQPε/qm⊊BQPε+δ/qm\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}mBQPε​/qm⊊BQPε+δ​/qm; for constant ε\varepsilonε the gap is O(log⁡m/m)O(\sqrt{\log m/m})O(logm/m​). Here, BQPε/qm\mathsf{BQP}_\varepsilon/\mathsf{q}mBQPε​/qm is the class of languages recognizable with error at most ε(n)\varepsilon(n)ε(n) by a polynomial-time quantum algorithm with an m(n)m(n)m(n)-qubit advice state that only depends on the input length nnn. We show this by proving a stronger separation Pε+δ/rm⊄BQPε/qm\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} mPε+δ​/rm⊂BQPε​/qm, where Pε/rm\mathsf{P}_{\varepsilon}/\mathsf{r}mPε​/rm is the class of languages recognizable with error at most ε(n)\varepsilon(n)ε(n) by a deterministic polynomial-time algorithm with an m(n)m(n)m(n)-bit advice string sampled from a distribution that depends only on nnn.