Parallelization techniques for quantum simulation of fermionic systems

Jacob Bringewatt1,2,3 and Zohreh Davoudi1,4,5

1Department of Physics, University of Maryland, College Park, Maryland 20742, USA
2Joint Center for Quantum Information and Computer Science, NIST/University of Maryland, College Park, Maryland 20742, USA
3Joint Quantum Institute, NIST/University of Maryland, College Park, Maryland 20742, USA
4Maryland Center for Fundamental Physics, University of Maryland, College Park, Maryland 20742, USA
5Institute for Robust Quantum Simulation, University of Maryland, College Park, Maryland 20742, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Mapping fermionic operators to qubit operators is an essential step for simulating fermionic systems on a quantum computer. We investigate how the choice of such a mapping interacts with the underlying qubit connectivity of the quantum processor to enable (or impede) parallelization of the resulting Hamiltonian-simulation algorithm. It is shown that this problem can be mapped to a path coloring problem on a graph constructed from the particular choice of encoding fermions onto qubits and the fermionic interactions onto paths. The basic version of this problem is called the weak coloring problem. Taking into account the fine-grained details of the mapping yields what is called the strong coloring problem, which leads to improved parallelization performance. A variety of illustrative analytical and numerical examples are presented to demonstrate the amount of improvement for both weak and strong coloring-based parallelizations. Our results are particularly important for implementation on near-term quantum processors where minimizing circuit depth is necessary for algorithmic feasibility.

While the basic element of a quantum computer is a qubit—a two-level quantum system—most matter is made of fermions, which have unique statistical properties, namely they obey the Pauli exclusion principle, that differ from the "native" qubit statistics of a quantum computer. Therefore, when simulating physical systems, such as electrons, quarks, nucleons, and certain nuclei and atoms, on a quantum computer, one must encode these fermionic statistics into the qubits, resulting in additional qubit and/or quantum-operation requirements. In this work, we consider a particular class of mappings from fermions to qubits, focusing on how one can optimize the mapping to the hardware in such a way that maximizes the amount of parallelization possible in quantum simulation algorithms for fermionic systems. We do this optimization by viewing the parallelization of fermion to qubit mappings as a graph coloring problem, where one seeks to color the vertices of a collection of vertices and edges so that no vertices that share an edge get the same color. Such optimizations are particularly important in the near-to-intermediate term when the runtime of quantum algorithms is sharply limited by noisy hardware.

► BibTeX data

► References

[1] I. M. Georgescu, S. Ashhab, and F. Nori, Rev. Mod. Phys. 86, 153 (2014).
https:/​/​doi.org/​10.1103/​RevModPhys.86.153

[2] B. Bauer, S. Bravyi, M. Motta, and G. K.-L. Chan, Chem. Rev. 120, 12685 (2020).
https:/​/​doi.org/​10.1021/​acs.chemrev.9b00829

[3] C. W. Bauer, Z. Davoudi, A. Balantekin, T. Bhattacharya, M. Carena, W. A. de Jong, P. Draper, A. El-Khadra, N. Gemelke, M. Hanada, D. Kharzeev, et al., arXiv preprint arXiv:2204.03381 (2022).
https:/​/​doi.org/​10.48550/​arXiv.2204.03381
arXiv:2204.03381

[4] Nuclear Physics and Quantum Information Science: Report by the NSAC QIS Subcommittee, Tech. Rep. (NSF & DOE Office of Science, 2019).
https:/​/​science.osti.gov/​-/​media/​np/​pdf/​Reports/​NSAC_QIS_Report.pdf

[5] P. Jordan and E. Wigner, Z. Phys. 47, 631 (1928).
https:/​/​doi.org/​10.1007/​978-3-662-02781-3_9

[6] G. Ortiz, J. E. Gubernatis, E. Knill, and R. Laflamme, Phys. Rev. A 64, 022319 (2001).
https:/​/​doi.org/​10.1103/​PhysRevA.64.022319

