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.
 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).
 Nuclear Physics and Quantum Information Science: Report by the NSAC QIS Subcommittee, Tech. Rep. (NSF & DOE Office of Science, 2019).
 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).
 F. Verstraete and J. I. Cirac, J. Stat. Mech. 2005, P09012 (2005).
 K. Setia, S. Bravyi, A. Mezzacapo, and J. D. Whitfield, Phys. Rev. 1, 033033 (2019).
 Z. Jiang, J. McClean, R. Babbush, and H. Neven, Phys. Rev. Applied 12, 064041 (2019).
 Y.-A. Chen, Phys. Rev. 2, 033527 (2020).
 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).
 N. Wiebe, D. Berry, P. Hoyer, and B. C. Sanders, J. Phys. A 43, 065203 (2010).
 D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Phys. Rev. Lett. 114, 090502 (2015).
 G. H. Low and I. L. Chuang, Phys. Rev. Lett. 118, 010501 (2017).
 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).
 J. Bringewatt and Z. Davoudi, https://github.com/jbringewatt/graph-coloring-fermion-parallelization.
 K. Stannigel, P. Hauke, D. Marcos, M. Hafezi, S. Diehl, M. Dalmonte, and P. Zoller, Phys. Rev. Lett. 112, 120406 (2014).
 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).
 D. Bryant, London Mathematical Society Lecture Note Series 346, 67 (2007).
 B. Alspach, Bull. Inst. Combin. Appl 52, 7 (2008).
 IBM, https://research.ibm.com/blog/heavy-hex-lattice.
 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).
 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).
 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).
 Anthony N. Ciavarella, Stephan Caspar, Marc Illa, and Martin J. Savage, "State Preparation in the Heisenberg Model through Adiabatic Spiraling", Quantum 7, 970 (2023).
 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-12-06 23:18:18). 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-12-06 23:18:16).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.