Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem.
The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm.
Counting problems are common in diverse fields such as statistical estimation, statistical physics, networking, etc.
As for quantum computing, the ability to perform quantum counting efficiently is needed in order to use Grover's search algorithm (because running Grover's search algorithm requires knowing how many solutions exist). Moreover, this algorithm solves the quantum existence problem (namely, deciding whether any solution exists) as a special case.
The algorithm was devised by Gilles Brassard, Peter Høyer and Alain Tapp in 1998.
Consider a finite set of size and a set of "solutions" (that is a subset of ). Define:
In other words, is the indicator function of .
Calculate the number of solutions .
Without any prior knowledge on the set of solutions (or the structure of the function ), a classical deterministic solution cannot perform better than , because all the elements of must be inspected (consider a case where the last element to be inspected is a solution).
The input consists of two registers (namely, two parts): the upper qubits comprise the first register, and the lower qubits are the second register.
The initial state of the system is . After applying multiple bit Hadamard gate operation on each of the registers separately, the state of the first register is
and the state of the second register is
an equal superposition state in the computational basis.
Because the size of the space is and the number of solutions is , we can define the normalized states:
Note that
which is the state of the second register after the Hadamard transform.
Geometric visualization of Grover's algorithm shows that in the two-dimensional space spanned by and , the Grover operator is a counterclockwise rotation; hence, it can be expressed as
in the orthonormal basis .
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Quantum computing has received wide-spread attention lately due the possibility of a near-term breakthrough of quantum supremacy. This course acts as an introduction to the area of quantum computing.
After introducing the foundations of classical and quantum information theory, and quantum measurement, the course will address the theory and practice of digital quantum computing, covering fundament
The course teaches non von-Neumann architectures. The first part of the course deals with quantum computing, sensing, and communications. The second focuses on field-coupled and conduction-based nanoc
En informatique quantique, la transformée de Fourier quantique (TFQ) est une transformation linéaire sur des bits quantiques, et est l'analogie quantique de la transformée de Fourier discrète. La transformée de Fourier quantique est l'un des nombreux algorithmes quantiques, qui incluent notamment l'algorithme de Shor qui permet de factoriser et de calculer le logarithme discret, l'algorithme d'estimation de phase quantique qui estime les valeurs propres d'un opérateur unitaire et les algorithmes traitant du problème de sous-groupe caché .
Explore l'algorithme de Grover, un algorithme de recherche quantique avec accélération quadratique, couvrant les circuits quantiques, les états finaux et les interprétations géométriques.
Quantum computing has made significant progress in recent years, with Google and IBM releasing quantum computers with 72 and 50 qubits, respectively. Google has also achieved quantum supremacy with its 54-qubit device, and IBM has announced the release of ...
EPFL2023
,
Universal quantum algorithms that prepare arbitrary n-qubit quantum states require O(2n) gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum st ...
IEEE2022
Quantum many-body control is a central milestone en route to harnessing quantum technologies. However, the exponential growth of the Hilbert space dimension with the number of qubits makes it challenging to classically simulate quantum many-body systems an ...