Quantum Counting
arXiv:quant-ph/9805082 · doi:10.1007/BFb0055105
Abstract
We study some extensions of Grover's quantum searching algorithm. First, we generalize the Grover iteration in the light of a concept called amplitude amplification. Then, we show that the quadratic speedup obtained by the quantum searching algorithm over classical brute force can still be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform approximate counting, which can be seen as an amplitude estimation process.
12 pages, LaTeX2e
References in corpus (6)
Cited by in corpus (49)
- Implementation of quantum search algorithm using classical Fourier optics
- Noisy intermediate-scale quantum computers
- Sliding mode control of quantum systems
- Hybrid quantum linear equation algorithm and its experimental test on IBM Quantum Experience
- Low depth algorithms for quantum amplitude estimation
- Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
- The Communication Complexity of the Hamming Distance Problem
- Quantum Speed-up for Approximating Partition Functions
- Generalized Quantum Search with Parallelism
- Quantum algorithms for testing properties of distributions
- Incoherent Control of Locally Controllable Quantum Systems
- Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection
- Quantum Searching via Entanglement and Partial Diffusion
- Fast Simulation of High-Depth QAOA Circuits
- Subdivided Phase Oracle for NISQ Search Algorithms
- Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
- An optimized quantum minimum searching algorithm with sure-success probability and its experiment simulation with Cirq
- Quantum algorithm to distinguish Boolean functions of different weights
- Quantum algorithms for scientific computing
- Quantum spectral clustering algorithm for unsupervised learning
- Strength and Weakness in Grover's Quantum Search Algorithm
- A hybrid classical-quantum approach to speed-up Q-learning
- Quantum Speedup Based on Classical Decision Trees
- A Novel Clustering Algorithm Based on Quantum Games
- Using Quantum Computers to Speed Up Dynamic Testing of Software
- Blind quantum machine learning with quantum bipartite correlator
- Quantum Search Approaches to Sampling-Based Motion Planning
- How Fast Can Quantum Annealers Count?
- On proving the robustness of algorithms for early fault-tolerant quantum computers
- Review of a Quantum Algorithm for Betti Numbers
- Dual-Frequency Quantum Phase Estimation Mitigates the Spectral Leakage of Quantum Algorithms
- New Developments in Quantum Algorithms
- Quantum Algorithm for Triangle Finding in Sparse Graphs
- The Prime state and its quantum relatives
- On the efficiency of Hamiltonian-based quantum computation for low-rank matrices
- Quantum Pathways for Charged Track Finding in High-Energy Collisions
- Quantum Privacy-Preserving Price E-Negotiation
- Complementary-multiphase quantum search for all numbers of target items
- Fixed-point quantum continuous search algorithm with optimal query complexity
- Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations
- Des-q: a quantum algorithm to provably speedup retraining of decision trees
- Selecting Efficient Phase Estimation With Constant-Precision Phase Shift Operators
- qSAT: Design of an Efficient Quantum Satisfiability Solver for Hardware Equivalence Checking
- On Quantum Perceptron Learning via Quantum Search
- A Quantum Algorithm for Finding Common Matches Between Databases with Reliable Behavior
- Improved Quantum Query Complexity on Easier Inputs
- Quantum Approximate Counting for Markov Chains and Application to Collision Counting
- Linear Order Matrix Inversion Method with Help from Quantum Searching Algorithm
- A Novel Approach to Quantum Heuristics for Structured Database Search