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:2306.05253 · Inverse Problems and Imaging

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem

Joonas Ilmavirta, Matti J. Lassas, Jinpeng Lu, Lauri Oksanen, Lauri Ylinen

Published Dec 5, 2024• 1 citation
arXivHTMLPDF

Abstract

We consider an inverse problem for a finite graph $ (X, E) $ where we are given a subset of vertices $ B\subset X $ and the distances $ d_{(X, E)}(b_1, b_2) $ between all pairs of vertices $ b_1, b_2\in B $. The distance between vertices $ x_1, x_2\in X $ is defined as the minimal number of edges in paths connecting the vertices. This problem can be regarded as a discrete version of the boundary rigidity problem in Riemannian geometry or the inverse travel time problem in geophysics. We develop quantum computing methods to find a solution to the problem, and show that the solution is unique under certain conditions. We prove the following uniqueness result: when $ (X, E) $ is a tree and $ B $ is the set of leaves of the tree, the graph $ (X, E) $ is uniquely determined in the class of all connected graphs having a fixed number of vertices. We present a quantum algorithm which, under arbitrary conditions, produces the graph $ (X, E) $, or one of those, which has the given number of vertices and the required distances between vertices in $ B $. To this end we develop an algorithm that takes in a qubit representation of a graph and combine it with Grover's search algorithm. The algorithm can be implemented using only $ O(|X|^2) $ qubits, the same order as the number of elements in the adjacency matrix of $ (X, E) $, and it has a quadratic improvement in computational cost compared to standard classical algorithms. Finally, we consider applications in the theory of computation, and show that a slight modification of the inverse problem above is NP-complete: all NP-problems can be reduced to a discrete inverse problem that we consider.

DOI
10.3934/ipi.2024049

Related papers

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•17 citations

Quantum Computing for Graph Partitioning with Optimal Speedup

Jincheng Zhang

Graph partitioning is a fundamental problem in computer science with applications in diverse fields like network design, compiler optimization, and data analysis. Traditional algorithms for graph partitioning often suffer from computational complexity, particularly when dealing with large graphs. This paper explores the potential of utilizing quantum computing to accelerate graph partitioning. Specifically, we investigate the application of Grover's algorithm, a quantum search algorithm, to the problem. Our core claim is that by leveraging the superposition and interference capabilities inherent in quantum mechanics, a quantum solution can achieve a provable speedup compared to classical approaches. We present a theoretical framework outlining the algorithm's operation and derive the expected speedup. The key mathematical formulation involves representing the graph partitioning problem as an unstructured search problem amenable to Grover's algorithm. We define the problem as minimizing the cut size, represented by the objective function: *f(S) = Σi∈S Σj∈Sc d(i, j)* where *S* is a subset of vertices, *Sc* is the complement of *S* in the graph, and *d(i, j)* is the shortest path distance between vertices *i* and *j*. The algorithm then constructs a quantum oracle that maps the problem state to a superposition of all possible partitions. Grover's algorithm is then applied to amplify the amplitude of the solution state, resulting in a high probability of finding an optimal or near-optimal partition. The speedup is directly proportional to the square root of the number of iterations performed by Grover's algorithm, which is influenced by the problem size and the quality of the oracle. We analyze the complexity of the quantum algorithm and compare it to the complexity of the best-known classical algorithms, demonstrating a potential for significant speedup. Further research will focus on optimizing the oracle construction and exploring other quantum algorithms suitable for graph partitioning.

•Sep 5, 2026•0 citations

Advances in quantum algorithms for the shortest path problem

Adam Wesołowski, Stephen Piddock

Given an undirected, weighted graph, with $n$ vertices and $m$ edges, and two special vertices $s$ and $t$, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in $\tilde{O}(l^2\sqrt{m})$ expected time and uses $O(\log{n})$ space on graphs where the shortest $s$-$t$ path is also a minimum resistance $s$-$t$ subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability $q>0.537$ of finding the shortest $s$-$t$ path. In such cases the quantum algorithm outputs the shortest $s$-$t$ path with high probability in $\widetilde{O}(\ell\sqrt{m})$ expected time and $O(\log{n})$ space, where $l$ is the length (or total weight, in case of weighted graphs) of the shortest $s$-$t$ path. This algorithm can be parallelised to $\tilde{O}(\sqrt{lm})$ circuit depth when using $O(l\log{n})$ space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.

