Quantum Approximate Counting
Quantum Amplitude Estimation (BHMT algorithm) · Optimization · Qiskit, Cirq
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.
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.
Provides a simplified, practical variant of quantum counting that achieves optimal query complexity using only standard Grover iterations.
Simulator / hardware-agnostic
Qiskit, Cirq