Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2103.09818 · International Journal of Parallel Emergent and Distributed Systems

Faster quantum concentration via Grover's search

Cem M. Unsal, A. Yavuz Oruç

Published Jul 17, 2023• 1 citation
arXivHTMLPDF

Abstract

One of the most important challenges in information networks is to gather data from a larger set of nodes to a smaller set of nodes. This can be done via the use of a concentrator architecture in the connection topology. This paper is a proof-of-concept that demonstrates a quantum-based controller in large interconnection networks can asymptotically perform this task faster. We specifically present quantum algorithms for routing concentration assignments on full capacity fat-and-slim concentrators, bounded fat-and-slim concentrators, and regular fat-and-slim concentrators. Classically, the concentration assignment takes O(n) time on all these concentrators, where n is the number of inputs. Powered by Grover's quantum search algorithm, our algorithms take O(ncln⁡c) time, where c is the capacity of the concentrator. Thus, our quantum algorithms are asymptotically faster than their classical counterparts, when cln2⁡c=o(n). In general, c=nμ, satisfies cln2⁡c=o(n), implying a time complexity of O(n0.5(1+μ)ln⁡n), for any μ,0<μ<1.

DOI
10.1080/17445760.2023.2231578

Related papers

Self-Routing Quantum Sparse Crossbar Packet Concentrators

Rahul Ratan, A. Yavuz Oruç

Quantum switching networks are derived from conventional switching networks by replacing the classical switches by quantum switches. We give the quantum circuit design and routing of an n \times m network, called a quantum concentrator that can direct quantum bit packets in arbitrary quantum states from any of its k inputs to some of its k outputs, where 1 \le k \le m \le n. Our designs are based on sparse crossbars which are rectangular grids of 2 \times 2 crosspoints. Sparse crossbar concentrator structures with theoretically minimum crosspoint complexities for any values of n and m are well known but no self-routing algorithms have been reported for such concentrators. We transform two such families of optimal concentrators, called fat-slim and banded sparse crossbars into quantum networks and provide self-routing algorithms for these families of concentrators. In this process, we extend the notion of packet concentration to a quantum network and design self-routing quantum crosspoints from quantum gates. We address issues critical to quantum operation like reversibility and localized self-routing and give a rigorous proof that quantum fat-slim and banded sparse crossbar concentrators are self-routable. The self-routing algorithms described in the paper can be used for both quantum and classical sparse crossbar concentrators by the linearity property of all quantum systems.

IEEE Transactions on Computers•Jun 23, 2010•7 citations

Random routing and concentration in quantum switching networks

Rahul Ratan

Flexible distribution of data in the form of quantum bits or qubits among spatially separated entities is an essential component of envisioned scalable quantum computing architectures. Accordingly, we consider the problem of dynamically permuting groups of quantum bits, i.e., qubit packets, using networks of reconfigurable quantum switches. We demonstrate and then explore the equivalence between the quantum process of creation of packet superpositions and the process of randomly routing packets in the corresponding classical network. In particular, we consider an n × n Baseline network for which we explicitly relate the pairwise input-output routing probabilities in the classical random routing scenario to the probability amplitudes of the individual packet patterns superposed in the quantum output state. We then analyze the effect of using quantum random routing on a classically non-blocking configuration like the Benes network. We prove that for an n × n quantum Benes network, any input packet assignment with no output contention is probabilistically self-routable. In particular, we prove that with random routing on the first (log n-1) stages and bit controlled self-routing on the last log n stages of a quantum Benes network, the output packet pattern corresponding to routing with no blocking is always present in the output quantum state with a non-zero probability. We give a lower bound on the probability of observing such patterns on measurement at the output and identify a class of 2 n-1 permutation patterns for which this bound is equal to 1, i.e., for all the permutation patterns in this class the following is true: in every pattern in the quantum output assignment all the valid input packets are present at their correct output addresses. In the second part of this thesis we give the complete design of quantum sparse crossbar concentrators. Sparse crossbar concentrators are rectangular grids of simple 2 × 2 switches or crosspoints, with the switches arranged such that any k inputs can be connected to some k outputs. We give the design of the quantum crosspoints for such concentrators and devise a self-routing method to concentrate quantum packets. Our main result is a rigorous proof that certain crossbar structures, namely, the fat-slim and banded quantum crossbars allow, without blocking, the realization of all concentration patterns with self-routing. In the last part we consider the scenario in which quantum packets are queued at the inputs to an n × n quantum non-blocking switch. We assume that each packet is a superposition of m classical packets. Under the assumption of uniform traffic, i.e., any output is equally likely to be accessed by a packet at an input we find the minimum value of m such that the output quantum state contains at least one packet pattern in which no two packets contend for the same output. Our calculations show that for m=9 the probability of a non-contending output pattern occurring in the quantum output is greater than 0.99 for all n up to 64.

