Quantum Approximate Counting
Benchmark based on the Brassard-Hoyer-Mosca-Tapp (BHMT) quantum counting algorithm, which estimates the number of marked items in an unstructured database with quadratic speedup over classical counting. Given N items with K marked, the algorithm estimates K to within relative error epsilon using O(1/epsilon * sqrt(N/K)) queries. A simplified variant achieves the same query complexity using only Grover iterations.[1]
- Algorithm: Quantum Amplitude Estimation (BHMT algorithm)
- Category: optimization
- Framework: Qiskit, Cirq
- Reproducible: Yes
- Published:
- counting
- amplitude-estimation
- Grover
- quadratic-speedup
- algorithm
What algorithm does Quantum Approximate Counting use?
Quantum Approximate Counting uses the Quantum Amplitude Estimation (BHMT algorithm) algorithm, categorized under optimization.
Frequently Asked Questions
What is the Quantum Approximate Counting benchmark?
Benchmark based on the Brassard-Hoyer-Mosca-Tapp (BHMT) quantum counting algorithm, which estimates the number of marked items in an unstructured database with quadratic speedup over classical counting. Given N items with K marked, the algorithm estimates K to within relative error epsilon using O(1/epsilon * sqrt(N/K)) queries. A simplified variant achieves the same query complexity using only Grover iterations.
Is Quantum Approximate Counting reproducible?
Yes, this benchmark is reproducible.