Quantum Approximate Counting, Simplified

Abstract

In 1998, Brassard, Hoyer, 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 $\epsilon$ by making only $O\left(\frac{1}{\epsilon }\sqrt{\frac{N}{K}}\right)$ 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.

Update November 2021: changed several constants throughout and gave an updated proof that simplifies the analysis. This also remedies an algebra mistake present in the previous version

References in corpus (3)

• Amplitude estimation without phase estimation
• Quantum Sub-Gaussian Mean Estimator
• Simpler Quantum Counting

Cited by in corpus (46)

• Quantum Computing for Finance: State of the Art and Future Prospects
• Amplitude estimation without phase estimation
• Iterative Quantum Amplitude Estimation
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• A Threshold for Quantum Advantage in Derivative Pricing
• Low depth algorithms for quantum amplitude estimation
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• A hybrid quantum-classical approach to mitigating measurement errors
• Quantum unary approach to option pricing
• Faster Amplitude Estimation
• Variational quantum amplitude estimation
• Amplitude estimation via maximum likelihood on noisy quantum computer
• Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth
• On the complexity of quantum partition functions
• Quantum Differentially Private Sparse Regression Learning
• Amplitude Estimation from Quantum Signal Processing
• A Grover search-based algorithm for the list coloring problem
• The Problem with Grover-Rudolph State Preparation for Quantum Monte-Carlo
• Modified Grover operator for amplitude estimation
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Quantum algorithms for scientific computing
• Efficient option pricing with unary-based photonic computing chip and generative adversarial learning
• Using Quantum Computers to Speed Up Dynamic Testing of Software
• Accelerated quantum circuit Monte-Carlo simulation for heavy quark thermalization
• Quantum Fourier Iterative Amplitude Estimation
• Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
• Option pricing under stochastic volatility on a quantum computer
• The Prime state and its quantum relatives
• Solving Fractional Differential Equations on a Quantum Computer: A Variational Approach
• Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization
• Noise-Aware Quantum Amplitude Estimation
• Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling
• Quantum Computing for Data Centric Engineering and Science
• Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation
• Bayesian Quantum Amplitude Estimation
• Basic quantum subroutines: finding multiple marked elements and summing numbers
• Quantum-enhanced mean value estimation via adaptive measurement
• Quantum-Enhanced Simulation-Based Optimization for Newsvendor Problems
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Simpler Quantum Counting
• Des-q: a quantum algorithm to provably speedup retraining of decision trees
• Quantum Boosting using Domain-Partitioning Hypotheses
• Tunable Quantum Neural Networks in the QPAC-Learning Framework
• Counting with the quantum alternating operator ansatz
• Quantum Approximate Counting for Markov Chains and Application to Collision Counting
• On the bias in iterative quantum amplitude estimation