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

arXiv2306.05253MaRDI QIDQ6510484FDOQ6510484

Authors: Joonas Ilmavirta, M. Lassas, Jinpeng Lu, Lauri Oksanen, Lauri Ylinen 

Abstract: We consider an inverse problem for a finite graph $(X,E)$ where we are given a subset of vertices $BsubsetX$ and the distances $d_{(X,E)}(b_1,b_2)$ of all vertices $b_1,b_{2}inB$. The distance of points $x_1,x_{2}inX$ 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{|}^2)$ 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.

Has companion code repository: https://github.com/l-oksanen/illoy2023

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

This page was built for publication: Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6510484)