Yuan Su

The efficient implementation of matrix arithmetic operations underpins the speedups of many quantum algorithms. We present a suite of methods to do matrix arithmetics---with the result encoded in the off-diagonal blocks of a Hamiltonian---using Hamiltonian evolutions of input operators. We show how to maintain this Hamiltonian block encoding, so that matrix operations can be composed one after another, and the entire computation takes $\leq 2$ ancilla qubits. We achieve this for matrix multiplication, matrix addition, matrix inversion, Hermitian conjugation, fractional scaling, integer scaling, complex phase scaling, as well as singular value transformation for both odd and even polynomials. We also develop an overlap estimation algorithm to extract classical properties of Hamiltonian block encoded operators, analogous to the well known Hadmard test, at no extra cost of qubit. Our Hamiltonian matrix multiplication uses the Lie group commutator product formula and its higher-order generalizations due to Childs and Wiebe. Our Hamiltonian singular value transformation employs a dominated polynomial approximation, wherein the approximation holds over the domain of interest, while the polynomial is upper bounded by the target function on the entire unit interval. When applied to quantum simulation, our methods inherit the commutator scaling of product formulas, while leveraging the power of matrix arithmetics to reduce the cost of each step. To illustrate this feature, we present a circuit for simulating a class of sum-of-squares Hamiltonians, covering systems studied recently in quantum chemistry. Our simulation attains a commutator scaling in step count, while the gate cost per step remains comparable to that of more advanced algorithms. We achieve this with $1$ ancilla qubit.

Abstract We consider simulating quantum systems on digital quantum computers. We show that the performance of quantum simulation can be improved by simultaneously exploiting the commutativity of Hamiltonian, the sparsity of interactions, and the prior knowledge of initial state. We achieve this using Trotterization for a class of correlated electrons that encompasses various physical systems, including the plane-wave-basis electronic structure and the Fermi-Hubbard model. We estimate the simulation error by taking the transition amplitude of nested commutators of Hamiltonian terms within the $\eta$-electron manifold. We develop multiple techniques for bounding the transition amplitude and the expectation of general fermionic operators, which may be of independent interest. We show that it suffices to use $\cO{\frac{n^{5/3}}{\eta^{2/3}}+n^{4/3}\eta^{2/3}}$ gates to simulate electronic structure in the plane-wave basis with $n$ spin orbitals and $\eta$ electrons up to a negligible factor, improving the best previous result in second quantization while outperforming the first-quantized simulation when $\eta=\Om{\sqrt{n}}$. We also obtain an improvement for simulating the Fermi-Hubbard model. We construct concrete examples for which our bounds are almost saturated, giving a nearly tight Trotterization of correlated electrons.