Tensor hypercontraction block encoding for quantum chemistry

ALGORITHM: Tensor hypercontraction block encoding for quantum chemistry
PROBLEM: Represent the spectrum of a quantum chemistry Hamiltonian, given in an arbitrary (for example molecular) orbital basis, as a block-encoded quantum circuit cheap enough to support phase estimation of a molecular eigenvalue.
IDEA: Lee, Berry, Gidney, Huggins, McClean, Wiebe and Babbush describe quantum circuits that block encode the spectra of quantum chemistry Hamiltonians in a basis of N arbitrary, for example molecular, orbitals. Their key insight is to factorize the Hamiltonian by a method the authors call tensor hypercontraction (THC), transforming the Coulomb operator into an isospectral diagonal form defined by the THC factors in a non-orthogonal basis; they then use qubitization to simulate the resulting non-orthogonal THC Hamiltonian in a way that the authors say avoids most complications of that non-orthogonal basis. The authors state that repeating these block-encoding circuits, combined with phase estimation, lets one sample in the molecular eigenbasis. They report that their construction is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis, and that, up to logarithmic factors, it matches the scaling of the most efficient prior block encodings — ones that can work only with orthogonal basis functions diagonalizing the Coulomb operator, such as the plane wave dual basis. The authors also reanalyze and reduce the cost of several of the best prior algorithms for these simulations, to give what they describe as a clear comparison to their own construction. They report compiling their algorithm for challenging finite-sized molecules such as FeMoCo, finding it requires the least fault-tolerant resources of any known approach, and, having laid out and optimized the surface-code resources the compilation needs, report that FeMoCo can be simulated using about four million physical qubits and under four days of runtime, under stated assumptions on cycle time and gate error rate.
REPORTED COST: Õ(N) Toffoli complexity for the block-encoding circuits, in a basis of N orbitals, with O(λ/ε) repetitions of those circuits needed for phase estimation to sample in the molecular eigenbasis, where λ is the 1-norm of the Hamiltonian coefficients and ε is the target precision. The abstract states this is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis, and that up to logarithmic factors it matches the scaling of the most efficient prior block encodings restricted to an orthogonal basis.
BASIS: The abstract of arXiv:2011.03494 states, in the raw TeX as fetched from the abs page: "We describe quantum circuits with only $\widetilde{\cal O}(N)$ Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of $N$ arbitrary (e.g., molecular) orbitals." Rendered into Unicode for the reader (script-O with a tilde becomes Õ, the italic N stays N), this is Õ(N) Toffoli complexity in a basis of N orbitals. The same abstract continues: "With ${\cal O}(\lambda / \epsilon)$ repetitions of these circuits one can use phase estimation to sample in the molecular eigenbasis, where $\lambda$ is the 1-norm of Hamiltonian coefficients and $\epsilon$ is the target precision." — rendered here as O(λ/ε) repetitions for 1-norm λ and target precision ε. It further states "This is the lowest complexity that has been shown for quantum computations of chemistry within an arbitrary basis." and that "up to logarithmic factors, this matches the scaling of the most efficient prior block encodings that can only work with orthogonal basis functions diagonalizing the Coloumb operator (e.g., the plane wave dual basis)" (the misspelling of Coulomb there is the abstract's own). The Classiq index entry for applications/chemistry/tensor_hypercontraction gives a directory path and a file list and states no bound; it was read and adds nothing to this field.
DEMONSTRATED BY: the Classiq library entry applications/chemistry/tensor_hypercontraction
PRIMARY SOURCE: Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, Ryan Babbush (2020), Even more efficient quantum computations of chemistry through tensor hypercontraction — https://arxiv.org/abs/2011.03494

This is a literature reference record, not an executable circuit.