A Caltech Library Service

Efficient classical simulation of noisy random quantum circuits in one dimension

Noh, Kyungjoo and Jiang, Liang and Fefferman, Bill (2020) Efficient classical simulation of noisy random quantum circuits in one dimension. Quantum, 4 . Art. No. 318. ISSN 2521-327X. doi:10.22331/q-2020-09-11-318.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


Understanding the computational power of noisy intermediate-scale quantum (NISQ) devices is of both fundamental and practical importance to quantum information science. Here, we address the question of whether error-uncorrected noisy quantum computers can provide computational advantage over classical computers. Specifically, we study noisy random circuit sampling in one dimension (or 1D noisy RCS) as a simple model for exploring the effects of noise on the computational power of a noisy quantum device. In particular, we simulate the real-time dynamics of 1D noisy random quantum circuits via matrix product operators (MPOs) and characterize the computational power of the 1D noisy quantum system by using a metric we call MPO entanglement entropy. The latter metric is chosen because it determines the cost of classical MPO simulation. We numerically demonstrate that for the two-qubit gate error rates we considered, there exists a characteristic system size above which adding more qubits does not bring about an exponential growth of the cost of classical MPO simulation of 1D noisy systems. Specifically, we show that above the characteristic system size, there is an optimal circuit depth, independent of the system size, where the MPO entanglement entropy is maximized. Most importantly, the maximum achievable MPO entanglement entropy is bounded by a constant that depends only on the gate error rate, not on the system size. We also provide a heuristic analysis to get the scaling of the maximum achievable MPO entanglement entropy as a function of the gate error rate. The obtained scaling suggests that although the cost of MPO simulation does not increase exponentially in the system size above a certain characteristic system size, it does increase exponentially as the gate error rate decreases, possibly making classical simulation practically not feasible even with state-of-the-art supercomputers.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Noh, Kyungjoo0000-0002-6318-8472
Jiang, Liang0000-0002-0000-9342
Fefferman, Bill0000-0002-9627-0210
Additional Information:© 2020 published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. Published: 2020-09-11. We would like to thank Fernando Brandao, John Preskill, Norbert Schuch, Soonwon Choi, Michael Gullans, Aidan Dang, Qian Xu, and Roozbeh Bassirianjahromi for helpful discussions. K.N. acknowledges Sunnie Kim for her help in setting up the computing resources, provided by the University of Chicago Research Computing Center, which were used to perform all the numerical simulations in this work. K.N. acknowledges support through the Korea Foundation for Advanced Studies. L.J. acknowledges support from the ARL-CDQI (W911NF-15-2-0067), ARO (W911NF-18-1-0020, W911NF-18-1-0212), ARO MURI (W911NF-16-1-0349), AFOSR MURI (FA9550-15-1-0015, FA9550-19-1-0399), DOE (DE-SC0019406), NSF (EFMA-1640959, OMA-1936118), and the Packard Foundation (2013-39273). B.F. acknowledges support from AFOSR YIP number FA9550-18-1-0148.
Funding AgencyGrant Number
Korea Foundation for Advanced StudiesUNSPECIFIED
Army Research LaboratoryW911NF-15-2-0067
Army Research Office (ARO)W911NF-18-1-0020
Army Research Office (ARO)W911NF-18-1-0212
Army Research Office (ARO)W911NF-16-1-0349
Air Force Office of Scientific Research (AFOSR)FA9550-15-1-0015
Air Force Office of Scientific Research (AFOSR)FA9550-19-1-0399
Department of Energy (DOE)DE-SC0019406
David and Lucile Packard Foundation2013-39273
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0148
Record Number:CaltechAUTHORS:20201001-120319290
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105720
Deposited By: Tony Diaz
Deposited On:01 Oct 2020 20:37
Last Modified:16 Nov 2021 18:45

Repository Staff Only: item control page