Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. SandersAbstract Arguably one of the most important applications of quantum computers is the simulation of quantum systems. In the case where the Hamiltonian consists of a sum of interaction terms between small subsystems, the simulation is thought to be exponentially more efficient than classical simulation. More generally, evolution under suitably specified sparse Hamiltonians may be efficiently simulated. In recent work we have shown that the complexity of simulating evolution under a Hamiltonian is very close to linear in the evolution time. In addition, we have shown that in the general case of a sparse Hamiltonian the complexity grows slowly with respect to the number of qubits. In this chapter we review these results.
Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. SandersAbstract Arguably one of the most important applications of quantum computers is the simulation of quantum systems. In the case where the Hamiltonian consists of a sum of interaction terms between small subsystems, the simulation is thought to be exponentially more efficient than classical simulation. More generally, evolution under suitably specified sparse Hamiltonians may be efficiently simulated. In recent work we have shown that the complexity of simulating evolution under a Hamiltonian is very close to linear in the evolution time. In addition, we have shown that in the general case of a sparse Hamiltonian the complexity grows slowly with respect to the number of qubits. In this chapter we review these results.
We explicitly show how to simulate time-dependent sparse Hamiltonian evolution on a quantum computer, with complexity that is close to linear in the evolution time. The complexity also depends on the magnitude of the derivatives of the Hamiltonian. We propose a range of techniques to simulate Hamiltonians with badly behaved derivatives. These include using adaptive time steps, adapting the order of the integrators, and omitting regions about discontinuities. The complexity of the algorithm is quantified by calls to an oracle, which yields information about the Hamiltonian, and accounts for all computational resources. We explicitly determine the number of bits of output that this oracle needs to provide, and show how to efficiently perform the required 1-sparse unitary operations using these bits. We also account for discretization error in the time, as well as accounting for Hamiltonians that are a sum of terms that are sparse in different bases.
The problem considered in this thesis is the following: We are given a Hamiltonian H and time t, and our goal is to approximately implement the unitary operator e^{-iHt} with an efficient quantum algorithm. We present an efficient algorithm for simulating sparse Hamiltonians. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian acts, this algorithm uses (d^2(d+log^* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which scales like (d^4(log^* N)||Ht||)^{1+o(1)}. In terms of the parameter t, these algorithms are essentially optimal due to a no--fast-forwarding theorem. \n \nIn the second part of this thesis, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, and rule out generic simulations taking time o(||Ht||), even though ||H|| is not a unique measure of the size of a dense Hamiltonian H. We also present a stronger limitation ruling out the possibility of generic simulations taking time poly(||Ht||,log N), showing that known simulations based on discrete-time quantum walks cannot be dramatically improved in general. We also show some positive results about simulating structured Hamiltonians efficiently.
Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.
Abstract This chapter presents some quantum algorithms to simulate the dynamics of a quantum system, one of the most important applications of a quantum computer. We introduce the conditions for efficient simulation of Hamiltonian dynamics. We then present some Trotterization methods, in which the time evolution operator is approximated as a product of terms, each of which can be implemented by a quantum circuit at polynomial cost. We show high-order decompositions and illustrate the use of a Trotterization method to simulate sparse Hamiltonians. We discuss the Taylor series method and the qubitization method. The latter achieves optimal cost in simulation time and target accuracy. We conclude the chapter with a proof that simulating Hamiltonian dynamics is BQP-complete
In this thesis, we present three innovations that can be used to simulate quantum dynamics on both quantum and classical computers. Our primary innovation is an efficient quantum algorithm for simulating time-dependent Hamiltonian evolution of general input states on a quantum computer. Given conditions on the smoothness of the Hamiltonian, the complexity of the algorithm is close to linear in the evolution time, and therefore is comparable to algorithms for time-independent Hamiltonians. In addition, we show how the complexity can be reduced by optimizing the time steps. The complexity of the algorithm is quantified by calls to an oracle, which yields information about the Hamiltonian. In contrast to previous work, which allowed an oracle query to yield an arbitrary number of bits or qubits, we assign a cost for each bit or qubit accessed, revealing hitherto unnoticed simulation costs. We also account for discretization errors in the time and the representation of the Hamiltonian. This work is enabled by our development of a decomposition scheme based on Lie-Trotter- Suzuki product formulae for ordered operator exponentials. We show, by counterexample, that Lie-Trotter-Suzuki approximations may be lower order than expected when applied to problems that have singularities or discontinuous derivatives of appropriate order. We address this problem by presenting a set of criteria that is sufficient for the validity of these approximations, prove convergence and provide upper bounds for the approximation error. We also provide a new analysis of the evolution of quantum adiabatic systems in this thesis. Our work contains the tightest upper bounds that are currently known, and the first tight lower bounds, for the error in the adiabatic approximation applied to fixed Hamiltonians in the limit of slow evolution. We use our results to address the Marzlin- Sanders counterexample Hamiltonian. Specifically, we provide sufficiency conditions for the validity of the adiabatic approximation and demonstrate that the Marzlin-Sanders counterexample fails to satisfy them. We also find a new class of time-dependent Hamiltonians that are related to the Marzlin0Sanders counterexample Hamiltonian, but nonetheless obey the adiabatic approximation for sufficiently slow evolutions.
This chapter introduces the basic concepts of digital quantum simulation. The study of the computational complexity of problems in quantum simulation helps us better understand how quantum computers can surpass classical computers. The chapter briefly summarizes a few important examples of complexity classes of decision problems. Quantum algorithms are procedures for applying elementary quantum logic gates to complete certain unitary transformations of the input state. The steps involved in carrying out a digital quantum simulation consist of three parts: state preparation, time evolution, and measurement of observables. The chapter provides an overview of state preparation and simulation of time evolution. The use of Suzuki–Trotter formulas in quantum simulation for time-independent sparse Hamiltonians is reviewed. The chapter reviews a method to effect nondestructive measurements of constants of the motion within the adiabatic model.