A simpler quantum counting algorithm based on amplitude amplification is presented. This algorithm is bounded by O(sqrt(N/M)) calls to the controlled-Grover operator where M is the number of marked states and N is the total number of states in the search space. This algorithm terminates within log(sqrt(N/M)) consecutive measurement steps when the probability p1 of measuring the state |1> is at least 0.5, and the result from the final step is used in estimating M by a classical post processing. The purpose of controlled-Grover iteration is to increase the probability p1. This algorithm requires less quantum resources in terms of the width and depth of the quantum circuit, produces a more accurate estimate of M, and runs significantly faster than the phase estimation-based quantum counting algorithm when the ratio M/N is small. We compare the two quantum counting algorithms by simulating various cases with a different M/N ratio, such as M/N > 0.125 or M/N < 0.001.
A simpler quantum counting algorithm based on amplitude amplification is presented. This algorithm is bounded by O(sqrt(N/M)) calls to the controlled-Grover operator where M is the number of marked states and N is the total number of states in the search space. This algorithm terminates within log(sqrt(N/M)) consecutive measurement steps when the probability p1 of measuring the state |1> is at least 0.5, and the result from the final step is used in estimating M by a classical post processing. The purpose of controlled-Grover iteration is to increase the probability p1. This algorithm requires less quantum resources in terms of the width and depth of the quantum circuit, produces a more accurate estimate of M, and runs significantly faster than the phase estimation-based quantum counting algorithm when the ratio M/N is small. We compare the two quantum counting algorithms by simulating various cases with a different M/N ratio, such as M/N > 0.125 or M/N < 0.001.
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.
Consider a Boolean function χ:X→{0,1} that partitions set X between its good and bad elements, where x is good if χ(x)=1 and bad otherwise. Consider also a quantum algorithm A such that A∣0⟩=∑x∈Xαx∣x⟩ is a quantum superposition of the elements of X, and let a denote the probability that a good element is produced if A∣0⟩ is measured. If we repeat the process of running A, measuring the output, and using χ to check the validity of the result, we shall expect to repeat 1/a times on the average before a solution is found. *Amplitude amplification* is a process that allows to find a good x after an expected number of applications of A and its inverse which is proportional to 1/a, assuming algorithm A makes no measurements. This is a generalization of Grover's searching algorithm in which A was restricted to producing an equal superposition of all members of X and we had a promise that a single x existed such that χ(x)=1. Our algorithm works whether or not the value of a is known ahead of time. In case the value of a is known, we can find a good x after a number of applications of A and its inverse which is proportional to 1/a even in the worst case. We show that this quadratic speedup can also 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 amplitude estimation, a process that allows to estimate the value of a. We apply amplitude estimation to the problem of *approximate counting*, in which we wish to estimate the number of x∈X such that χ(x)=1. We obtain optimal quantum algorithms in a variety of settings.
Grover's algorithm searches an unstructured database of N entries, finding a marked element in time O(N). The algorithm was later generalised to amplitude amplification. The original algorithm succeeds with probability close to one and needs to run for a number of iterations chosen ahead of time. We discuss an implementation of amplitude amplification that, instead, runs for a number of iterations unspecified a priori and only halts on success. We prove that this approach maintains the quadratic speed-up of the original quantum algorithm. The key component is a feedback loop controlled by a weak measurement that allows limited monitoring of the evolution of the quantum state.
Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.
Generic quantum search algorithm searches for target entity in an unsorted database by repeatedly applying canonical Grover’s quantum rotation transform to reach near the vicinity of the target entity represented by a basis state in the Hilbert space associated with the qubits. Thus, when qubits are measured, there is a high probability of finding the target entity. However, the number of times quantum rotation transform is to be applied for reaching near the vicinity of the target is a function of the number of target entities present in the unsorted database, which is generally unknown. A wrong estimate of the number of target entities can lead to overshooting or undershooting the targets, thus reducing the success probability. Some proposals have been made to overcome this limitation. These proposals either employ quantum counting to estimate the number of solutions or fixed point schemes. This paper proposes a new scheme for stopping the application of quantum rotation transformation on reaching near the targets by measurement and subsequent processing to estimate the distance of the state vector from the target states. It ensures a success probability, which is at least greater than half for all the ratios of the number of target entities to the total number of entities in a database, which are less than half. The search problem is trivial for remaining possible ratios. The proposed scheme is simpler than quantum counting and more efficient than the known fixed-point schemes. It has same order of computational complexity as canonical Grover`s search algorithm but is slow by a factor of two and requires an additional ancilla qubit.
Grover's algorithm is a well-known contribution to quantum computing. It searches one value within an unordered sequence faster than any classical algorithm. A fundamental part of this algorithm is the so-called oracle, a quantum circuit that marks the quantum state corresponding to the desired value. A generalization of it is the oracle for Amplitude Amplification, that marks multiple desired states. In this work we present a classical algorithm that builds a phase-marking oracle for Amplitude Amplification. This oracle performs a less-than operation, marking states representing natural numbers smaller than a given one. Results of both simulations and experiments are shown to prove its functionality. This less-than oracle implementation works on any number of qubits and does not require any ancilla qubits. Regarding depth, the proposed implementation is compared with the one generated by Qiskit automatic method, UnitaryGate. We show that the depth of our less-than oracle implementation is always lower. This difference is significant enough for our method to outperform UnitaryGate on real quantum hardware.