[7] V. Havlíček, M. Troyer, and J. D. Whitfield, Phys. Rev. A 95, 032332 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.95.032332

[8] L. Clinton, J. Bausch, and T. Cubitt, Nat. Comm. 12, 1 (2021).
https:/​/​doi.org/​10.1038/​s41467-021-25196-0

[9] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2010).
https:/​/​doi.org/​10.1017/​CBO9780511976667

[10] M. B. Hastings, D. Wecker, B. Bauer, and M. Troyer, arXiv preprint arXiv:1403.1539 (2014).
https:/​/​doi.org/​10.48550/​arXiv.1403.1539
arXiv:1403.1539

[11] R. Babbush, N. Wiebe, J. McClean, J. McClain, H. Neven, and G. K.-L. Chan, Phys. Rev. X 8, 011044 (2018).
https:/​/​doi.org/​10.1103/​PhysRevX.8.011044

[12] I. D. Kivlichan, J. McClean, N. Wiebe, C. Gidney, A. Aspuru-Guzik, G. K.-L. Chan, and R. Babbush, Phys. Rev. Lett. 120, 110501 (2018).
https:/​/​doi.org/​10.1103/​PhysRevLett.120.110501

[13] C. Cade, L. Mineh, A. Montanaro, and S. Stanisic, Phys. Rev. B 102, 235122 (2020).
https:/​/​doi.org/​10.1103/​PhysRevB.102.235122

[14] S. B. Bravyi and A. Y. Kitaev, Ann. of Phys. 298, 210 (2002).
https:/​/​doi.org/​10.1006/​aphy.2002.6254

[15] F. Verstraete and J. I. Cirac, J. Stat. Mech. 2005, P09012 (2005).
https:/​/​doi.org/​10.1088/​1742-5468/​2005/​09/​p09012

[16] J. D. Whitfield, V. Havlíček, and M. Troyer, Phys. Rev. A 94, 030301 (2016).
https:/​/​doi.org/​10.1103/​PhysRevA.94.030301

[17] M. Steudtner and S. Wehner, New J. Phys. 20, 063010 (2018a).
https:/​/​doi.org/​10.1088/​1367-2630/​aac54f

[18] M. Steudtner and S. Wehner, Phys. Rev. A 99, 022308 (2019).
https:/​/​doi.org/​10.1103/​PhysRevA.99.022308

[19] K. Setia, S. Bravyi, A. Mezzacapo, and J. D. Whitfield, Phys. Rev. 1, 033033 (2019).
https:/​/​doi.org/​10.1103/​PhysRevResearch.1.033033

[20] Z. Jiang, J. McClean, R. Babbush, and H. Neven, Phys. Rev. Applied 12, 064041 (2019).
https:/​/​doi.org/​10.1103/​PhysRevApplied.12.064041

[21] Y.-A. Chen, Phys. Rev. 2, 033527 (2020).
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.033527

[22] R. W. Chien and J. D. Whitfield, arXiv preprint arXiv:2009.11860 (2020).
https:/​/​doi.org/​10.48550/​arXiv.2009.11860
arXiv:2009.11860

[23] C. Derby, J. Klassen, J. Bausch, and T. Cubitt, Phys. Rev. B 104, 035118 (2021).
https:/​/​doi.org/​10.1103/​PhysRevB.104.035118

[24] W. Kirby, B. Fuller, C. Hadfield, and A. Mezzacapo, PRX Quantum 3, 020351 (2022).
https:/​/​doi.org/​10.1103/​PRXQuantum.3.020351

[25] M. Chiew and S. Strelchuk, arXiv preprint arXiv:2110.12792 (2021).
arXiv:2110.12792

[26] A. Tranter, S. Sofia, J. Seeley, M. Kaicher, J. McClean, R. Babbush, P. V. Coveney, F. Mintert, F. Wilhelm, and P. J. Love, Int. J. Quantum Chem. 115, 1431 (2015).
https:/​/​doi.org/​10.1002/​qua.24969