arXiv:2408.10427•Aug 19, 2024•1 citation

Quantum-accelerated shortest path search on a graph in unsorted space

Паскаль Мишелевич Хури, Алина Дмитриевна Клишева, Petr Demchenko +3 more

Algorithms and data structures are important in information technology (particularly in 6G terahertz wireless communications), logistics, transportation, and route planning in medicine. One of the fundamental algorithms that find application in many practical problems is the shortest path algorithm. The shortest path algorithm is used to find the optimal route between two vertices while minimizing the length or number of intermediate nodes. This problem is one of the 21 NP-hard problems formulated by Richard Karp in 1972. It still poses a serious challenge to science, since there is no polynomial algorithm that can provide an exact solution to this problem. The article considers approaches to solving the problem of finding the shortest path on a graph, and discusses their advantages and disadvantages. Various algorithms, such as the Bellman-Ford algorithm, Dijkstra, and the A* algorithm, are considered; their efficiency and applicability in various situations are analyzed. Issues of optimization of shortest path algorithms are discussed, such as the use of heuristics, graph preprocessing, and other methods that can improve the performance and accuracy of algorithms. The article proposes an optimization of Dijkstra’s algorithm with quantum acceleration. The stability of the quantum algorithm and the magnitude of distortions in a circuit with a different number of qubits are estimated. It is shown that with an increase in the intensity of distortions, the probability of detecting the desired element decreases, and the time spent on its search increases. When using Grover’s algorithm to optimize a path in a quantum network, these interferences cause an increase in the time it takes to find the optimal path and an increase in the probability of choosing an incorrect route. It is shown that an increase in the number of qubits and, accordingly, the number of iterations makes the algorithm more stable. It is demonstrated that the stability of Grover’s algorithm for circuits with a large number of qubits has a similar nature. The work of quantum circuits on 9, 10 and 11 qubits, the difference in the probabilities of correct operation differs by less than 10–3. Thus, from the obtained dependencies, it is possible to predict the nature of such an influence on circuits with an even larger number of qubits, the stability of which cannot be studied due to the insufficient computing power of classical computers. The most efficient way to modify Dijkstra’s algorithm is to replace the priority queue in the classical version of the algorithm with some quantum data structure that finds the minimum element for the next iteration of the algorithm. Despite the fact that quantum search does not provide a potential gain in asymptotics, another quantum modification of Dijkstra’s algorithm can be used. Namely, instead of maintaining and searching for a minimum in the priority queue, use the quantum algorithm immediately to search for a vertex that needs to be added to the shortest path tree, which will additionally acceleration the graph traversal by Dijkstra’s algorithm.

Scientific and technical journal of information technologies mechanics and optics•Jul 9, 2026•0 citations

Quantum algorithms for path and cycle containment problems

Arjan Cornelissen, Amin Shiraz Gilani, Subhasree Patro

The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph $H$ is present in an input graph $G$, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length $k$. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly $k$, or at most $k$. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes. When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity $\widetilde{O}(n^{3/2-α_k})$, where $α_k \in Θ(c^{-k})$ and $c = \sqrt{3+\sqrt{17}}/2 \approx 1.33$, beating the previous best upper bound $O(n^{3/2})$ on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an $O(\sqrt{n})$ query algorithm.

quant-pharXiv:2605.09017•Leibniz international proceedings in informatics•May 12, 2026•0 citations

Quantum algorithms and the maximum clique problem in graphs

Matheus Augusto Condé Dias

Determining the cardinality of the maximum clique on a simple graph is a NP-hard problem with several applications of interest. The best know classical algorithm for this problem has 𝒪(3𝑛/3) time complexity. Classical computing uses phenomena from classical physics to model, store and process information. Consequently, the entire model of classical computing is bounded superiorly by the limits of classical physics. As an alternative, Quantum Computing has been developed to take advantage of quantum phenomena and provide the constructions of circuits capable of performing certain computations more efficiently. In this paper, two quantum solutions to the maximum clique problem will be proposed and analyzed, based on the Grover Quantum Search algorithms and the Quantum Minimal Search Algorithm, comparing their respective time complexities with the best known classical solution.

