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 exploit this intuition. For the case of sparse Hamiltonian simulation, the gate complexity scales with the L1 norm ∫t0dτ∥H(τ)∥max, whereas the best previous results scale with tmaxτ∈[0,t]∥H(τ)∥max. We also show analogous results for Hamiltonians that are linear combinations of unitaries. Our approaches thus provide an improvement over previous simulation algorithms that can be substantial when the Hamiltonian varies significantly. We introduce two new techniques: a classical sampler of time-dependent Hamiltonians and a rescaling principle for the Schrödinger equation. The rescaled Dyson-series algorithm is nearly optimal with respect to all parameters of interest, whereas the sampling-based approach is easier to realize for near-term simulation. By leveraging the L1-norm information, we obtain polynomial speedups for semi-classical simulations of scattering processes in quantum chemistry.

%8 06/17/2019 %G eng %U https://arxiv.org/abs/1906.07115 %0 Journal Article %J Proceedings of the 51st ACM Symposium on Theory of Computing (to appear) %D 2018 %T Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics %A Andras Gilyen %A Yuan Su %A Guang Hao Low %A Nathan Wiebe %XQuantum computing is powerful because unitary operators describing the time-evolution of a quantum system have exponential size in terms of the number of qubits present in the system. We develop a new "Singular value transformation" algorithm capable of harnessing this exponential advantage, that can apply polynomial transformations to the singular values of a block of a unitary, generalizing the optimal Hamiltonian simulation results of Low and Chuang. The proposed quantum circuits have a very simple structure, often give rise to optimal algorithms and have appealing constant factors, while usually only use a constant number of ancilla qubits. We show that singular value transformation leads to novel algorithms. We give an efficient solution to a certain "non-commutative" measurement problem and propose a new method for singular value estimation. We also show how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum. Finally, as a quantum machine learning application we show how to efficiently implement principal component regression. "Singular value transformation" is conceptually simple and efficient, and leads to a unified framework of quantum algorithms incorporating a variety of quantum speed-ups. We illustrate this by showing how it generalizes a number of prominent quantum algorithms, including: optimal Hamiltonian simulation, implementing the Moore-Penrose pseudoinverse with exponential precision, fixed-point amplitude amplification, robust oblivious amplitude amplification, fast QMA amplification, fast quantum OR lemma, certain quantum walk results and several quantum machine learning algorithms. In order to exploit the strengths of the presented method it is useful to know its limitations too, therefore we also prove a lower bound on the efficiency of singular value transformation, which often gives optimal bounds.

%B Proceedings of the 51st ACM Symposium on Theory of Computing (to appear) %8 2018/06/05 %G eng %U https://arxiv.org/abs/1806.01838 %0 Journal Article %J Journal of Mathematical Physics %D 2013 %T Product Formulas for Exponentials of Commutators %A Andrew M. Childs %A Nathan Wiebe %X We provide a recursive method for constructing product formula approximations to exponentials of commutators, giving the first approximations that are accurate to arbitrarily high order. Using these formulas, we show how to approximate unitary exponentials of (possibly nested) commutators using exponentials of the elementary operators, and we upper bound the number of elementary exponentials needed to implement the desired operation within a given error tolerance. By presenting an algorithm for quantum search using evolution according to a commutator, we show that the scaling of the number of exponentials in our product formulas with the evolution time is nearly optimal. Finally, we discuss applications of our product formulas to quantum control and to implementing anticommutators, providing new methods for simulating many-body interaction Hamiltonians. %B Journal of Mathematical Physics %V 54 %P 062202 %8 2013/02/07 %G eng %U http://arxiv.org/abs/1211.4945v2 %N 6 %! J. Math. Phys. %R 10.1063/1.4811386 %0 Journal Article %J Quantum Information and Computation %D 2012 %T Hamiltonian Simulation Using Linear Combinations of Unitary Operations %A Andrew M. Childs %A Nathan Wiebe %X We present a new approach to simulating Hamiltonian dynamics based on implementing linear combinations of unitary operations rather than products of unitary operations. The resulting algorithm has superior performance to existing simulation algorithms based on product formulas and, most notably, scales better with the simulation error than any known Hamiltonian simulation technique. Our main tool is a general method to nearly deterministically implement linear combinations of nearby unitary operations, which we show is optimal among a large class of methods. %B Quantum Information and Computation %V 12 %P 901-924 %8 2012/11/01 %G eng %U http://arxiv.org/abs/1202.5822v1 %N 11-12 %! Quantum Information and Computation 12