[27] A. Tranter, P. J. Love, F. Mintert, and P. V. Coveney, J. Chem. Theory Comput. 14, 5617 (2018).
https:/​/​doi.org/​10.1021/​acs.jctc.8b00450

[28] M. Steudtner and S. Wehner, New J. Phys. 20, 063010 (2018b).
https:/​/​doi.org/​10.1088/​1367-2630/​aac54f

[29] M. Suzuki, J. of Math. Phys. 32, 400 (1991).
https:/​/​doi.org/​10.1063/​1.529425

[30] N. Wiebe, D. Berry, P. Hoyer, and B. C. Sanders, J. Phys. A 43, 065203 (2010).
https:/​/​doi.org/​10.1088/​1751-8113/​43/​6/​065203

[31] A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, Phys. Rev. X 11, 011020 (2021).
https:/​/​doi.org/​10.1103/​PhysRevX.11.011020

[32] A. M. Childs and N. Wiebe, arXiv preprint arXiv:1202.5822 (2012).
https:/​/​doi.org/​10.26421/​QIC12.11-12
arXiv:1202.5822

[33] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Phys. Rev. Lett. 114, 090502 (2015).
https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502

[34] G. H. Low and I. L. Chuang, Phys. Rev. Lett. 118, 010501 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.118.010501

[35] G. H. Low and I. L. Chuang, Quantum 3, 163 (2019).
https:/​/​doi.org/​10.22331/​q-2019-07-12-163

[36] S. Chakraborty, A. Gilyén, and S. Jeffery, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) Leibniz International Proceedings in Informatics (LIPIcs), 132, 33:1 (2019).
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.33

[37] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019) pp. 193–204.
https:/​/​doi.org/​10.1145/​3313276.3316366

[38] A. Kalev and I. Hen, Quantum 5, 426 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-08-426

[39] A. Rajput, A. Roggero, and N. Wiebe, arXiv preprint arXiv:2109.03308 (2021).
https:/​/​doi.org/​10.48550/​arXiv.2109.03308
arXiv:2109.03308

[40] J. Bringewatt and Z. Davoudi, https:/​/​github.com/​jbringewatt/​graph-coloring-fermion-parallelization.
https:/​/​github.com/​jbringewatt/​graph-coloring-fermion-parallelization

[41] Z. Jiang, A. Kalev, W. Mruczkiewicz, and H. Neven, Quantum 4, 276 (2020).
https:/​/​doi.org/​10.22331/​q-2020-06-04-276

[42] A. Y. Vlasov, Quanta 11, 97 (2022).
https:/​/​doi.org/​10.12743/​quanta.v11i1.199

[43] R. C. Ball, Phys. Rev. Lett. 95, 176407 (2005).
https:/​/​doi.org/​10.1103/​PhysRevLett.95.176407

[44] C. Derby and J. Klassen, arXiv preprint arXiv:2101.10735 (2021).
https:/​/​doi.org/​10.48550/​arXiv.2101.10735
arXiv:2101.10735

[45] A. Y. Kitaev, Ann. Phys. 303, 2 (2003).
https:/​/​doi.org/​10.1016/​S0003-4916(02)00018-0

[46] Y.-A. Chen, A. Kapustin, and Đorđe Radičević, Ann. Phys. 393, 234 (2018).
https:/​/​doi.org/​10.1016/​j.aop.2018.03.024

[47] J. R. Stryker, Phys. Rev. A 99, 042301 (2019).
https:/​/​doi.org/​10.1103/​PhysRevA.99.042301

[48] M. C. Tran, Y. Su, D. Carney, and J. M. Taylor, PRX Quantum 2, 010323 (2021).
https:/​/​doi.org/​10.1103/​PRXQuantum.2.010323

[49] H. Lamm, S. Lawrence, and Y. Yamauchi, arXiv preprint arXiv:2005.12688 (2020).
https:/​/​doi.org/​10.48550/​arXiv.2005.12688
arXiv:2005.12688

