



@article {3512,
	title = {Multi-product Hamiltonian simulation with explicit commutator scaling},
	year = {2024},
	month = {3/13/2024},
	abstract = {<p>The well-conditioned multi-product formula (MPF), proposed by [Low, Kliuchnikov, and Wiebe, 2019], is a simple high-order time-independent Hamiltonian simulation algorithm that implements a linear combination of standard product formulas of low order. While the MPF aims to simultaneously exploit commutator scaling among Hamiltonians and achieve near-optimal time and precision dependence, its lack of a rigorous error bound on the nested commutators renders its practical advantage ambiguous. In this work, we conduct a rigorous complexity analysis of the well-conditioned MPF, demonstrating explicit commutator scaling and near-optimal time and precision dependence at the same time. Using our improved complexity analysis, we present several applications of practical interest where the MPF based on a second-order product formula can achieve a polynomial speedup in both system size and evolution time, as well as an exponential speedup in precision, compared to second-order and even higher-order product formulas. Compared to post-Trotter methods, the MPF based on a second-order product formula can achieve polynomially better scaling in system size, with only poly-logarithmic overhead in evolution time and precision.</p>},
	url = {https://arxiv.org/abs/2403.08922},
	author = {Junaid Aftab and Dong An and Konstantina Trivisa}
}
@article {2700,
	title = {Efficient quantum algorithm for dissipative nonlinear differential equations},
	journal = {Proceedings of the National Academy of Sciences},
	volume = {118},
	year = {2021},
	month = {3/1/2021},
	chapter = {e2026805118},
	abstract = {<p>While there has been extensive previous work on efficient quantum algorithms for linear differential equations, analogous progress for nonlinear differential equations has been severely limited due to the linearity of quantum mechanics. Despite this obstacle, we develop a quantum algorithm for initial value problems described by dissipative quadratic n-dimensional ordinary differential equations. Assuming R\&lt;1, where R is a parameter characterizing the ratio of the nonlinearity to the linear dissipation, this algorithm has complexity T2poly(logT,logn)/ϵ, where T is the evolution time and ϵ is the allowed error in the output quantum state. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. We achieve this improvement using the method of Carleman linearization, for which we give an improved 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 R\&ge;2\&ndash;\&radic;. Finally, we discuss potential applications of this approach to problems arising in biology as well as in fluid and plasma dynamics.</p>},
	doi = {https://doi.org/10.1073/pnas.2026805118},
	url = {https://arxiv.org/abs/2011.03185},
	author = {Jin-Peng Liu and Herman {\O}ie Kolden and Hari K. Krovi and Nuno F. Loureiro and Konstantina Trivisa and Andrew M. Childs}
}
