Papers › Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
Joonas Ilmavirta, Matti Lassas, Jinpeng Lu, Lauri Oksanen, Lauri Ylinen
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We consider an inverse problem for a finite graph (X,E) where we are given a subset of vertices B⊂X and the distances d_((X,E))(b₁,b₂) of all vertices b₁,b₂∈B. The distance of points x₁,x₂∈X is defined as the minimal number of edges needed to connect two vertices, so all edges have length 1. The inverse problem is a discrete version of the boundary rigidity problem in Riemannian geometry or the inverse travel time problem in geophysics. We will show that this problem has unique solution under certain conditions and develop quantum computing methods to solve it. 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) can be uniquely determined in the class of all graphs having a fixed number of vertices. We present a quantum computing algorithm which produces a graph (X,E), or one of those, which has a 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|²) qubits, the same order as the number of elements in the adjacency matrix of (X,E). It also has a quadratic improvement in computational cost compared to standard classical algorithms. Finally, we consider applications in theory of computation, and show that a slight modification of the above inverse problem is NP-complete: all NP-problems can be reduced to a discrete inverse problem we consider.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections