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

Abstract. 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) (b1, b2) between all pairs of vertices b1, b2 ∈ B. The distance between vertices x1, 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) 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.