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

Joonas Ilmavirta; Matti Lassas; Jinpeng Lu; Lauri Oksanen; Lauri Ylinen

doi:10.3934/ipi.2024049

Article Contents

2025, Volume 19, Issue 4: 660-692. Doi: 10.3934/ipi.2024049

This issue Previous Article A distributed Douglas-Rachford splitting method for solving linear constrained multi-block weakly convex problems Next Article Recovery of an inclusion in photoacoustic imaging

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

1.
Department of Mathematics and Statistics, University of Jyväskylä, Finland
2.
Department of Mathematics and Statistics, University of Helsinki, Finland
3.
Department of Electronics and Nanoengineering, Aalto University, Finland

^*Corresponding author: Jinpeng Lu
^*Corresponding author: Jinpeng Lu

Received: May 2024

Revised: October 2024

Early access: December 4, 2024

Published online: December 4, 2024

Abstract / Introduction Full Text(HTML) Figure(3) Related Papers Cited by

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.

Keywords:

Mathematics Subject Classification: Primary: 68Q12, 52C25; Secondary: 68Q17.

Citation:

Full Text(HTML)

Figure 1. From $ F = (u_1\lor u_2) \land (\bar{u}_1\lor\bar{u}_3) \land (u_2\lor\bar{u}_3) \land u_3 $ we construct an instance of the restricted inverse travel time problem (Problem 1.2). The set $ E_0 $ of edges that must be present in the solution is taken to be the empty set; the set $ E_1 $ of edges that are allowed to appear in the solution consists of the solid and the dotted lines. The distance from $ u_j $ to $ \bar{u}_j $ and from $ \mathsf{TRUE} $ to $ C_i $ is required to be $ 3 $ for all $ i $ and $ j $. A solution for this instance is the subgraph drawn with solid lines; in the corresponding assignment that satisfies $ F $ the literals connected with a solid line to $ \mathsf{TRUE} $ are true

Download: Full-size image PowerPoint slide

Figure 2. Figures (a)–(d) depict the four instances (labeled A–D, respectively) of Problem 1.1 that we consider. The vertices $ b_j\in B $ are drawn in blue; their distances are tabulated in (e). The dashed edges in (c) are edges that do not affect the distance data, thus this instance has a nonunique solution

Download: Full-size image PowerPoint slide

