Exponentially faster implementations of Select(H) for fermionic Hamiltonians

Kianna Wan

Stanford Institute for Theoretical Physics, Stanford University, Stanford, CA 94305, USA
PsiQuantum, Palo Alto, CA 94304, USA

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


We present a simple but general framework for constructing quantum circuits that implement the multiply-controlled unitary $\text{Select}(H) := \sum_\ell |\ell\rangle\langle\ell|\otimes H_\ell$, where $H = \sum_\ell H_\ell$ is the Jordan-Wigner transform of an arbitrary second-quantised fermionic Hamiltonian. $\text{Select}(H)$ is one of the main subroutines of several quantum algorithms, including state-of-the-art techniques for Hamiltonian simulation. If each term in the second-quantised Hamiltonian involves at most $k$ spin-orbitals and $k$ is a constant independent of the total number of spin-orbitals $n$ (as is the case for the majority of quantum chemistry and condensed matter models considered in the literature, for which $k$ is typically 2 or 4), our implementation of $\text{Select}(H)$ requires no ancilla qubits and uses $\mathcal{O}(n)$ Clifford+T gates, with the Clifford gates applied in $\mathcal{O}(log^2 n)$ layers and the $T$ gates in $O(log n)$ layers. This achieves an exponential improvement in both Clifford- and T-depth over previous work, while maintaining linear gate count and reducing the number of ancillae to zero.

► BibTeX data

► References

[1] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan. Quantum computational chemistry. Reviews of Modern Physics, 92 (1), 2020. 10.1103/​RevModPhys.92.015003.

[2] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik. Quantum chemistry in the age of quantum computing. Chemical Reviews, 119 (19): 10856–10915, 2019. 10.1021/​acs.chemrev.8b00803.

[3] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. Quantum algorithms for quantum chemistry and quantum materials science. Chemical Reviews, 120 (22): 12685–12717, 2020. 10.1021/​acs.chemrev.9b00829.

[4] Daniel S. Abrams and Seth Lloyd. Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors. Physical Review Letters, 83 (24): 5162–5165, 1999. 10.1103/​PhysRevLett.83.5162.

[5] A. Yu. Kitaev. Quantum measurements and the abelian stabilizer problem, 1995. URL https:/​/​arxiv.org/​abs/​quant-ph/​9511026.

[6] R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454 (1969): 339–354, 1998. 10.1098/​rspa.1998.0164.

[7] R. D. Somma, S. Boixo, H. Barnum, and E. Knill. Quantum simulations of classical annealing processes. Physical Review Letters, 101 (13), 2008. 10.1103/​PhysRevLett.101.130504.

[8] David Poulin, Alexei Kitaev, Damian S. Steiger, Matthew B. Hastings, and Matthias Troyer. Quantum algorithm for spectral measurement with a lower gate count. Physical Review Letters, 121 (1), 2018. 10.1103/​PhysRevLett.121.010501.

[9] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution, 2000. URL https:/​/​arxiv.org/​abs/​quant-ph/​0001106.

[10] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge, 2003. URL https:/​/​arxiv.org/​abs/​quant-ph/​0301023.

[11] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters, 118 (1), 2017. 10.1103/​PhysRevLett.118.010501.

[12] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum, 3: 163. 10.22331/​q-2019-07-12-163.

[13] Dominic W. Berry, Mária Kieferová, Artur Scherer, Yuval R. Sanders, Guang Hao Low, Nathan Wiebe, Craig Gidney, and Ryan Babbush. Improved techniques for preparing eigenstates of fermionic Hamiltonians. npj Quantum Information, 4 (1). 10.1038/​s41534-018-0071-5.

[14] Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear ${T}$ complexity. Physical Review X, 8 (4). 10.1103/​PhysRevX.8.041015.

[15] Guang Hao Low and Nathan Wiebe. Hamiltonian simulation in the interaction picture, 2018. URL https:/​/​arxiv.org/​abs/​1805.00675.

[16] Mária Kieferová, Artur Scherer, and Dominic W. Berry. Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series. Physical Review A, 99 (4), 2019. 10.1103/​PhysRevA.99.042314.

[17] Kianna Wan and Isaac Kim. Fast digital methods for adiabatic state preparation, 2020. URL https:/​/​arxiv.org/​abs/​2004.04164.

[18] Matthew B. Hastings. Lieb-Schultz-Mattis in higher dimensions. Phys. Rev. B, 69: 104431, 2004. 10.1103/​PhysRevB.69.104431.

