Approximate Counting refers to the problem where we are given query access to a function $f : [N] \to \{0,1\}$, and we wish to estimate $K = #\{x : f(x) = 1\}$ to within a factor of $1+ε$ (with high probability), while minimizing the number of queries. In the quantum setting, Approximate Counting can be done with $O\left(\min\left(\sqrt{N/ε}, \sqrt{N/K}/ε\right)\right)$ queries. It has recently been shown that this can be achieved by a simple algorithm that only uses "Grover iterations"; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve $O\left(\sqrt{N/ε}\right)$ query complexity, which is tight.
Approximate Counting refers to the problem where we are given query access to a function f:[N]→{0,1}, and we wish to estimate K = #\{x : f(x) = 1\} to within a factor of 1+ε (with high probability), while minimizing the number of queries. In the quantum setting, Approximate Counting can be done with O(min(N/ε,N/K/ε)) queries. It has recently been shown that this can be achieved by a simple algorithm that only uses "Grover iterations"; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve O(N/ε) query complexity, which is tight.
In 1998, Brassard, Høyer, Mosca, and Tapp (BHMT) gave a quantum algorithm for approximate counting. Given a list of N items, K of them marked, their algorithm estimates K to within relative error ∊ by making only queries. Although this speedup is of “Grover” type, the BHMT algorithm has the curious feature of relying on the Quantum Fourier Transform (QFT), more commonly associated with Shor's algorithm. Is this necessary? This paper presents a simplified algorithm, which we prove achieves the same query complexity using Grover iterations only. We also generalize this to a QFT-free algorithm for amplitude estimation. Related approaches to approximate counting were sketched previously by Grover, Abrams and Williams, Suzuki et al., and Wie (the latter two as we were writing this paper), but in all cases without rigorous analysis.
We propose in this paper a rough counting algorithm and modified version of Grover's search algorithm. The proposed counting algorithm uses Deutsch-Jozsa's algorithm to roughly estimate the number of items satisfying some search conditions by reconstructing the output distribution. The modified Grover's search combines the counting into one part of the algorithm and uses the counting result to determine the number of Grover's iterations taken to get such items. We provide an analysis of expected probability of the proposed algorithm taking into account the problem size, the number of satisfying items and the query complexity to show that the proposed modified Grover's search is optimal.
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 Θ(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 Ω(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 Ω(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) NP queries, then BPPNP[o(n)] contains a PNP-complete problem if the algorithm is classical and FBQPNP[o(n)] contains an FPNP-complete problem if the algorithm is quantum.
We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Laurent polynomials (i.e., polynomials with positive and negative integer exponents). Specifically, we resolve the complexity of approximate counting, the problem of multiplicatively estimating the size of a nonempty set S⊆[N], in two natural generalizations of quantum query complexity. Our first result holds in the standard Quantum Merlin--Arthur (QMA) setting, in which a quantum algorithm receives an untrusted quantum witness. We show that, if the algorithm makes T quantum queries to S, and also receives an (untrusted) m-qubit quantum witness, then either m=Ω(∣S∣) or T=Ω(N/∣S∣). This is optimal, matching the straightforward protocols where the witness is either empty, or specifies all the elements of S. As a corollary, this resolves the open problem of giving an oracle separation between SBP, the complexity class that captures approximate counting, and QMA. In our second result, we ask what if, in addition to a membership oracle for S, a quantum algorithm is also given "QSamples" -- i.e., copies of the state ∣S⟩=∣S∣1∑i∈S∣i⟩ -- or even access to a unitary transformation that enables QSampling? We show that, even then, the algorithm needs either Θ(N/∣S∣) queries or else Θ(min{∣S∣1/3,N/∣S∣}) QSamples or accesses to the unitary. Our lower bounds in both settings make essential use of Laurent polynomials, but in different ways.
In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size N by using only O(N) queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either M or K, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let m be the required number of iterations; we prove that under certain restrictions on the sizes of M and K the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.
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 achieved via simulated annealing, where the counting problem is formulated in terms of 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 that produces samples from μβ for β∈[βmin,βmax]. The best bound achieved by known annealing algorithms with relative error ε is O(qlogh/ε2), where q,h are parameters which respectively bound lnQ and H. However, all known algorithms attaining this near-optimal complexity are inherently sequential, or *adaptive*: the queried parameters β depend on previous samples. We develop a simple non-adaptive algorithm for approximate counting using O(qlog2h/ε2) samples, as well as an algorithm that achieves O(qlogh/ε2) samples with just two rounds of adaptivity, matching the best sample complexity of sequential algorithms. These algorithms naturally give rise to work-efficient parallel (RNC) counting algorithms. We discuss applications to RNC counting algorithms for several classic models, including the anti-ferromagnetic 2-spin, monomer-dimer and ferromagnetic Ising models.