[50] J. C. Halimeh, H. Lang, J. Mildenberger, Z. Jiang, and P. Hauke, PRX Quantum 2, 040311 (2021).
https:/​/​doi.org/​10.1103/​PRXQuantum.2.040311

[51] M. Van Damme, J. Mildenberger, F. Grusdt, P. Hauke, and J. C. Halimeh, arXiv preprint arXiv:2110.08041 (2021).
https:/​/​doi.org/​10.48550/​arXiv.2110.08041
arXiv:2110.08041

[52] K. Stannigel, P. Hauke, D. Marcos, M. Hafezi, S. Diehl, M. Dalmonte, and P. Zoller, Phys. Rev. Lett. 112, 120406 (2014).
https:/​/​doi.org/​10.1103/​PhysRevLett.112.120406

[53] V. Kasper, T. V. Zache, F. Jendrzejewski, M. Lewenstein, and E. Zohar, arXiv preprint arXiv:2012.08620 (2020).
https:/​/​doi.org/​10.48550/​arXiv.2012.08620
arXiv:2012.08620

[54] N. H. Nguyen, M. C. Tran, Y. Zhu, A. M. Green, C. H. Alderete, Z. Davoudi, and N. M. Linke, arXiv preprint arXiv:2112.14262 (2021).
https:/​/​doi.org/​10.1103/​PRXQuantum.3.020324
arXiv:2112.14262

[55] K. Setia and J. D. Whitfield, J. Chem. Phys. 148, 164104 (2018).
https:/​/​doi.org/​10.1063/​1.5019371

[56] A. M. Childs, A. Ostrander, and Y. Su, Quantum 3, 182 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-182

[57] A. Tranter, P. J. Love, F. Mintert, N. Wiebe, and P. V. Coveney, Entropy 21, 10.3390/​e21121218 (2019).
https:/​/​doi.org/​10.3390/​e21121218

[58] T. Erlebach and K. Jansen, Theoretical Computer Science 255, 33 (2001).
https:/​/​doi.org/​10.1016/​S0304-3975(99)00152-8

[59] R. M. Karp, in Complexity of computer computations (Springer, Boston, MA, 1972) pp. 85–103.
https:/​/​doi.org/​10.1007/​978-1-4684-2001-2_9

[60] R. L. Brooks, in Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 37 (Cambridge University Press, 1941) pp. 194–197.
https:/​/​doi.org/​10.1017/​S030500410002168X

[61] S. Sachdev and J. Ye, Phys. Rev. Lett. 70, 3339 (1993).
https:/​/​doi.org/​10.1103/​PhysRevLett.70.3339

[62] V. Rosenhaus, J. Phys. A 52, 323001 (2019).
https:/​/​doi.org/​10.1088/​1751-8121/​ab2ce1

[63] A. Soifer, The mathematical coloring book: Mathematics of coloring and the colorful life of its creators (Springer, 2009).
https:/​/​doi.org/​10.1007/​978-0-387-74642-5

[64] D. Bryant, London Mathematical Society Lecture Note Series 346, 67 (2007).

[65] B. Alspach, Bull. Inst. Combin. Appl 52, 7 (2008).

[66] K. Mehlhorn, P. Sanders, and P. Sanders, Algorithms and data structures: The basic toolbox, Vol. 55 (Springer, 2008).
https:/​/​doi.org/​10.1007/​978-3-540-77978-0

[67] D. J. A. Welsh and M. B. Powell, Comput. J. 10, 85 (1967).
https:/​/​doi.org/​10.1093/​comjnl/​10.1.85

[68] T. Husfeldt, in Topics in Chromatic Graph Theory (Cambridge University Press, 2015) pp. 277–303.
https:/​/​doi.org/​10.1017/​CBO9781139519793

