2

Nearly tight Trotterization of interacting electrons

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 …

Faster Digital Quantum Simulation by Symmetry Protection

Simulating the dynamics of quantum systems is an important application of quantum computers and has seen a variety of implementations on current hardware. We show that by introducing quantum gates implementing unitary transformations generated by the …

A Theory of Trotter Error

The Lie-Trotter formula, together with its higher-order generalizations, provides a simple approach to decomposing the exponential of a sum of operators. Despite significant effort, the error scaling of such product formulas remains poorly …

Time-dependent Hamiltonian simulation with $L^1$-norm scaling

The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that …

Approximate Quantum Fourier Transform with $O(n\log(n))$ T gates

The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over …

Faster quantum simulation by randomization

Product formulas can be used to simulate Hamiltonian dynamics on a quantum computer by approximating the exponential of a sum of operators by a product of exponentials of the individual summands. This approach is both straightforward and surprisingly …

Framework for Hamiltonian simulation and beyond: standard-form encoding, qubitization, and quantum signal processing

A unified framework for quantum simulation developed by Guang Hao Low and Isaac L. Chuang that leads to a simulation algorithm with not only optimal query complexity but also low ancilla overhead.

Nearly optimal lattice simulation by product formulas

We consider simulating an $n$-qubit Hamiltonian with nearest-neighbor interactions evolving for time $t$ on a quantum computer. We show that this simulation has gate complexity $(nt)^{1+o(1)}$ using product formulas, a straightforward approach that …

Toward the first quantum simulation with quantum speedup

With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, …