Abstract
We normally think of implicit Mechanical Computer Aided Engineering (MCAE) as being a resource intensive process, dominated by multifrontal linear solvers that scale super linearly in complexity as the problem size grows. However, as the processor count increases, the reordering that reduces the storage and operation count for the sparse linear solver is emerging as the biggest computational bottleneck and is expected to grow. Reordering is NP-complete, and the nested dissection heuristic is generally preferred for MCAE problems. Nested dissection in turn rests on graph partitioning, another NP-complete problem. There are quantum computing algorithms which provide new heuristics for NP-complete problems, and the rapid growth of today’s noisy quantum computers and associated error mitigation techniques leads us to consider them as possible accelerators for reordering. This review reports on the evaluation of the relative merits of several short depth quantum algorithms used for graph partitioning, integration with the LS-DYNA MCAE application, and using the initial results generated on IBM quantum computers to bring to attention critical focus areas based on the methods used within.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Barnard, S.T., Simon, H.D.: A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. In: Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing, PPSC 1993, Norfolk, Virginia, USA, 22–24 March 1993, pp. 711–718. SIAM (1993)
Van Den Berg, E., Minev, Z.K., Temme, K.: Model-free readout-error mitigation for quantum expectation values (2020). https://doi.org/10.48550/ARXIV.2012.09738. https://arxiv.org/abs/2012.09738
Bravo-Prieto, C., LaRose, R., Cerezo, M., Subasi, Y., Cincio, L., Coles, P.J.: Variational quantum linear solver. arXiv preprint arXiv:1909.05820 (2019)
Bui, T.N., Jones, C.: A heuristic for reducing fill-in in sparse matrix factorization. In: Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing, PPSC 1993, Norfolk, Virginia, USA, 22–24 March 1993, pp. 445–452. SIAM (1993)
Cerezo, M., Sone, A., Volkoff, T., Cincio, L., Coles, P.J.: Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nat. Commun. 12(1), 1–12 (2021)
Chang, J.B.: Improved superconducting qubit coherence using titanium nitride. Appl. Phys. Lett. 103(1), 012602 (2013)
Davis, T.A., Hu, Y.: The university of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1–25 (2011). https://doi.org/10.1145/2049662.2049663
Du, Y., Hsieh, M.H., Liu, T., Tao, D.: Expressive power of parametrized quantum circuits. Phys. Rev. Res. 2(3), 033125 (2020)
Egger, D.J., Mareček, J., Woerner, S.: Warm-starting quantum optimization. Quantum 5, 479 (2021)
Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014)
Fuller, B., et al.: Approximate solutions of combinatorial problems via quantum relaxations. arXiv preprint arXiv:2111.03167 (2021)
George, A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10(2), 345–363 (1973)
Ghysels, P., Li, X.S., Chávez, G., Liu, Y., Jacquelin, M., Ng, E.: Preconditioning using rank-structured sparse matrix factorization. In: SIAM Conference on Computational Science and Engineering (2019)
Glover, F., Kochenberger, G., Du, Y.: A tutorial on formulating and using QUBO models (2018). https://doi.org/10.48550/ARXIV.1811.11538. https://arxiv.org/abs/1811.11538
Grover, L.K.: A fast quantum mechanical algorithm for database search. In Proceedings of the 28th ACM Symposium on the Theory of Computing, pp. 212–219 (1996)
Kandala, A., et al.: Hardware-efficient variational quantum Eigensolver for small molecules and quantum magnets. Nature 549(7671), 242–246 (2017)
Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359–392 (1998)
Lloyd, S.: Quantum algorithm for solving linear systems of equations. In: APS March Meeting Abstracts, vol. 2010, pp. D4–002 (2010)
Lucas, A.: Ising formulations of many np problems. Front. Phys. 2, 5 (2014)
Lucas, R.F., et al.: Implicit analysis of jet engine models on thousands of processors. In: Sparse Days (2019)
Markowitz, H.M.: The elimination form of the inverse and its application to linear programming. Manage. Sci. 3(3), 255–269 (1957). http://www.jstor.org/stable/2627454
Montanaro, A., Pallister, S.: Quantum algorithms and the finite element method. Phys. Rev. A 93(3), 032324 (2016)
Pan, V.: Complexity of algorithms for linear systems of equations. In: Spedicato, E. (ed.) Computer Algorithms for Solving Linear Algebraic Equations. NATO ASI Series, vol. 77, pp. 27–56. Springer, Berlin (1991). https://doi.org/10.1007/978-3-642-76717-3_2
Peruzzo, A., et al.: A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5(1), 4213 (2014). https://doi.org/10.1038/ncomms5213
Polina, B., Arthur, S., Yuriy, Z., Manhong, Y., Dingshun, l.: Hot-start optimization for variational quantum Eigensolver (2021). https://doi.org/10.48550/ARXIV.2104.15001. https://arxiv.org/abs/2104.15001
Teramoto, K., Raymond, R., Wakakuwa, E., Imai, H.: Quantum-relaxation based optimization algorithms: theoretical extensions. arXiv preprint arXiv:2302.09481 (2023)
Wallraff, A., et al.: Strong coupling of a single photon to a superconducting qubit using circuit quantum electrodynamics. Nature 431(7005), 162–167 (2004)
Wang, S.: Noise-induced barren plateaus in variational quantum algorithms. Nat. Commun. 12(1), 1–11 (2021)
Wiesner, S.: Conjugate coding. ACM SIGACT News 15, 77–78 (1983)
Acknowledgements
The authors acknowledge use of the IBM Quantum devices for this work. The authors are also thankful to Bryce Fuller, Stefan Woerner, Rudy Raymond, Paul Nation and Antonio Mezzacapo for insightful discussions and Johannes Greiner, Stefan Woerner and Paul Nation for a careful read of the manuscript.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Kolak, S. et al. (2023). Evaluating Quantum Algorithms for Linear Solver Workflows. In: Bienz, A., Weiland, M., Baboulin, M., Kruse, C. (eds) High Performance Computing. ISC High Performance 2023. Lecture Notes in Computer Science, vol 13999. Springer, Cham. https://doi.org/10.1007/978-3-031-40843-4_47
Download citation
DOI: https://doi.org/10.1007/978-3-031-40843-4_47
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-40842-7
Online ISBN: 978-3-031-40843-4
eBook Packages: Computer ScienceComputer Science (R0)