•Sep 14, 2022•0 citations
We consider an inverse problem for a finite graph (X,E)(X, E)(X,E) where we are given a subset of vertices B⊂XB\subset XB⊂X and the distances d(X,E)(b1,b2)d_{(X, E)}(b_1, b_2)d(X,E)​(b1​,b2​) between all pairs of vertices b1,b2∈Bb_1, b_2\in Bb1​,b2​∈B. The distance between vertices x1,x2∈Xx_1, x_2\in Xx1​,x2​∈X is defined as the minimal number of edges in paths connecting the vertices. This problem can be regarded as a discrete version of the boundary rigidity problem in Riemannian geometry or the inverse travel time problem in geophysics. We develop quantum computing methods to find a solution to the problem, and show that the solution is unique under certain conditions. We prove the following uniqueness result: when (X,E)(X, E)(X,E) is a tree and BBB is the set of leaves of the tree, the graph (X,E)(X, E)(X,E) is uniquely determined in the class of all connected graphs having a fixed number of vertices. We present a quantum algorithm which, under arbitrary conditions, produces the graph (X,E)(X, E)(X,E), or one of those, which has the given number of vertices and the required distances between vertices in BBB. To this end we develop an algorithm that takes in a qubit representation of a graph and combine it with Grover's search algorithm. The algorithm can be implemented using only O(∣X∣2)O(|X|^2)O(∣X∣2) qubits, the same order as the number of elements in the adjacency matrix of (X,E)(X, E)(X,E), and it has a quadratic improvement in computational cost compared to standard classical algorithms. Finally, we consider applications in the theory of computation, and show that a slight modification of the inverse problem above is NP-complete: all NP-problems can be reduced to a discrete inverse problem that we consider.
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.
Graph partitioning is a fundamental problem in computer science with applications in diverse fields like network design, compiler optimization, and data analysis. Traditional algorithms for graph partitioning often suffer from computational complexity, particularly when dealing with large graphs. This paper explores the potential of utilizing quantum computing to accelerate graph partitioning. Specifically, we investigate the application of Grover's algorithm, a quantum search algorithm, to the problem. Our core claim is that by leveraging the superposition and interference capabilities inherent in quantum mechanics, a quantum solution can achieve a provable speedup compared to classical approaches. We present a theoretical framework outlining the algorithm's operation and derive the expected speedup. The key mathematical formulation involves representing the graph partitioning problem as an unstructured search problem amenable to Grover's algorithm. We define the problem as minimizing the cut size, represented by the objective function: *f(S) = Σi∈S Σj∈Sc d(i, j)* where *S* is a subset of vertices, *Sc* is the complement of *S* in the graph, and *d(i, j)* is the shortest path distance between vertices *i* and *j*. The algorithm then constructs a quantum oracle that maps the problem state to a superposition of all possible partitions. Grover's algorithm is then applied to amplify the amplitude of the solution state, resulting in a high probability of finding an optimal or near-optimal partition. The speedup is directly proportional to the square root of the number of iterations performed by Grover's algorithm, which is influenced by the problem size and the quality of the oracle. We analyze the complexity of the quantum algorithm and compare it to the complexity of the best-known classical algorithms, demonstrating a potential for significant speedup. Further research will focus on optimizing the oracle construction and exploring other quantum algorithms suitable for graph partitioning.
Given an undirected, weighted graph, with nnn vertices and mmm edges, and two special vertices sss and ttt, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in O~(l2m)\tilde{O}(l^2\sqrt{m})O~(l2m​) expected time and uses O(log⁡n)O(\log{n})O(logn) space on graphs where the shortest sss-ttt path is also a minimum resistance sss-ttt subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability q>0.537q>0.537q>0.537 of finding the shortest sss-ttt path. In such cases the quantum algorithm outputs the shortest sss-ttt path with high probability in O~(ℓm)\widetilde{O}(\ell\sqrt{m})O(ℓm​) expected time and O(log⁡n)O(\log{n})O(logn) space, where lll is the length (or total weight, in case of weighted graphs) of the shortest sss-ttt path. This algorithm can be parallelised to O~(lm)\tilde{O}(\sqrt{lm})O~(lm​) circuit depth when using O(llog⁡n)O(l\log{n})O(llogn) space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.
Algorithms and data structures are important in information technology (particularly in 6G terahertz wireless communications), logistics, transportation, and route planning in medicine. One of the fundamental algorithms that find application in many practical problems is the shortest path algorithm. The shortest path algorithm is used to find the optimal route between two vertices while minimizing the length or number of intermediate nodes. This problem is one of the 21 NP-hard problems formulated by Richard Karp in 1972. It still poses a serious challenge to science, since there is no polynomial algorithm that can provide an exact solution to this problem. The article considers approaches to solving the problem of finding the shortest path on a graph, and discusses their advantages and disadvantages. Various algorithms, such as the Bellman-Ford algorithm, Dijkstra, and the A* algorithm, are considered; their efficiency and applicability in various situations are analyzed. Issues of optimization of shortest path algorithms are discussed, such as the use of heuristics, graph preprocessing, and other methods that can improve the performance and accuracy of algorithms. The article proposes an optimization of Dijkstra’s algorithm with quantum acceleration. The stability of the quantum algorithm and the magnitude of distortions in a circuit with a different number of qubits are estimated. It is shown that with an increase in the intensity of distortions, the probability of detecting the desired element decreases, and the time spent on its search increases. When using Grover’s algorithm to optimize a path in a quantum network, these interferences cause an increase in the time it takes to find the optimal path and an increase in the probability of choosing an incorrect route. It is shown that an increase in the number of qubits and, accordingly, the number of iterations makes the algorithm more stable. It is demonstrated that the stability of Grover’s algorithm for circuits with a large number of qubits has a similar nature. The work of quantum circuits on 9, 10 and 11 qubits, the difference in the probabilities of correct operation differs by less than 10–3. Thus, from the obtained dependencies, it is possible to predict the nature of such an influence on circuits with an even larger number of qubits, the stability of which cannot be studied due to the insufficient computing power of classical computers. The most efficient way to modify Dijkstra’s algorithm is to replace the priority queue in the classical version of the algorithm with some quantum data structure that finds the minimum element for the next iteration of the algorithm. Despite the fact that quantum search does not provide a potential gain in asymptotics, another quantum modification of Dijkstra’s algorithm can be used. Namely, instead of maintaining and searching for a minimum in the priority queue, use the quantum algorithm immediately to search for a vertex that needs to be added to the shortest path tree, which will additionally acceleration the graph traversal by Dijkstra’s algorithm.
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph HHH is present in an input graph GGG, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length kkk. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly kkk, or at most kkk. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes. When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity O~(n3/2−αk)\widetilde{O}(n^{3/2-α_k})O(n3/2−αk​), where αk∈Θ(c−k)α_k \in Θ(c^{-k})αk​∈Θ(c−k) and c=3+17/2≈1.33c = \sqrt{3+\sqrt{17}}/2 \approx 1.33c=3+17​​/2≈1.33, beating the previous best upper bound O(n3/2)O(n^{3/2})O(n3/2) on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an O(n)O(\sqrt{n})O(n​) query algorithm.
Determining the cardinality of the maximum clique on a simple graph is a NP-hard problem with several applications of interest. The best know classical algorithm for this problem has 𝒪(3𝑛/3) time complexity. Classical computing uses phenomena from classical physics to model, store and process information. Consequently, the entire model of classical computing is bounded superiorly by the limits of classical physics. As an alternative, Quantum Computing has been developed to take advantage of quantum phenomena and provide the constructions of circuits capable of performing certain computations more efficiently. In this paper, two quantum solutions to the maximum clique problem will be proposed and analyzed, based on the Grover Quantum Search algorithms and the Quantum Minimal Search Algorithm, comparing their respective time complexities with the best known classical solution.