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.
Specifically, we study 1D noisy random circuit sampling as a simple model for exploring the adverse effects of the realistic gate errors. The key takeaway from our work is that in noisy settings, there exists a characteristic system size, determined solely by the gate error rate, above which adding more qubits does not bring about an exponential growth of the computing power of a noisy quantum system. That is, quality limits the utility of quantity. In particular, we demonstrate that matrix product operators are able to describe the dynamics of a 1D noisy system in a reliable and compressed way.
Our work provides a framework for assessing the utility of near-term quantum computing technologies based on noisy intermediate-scale quantum (NISQ) devices. Going beyond the chain architecture and investigating more general settings (e.g., planar architecture) would be a fruitful future research direction.
 P. W. Shor, ``Algorithms for quantum computation: discrete logarithms and factoring,'' in Proceedings 35th Annual Symposium on Foundations of Computer Science (1994) pp. 124–134.
 A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, ``Surface codes: Towards practical large-scale quantum computation,'' Phys. Rev. A 86, 032324 (2012a).
 C. Horsman, A. G. Fowler, S. Devitt, and R. V. Meter, ``Surface code quantum computing by lattice surgery,'' New Journal of Physics 14, 123011 (2012).
 J. Haah, M. B. Hastings, D. Poulin, and D. Wecker, ``Magic state distillation with low space overhead and optimal asymptotic input count,'' Quantum 1, 31 (2017).
 R. Chao and B. W. Reichardt, ``Quantum error correction with only two extra qubits,'' Phys. Rev. Lett. 121, 050502 (2018a).
 C. Chamberland, G. Zhu, T. J. Yoder, J. B. Hertzberg, and A. W. Cross, ``Topological and subsystem codes on low-degree graphs with flag qubits,'' Phys. Rev. X 10, 011022 (2020a).
 C. Chamberland, A. Kubica, T. J. Yoder, and G. Zhu, ``Triangular color codes on trivalent graphs with flag qubits,'' New Journal of Physics 22, 023019 (2020b).
 P. Das, C. A. Pattison, S. Manne, D. Carmean, K. Svore, M. Qureshi, and N. Delfosse, ``A Scalable Decoder Micro-architecture for Fault-Tolerant Quantum Computing,'' arXiv e-prints , arXiv:2001.06598 (2020), arXiv:2001.06598 [quant-ph].
 N. Delfosse, B. W. Reichardt, and K. M. Svore, ``Beyond single-shot fault-tolerant quantum error correction,'' arXiv e-prints , arXiv:2002.05180 (2020), arXiv:2002.05180 [quant-ph].
 C. Chamberland and K. Noh, ``Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits,'' arXiv e-prints , arXiv:2003.03049 (2020), arXiv:2003.03049 [quant-ph].
 M. J. Bremner, R. Jozsa, and D. J. Shepherd, ``Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 459–472 (2011).
 S. Aaronson and A. Arkhipov, ``The computational complexity of linear optics,'' in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11 (Association for Computing Machinery, New York, NY, USA, 2011) p. 333–342.
 C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, ``Gaussian boson sampling,'' Phys. Rev. Lett. 119, 170501 (2017).
 B. Fefferman and C. Umans, ``On the Power of Quantum Fourier Sampling,'' in 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 61, edited by A. Broadbent (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016) pp. 1:1–1:19.
 S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, ``Characterizing quantum supremacy in near-term devices,'' Nature Physics 14, 595–600 (2018).
 M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White, ``Photonic boson sampling in a tunable circuit,'' Science 339, 794–798 (2013).
 J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X.-M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, ``Boson sampling on a photonic chip,'' Science 339, 798–801 (2013).
 A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvão, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, ``Integrated multimode interferometers with arbitrary designs for photonic boson sampling,'' Nature Photonics 7, 545–549 (2013).
 A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing, ``Classical boson sampling algorithms with superior performance to near-term experiments,'' Nature Physics 13, 1153–1157 (2017).
 P. Clifford and R. Clifford, ``The classical complexity of boson sampling,'' in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 146–155.
 A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, ``On the complexity and verification of quantum random circuit sampling,'' Nature Physics 15, 159–163 (2019).
 S. Aaronson and L. Chen, ``Complexity-Theoretic Foundations of Quantum Supremacy Experiments,'' in 32nd Computational Complexity Conference (CCC 2017), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 79, edited by R. O'Donnell (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017) pp. 22:1–22:67.
 F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, ``Quantum supremacy using a programmable superconducting processor,'' Nature 574, 505–510 (2019).
 E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, and R. Wisnieff, ``Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits,'' arXiv e-prints , arXiv:1910.09534 (2019), arXiv:1910.09534 [quant-ph].
 R. Movassagh, ``Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling,'' arXiv e-prints , arXiv:1810.04681 (2018), arXiv:1810.04681 [quant-ph].
 F. Verstraete, J. J. García-Ripoll, and J. I. Cirac, ``Matrix product density operators: Simulation of finite-temperature and dissipative systems,'' Phys. Rev. Lett. 93, 207204 (2004).
 M. Zwolak and G. Vidal, ``Mixed-state dynamics in one-dimensional quantum lattice systems: A time-dependent superoperator renormalization algorithm,'' Phys. Rev. Lett. 93, 207205 (2004).
 J. Emerson, M. Silva, O. Moussa, C. Ryan, M. Laforest, J. Baugh, D. G. Cory, and R. Laflamme, ``Symmetrized characterization of noisy quantum processes,'' Science 317, 1893–1896 (2007).
 C. H. Bennett, H. J. Bernstein, S. Popescu, and B. Schumacher, ``Concentrating partial entanglement by local operations,'' Phys. Rev. A 53, 2046–2052 (1996a).
 C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters, ``Mixed-state entanglement and quantum error correction,'' Phys. Rev. A 54, 3824–3851 (1996b).
 B. M. Terhal, M. Horodecki, D. W. Leung, and D. P. DiVincenzo, ``The entanglement of purification,'' Journal of Mathematical Physics 43, 4286–4298 (2002), https://doi.org/10.1063/1.1498001.
 J. Guth Jarkovský, A. Molnár, N. Schuch, and J. I. Cirac, ``Efficient description of many-body systems with matrix product density operators,'' PRX Quantum 1, 010304 (2020).
 T. Prosen and M. Žnidarič, ``Matrix product simulations of non-equilibrium steady states of quantum spin chains,'' Journal of Statistical Mechanics: Theory and Experiment 2009, P02035 (2009).
 D. Aharonov and M. Ben-Or, ``Polynomial simulations of decohered quantum computers,'' in Proceedings of 37th Conference on Foundations of Computer Science (1996) pp. 46–55.
 A. Dang, Distributed Matrix Product State Simulations of Large-Scale Quantum Circuits, Master's thesis, The University of Melbourne (2017).
 G. Vidal, ``Class of quantum many-body states that can be efficiently simulated,'' Phys. Rev. Lett. 101, 110501 (2008).
 M. Szyniszewski, A. Romito, and H. Schomerus, ``Entanglement transition from variable-strength weak measurements,'' Phys. Rev. B 100, 064204 (2019).
 S. Choi, Y. Bao, X.-L. Qi, and E. Altman, ``Quantum error correction in scrambling dynamics and measurement-induced phase transition,'' Phys. Rev. Lett. 125, 030505 (2020).
 M. J. Gullans and D. A. Huse, ``Scalable probes of measurement-induced criticality,'' Phys. Rev. Lett. 125, 070606 (2020).
 A. Zabalo, M. J. Gullans, J. H. Wilson, S. Gopalakrishnan, D. A. Huse, and J. H. Pixley, ``Critical properties of the measurement-induced transition in random quantum circuits,'' Phys. Rev. B 101, 060301 (2020).
 R. Fan, S. Vijay, A. Vishwanath, and Y.-Z. You, ``Self-Organized Error Correction in Random Unitary Circuits with Measurement,'' arXiv e-prints , arXiv:2002.12385 (2020), arXiv:2002.12385 [cond-mat.stat-mech].
 C.-M. Jian, Y.-Z. You, R. Vasseur, and A. W. W. Ludwig, ``Measurement-induced criticality in random quantum circuits,'' Phys. Rev. B 101, 104302 (2020).
 Y. Li, X. Chen, A. W. W. Ludwig, and M. P. A. Fisher, ``Conformal invariance and quantum non-locality in hybrid quantum circuits,'' arXiv e-prints , arXiv:2003.12721 (2020), arXiv:2003.12721 [quant-ph].
 M. J. Bremner, A. Montanaro, and D. J. Shepherd, ``Achieving quantum supremacy with sparse and noisy commuting quantum computations,'' Quantum 1, 8 (2017).
 S. Boixo, V. N. Smelyanskiy, and H. Neven, ``Fourier analysis of sampling from noisy chaotic quantum circuits,'' arXiv e-prints , arXiv:1708.01875 (2017), arXiv:1708.01875 [quant-ph].
 F. Verstraete and J. I. Cirac, ``Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions,'' arXiv e-prints , cond-mat/0407066 (2004), arXiv:cond-mat/0407066 [cond-mat.str-el].
 N. Schuch, M. M. Wolf, F. Verstraete, and J. I. Cirac, ``Computational complexity of projected entangled pair states,'' Phys. Rev. Lett. 98, 140506 (2007).
 J. Haferkamp, D. Hangleiter, J. Eisert, and M. Gluza, ``Contracting projected entangled pair states is average-case hard,'' Phys. Rev. Research 2, 013010 (2020).
 J. Napp, R. L. La Placa, A. M. Dalzell, F. G. S. L. Brandao, and A. W. Harrow, ``Efficient classical simulation of random shallow 2D quantum circuits,'' arXiv e-prints , arXiv:2001.00021 (2019), arXiv:2001.00021 [quant-ph].
 U. Schollwöck, ``The density-matrix renormalization group in the age of matrix product states,'' Annals of Physics 326, 96 – 192 (2011), january 2011 Special Issue.
 Song Cheng, Chenfeng Cao, Chao Zhang, Yongxiang Liu, Shi-Yao Hou, Pengxiang Xu, and Bei Zeng, "Simulating noisy quantum circuits with matrix product density operators", Physical Review Research 3 2, 023005 (2021).
 Ivan H. Deutsch, "Harnessing the Power of the Second Quantum Revolution", PRX Quantum 1 2, 020101 (2020).
 Yi-Ting Chen, Collin Farquhar, and Robert M. Parrish, "Low-rank density-matrix evolution for noisy quantum circuits", npj Quantum Information 7 1, 61 (2021).
 M. Szyniszewski, A. Romito, and H. Schomerus, "Universality of Entanglement Transitions from Stroboscopic to Continuous Measurements", Physical Review Letters 125 21, 210602 (2020).
 Jordi Tura, "Imperfections Lower the Simulation Cost of Quantum Computers", Physics 13, 183 (2020).
 Changhun Oh, Kyungjoo Noh, Bill Fefferman, and Liang Jiang, "Classical simulation of lossy boson sampling using matrix product operators", Physical Review A 104 2, 022407 (2021).
 Cupjin Huang, Fang Zhang, Michael Newman, Xiaotong Ni, Dawei Ding, Junjie Cai, Xun Gao, Tenghui Wang, Feng Wu, Gengyan Zhang, Hsiang-Sheng Ku, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, Hui-Hai Zhao, Chunqing Deng, and Jianxin Chen, "Efficient parallelization of tensor network contraction for simulating quantum computation", Nature Computational Science 1 9, 578 (2021).
 Boaz Barak, Chi-Ning Chou, and Xun Gao, "Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits", arXiv:2005.02421.
 Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Fault-tolerant quantum speedup from constant depth quantum circuits", arXiv:2005.11539, Physical Review Research 2 3, 033444 (2020).
 Shuvro Chowdhury, Kerem Y. Camsari, and Supriyo Datta, "Emulating Quantum Interference with Generalized Ising Machines", arXiv:2007.07379.
 Benjamin Villalonga, Murphy Yuezhen Niu, Li Li, Hartmut Neven, John C. Platt, Vadim N. Smelyanskiy, and Sergio Boixo, "Efficient approximation of experimental Gaussian boson sampling", arXiv:2109.11525.
The above citations are from Crossref's cited-by service (last updated successfully 2021-10-27 18:10:05) and SAO/NASA ADS (last updated successfully 2021-10-27 18:10:06). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is 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.