•Jan 1, 2008•0 citations

Implementation of Grover’s Iterator for Quantum Searching With an Arbitrary Number of Qubits

Sihyung Lee, Seung Yeob Nam

Grover’s algorithm harnesses the power of quantum computing to swiftly locate specific elements in an unstructured database, outperforming classical computers in tasks like database searching. This algorithm capitalizes on the unique ability of qubits to be in both 0 and 1 states simultaneously (superposition), allowing it to scan the entire search space at once. It then boosts the probability of the target element, making it more prominent. While the foundational concepts of Grover’s algorithm are well-documented, practical implementation using quantum operators, especially for large search spaces, remains less explored beyond basic examples with a small number of qubits. Existing general synthesis techniques often involve numerous operators or are time-consuming. Our proposed methods specifically address the amplitude-amplification component of Grover’s algorithm for any size of search space. These methods detail the required types and quantities of qubits and operators, emphasizing minimal usage and efficient assembly. Developed and evaluated in Python, our methods consistently identified target elements with over 95% accuracy and achieved configurations comparably compact as those in the existing literature but at a faster pace. We anticipate that these methods facilitate practical implementations of Grover’s algorithm across various domains.

IEEE Access•Jan 1, 2024•7 citations

Evaluating the Practicality of Grover’s Algorithm for Large-Scale Data Search via Quantum Simulation

Lovish Bhatia, Vinay Shankar Pandey, Ajay K. Sharma

Abstract Quantum computing can solve some classes of problems faster than classical computing. Among the greatest quantum algorithms to showcase this benefit is Grover's search algorithm, which has a quadratic speed-up for unstructured search problems. In this study, we present an implementation of Grover’s algorithm on a large-scale dataset comprising approximately 131,072 (217) names. We contrast its efficiency with the classical linear search based on time complexity, scalability, and the likelihood of success. The experiment was conducted using Qiskit on a quantum simulator, where several query scenarios were implemented to verify the algorithm's efficiency and accuracy. Our findings highlight the theoretical advantage of Grover’s algorithm in situations involving large data sets, while also discussing real-world limitations such as gate noise, qubit number, and circuit depth as we move towards actual quantum hardware. This study serves as a step toward evaluating the real-world relevance of quantum search algorithms and provides information on current challenges and future directions in quantum information retrieval.

•Jul 2, 2025•1 citation

Grover search with smaller oracles

Dan Li

Grover search is one of the most important quantum algorithms. In this paper, we consider a kind of search that the conditions of satisfaction $T$ can be rewritten as $T=T_1\bigcap T_2$. Then we present a new Grover search with smaller oracles. The time complexity of this algorithm $O(\fracπ{4}\sqrt{\frac{N}{bλ}}+\fracπ{4}\sqrt{\frac{b}τ})$, which is smaller than the time complexity of original Grover search, i.e. $O(\fracπ{4}\sqrt{\frac{N}{M}})$.

arXiv:2007.03526•Jul 6, 2020•0 citations

Grover's Search Algorithm for Database Validation

Datapro Computers Pvt Ltd, Shravani Salapu

In my project I would have considered how the old search algorithms that are used when working with large unstructured data set end up taking linear time (O(N)) that in effect is the time that scales with the size of the data. These old ways get gradually sluggish, as everything gets bigger. Then I read about quantum computing, and especially Search Algorithm that was developed by Grover which is capable of quadratic speed-up with a complexity of O(sqrt(N)) of unstructured data. I created a hybrid system which fuses classical and quantum search applied on Flask as the web front end and Qiskit as the quantum one. This will enable me to compare the simple linear algorithm of searching through the list item-by-item with the quantum algorithm of Grover which uses superposition, a marking oracle to identify the desired item, and multiple amplitude amplification diffusion operators. The web page also accepts a student ID, and actually searches both simultaneously and allows me to tweak a depolarizing noise model so as to more closely mimic real quantum hardware. I measured such variables as the number of calls to the oracle, the number of qubits that I require, the quantum run time, and the number of measurements that I receive out of the quantum measurement. As the results indicate, the algorithm developed by Grover reduces the number of operations significantly compared to the classical one, and it must be emphasized that the algorithm remains quite effective even in the case of simulated noise. On the whole, it demonstrates that the classical and quantum components may be an efficient method to deal with the large search in the database.

