Exponentially faster implementations of Select(H) for fermionic Hamiltonians

Abstract

We present a simple but general framework for constructing quantum circuits that implement the multiply-controlled unitary $\text{Select}(H)\equiv {\sum }_{\ell }|\ell ⟩⟨\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.

arXiv comment15 pages; added some comments, including about other fermion-to-qubit mappings

References in corpus (27)

• Elementary gates for quantum computation
• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• Quantum Algorithms Revisited
• Fermionic quantum computation
• Hamiltonian Simulation by Qubitization
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Quantum algorithms for quantum chemistry and quantum materials science
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Lieb-Schultz-Mattis in Higher Dimensions
• Toward the first quantum simulation with quantum speedup
• The Bravyi-Kitaev transformation for quantum computation of electronic structure
• Quantum Computation by Adiabatic Evolution
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Quantum Simulations of Classical Annealing Processes
• Near-optimal ground state preparation
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Operator Locality in Quantum Simulation of Fermionic Models
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series
• A bridge to lower overhead quantum computation
• Hamiltonian Simulation in the Interaction Picture
• Fast digital methods for adiabatic state preparation

Cited by in corpus (6)

• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• Preparing Bethe Ansatz Eigenstates on a Quantum Computer
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• Systematic many-fermion Hamiltonian input scheme and spectral calculations on quantum computers
• Efficient application of the factorized form of the unitary coupled-cluster ansatz for the variational quantum eigensolver algorithm by using linear combination of unitaries