A Caltech Library Service

Quantum simulation via randomized product formulas: Low gate complexity with accuracy guarantees

Chen, Chi-Fang and Huang, Hsin-Yuan (Robert) and Kueng, Richard and Tropp, Joel A. (2020) Quantum simulation via randomized product formulas: Low gate complexity with accuracy guarantees. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Quantum simulation has wide applications in quantum chemistry and physics. Recently, scientists have begun exploring the use of randomized methods for accelerating quantum simulation. Among them, a simple and powerful technique, called qDRIFT, is known to generate random product formulas for which the average quantum channel approximates the ideal evolution. This work provides a comprehensive analysis of a single realization of the random product formula produced by qDRIFT. The main results prove that a typical realization of the randomized product formula approximates the ideal unitary evolution up to a small diamond-norm error. The gate complexity is independent of the number of terms in the Hamiltonian, but it depends on the system size and the sum of the interaction strengths in the Hamiltonian. Remarkably, the same random evolution starting from an arbitrary, but fixed, input state yields a much shorter circuit suitable for that input state. If the observable is also fixed, the same random evolution provides an even shorter product formula. The proofs depend on concentration inequalities for vector and matrix martingales. Numerical experiments verify the theoretical predictions.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Chen, Chi-Fang0000-0001-5589-7896
Huang, Hsin-Yuan (Robert)0000-0001-5317-2613
Tropp, Joel A.0000-0003-1024-1791
Additional Information:The authors want to thank John Preskill and Yuan Su for valuable inputs and inspiring discussions. Earl Campbell and Nathan Wiebe provided insightful comments, as well as encouraging feedback. CC is thankful for Physics TA Relief Fellowship at Caltech. HH is supported by the Kortschak Scholars Program. RK acknowledges funding from ONR Award N00014-17-1-2146 and ARO Award W911NF121054). JAT gratefully acknowledges funding from the ONR Awards N00014-17-1-2146 and N00014-18-1-2363 and from NSF Award 1952777.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-17-1-2146
Army Research Office (ARO)W911NF121054
Office of Naval Research (ONR)N00014-18-1-2363
Record Number:CaltechAUTHORS:20201218-154423869
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:107213
Deposited By: George Porter
Deposited On:21 Dec 2020 15:44
Last Modified:21 Dec 2020 15:44

Repository Staff Only: item control page