*Proc Natl Acad Sci U S A ; 118(35)2021 08 31.*

##### RESUMO

Nonlinear differential equations model diverse phenomena but are notoriously difficult to solve. While there has been extensive previous work on efficient quantum algorithms for linear differential equations, the linearity of quantum mechanics has limited analogous progress for the nonlinear case. Despite this obstacle, we develop a quantum algorithm for dissipative quadratic n-dimensional ordinary differential equations. Assuming [Formula: see text], where R is a parameter characterizing the ratio of the nonlinearity and forcing to the linear dissipation, this algorithm has complexity [Formula: see text], where T is the evolution time, Ïµ is the allowed error, and q measures decay of the solution. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. While exponential decay precludes efficiency, driven equations can avoid this issue despite the presence of dissipation. Our algorithm uses the method of Carleman linearization, for which we give a convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for [Formula: see text] Finally, we discuss potential applications, showing that the [Formula: see text] condition can be satisfied in realistic epidemiological models and giving numerical evidence that the method may describe a model of fluid dynamics even for larger values of R.

*Phys Rev A (Coll Park) ; 1022020.*

##### RESUMO

Strongly long-range interacting quantum systems-those with interactions decaying as a power law 1/r α in the distance r on a D-dimensional lattice for α â©½ D-have received significant interest in recent years. They are present in leading experimental platforms for quantum computation and simulation, as well as in theoretical models of quantum-information scrambling and fast entanglement creation. Since no notion of locality is expected in such systems, a general understanding of their dynamics is lacking. In a step towards rectifying this problem, we prove two Lieb-Robinson-type bounds that constrain the time for signaling and scrambling in strongly long-range interacting systems, for which no tight bounds were previously known. Our first bound applies to systems mappable to free-particle Hamiltonians with long-range hopping, and is saturable for α â©½ D/2. Our second bound pertains to generic long-range interacting spin Hamiltonians and gives a tight lower bound for the signaling time to extensive subsets of the system for all α< D. This many-site signaling time lower bounds the scrambling time in strongly long-range interacting systems.

*Phys Rev Lett ; 124(22): 220502, 2020 Jun 05.*

##### RESUMO

Quantum computers can efficiently simulate the dynamics of quantum systems. In this Letter, we study the cost of digitally simulating the dynamics of several physically relevant systems using the first-order product-formula algorithm. We show that the errors from different Trotterization steps in the algorithm can interfere destructively, yielding a much smaller error than previously estimated. In particular, we prove that the total error in simulating a nearest-neighbor interacting system of n sites for time t using the first-order product formula with r time slices is O(nt/r+nt^{3}/r^{2}) when nt^{2}/r is less than a small constant. Given an error tolerance Ïµ, the error bound yields an estimate of max{O(n^{2}t/Ïµ),O(n^{2}t^{3/2}/Ïµ^{1/2})} for the total gate count of the simulation. The estimate is tighter than previous bounds and matches the empirical performance observed in Childs et al. [Proc. Natl. Acad. Sci. U.S.A. 115, 9456 (2018)PNASA60027-842410.1073/pnas.1801723115]. We also provide numerical evidence for potential improvements and conjecture an even tighter estimate for the gate count.

*Phys Rev Lett ; 123(5): 050503, 2019 Aug 02.*

##### RESUMO

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 has been demonstrated by several experimental groups. While it is reasonable to expect this complexity-in particular, this was claimed without rigorous justification by Jordan, Lee, and Preskill-we are not aware of a straightforward proof. Our approach is based on an analysis of the local error structure of product formulas, as introduced by Descombes and Thalhammer and significantly simplified here. We prove error bounds for canonical product formulas, which include well-known constructions such as the Lie-Trotter-Suzuki formulas. We also develop a local error representation for time-dependent Hamiltonian simulation, and we discuss generalizations to periodic boundary conditions, constant-range interactions, and higher dimensions. Combined with a previous lower bound, our result implies that product formulas can simulate lattice Hamiltonians with nearly optimal gate complexity.

*Phys Rev X ; 92019.*

##### RESUMO

The propagation of information in nonrelativistic quantum systems obeys a speed limit known as a Lieb-Robinson bound. We derive a new Lieb-Robinson bound for systems with interactions that decay with distance r as a power law, 1/r α . The bound implies an effective light cone tighter than all previous bounds. Our approach is based on a technique for approximating the time evolution of a system, which was first introduced as part of a quantum simulation algorithm by Haah et al., FOCS'18. To bound the error of the approximation, we use a known Lieb-Robinson bound that is weaker than the bound we establish. This result brings the analysis full circle, suggesting a deep connection between Lieb-Robinson bounds and digital quantum simulation. In addition to the new Lieb-Robinson bound, our analysis also gives an error bound for the Haah et al. quantum simulation algorithm when used to simulate power-law decaying interactions. In particular, we show that the gate count of the algorithm scales with the system size better than existing algorithms when α > 3D (where D is the number of dimensions).

*Proc Natl Acad Sci U S A ; 115(38): 9456-9461, 2018 09 18.*

##### RESUMO

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, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.

*Proc Math Phys Eng Sci ; 474(2209): 20170480, 2018 Jan.*

##### RESUMO

How many quantum queries are required to determine the coefficients of a degree-d polynomial in n variables? We present and analyse quantum algorithms for this multivariate polynomial interpolation problem over the fields [Formula: see text], [Formula: see text] and [Formula: see text]. We show that [Formula: see text] and [Formula: see text] queries suffice to achieve probability 1 for [Formula: see text] and [Formula: see text], respectively, where [Formula: see text] except for d=2 and four other special cases. For [Formula: see text], we show that â(d/(n+d))(n+dd) â queries suffice to achieve probability approaching 1 for large field order q. The classical query complexity of this problem is (n+dd) , so our result provides a speed-up by a factor of n+1, (n+1)/2 and (n+d)/d for [Formula: see text], [Formula: see text] and [Formula: see text], respectively. Thus, we find a much larger gap between classical and quantum algorithms than the univariate case, where the speedup is by a factor of 2. For the case of [Formula: see text], we conjecture that [Formula: see text] queries also suffice to achieve probability approaching 1 for large field order q, although we leave this as an open problem.

*Phys Rev Lett ; 114(9): 090502, 2015 Mar 06.*

##### RESUMO

We describe a simple, efficient method for simulating Hamiltonian dynamics on a quantum computer by approximating the truncated Taylor series of the evolution operator. Our method can simulate the time evolution of a wide variety of physical systems. As in another recent algorithm, the cost of our method depends only logarithmically on the inverse of the desired precision, which is optimal. However, we simplify the algorithm and its analysis by using a method for implementing linear combinations of unitary operations together with a robust form of oblivious amplitude amplification.

*Science ; 339(6121): 791-4, 2013 Feb 15.*

##### RESUMO

A quantum walk is a time-homogeneous quantum-mechanical process on a graph defined by analogy to classical random walk. The quantum walker is a particle that moves from a given vertex to adjacent vertices in quantum superposition. We consider a generalization to interacting systems with more than one walker, such as the Bose-Hubbard model and systems of fermions or distinguishable particles with nearest-neighbor interactions, and show that multiparticle quantum walk is capable of universal quantum computation. Our construction could, in principle, be used as an architecture for building a scalable quantum computer with no need for time-dependent control.

*Phys Rev Lett ; 102(18): 180501, 2009 May 08.*

##### RESUMO

In some of the earliest work on quantum computing, Feynman showed how to implement universal quantum computation with a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any quantum computation encoded in some graph. The main idea is to implement quantum gates by scattering processes.