DAMTP, Centre for Mathematical Sciences, University of Cambridge, Cambridge CB30WA, UK
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Simulating fermionic systems on a quantum computer requires a high-performing mapping of fermionic states to qubits. A characteristic of an efficient mapping is its ability to translate local fermionic interactions into local qubit interactions, leading to easy-to-simulate qubit Hamiltonians.
$All$ fermion-qubit mappings must use a numbering scheme for the fermionic modes in order for translation to qubit operations. We make a distinction between the unordered labelling of fermions and the ordered labelling of the qubits. This separation shines light on a new way to design fermion-qubit mappings by making use of the enumeration scheme for the fermionic modes. The purpose of this paper is to demonstrate that this concept permits notions of fermion-qubit mappings that are $optimal$ with regard to any cost function one might choose. Our main example is the minimisation of the average number of Pauli matrices in the Jordan-Wigner transformations of Hamiltonians for fermions interacting in square lattice arrangements. In choosing the best ordering of fermionic modes for the Jordan-Wigner transformation, and unlike other popular modifications, our prescription does not cost additional resources such as ancilla qubits.
We demonstrate how Mitchison and Durbin’s enumeration pattern minimises the average Pauli weight of Jordan-Wigner transformations of systems interacting in square lattices. This leads to qubit Hamiltonians consisting of terms with average Pauli weights 13.9% shorter than previously known. By adding only two ancilla qubits we introduce a new class of fermion-qubit mappings, and reduce the average Pauli weight of Hamiltonian terms by 37.9% compared to previous methods. For $n$-mode fermionic systems in cellular arrangements, we find enumeration patterns which result in $n^{1/4}$ improvement in average Pauli weight over naïve schemes.
Featured image: The Jordan–Wigner transformation produces qubit Hamiltonians that depend on the choice of fermionic enumeration. If the fermionic Hamiltonian contains hopping terms that form a square lattice, the Mitchison–Durbin pattern (right) produces qubit Hamiltonians with hopping terms of the minimum possible average weight.
Popular summary
The emerging quantum computers open new avenues for simulating fermionic systems achieving scales that previously were intractable to their classical counterparts. Currently, the task of simulating fermionic systems on a quantum computer requires large overheads due to the inherent non-local nature of interactions. Numerous efforts to reduce the simulation complexity on a quantum device established a tradeoff: they reduce the complexity of simulation at a cost of expending valuable quantum resources such as qubits that scale proportionally to the system size.
We introduce a novel way to reduce the complexity of the simulation by exploiting a new degree of freedom – the way to enumerate fermions. The savings come free-of-charge and only require one to generate a fermion labelling scheme. We provide an optimal scheme for the most common two-dimensional layout – the rectangular lattice. Our method allows for much stronger, polynomial reductions of the overhead for natural classes of practical systems.
► BibTeX data
► References
[1] Dave Wecker, Matthew B Hastings, Nathan Wiebe, Bryan K Clark, Chetan Nayak, and Matthias Troyer. “Solving strongly correlated electron models on a quantum computer”. Physical Review A 92, 062318 (2015).
https://doi.org/10.1103/PhysRevA.92.062318
[2] Giacomo Mauro D’Ariano, Franco Manessi, Paolo Perinotti, and Alessandro Tosini. “The feynman problem and fermionic entanglement: Fermionic theory versus qubit theory”. International Journal of Modern Physics A 29, 1430025 (2014).
https://doi.org/10.1142/S0217751X14300257
[3] Nicolai Friis, Antony R Lee, and David Edward Bruschi. “Fermionic-mode entanglement in quantum information”. Physical Review A 87, 022338 (2013).
https://doi.org/10.1103/PhysRevA.87.022338
[4] Panagiotis Kl Barkoutsos, Nikolaj Moll, Peter WJ Staar, Peter Mueller, Andreas Fuhrer, Stefan Filipp, Matthias Troyer, and Ivano Tavernelli. “Fermionic hamiltonians for quantum simulations: a general reduction scheme” (2017). arXiv:1706.03637.
arXiv:1706.03637
[5] Benjamin P Lanyon, James D Whitfield, Geoff G Gillett, Michael E Goggin, Marcelo P Almeida, Ivan Kassal, Jacob D Biamonte, Masoud Mohseni, Ben J Powell, Marco Barbieri, et al. “Towards quantum chemistry on a quantum computer”. Nature chemistry 2, 106–111 (2010).
https://doi.org/10.1038/nchem.483
[6] Manfred Salmhofer. “Renormalization in condensed matter: Fermionic systems–from mathematics to materials”. Nuclear Physics B 941, 868–899 (2019).
https://doi.org/10.1016/j.nuclphysb.2018.07.004
[7] Christina Verena Kraus. “A quantum information perspective of fermionic quantum many-body systems”. PhD thesis. Technische Universität München. (2009).
[8] Ali Hamed Moosavian and Stephen Jordan. “Faster quantum algorithm to simulate fermionic quantum field theory”. Physical Review A 98, 012332 (2018).
https://doi.org/10.1103/PhysRevA.98.012332
[9] Joshua J. Goings, Alec White, Joonho Lee, Christofer S. Tautermann, Matthias Degroote, Craig Gidney, Toru Shiozaki, Ryan Babbush, and Nicholas C. Rubin. “Reliably assessing the electronic structure of cytochrome p450 on today’s classical computers and tomorrow’s quantum computers”. Proceedings of the National Academy of Sciences 119, e2203533119 (2022). arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.2203533119.
https://doi.org/10.1073/pnas.2203533119
arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.2203533119
[10] Kaoru Hagiwara, K Hikasa, Kenzo Nakamura, M Tanabashi, M Aguilar-Benitez, C Amsler, RMichael Barnett, PR Burchat, CD Carone, C Caso, et al. “Review of particle physics”. Physical Review D (Particles and Fields) 66 (2002).
https://doi.org/10.1103/PhysRevD.98.030001
[11] Matthew B. Hastings and Ryan O’Donnell. “Optimizing strongly interacting fermionic hamiltonians”. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Page 776–789. STOC 2022New York, NY, USA (2022). Association for Computing Machinery.
https://doi.org/10.1145/3519935.3519960
[12] Alán Aspuru-Guzik, Anthony D Dutoi, Peter J Love, and Martin Head-Gordon. “Simulated quantum computation of molecular energies”. Science 309, 1704–1707 (2005).
https://doi.org/10.1126/science.1113479
[13] Hefeng Wang, Sabre Kais, Alán Aspuru-Guzik, and Mark R Hoffmann. “Quantum algorithm for obtaining the energy spectrum of molecular systems”. Physical Chemistry Chemical Physics 10, 5388–5393 (2008).
https://doi.org/10.1039/b804804e
[14] Ivan Kassal and Alán Aspuru-Guzik. “Quantum algorithm for molecular properties and geometry optimization”. The Journal of chemical physics 131, 224102 (2009).
https://doi.org/10.1063/1.3266959
[15] Ivan Kassal, Stephen P Jordan, Peter J Love, Masoud Mohseni, and Alán Aspuru-Guzik. “Polynomial-time quantum algorithm for the simulation of chemical dynamics”. Proceedings of the National Academy of Sciences 105, 18681–18686 (2008).
https://doi.org/10.1073/pnas.0808245105
[16] Jarrod R McClean, Ryan Babbush, Peter J Love, and Alán Aspuru-Guzik. “Exploiting locality in quantum computation for quantum chemistry”. The journal of physical chemistry letters 5, 4368–4380 (2014).
https://doi.org/10.1021/jz501649m
[17] Frank Verstraete and J Ignacio Cirac. “Mapping local hamiltonians of fermions to local Hamiltonians of spins”. Journal of Statistical Mechanics: Theory and Experiment 2005, P09012 (2005).
https://doi.org/10.1088/1742-5468/2005/09/P09012
[18] Ivan Kassal, James D Whitfield, Alejandro Perdomo-Ortiz, Man-Hong Yung, and Alán Aspuru-Guzik. “Simulating chemistry using quantum computers”. Annual review of physical chemistry 62, 185–207 (2011).
https://doi.org/10.1146/annurev-physchem-032210-103512
[19] Julia Kempe, Alexei Kitaev, and Oded Regev. “The complexity of the local Hamiltonian problem”. Siam journal on computing 35, 1070–1097 (2006).
https://doi.org/10.1137/S0097539704445226
[20] Ryan Babbush, Peter J Love, and Alán Aspuru-Guzik. “Adiabatic quantum simulation of quantum chemistry”. Scientific reports 4, 1–11 (2014).
https://doi.org/10.1038/srep06603
[21] Gerardo Ortiz, James E Gubernatis, Emanuel Knill, and Raymond Laflamme. “Quantum algorithms for fermionic simulations”. Physical Review A 64, 022319 (2001).
https://doi.org/10.1103/PhysRevA.64.022319
[22] Alexei Y. Kitaev. “Quantum measurements and the abelian stabilizer problem”. Electron. Colloquium Comput. Complex. TR96 (1995). url: https://api.semanticscholar.org/CorpusID:17023060.
https://api.semanticscholar.org/CorpusID:17023060
[23] Daniel S Abrams and Seth Lloyd. “Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors”. Physical Review Letters 83, 5162 (1999).
https://doi.org/10.1103/PhysRevLett.83.5162
[24] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. “A variational eigenvalue solver on a photonic quantum processor”. Nature communications 5, 1–7 (2014).
https://doi.org/10.1038/ncomms5213
[25] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. “The theory of variational hybrid quantum-classical algorithms”. New Journal of Physics 18, 023023 (2016).
https://doi.org/10.1088/1367-2630/18/2/023023
[26] Matthew B Hastings, Dave Wecker, Bela Bauer, and Matthias Troyer. “Improving quantum algorithms for quantum chemistry”. Quantum Information & Computation 15, 1–21 (2015).
https://doi.org/10.26421/QIC15.1-2-1
[27] Pascual Jordan and Eugene Paul Wigner. “Über das Paulische Äquivalenzverbot”. Zeitschrift fur Physik 47, 631–651 (1928).
https://doi.org/10.1007/BF01331938
[28] Elliott Lieb, Theodore Schultz, and Daniel Mattis. “Two soluble models of an antiferromagnetic chain”. Annals of Physics 16, 407–466 (1961).
https://doi.org/10.1016/0003-4916(61)90115-4
[29] Rami Barends, L Lamata, Julian Kelly, L García-Álvarez, Austin G Fowler, A Megrant, Evan Jeffrey, Ted C White, Daniel Sank, Josh Y Mutus, et al. “Digital quantum simulation of fermionic models with a superconducting circuit”. Nature communications 6, 1–7 (2015).
https://doi.org/10.1038/ncomms8654
[30] Yu-An Chen, Anton Kapustin, and Đorđe Radičević. “Exact bosonization in two spatial dimensions and a new class of lattice gauge theories”. Annals of Physics 393, 234–253 (2018).
https://doi.org/10.1016/j.aop.2018.03.024
[31] Yu-An Chen and Anton Kapustin. “Bosonization in three spatial dimensions and a 2-form gauge theory”. Physical Review B 100, 245127 (2019).
https://doi.org/10.1103/PhysRevB.100.245127
[32] Yu-An Chen. “Exact bosonization in arbitrary dimensions”. Physical Review Research 2, 033527 (2020).
https://doi.org/10.1103/PhysRevResearch.2.033527
[33] Yu-An Chen, Yijia Xu, et al. “Equivalence between fermion-to-qubit mappings in two spatial dimensions”. PRX Quantum 4, 010326 (2023).
https://doi.org/10.1103/PRXQuantum.4.010326
[34] Kanav Setia, Sergey Bravyi, Antonio Mezzacapo, and James D Whitfield. “Superfast encodings for fermionic quantum simulation”. Physical Review Research 1, 033033 (2019).
https://doi.org/10.1021/acs.jctc.2c01119
[35] Zhang Jiang, Jarrod McClean, Ryan Babbush, and Hartmut Neven. “Majorana loop stabilizer codes for error mitigation in fermionic quantum simulations”. Physical Review Applied 12, 064041 (2019).
https://doi.org/10.1103/PhysRevApplied.12.064041
[36] Charles Derby and Joel Klassen. “Low weight fermionic encodings for lattice models” (2020). arXiv:2003.06939.
https://doi.org/10.1103/PhysRevB.104.035118
arXiv:2003.06939
[37] Mark Steudtner and Stephanie Wehner. “Quantum codes for quantum simulation of fermions on a square lattice of qubits”. Physical Review A 99, 022308 (2019).
https://doi.org/10.1103/PhysRevA.99.022308
[38] Zhang Jiang, Amir Kalev, Wojciech Mruczkiewicz, and Hartmut Neven. “Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning”. Quantum 4, 276 (2020).
https://doi.org/10.22331/q-2020-06-04-276
[39] Sergey B Bravyi and Alexei Y Kitaev. “Fermionic quantum computation”. Annals of Physics 298, 210–226 (2002).
https://doi.org/10.1006/aphy.2002.6254
[40] Graeme Mitchison and Richard Durbin. “Optimal numberings of an $N$$times$$N$ array”. SIAM Journal on Algebraic Discrete Methods 7, 571–582 (1986).
https://doi.org/10.1137/0607063
[41] Michael R Garey, David S Johnson, and Larry Stockmeyer. “Some simplified NP-complete problems”. In Proceedings of the sixth annual ACM symposium on Theory of computing. Pages 47–63. (1974).
https://doi.org/10.1145/800119.803884
[42] Michael R Garey, Ronald L Graham, David S Johnson, and Donald Ervin Knuth. “Complexity results for bandwidth minimization”. SIAM Journal on Applied Mathematics 34, 477–495 (1978).
https://doi.org/10.1137/0134037
[43] Michael R Garey and David S Johnson. “Computers and intractability; a guide to the theory of np-completeness”. W. H. Freeman & Co. USA (1990).
https://doi.org/10.5555/578533
[44] John Hubbard and Brian Hilton Flowers. “Electron correlations in narrow energy bands”. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences 276, 238–257 (1963). arXiv:https://royalsocietypublishing.org/doi/pdf/10.1098/rspa.1963.0204.
https://doi.org/10.1098/rspa.1963.0204
arXiv:https://royalsocietypublishing.org/doi/pdf/10.1098/rspa.1963.0204
[45] Michael A. Nielsen. “The fermionic canonical commutation relations and the jordan-wigner transform”. url: https://futureofmatter.com/assets/fermions_and_jordan_wigner.pdf.
https://futureofmatter.com/assets/fermions_and_jordan_wigner.pdf
[46] Aaron Miller, Zoltán Zimborás, Stefan Knecht, Sabrina Maniscalco, and Guillermo García-Pérez. “Bonsai algorithm: Grow your own fermion-to-qubit mappings”. PRX Quantum 4, 030314 (2023).
https://doi.org/10.1103/PRXQuantum.4.030314
[47] Mitchell Chiew and Sergii Strelchuk. “To appear”.
[48] Andrew Tranter, Peter J Love, Florian Mintert, and Peter V Coveney. “A comparison of the bravyi–kitaev and jordan–wigner transformations for the quantum simulation of quantum chemistry”. Journal of chemical theory and computation 14, 5617–5630 (2018).
https://doi.org/10.1021/acs.jctc.8b00450
[49] Jacob T Seeley, Martin J Richard, and Peter J Love. “The Bravyi-Kitaev transformation for quantum computation of electronic structure”. The Journal of chemical physics 137, 224109 (2012).
https://doi.org/10.1063/1.4768229
[50] Tjalling C Koopmans and Martin Beckmann. “Assignment problems and the location of economic activities”. Econometrica: journal of the Econometric SocietyPages 53–76 (1957).
https://doi.org/10.2307/1907742
[51] Martin Juvan and Bojan Mohar. “Optimal linear labelings and eigenvalues of graphs”. Discrete Applied Mathematics 36, 153–168 (1992).
https://doi.org/10.1016/0166-218X(92)90229-4
[52] Alan George and Alex Pothen. “An analysis of spectral envelope reduction via quadratic assignment problems”. SIAM Journal on Matrix Analysis and Applications 18, 706–732 (1997). arXiv:https://doi.org/10.1137/S089547989427470X.
https://doi.org/10.1137/S089547989427470X
arXiv:https://doi.org/10.1137/S089547989427470X
[53] Steven Bradish Horton. “The optimal linear arrangement problem: algorithms and approximation”. PhD thesis. School of Industrial and Systems Engineering, Georgia Institute of Technology. (1997).
[54] Yung-Ling Lai and Kenneth Williams. “A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs”. Journal of graph theory 31, 75–94 (1999).
https://doi.org/10.1002/(sici)1097-0118(199906)31:23.0.co;2-s
[55] Greg N Frederickson and Susanne E Hambrusch. “Planar linear arrangements of outerplanar graphs”. IEEE transactions on Circuits and Systems 35, 323–333 (1988).
https://doi.org/10.1109/31.1745
[56] Fan-Rong King Chung. “On optimal linear arrangements of trees”. Computers & mathematics with applications 10, 43–60 (1984).
https://doi.org/10.1016/0898-1221(84)90085-3
[57] James B Saxe. “Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time”. SIAM Journal on Algebraic Discrete Methods 1, 363–369 (1980). arXiv:https://doi.org/10.1137/0601042.
https://doi.org/10.1137/0601042
arXiv:https://doi.org/10.1137/0601042
[58] Nikolaj Moll, Andreas Fuhrer, Peter Staar, and Ivano Tavernelli. “Optimizing qubit resources for quantum chemistry simulations in second quantization on a quantum computer”. Journal of Physics A: Mathematical and Theoretical 49, 295301 (2016).
https://doi.org/10.1088/1751-8113/49/29/295301
[59] James D Whitfield, Vojtěch Havlíček, and Matthias Troyer. “Local spin operators for fermion simulations”. Phys. Rev. A 94, 030301 (2016).
https://doi.org/10.1103/PhysRevA.94.030301
[60] Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. “On the Qubit Routing Problem”. In Wim van Dam and Laura Mancinska, editors, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Volume 135 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:32. Dagstuhl, Germany (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https://doi.org/10.4230/LIPIcs.TQC.2019.5
[61] Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, and Jialin Zhang. “Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis”. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Pages 213–229. SIAM (2020).
https://doi.org/10.48550/arXiv.1907.05087
Cited by
[1] Adrian Chapman, Samuel J. Elman, and Ryan L. Mann, “A Unified Graph-Theoretic Framework for Free-Fermion Solvability”, arXiv:2305.15625, (2023).
[2] Adrian Chapman, Steven T. Flammia, and Alicia J. Kollár, “Free-Fermion Subsystem Codes”, PRX Quantum 3 3, 030321 (2022).
[3] Campbell McLauchlan and Benjamin Béri, “A new twist on the Majorana surface code: Bosonic and fermionic defects for fault-tolerant quantum computation”, arXiv:2211.11777, (2022).
[4] Aaron Miller, Zoltán Zimborás, Stefan Knecht, Sabrina Maniscalco, and Guillermo García-Pérez, “Bonsai Algorithm: Grow Your Own Fermion-to-Qubit Mappings”, PRX Quantum 4 3, 030314 (2023).
[5] Jacob Bringewatt and Zohreh Davoudi, “Parallelization techniques for quantum simulation of fermionic systems”, Quantum 7, 975 (2023).
[6] Anton Nykänen, Matteo A. C. Rossi, Elsi-Mari Borrelli, Sabrina Maniscalco, and Guillermo García-Pérez, “Mitigating the measurement overhead of ADAPT-VQE with optimised informationally complete generalised measurements”, arXiv:2212.09719, (2022).
[7] Riley W. Chien and Joel Klassen, “Optimizing fermionic encodings for both Hamiltonian and hardware”, arXiv:2210.05652, (2022).
[8] Oliver O’Brien and Sergii Strelchuk, “Ultrafast Hybrid Fermion-to-Qubit mapping”, arXiv:2211.16389, (2022).
[9] Riley W. Chien, Kanav Setia, Xavier Bonet-Monroig, Mark Steudtner, and James D. Whitfield, “Simulating quantum error mitigation in fermionic encodings”, arXiv:2303.02270, (2023).
The above citations are from SAO/NASA ADS (last updated successfully 2023-10-18 12:44:36). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2023-10-18 12:44:33: Could not fetch cited-by data for 10.22331/q-2023-10-18-1145 from Crossref. This is normal if the DOI was registered recently.
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.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-10-18-1145/