[69] A. Brandstädt, V. B. Le, and J. P. Spinrad, Graph classes: a survey (SIAM, 1999).
https:/​/​doi.org/​10.1137/​1.9780898719796

[70] IBM, https:/​/​research.ibm.com/​blog/​heavy-hex-lattice.
https:/​/​research.ibm.com/​blog/​heavy-hex-lattice

[71] C. Chamberland, G. Zhu, T. J. Yoder, J. B. Hertzberg, and A. W. Cross, Phys. Rev. X 10, 011022 (2020).
https:/​/​doi.org/​10.1103/​PhysRevX.10.011022

[72] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al., Nature 574, 505 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[73] R. Machleidt and D. R. Entem, Physics Reports 503, 1 (2011).
https:/​/​doi.org/​10.1016/​j.physrep.2011.02.001

[74] T. Byrnes and Y. Yamamoto, Phys. Rev. A 73, 022328 (2006).
https:/​/​doi.org/​10.1103/​PhysRevA.73.022328

[75] H. Lamm, S. Lawrence, Y. Yamauchi, N. Collaboration, et al., Phys. Rev. D 100, 034518 (2019).
https:/​/​doi.org/​10.1103/​PhysRevD.100.034518

[76] A. F. Shaw, P. Lougovski, J. R. Stryker, and N. Wiebe, Quantum 4, 306 (2020).
https:/​/​doi.org/​10.22331/​q-2020-08-10-306

[77] D. Paulson, L. Dellantonio, J. F. Haase, A. Celi, A. Kan, A. Jena, C. Kokail, R. Van Bijnen, K. Jansen, P. Zoller, et al., PRX Quantum 2, 030334 (2021).
https:/​/​doi.org/​10.1103/​PRXQuantum.2.030334

[78] A. Ciavarella, N. Klco, and M. J. Savage, Phys. Rev. D 103, 094501 (2021).
https:/​/​doi.org/​10.1103/​PhysRevD.103.094501

[79] A. Kan and Y. Nam, arXiv preprint arXiv:2107.12769 (2021).
https:/​/​doi.org/​10.48550/​arXiv.2107.12769
arXiv:2107.12769

[80] C. Hamer, Z. Weihong, and J. Oitmaa, Phys. Rev. D 56, 55 (1997).
https:/​/​doi.org/​10.1103/​PhysRevD.56.55

[81] E. Zohar and J. I. Cirac, Phys. Rev. D 99, 114511 (2019).
https:/​/​doi.org/​10.1103/​PhysRevD.99.114511

[82] Z. Davoudi, I. Raychowdhury, and A. Shaw, Phys. Rev. D 104, 074505 (2021).
https:/​/​doi.org/​10.1103/​PhysRevD.104.074505

[83] N. Klco and M. J. Savage, Phys. Rev. D 103, 065007 (2021).
https:/​/​doi.org/​10.1103/​PhysRevD.103.065007

Cited by

[1] Roland C. Farrell, Ivan A. Chernyshev, Sarah J. M. Powell, Nikita A. Zemlevskiy, Marc Illa, and Martin J. Savage, "Preparations for quantum simulations of quantum chromodynamics in 1 +1 dimensions. II. Single-baryon β -decay in real time", Physical Review D 107 5, 054513 (2023).

[2] Anthony N. Ciavarella, Stephan Caspar, Marc Illa, and Martin J. Savage, "State Preparation in the Heisenberg Model through Adiabatic Spiraling", Quantum 7, 970 (2023).

[3] João Barata, Xiaojian Du, Meijian Li, Wenyang Qian, and Carlos A. Salgado, "Medium induced jet broadening in a quantum computer", Physical Review D 106 7, 074013 (2022).

[4] Anthony N. Ciavarella, Stephan Caspar, Hersh Singh, and Martin J. Savage, "Preparation for quantum simulation of the (1 +1 ) -dimensional O(3) nonlinear σ model using cold atoms", Physical Review A 107 4, 042404 (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-06-09 07:59:00). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-06-09 07:58:58).