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• 1 citation
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•0 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•0 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

Optimal Random Self-Reductions for All Linear Problems

Shuichi Hirahara, Nobutaka Shimizu

The linear problem specified by an n × n matrix M over a finite field is the problem of computing the product of M and a given vector x. We present optimal error-tolerant random self-reductions (also known as worst-case to average-case reductions) for all linear problems: Given a linear-size circuit that computes M x on an ε-fraction of inputs x for a positive constant ε, we construct a randomized linear-size circuit that computes M x for all inputs x with high probability. This resolves the open problem posed by Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA’24), who presented quantum n1.5-time random self-reductions for all linear problems. Somewhat surprisingly, we also demonstrate the quantum advantage of their quantum reduction over classical uniform algorithms, by proving that any classical subquadratic-time random self-reduction requires the advice complexity of Ω(log(1/ε) · logn), as long as the field size is at most 1/ε. We complement this advice complexity lower bound by presenting (1) a random self-reduction with the optimal advice complexity of O(log(1/ε) · logn) and (2) a uniform random self-reduction over a large finite field.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 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 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.
The linear problem specified by an n × n matrix M over a finite field is the problem of computing the product of M and a given vector x. We present optimal error-tolerant random self-reductions (also known as worst-case to average-case reductions) for all linear problems: Given a linear-size circuit that computes M x on an ε-fraction of inputs x for a positive constant ε, we construct a randomized linear-size circuit that computes M x for all inputs x with high probability. This resolves the open problem posed by Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA’24), who presented quantum n1.5-time random self-reductions for all linear problems. Somewhat surprisingly, we also demonstrate the quantum advantage of their quantum reduction over classical uniform algorithms, by proving that any classical subquadratic-time random self-reduction requires the advice complexity of Ω(log(1/ε) · logn), as long as the field size is at most 1/ε. We complement this advice complexity lower bound by presenting (1) a random self-reduction with the optimal advice complexity of O(log(1/ε) · logn) and (2) a uniform random self-reduction over a large finite field.