[19] Yimin Ge, Jordi Tura, and J. Ignacio Cirac. Faster ground state preparation and high-precision ground energy estimation with fewer qubits. Journal of Mathematical Physics, 60 (2): 022202, 2019. 10.1063/​1.5027484.

[20] Lin Lin and Yu Tong. Near-optimal ground state preparation, 2020. URL https:/​/​arxiv.org/​abs/​2002.12508.

[21] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation, 12 (11-12), 2012. 10.26421/​qic12.11-12.

[22] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters, 114 (9), 2015. 10.1103/​PhysRevLett.114.090502.

[23] P. Jordan and E. Wigner. Über das Paulische Äquivalenzverbot. Zeitschrift für Physik, 47 (9-10): 631–651, 1928. 10.1007/​bf01331938.

[24] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences, 115 (38): 9456–9461, 2018. 10.1073/​pnas.1801723115.

[25] Vojtěch Havlíček, Matthias Troyer, and James D. Whitfield. Operator locality in the quantum simulation of fermionic models. Physical Review A, 95 (3), 2017. 10.1103/​PhysRevA.95.032332.

[26] Sergey B. Bravyi and Alexei Yu. Kitaev. Fermionic quantum computation. Annals of Physics, 298 (1): 210–226, 2002. 10.1006/​aphy.2002.6254.

[27] 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 (22): 224109, 2012. 10.1063/​1.4768229.

[28] Andrew Tranter, Sarah Sofia, Jake Seeley, Michael Kaicher, Jarrod McClean, Ryan Babbush, Peter V. Coveney, Florian Mintert, Frank Wilhelm, and Peter J. Love. The Bravyi-Kitaev transformation: Properties and applications. International Journal of Quantum Chemistry, 115 (19): 1431–1441, 2015. 10.1002/​qua.24969.

[29] Dan Stefan Eniceicu and Kianna Wan, unpublished.

[30] Ryan Babbush, Dominic W. Berry, and Hartmut Neven. Quantum simulation of the Sachdev-Ye-Kitaev model by asymmetric qubitization. Physical Review A, 99 (4), 2019. 10.1103/​PhysRevA.99.040301.

[31] Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. Trading T-gates for dirty qubits in state preparation and unitary synthesis, 2018. URL https:/​/​arxiv.org/​abs/​1812.00954.

[32] Austin G. Fowler and Simon J. Devitt. A bridge to lower overhead quantum computation, 2012. URL https:/​/​arxiv.org/​abs/​1209.0510.

[33] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical Review A, 52 (5): 3457–3467, 1995. 10.1103/​PhysRevA.52.3457.

[34] Attila Szabo and Neil S. Ostlund. Modern Quantum Chemistry: Introduction to Advanced Electronic Structure Theory. Dover Publications, Inc., Mineola, 1996.

[35] Trygve Helgaker, Poul Jørgensen, and Jeppe Olsen. Molecular Electronic-Structure Theory. John Wiley & Sons, Ltd, 2000. 10.1002/​9781119019572.

[36] Craig Gidney, personal communication.

Cited by

[1] Isaac H. Kim, Ye-Hua Liu, Sam Pallister, William Pol, Sam Roberts, and Eunseok Lee, "Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules", Physical Review Research 4 2, 023019 (2022).

[2] Trevor Keen, Bo Peng, Karol Kowalski, Pavel Lougovski, and Steven Johnston, "Hybrid quantum-classical approach for coupled-cluster Green's function theory", Quantum 6, 675 (2022).

[3] Luogen Xu and James K. Freericks, "Efficient Application of the Factorized form of the Unitary Coupled-Cluster Ansatz for the Variational Quantum Eigensolver Algorithm by Using Linear Combination of Unitaries", Symmetry 15 7, 1429 (2023).

[4] John S. Van Dyke, George S. Barron, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou, "Preparing Bethe Ansatz Eigenstates on a Quantum Computer", PRX Quantum 2 4, 040329 (2021).

[5] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[6] Andrew J. Landahl and Benjamin C. A. Morrison, "Logical fermions for fault-tolerant quantum simulation", arXiv:2110.10280, (2021).

[7] Gregory Boyd, "Low-Overhead Parallelisation of LCU via Commuting Operators", arXiv:2312.00696, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-12 14:56:56) and SAO/NASA ADS (last updated successfully 2024-04-12 14:56:56). The list may be incomplete as not all publishers provide suitable and complete citation data.