•Aug 11, 2026•0 citations
One of the most important challenges in information networks is to gather data from a larger set of nodes to a smaller set of nodes. This can be done via the use of a concentrator architecture in the connection topology. This paper is a proof-of-concept that demonstrates a quantum-based controller in large interconnection networks can asymptotically perform this task faster. We specifically present quantum algorithms for routing concentration assignments on full capacity fat-and-slim concentrators, bounded fat-and-slim concentrators, and regular fat-and-slim concentrators. Classically, the concentration assignment takes O(n) time on all these concentrators, where n is the number of inputs. Powered by Grover's quantum search algorithm, our algorithms take O(ncln⁡c) time, where c is the capacity of the concentrator. Thus, our quantum algorithms are asymptotically faster than their classical counterparts, when cln2⁡c=o(n). In general, c=nμ, satisfies cln2⁡c=o(n), implying a time complexity of O(n0.5(1+μ)ln⁡n), for any μ,0<μ<1.
Quantum switching networks are derived from conventional switching networks by replacing the classical switches by quantum switches. We give the quantum circuit design and routing of an n \times m network, called a quantum concentrator that can direct quantum bit packets in arbitrary quantum states from any of its k inputs to some of its k outputs, where 1 \le k \le m \le n. Our designs are based on sparse crossbars which are rectangular grids of 2 \times 2 crosspoints. Sparse crossbar concentrator structures with theoretically minimum crosspoint complexities for any values of n and m are well known but no self-routing algorithms have been reported for such concentrators. We transform two such families of optimal concentrators, called fat-slim and banded sparse crossbars into quantum networks and provide self-routing algorithms for these families of concentrators. In this process, we extend the notion of packet concentration to a quantum network and design self-routing quantum crosspoints from quantum gates. We address issues critical to quantum operation like reversibility and localized self-routing and give a rigorous proof that quantum fat-slim and banded sparse crossbar concentrators are self-routable. The self-routing algorithms described in the paper can be used for both quantum and classical sparse crossbar concentrators by the linearity property of all quantum systems.
Flexible distribution of data in the form of quantum bits or qubits among spatially separated entities is an essential component of envisioned scalable quantum computing architectures. Accordingly, we consider the problem of dynamically permuting groups of quantum bits, i.e., qubit packets, using networks of reconfigurable quantum switches. We demonstrate and then explore the equivalence between the quantum process of creation of packet superpositions and the process of randomly routing packets in the corresponding classical network. In particular, we consider an n × n Baseline network for which we explicitly relate the pairwise input-output routing probabilities in the classical random routing scenario to the probability amplitudes of the individual packet patterns superposed in the quantum output state. We then analyze the effect of using quantum random routing on a classically non-blocking configuration like the Benes network. We prove that for an n × n quantum Benes network, any input packet assignment with no output contention is probabilistically self-routable. In particular, we prove that with random routing on the first (log n-1) stages and bit controlled self-routing on the last log n stages of a quantum Benes network, the output packet pattern corresponding to routing with no blocking is always present in the output quantum state with a non-zero probability. We give a lower bound on the probability of observing such patterns on measurement at the output and identify a class of 2 n-1 permutation patterns for which this bound is equal to 1, i.e., for all the permutation patterns in this class the following is true: in every pattern in the quantum output assignment all the valid input packets are present at their correct output addresses. In the second part of this thesis we give the complete design of quantum sparse crossbar concentrators. Sparse crossbar concentrators are rectangular grids of simple 2 × 2 switches or crosspoints, with the switches arranged such that any k inputs can be connected to some k outputs. We give the design of the quantum crosspoints for such concentrators and devise a self-routing method to concentrate quantum packets. Our main result is a rigorous proof that certain crossbar structures, namely, the fat-slim and banded quantum crossbars allow, without blocking, the realization of all concentration patterns with self-routing. In the last part we consider the scenario in which quantum packets are queued at the inputs to an n × n quantum non-blocking switch. We assume that each packet is a superposition of m classical packets. Under the assumption of uniform traffic, i.e., any output is equally likely to be accessed by a packet at an input we find the minimum value of m such that the output quantum state contains at least one packet pattern in which no two packets contend for the same output. Our calculations show that for m=9 the probability of a non-contending output pattern occurring in the quantum output is greater than 0.99 for all n up to 64.
Grover’s algorithm harnesses the power of quantum computing to swiftly locate specific elements in an unstructured database, outperforming classical computers in tasks like database searching. This algorithm capitalizes on the unique ability of qubits to be in both 0 and 1 states simultaneously (superposition), allowing it to scan the entire search space at once. It then boosts the probability of the target element, making it more prominent. While the foundational concepts of Grover’s algorithm are well-documented, practical implementation using quantum operators, especially for large search spaces, remains less explored beyond basic examples with a small number of qubits. Existing general synthesis techniques often involve numerous operators or are time-consuming. Our proposed methods specifically address the amplitude-amplification component of Grover’s algorithm for any size of search space. These methods detail the required types and quantities of qubits and operators, emphasizing minimal usage and efficient assembly. Developed and evaluated in Python, our methods consistently identified target elements with over 95% accuracy and achieved configurations comparably compact as those in the existing literature but at a faster pace. We anticipate that these methods facilitate practical implementations of Grover’s algorithm across various domains.
Abstract Quantum computing can solve some classes of problems faster than classical computing. Among the greatest quantum algorithms to showcase this benefit is Grover's search algorithm, which has a quadratic speed-up for unstructured search problems. In this study, we present an implementation of Grover’s algorithm on a large-scale dataset comprising approximately 131,072 (217) names. We contrast its efficiency with the classical linear search based on time complexity, scalability, and the likelihood of success. The experiment was conducted using Qiskit on a quantum simulator, where several query scenarios were implemented to verify the algorithm's efficiency and accuracy. Our findings highlight the theoretical advantage of Grover’s algorithm in situations involving large data sets, while also discussing real-world limitations such as gate noise, qubit number, and circuit depth as we move towards actual quantum hardware. This study serves as a step toward evaluating the real-world relevance of quantum search algorithms and provides information on current challenges and future directions in quantum information retrieval.
Grover search is one of the most important quantum algorithms. In this paper, we consider a kind of search that the conditions of satisfaction TTT can be rewritten as T=T1⋂T2T=T_1\bigcap T_2T=T1​⋂T2​. Then we present a new Grover search with smaller oracles. The time complexity of this algorithm O(π4Nbλ+π4bτ)O(\fracπ{4}\sqrt{\frac{N}{bλ}}+\fracπ{4}\sqrt{\frac{b}τ})O(4π​bλN​​+4π​τb​​), which is smaller than the time complexity of original Grover search, i.e. O(π4NM)O(\fracπ{4}\sqrt{\frac{N}{M}})O(4π​MN​​).
In my project I would have considered how the old search algorithms that are used when working with large unstructured data set end up taking linear time (O(N)) that in effect is the time that scales with the size of the data. These old ways get gradually sluggish, as everything gets bigger. Then I read about quantum computing, and especially Search Algorithm that was developed by Grover which is capable of quadratic speed-up with a complexity of O(sqrt(N)) of unstructured data. I created a hybrid system which fuses classical and quantum search applied on Flask as the web front end and Qiskit as the quantum one. This will enable me to compare the simple linear algorithm of searching through the list item-by-item with the quantum algorithm of Grover which uses superposition, a marking oracle to identify the desired item, and multiple amplitude amplification diffusion operators. The web page also accepts a student ID, and actually searches both simultaneously and allows me to tweak a depolarizing noise model so as to more closely mimic real quantum hardware. I measured such variables as the number of calls to the oracle, the number of qubits that I require, the quantum run time, and the number of measurements that I receive out of the quantum measurement. As the results indicate, the algorithm developed by Grover reduces the number of operations significantly compared to the classical one, and it must be emphasized that the algorithm remains quite effective even in the case of simulated noise. On the whole, it demonstrates that the classical and quantum components may be an efficient method to deal with the large search in the database.