Figure 3. Plots (a)–(d) display simulation results for instances A–D, respectively. In (a) the probability of measurement for each value of $ \vec{e} $ (the adjacency matrix of a $ 3 $-vertex graph) is shown. In (b)–(d) the probabilities of those values of $ \vec{e} $ that correspond to a solution of the instance are shown; "rest" is the sum of the probabilities of those values that are not a solution. The bitstring denoting the measurement result consists of the elements of $ e(j, k) $, $ 1\le j<k\le n $, of $ \vec{e} $ in reverse lexicographical order so that, e.g., in the case $ n = 3 $ the string corresponds to $ e(2, 3)\, e(1, 3)\, e(1, 2) $. Table (e) shows the value of parameter $ L $ (number of Grover iterations), the number of qubits (including ancillae), and the dimension of the state space of the qubit register, for each of the instances A–D

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	S. Aaronson, Introduction to quantum information science lecture notes, https://www.scottaaronson.com/qclec.pdf, 2018.
[2]	M. Aouchiche and P. Hansen, Distance spectra of graphs: A survey, Linear Algebra Appl., 458 (2014), 301-386. doi: 10.1016/j.laa.2014.06.010.
[3]	S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, Cambridge, 2009. doi: 10.1017/CBO9780511804090.
[4]	A. T. Balaban, D. Ciubotariu and M. Medeleanu, Topological indices and real number vertex invariants based on graph eigenvalues or eigenvectors, J. Chem. Inf. Comput. Sci., 31 (1991), 517-523. doi: 10.1021/ci00004a014.
[5]	E. Blåsten, H. Isozaki, M. Lassas and J. Lu, Gel'fand's inverse problem for the graph Laplacian, J. Spectral Theory, 13 (2023), 1-45. doi: 10.4171/jst/455.
[6]	E. Blåsten, H. Isozaki, M. Lassas and J. Lu, Inverse problems for discrete heat equations and random walks for a class of graphs, SIAM J. Discrete Math., 37 (2023), 831-863. doi: 10.1137/21M1439936.
[7]	E. Bonnet, S. Cabello, B. Mohar and H. Pérez-Rosés, The inverse Voronoi problem in graphs I: Hardness, Algorithmica, 82 (2020), 3018-3040. doi: 10.1007/s00453-020-00716-4.
[8]	M. Boyer, G. Brassard, P. Høyer and A. Tapp, Tight bounds on quantum searching, Fortschritte der Physik: Progress of Physics, 46 (1998), 493-505. doi: 10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P.
[9]	P. Buneman, A note on the metric properties of trees, J. Combin. Theory Ser. B, 17 (1974), 48-50. doi: 10.1016/0095-8956(74)90047-1.
[10]	P. Buneman, The recovery of trees from measures of dissimilarity, in Mathematics in the Archaeological and Historical Sciences, (eds. F. Hodson, D. Kendall and P. Tautu), Edinburgh University Press, Edinburgh, 1971,387-395.
[11]	D. Burago, Y. Burago and S. Ivanov, A Course in Metric Geometry, Graduate Studies in Mathematics, American Mathematical Society, Providence, RI.
[12]	D. Burago and S. Ivanov, Boundary rigidity and filling volume minimality of metrics close to a flat one, Ann. of Math. (2), 171 (2010), 1183-1211. doi: 10.4007/annals.2010.171.1183.
[13]	D. Burago and S. Ivanov, Area minimizers and boundary rigidity of almost hyperbolic metrics, Duke Math. J., 162 (2013), 1205-1248. doi: 10.1215/00127094-2142529.
[14]	R. Castro, M. Coates, G. Liang, R. Nowak and B. Yu, Network Tomography: Recent Developments, Statistical Science, 19 (2004), 499-517. doi: 10.1214/088342304000000422.
[15]	V. Chellappan and K. Krithivasan, Distance realization problem in network tomography: A heuristic approach, in 2013 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS), IEEE, 2013, 1-6. doi: 10.1109/ANTS.2013.6802848.
[16]	F. Chung, M. Garrett, R. Graham and D. Shallcross, Distance realization problems with applications to internet tomography, J. Comput. System Sci., 63 (2001), 432-448. doi: 10.1006/jcss.2001.1785.
[17]	S. A. Cook, The complexity of theorem-proving procedures, in Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC '71, Association for Computing Machinery, New York, NY, USA, 1971,151-158. doi: 10.1145/800157.805047.
[18]	C. B. Croke, Rigidity and the distance between boundary points, J. Differential Geom., 33 (1991), 445-464. doi: 10.4310/jdg/1214446326.
[19]	C. B. Croke, N. S. Dairbekov and V. A. Sharafutdinov, Local boundary rigidity of a compact riemannian manifold with curvature bounded above, Trans. Amer. Math. Soc., 352 (2000), 3937-3956. doi: 10.1090/S0002-9947-00-02532-0.
[20]	F. Delsuc, H. Brinkmann and H. Philippe, Phylogenomics and the reconstruction of the tree of life, Nature Reviews Genetics, 6 (2005), 361-375. doi: 10.1038/nrg1603.
[21]	R. C. Entringer, D. E. Jackson and D. A. Snyder, Distance in graphs, Czechoslovak Math. J., 26 (1976), 283-296. doi: 10.21136/CMJ.1976.101401.
[22]	S. N. Evans, Probability and Real Trees, Lecture Notes in Mathematics, Springer, 2008. doi: 10.1007/978-3-540-74798-7.
[23]	J. Felsenstein, Inferring Phylogenies, Sinauer, 2003.
[24]	M. R. Garey and D. S. Johnson, Computers and Intractability, vol. 174, Freeman San Francisco, 1979.
[25]	H. Gernandt and J. Rohleder, A Calderón type inverse problem for tree graphs, Linear Algebra Appl., 646 (2022), 29-42. doi: 10.1016/j.laa.2022.03.018.
[26]	M. Gromov, Filling Riemannian manifolds, J. Differential Geom., 18 (1983), 1-147. doi: 10.4310/jdg/1214509283.
[27]	L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), ACM, New York, 1996,212-219. doi: 10.1145/237814.237866.
[28]	S. L. Hakimi and S. S. Yau, Distance matrix of a graph and its realizability, Quart. Appl. Math., 22 (1965), 305-317. doi: 10.1090/qam/184873.
[29]	G. Herglotz, {\"U}ber das benndorfsche problem der fortpflanzungsgeschwindigkeit der erdbebenstrahlen, Physikal. Zeitschr., 8 (1907), 145-147.
[30]	D. S. Hochba, Approximation algorithms for np-hard problems, ACM Sigact News, 28 (1997), 40-52. doi: 10.1145/261342.571216.
[31]	J. Ilmavirta, M. Lassas, J. Lu, L. Oksanen and L. Ylinen, Illoy2023, https://github.com/l-oksanen/ILLOY2023/, 2023.
[32]	S. Ivanov, On two-dimensional minimal filling, Algebra i Analiz, 13 (2001), 26-38.
[33]	S. Ivanov, Volume comparison via boundary distances, in Proceedings of the ICM, vol. II, Hindustan Book Agency, New Delhi, 2010,769-784.
[34]	A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson and J. M. Gambetta, Quantum computing with Qiskit, arXiv: 2405.08810.
[35]	A. Yu. Kitaev, A. H. Shen and M. N. Vyalyi, Classical and Quantum Computation, Graduate Studies in Mathematics, American Mathematical Society, 2002. doi: 10.1090/gsm/047.
[36]	M. Lassas, V. Sharafutdinov and G. Uhlmann, Semiglobal boundary rigidity for Riemannian metrics, Math. Ann., 325 (2003), 767-793. doi: 10.1007/s00208-002-0407-4.
[37]	N. Masuda, M. A. Porter and R. Lambiotte, Random walks and diffusion on networks, Physics Reports, 716/717 (2017), 1-58. doi: 10.1016/j.physrep.2017.07.007.
[38]	R. Michel, Sur la rigidité imposée par la longueur des géodésiques, Invent. Math., 65 (1981), 71-83. doi: 10.1007/BF01389295.
[39]	R. G. Mukhometov and V. G. Romanov, On the problem of finding an isotropic riemannian metric in an $n$-dimensional space, Dokl. Akad. Nauk SSSR, 243 (1978), 41-44.
[40]	G. Nannicini, An introduction to quantum computing, without the physics, SIAM Rev., 62 (2020), 936-981. doi: 10.1137/18M1170650.
[41]	M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2000.
[42]	C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Reading, MA, 1994.
[43]	G. P. Paternain, M. Salo and G. Uhlmann, Geometric Inverse Problems: With Emphasis on Two Dimensions, Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2023. doi: 10.1017/9781009039901.
[44]	L. Pestov and G. Uhlmann, Two dimensional compact simple Riemannian manifolds are boundary distance rigid, Ann. of Math. (2), 161 (2005), 1093-1110. doi: 10.4007/annals.2005.161.1093.
[45]	C. Semple and M. Steel, Phylogenetics, vol. 24 of Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2003.
[46]	J. Simões Pereira, A note on the tree realizability of a distance matrix, J. Combin. Theory, 6 (1969), 303-310. doi: 10.1016/S0021-9800(69)80092-X.
[47]	P. Stefanov and G. Uhlmann, Boundary rigidity and stability for generic simple metrics, J. Amer. Math. Soc., 18 (2005), 975-1003. doi: 10.1090/S0894-0347-05-00494-7.
[48]	P. Stefanov, G. Uhlmann and A. Vasy, Boundary rigidity with partial data, J. Amer. Math. Soc., 29 (2016), 299-332. doi: 10.1090/jams/846.
[49]	P. Stefanov, G. Uhlmann and A. Vasy, Local and global boundary rigidity and the geodesic x-ray transform in the normal gauge, Ann. of Math. (2), 194 (2021), 1-95. doi: 10.4007/annals.2021.194.1.1.
[50]	P. Stefanov, G. Uhlmann, A. Vasy and H. Zhou, Travel time tomography, Acta Math. Sin. (Engl. Ser.), 35 (2019), 1085-1114. doi: 10.1007/s10114-019-8338-0.
[51]	G. Uhlmann, Inverse problems: Seeing the unseen, Bull. Math. Sci., 4 (2014), 209-279. doi: 10.1007/s13373-014-0051-9.
[52]	E. Wiechert, Bestimmung des weges von erdbebenwellen im erdinnern, Theoretisches. Phys. Z., 11 (1910), 294-311.
[53]	H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69 (1947), 17-20. doi: 10.1021/ja01193a005.
[54]	D. M. Wittmann, D. Schmidl, F. Blöchl and F. J. Theis, Reconstruction of graphs based on random walks, Theoret. Comput. Sci., 410 (2009), 3826-3838. doi: 10.1016/j.tcs.2009.05.026.
[55]	K. Xu, M. Liu, K. Ch. Das, I. Gutman and B. Furtula, A survey on graphs extremal with respect to distance–based topological indices, MATCH Commun. Math. Comput. Chem., 71 (2014), 461-508.
[56]	K. A. Zaretskii, Constructing a tree on the basis of a set of distances between the hanging vertices, Uspekhi Mat. Nauk, 20 (1965), 90-92.
[57]	B. Zhou and N. Trinajstić, Mathematical properties of molecular descriptors based on distances, Croatica Chemica Acta, 83 (2010), 227-242.