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:2603.04758

Quantum Algorithms for Network Signal Coordination

Vinayak Dixit, Richard Pech

quant-phcs.CCcs.DScs.NISubmitted Mar 5, 2026• Announced Mar 6, 2026• 1 citation
arXivHTMLPDF

Abstract

There has been increasing interest in developing efficient quantum algorithms for hard classical problems. The Network Signal Coordination (NSC) problem is one such problem known to be NP complete. We implement Grover's search algorithm to solve the NSC problem to provide quadratic speedup. We further extend the algorithm to a Robust NSC formulation and analyse its complexity under both constant and polynomial-precision robustness parameters. The Robust NSC problem determines whether there exists a fraction (alpha) of solutions space that will lead to system delays less than a maximum threshold (K). The key contributions of this work are (1) development of a quantum algorithm for the NSC problem, and (2) a quantum algorithm for the Robust NSC problem whose iteration count is O(1/sqrt(alpha)), independent of the search space size, and (3) an extension to polynomial-precision robustness where alpha = alpha_o/p(N) decays polynomially with network size, retaining a quadratic quantum speedup. We demonstrate its implementation through simulation and on an actual quantum computer.

Related papers

A quantum–classical approach to solve the graph coloring problem with minimum colors

Prem Shanker Dwivedi, Abhinav Kumar, Amit Biswas +1 more

Abstract Graph coloring with minimum colors is a well-known NP-complete problem in computer science and mathematics, having diverse real-life applications such as scheduling, register allocation, and frequency assignment. However, a classical computer requires exponential time to solve the graph coloring problem with the minimum number of colors. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for speedup on specific problems, although solutions are typically obtained with a certain probability of correctness. This work proposes a quantum–classical method for solving the graph coloring problem and finding the chromatic number of a graph with guaranteed correctness, and also reduces the time and qubit complexities. The proposed method is inspired by Randomized Grover’s search algorithm, and the classical binary search algorithm. Here, Randomized Grover’s search algorithm provides quadratic speedup and this algorithm is useful in real situations when the number of solutions is not known in advance in contrast to the Grover’s search algorithm. The binary search algorithm helps to achieve logarithmic speedup, which reduces overall complexity. The experimental results strongly validate our claims and demonstrate the superiority of the approach. Furthermore, a comprehensive mathematical analysis is carried out to examine its complexities, as well as to compare its computational efficiency with existing methods.

Physica Scripta•Oct 9, 2026•0 citations

Quantum speedup in solving the maximal-clique problem

Weng-Long Chang, Qi Yu, Zhaokai Li +3 more

The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph $G$ with $n$ vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, $O(\sqrt{{2}^{n}})$ and $O({n}^{2})$. With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph $G$ with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.

arXiv:1803.11356•Physical Review A•Mar 29, 2018•18 citations

Toward Applying Quantum Computing to Network Verification

Kahlil Dozier, Justin Beltran, K. Jordan Berg +4 more

Network verification, broadly defined as proving the correctness of certain properties resulting from a network's configuration, cannot be efficiently solved on classical hardware via brute force. Prior work has developed a variety of methods that scale by observing a structure in the search space and then evaluating classes induced by that structure. However, even these classification mechanisms have their limitations. In this paper, we consider a radically different approach: applying quantum computing to more efficiently solve network verification problems. We provide an overview of how to map variants of verification problems into unstructured search problems that can be solved via quantum computing with quadratic speedup, making the approach feasible in theory to problems that twice as big in the size of the input. Emerging quantum systems cannot yet tackle problems of practical interest, but rapid advances in hardware and algorithm development make now a great time to start thinking about their application. With this in mind, we explore the limits of scale of the problem for which quantum computing can solve network verification problems as unstructured search.

arXiv:2410.17184•ACM Workshop on Hot Topics in Networks (HotNets)•Nov 11, 2024•1 citation

Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the Dominating Set Problem

Jehn‐Ruey Jiang, Qiao-Yi Lin

Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O($\sqrt N$) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.

arXiv:2312.09388•Dec 14, 2023•5 citations

