@unpublished{quantum-graph-ip,
    author = {Joonas Ilmavirta and Matti Lassas and Jinpeng Lu and Lauri Oksanen and Lauri Ylinen},
    title = {{Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem}},
    month = jun,
    year = 2023,
    arxiv = {2306.05253},
    url={http://users.jyu.fi/~jojapeil/pub/quantum-graph-ip.pdf},
    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)$ of all
vertices $b_1,b_2\in B$. The distance of points $x_1,x_2\in 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|^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.}
}