Christopher Kang

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.