The Subset Sum Problem: Reducing Time Complexity of NP-Completeness with Quantum Search

Bo Moon

The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. Although there are polynomial time approximations and heuristics, these are not always acceptable, yet exact-solution algorithms are unfeasible for large input. Quantum computation offers new insights for not only the Subset Sum Problem but also the entire NP-complete class; most notably, Grover's quantum algorithm for an unstructured database search can be tailored to identify solutions to problems within mathematics and computer science. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.

Undergraduate Journal of Mathematical Modeling One + Two•May 1, 2013•3 citations

Practical Guide to Quantum Computing: Grover's Algorithm # 4

Mikhail Pavlov

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.

•Mar 4, 2026•0 citations
There has been increasing interest in developing efficient quantum algorithms for hard classical problems. The Network Signal Coordination (NSC) problem is one such problem known to be NP complete. We implement Grover's search algorithm to solve the NSC problem to provide quadratic speedup. We further extend the algorithm to a Robust NSC formulation and analyse its complexity under both constant and polynomial-precision robustness parameters. The Robust NSC problem determines whether there exists a fraction (alpha) of solutions space that will lead to system delays less than a maximum threshold (K). The key contributions of this work are (1) development of a quantum algorithm for the NSC problem, and (2) a quantum algorithm for the Robust NSC problem whose iteration count is O(1/sqrt(alpha)), independent of the search space size, and (3) an extension to polynomial-precision robustness where alpha = alpha_o/p(N) decays polynomially with network size, retaining a quadratic quantum speedup. We demonstrate its implementation through simulation and on an actual quantum computer.
Abstract Graph coloring with minimum colors is a well-known NP-complete problem in computer science and mathematics, having diverse real-life applications such as scheduling, register allocation, and frequency assignment. However, a classical computer requires exponential time to solve the graph coloring problem with the minimum number of colors. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for speedup on specific problems, although solutions are typically obtained with a certain probability of correctness. This work proposes a quantum–classical method for solving the graph coloring problem and finding the chromatic number of a graph with guaranteed correctness, and also reduces the time and qubit complexities. The proposed method is inspired by Randomized Grover’s search algorithm, and the classical binary search algorithm. Here, Randomized Grover’s search algorithm provides quadratic speedup and this algorithm is useful in real situations when the number of solutions is not known in advance in contrast to the Grover’s search algorithm. The binary search algorithm helps to achieve logarithmic speedup, which reduces overall complexity. The experimental results strongly validate our claims and demonstrate the superiority of the approach. Furthermore, a comprehensive mathematical analysis is carried out to examine its complexities, as well as to compare its computational efficiency with existing methods.
The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph GGG with nnn vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, O(2n)O(\sqrt{{2}^{n}})O(2n​) and O(n2)O({n}^{2})O(n2). With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph GGG with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.
Network verification, broadly defined as proving the correctness of certain properties resulting from a network's configuration, cannot be efficiently solved on classical hardware via brute force. Prior work has developed a variety of methods that scale by observing a structure in the search space and then evaluating classes induced by that structure. However, even these classification mechanisms have their limitations. In this paper, we consider a radically different approach: applying quantum computing to more efficiently solve network verification problems. We provide an overview of how to map variants of verification problems into unstructured search problems that can be solved via quantum computing with quadratic speedup, making the approach feasible in theory to problems that twice as big in the size of the input. Emerging quantum systems cannot yet tackle problems of practical interest, but rapid advances in hardware and algorithm development make now a great time to start thinking about their application. With this in mind, we explore the limits of scale of the problem for which quantum computing can solve network verification problems as unstructured search.
Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O(N\sqrt NN​) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.
The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. Although there are polynomial time approximations and heuristics, these are not always acceptable, yet exact-solution algorithms are unfeasible for large input. Quantum computation offers new insights for not only the Subset Sum Problem but also the entire NP-complete class; most notably, Grover's quantum algorithm for an unstructured database search can be tailored to identify solutions to problems within mathematics and computer science. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.
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.