Efficient classical simulation of noisy random quantum circuits in one dimension
1Department of Physics, Yale University, New Haven, Connecticut 06520, USA
2AWS Center for Quantum Computing, Pasadena, CA, 91125, USA
3Pritzker School of Molecular Engineering, University of Chicago, Chicago, Illinois 60637, USA
4Department of Computer Science, University of Chicago, Chicago, Illinois 60637, USA
| Published: | 2020-09-11, volume 4, page 318 |
| Eprint: | arXiv:2003.13163v3 |
| Doi: | https://doi.org/10.22331/q-2020-09-11-318 |
| Citation: | Quantum 4, 318 (2020). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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.
Popular summary
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.
► BibTeX data
► References
[1] 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.
https://doi.org/10.1109/SFCS.1994.365700
[2] S. Lloyd, ``Universal quantum simulators,'' Science 273, 1073–1078 (1996).
https://doi.org/10.1126/science.273.5278.1073
[3] P. W. Shor, ``Fault-tolerant quantum computation,'' in Proceedings of 37th Conference on Foundations of Computer Science (1996) pp. 56–65.
https://doi.org/10.1109/SFCS.1996.548464
[4] D. Gottesman, ``Fault-tolerant quantum computation with local gates,'' Journal of Modern Optics 47, 333–345 (2000).
https://doi.org/10.1080/09500340008244046
[5] S. Bravyi and A. Kitaev, ``Universal quantum computation with ideal clifford gates and noisy ancillas,'' Phys. Rev. A 71, 022316 (2005).
https://doi.org/10.1103/PhysRevA.71.022316
[6] E. Knill, ``Quantum computing with realistically noisy devices,'' Nature 434, 39–44 (2005).
https://doi.org/10.1038/nature03350
[7] D. Gottesman, ``An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation,'' arXiv e-prints , arXiv:0904.2557 (2009), arXiv:0904.2557 [quant-ph].
arXiv:0904.2557
[8] 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).
https://doi.org/10.1103/PhysRevA.86.032324
[9] A. G. Fowler, A. C. Whiteside, A. L. McInnes, and A. Rabbani, ``Topological code autotune,'' Phys. Rev. X 2, 041003 (2012b).
https://doi.org/10.1103/PhysRevX.2.041003
[10] S. Bravyi and J. Haah, ``Magic-state distillation with low overhead,'' Phys. Rev. A 86, 052329 (2012).
https://doi.org/10.1103/PhysRevA.86.052329
[11] 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).
https://doi.org/10.1088/1367-2630/14/12/123011
[12] 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).
https://doi.org/10.22331/q-2017-10-03-31
[13] C. Chamberland and M. E. Beverland, ``Flag fault-tolerant error correction with arbitrary distance codes,'' Quantum 2, 53 (2018).
https://doi.org/10.22331/q-2018-02-08-53
[14] R. Chao and B. W. Reichardt, ``Quantum error correction with only two extra qubits,'' Phys. Rev. Lett. 121, 050502 (2018a).
https://doi.org/10.1103/PhysRevLett.121.050502
[15] R. Chao and B. W. Reichardt, ``Fault-tolerant quantum computation with few qubits,'' npj Quantum Information 4, 42 (2018b).
https://doi.org/10.1038/s41534-018-0085-z
[16] C. Chamberland and A. W. Cross, ``Fault-tolerant magic state preparation with flag qubits,'' Quantum 3, 143 (2019).
https://doi.org/10.22331/q-2019-05-20-143
[17] D. Litinski, ``Magic State Distillation: Not as Costly as You Think,'' Quantum 3, 205 (2019).
https://doi.org/10.22331/q-2019-12-02-205
[18] R. Chao and B. W. Reichardt, ``Flag fault-tolerant error correction for any stabilizer code,'' PRX Quantum 1, 010302 (2020).
https://doi.org/10.1103/PRXQuantum.1.010302
[19] 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).
https://doi.org/10.1103/PhysRevX.10.011022
[20] 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).
https://doi.org/10.1088/1367-2630/ab68fd
[21] 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].
arXiv:2001.06598
[22] N. Delfosse, ``Hierarchical decoding to reduce hardware requirements for quantum computing,'' arXiv e-prints , arXiv:2001.11427 (2020), arXiv:2001.11427 [quant-ph].
arXiv:2001.11427
[23] 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].
arXiv:2002.05180
[24] 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].
arXiv:2003.03049
[25] J. Preskill, ``Quantum Computing in the NISQ era and beyond,'' Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79
[26] 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).
https://doi.org/10.1098/rspa.2010.0301
[27] 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.
https://doi.org/10.1145/1993636.1993682
[28] C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, ``Gaussian boson sampling,'' Phys. Rev. Lett. 119, 170501 (2017).
https://doi.org/10.1103/PhysRevLett.119.170501
[29] 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.
https://doi.org/10.4230/LIPIcs.TQC.2016.1
[30] 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).
https://doi.org/10.1038/s41567-018-0124-x
[31] 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).
https://doi.org/10.1126/science.1231440
[32] 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).
https://doi.org/10.1126/science.1231692
[33] M. Tillmann, B. Dakić, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, ``Experimental boson sampling,'' Nature Photonics 7, 540–544 (2013).
https://doi.org/10.1038/nphoton.2013.102
[34] 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).
https://doi.org/10.1038/nphoton.2013.112
[35] 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).
https://doi.org/10.1038/nphys4270
[36] 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.
https://doi.org/10.1137/1.9781611975031.10
[37] J. Renema, V. Shchesnovich, and R. Garcia-Patron, ``Classical simulability of noisy boson sampling,'' arXiv e-prints , arXiv:1809.01953 (2018), arXiv:1809.01953 [quant-ph].
arXiv:1809.01953
[38] R. García-Patrón, J. J. Renema, and V. Shchesnovich, ``Simulating boson sampling in lossy architectures,'' Quantum 3, 169 (2019).
https://doi.org/10.22331/q-2019-08-05-169
[39] 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).
https://doi.org/10.1038/s41567-018-0318-2
[40] 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.
https://doi.org/10.4230/LIPIcs.CCC.2017.22
[41] 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).
https://doi.org/10.1038/s41586-019-1666-5
[42] 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].
arXiv:1910.09534
[43] 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].
arXiv:1810.04681
[44] R. Movassagh, ``Quantum supremacy and random circuits,'' arXiv e-prints , arXiv:1909.06210 (2019), arXiv:1909.06210 [quant-ph].
arXiv:1909.06210
[45] G. Vidal, ``Efficient classical simulation of slightly entangled quantum computations,'' Phys. Rev. Lett. 91, 147902 (2003).
https://doi.org/10.1103/PhysRevLett.91.147902
[46] Y. Zhou, E. M. Stoudenmire, and X. Waintal, ``What limits the simulation of quantum computers?'' arXiv e-prints , arXiv:2002.07730 (2020), arXiv:2002.07730 [quant-ph].
arXiv:2002.07730
[47] 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).
https://doi.org/10.1103/PhysRevLett.93.207204
[48] 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).
https://doi.org/10.1103/PhysRevLett.93.207205
[49] M.-D. Choi, ``Completely positive linear maps on complex matrices,'' Linear Algebra and its Applications 10, 285 – 290 (1975).
https://doi.org/10.1016/0024-3795(75)90075-0
[50] 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).
https://doi.org/10.1126/science.1145699
[51] C. H. Bennett, H. J. Bernstein, S. Popescu, and B. Schumacher, ``Concentrating partial entanglement by local operations,'' Phys. Rev. A 53, 2046–2052 (1996a).
https://doi.org/10.1103/PhysRevA.53.2046
[52] 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).
https://doi.org/10.1103/PhysRevA.54.3824
[53] 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.
https://doi.org/10.1063/1.1498001
arXiv:https://doi.org/10.1063/1.1498001
[54] 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).
https://doi.org/10.1103/PRXQuantum.1.010304
[55] T. Prosen and I. Pižorn, ``Operator space entanglement entropy in a transverse ising chain,'' Phys. Rev. A 76, 032316 (2007).
https://doi.org/10.1103/PhysRevA.76.032316
[56] 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).
https://doi.org/10.1088/1742-5468/2009/02/p02035
[57] S. Xu and B. Swingle, ``Accessing scrambling using matrix product operators,'' Nature Physics 16, 199–204 (2020).
https://doi.org/10.1038/s41567-019-0712-4
[58] P. Zanardi, ``Entanglement of quantum evolutions,'' Phys. Rev. A 63, 040304 (2001).
https://doi.org/10.1103/PhysRevA.63.040304
[59] 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.
https://doi.org/10.1109/SFCS.1996.548463
[60] A. W. Harrow and M. A. Nielsen, ``Robustness of quantum gates in the presence of noise,'' Phys. Rev. A 68, 012308 (2003).
https://doi.org/10.1103/PhysRevA.68.012308
[61] D. N. Page, ``Average entropy of a subsystem,'' Phys. Rev. Lett. 71, 1291–1294 (1993).
https://doi.org/10.1103/PhysRevLett.71.1291
[62] S. K. Foong and S. Kanno, ``Proof of page's conjecture on the average entropy of a subsystem,'' Phys. Rev. Lett. 72, 1148–1151 (1994).
https://doi.org/10.1103/PhysRevLett.72.1148
[63] J. Sánchez-Ruiz, ``Simple proof of page's conjecture on the average entropy of a subsystem,'' Phys. Rev. E 52, 5653–5655 (1995).
https://doi.org/10.1103/PhysRevE.52.5653
[64] S. Sen, ``Average entropy of a quantum subsystem,'' Phys. Rev. Lett. 77, 1–3 (1996).
https://doi.org/10.1103/PhysRevLett.77.1
[65] A. Dang, Distributed Matrix Product State Simulations of Large-Scale Quantum Circuits, Master's thesis, The University of Melbourne (2017).
[66] F. Verstraete and J. I. Cirac, ``Matrix product states represent ground states faithfully,'' Phys. Rev. B 73, 094423 (2006).
https://doi.org/10.1103/PhysRevB.73.094423
[67] G. Vidal, ``Class of quantum many-body states that can be efficiently simulated,'' Phys. Rev. Lett. 101, 110501 (2008).
https://doi.org/10.1103/PhysRevLett.101.110501
[68] Y. Li, X. Chen, and M. P. A. Fisher, ``Quantum zeno effect and the many-body entanglement transition,'' Phys. Rev. B 98, 205136 (2018).
https://doi.org/10.1103/PhysRevB.98.205136
[69] A. Chan, R. M. Nandkishore, M. Pretko, and G. Smith, ``Unitary-projective entanglement dynamics,'' Phys. Rev. B 99, 224307 (2019).
https://doi.org/10.1103/PhysRevB.99.224307
[70] B. Skinner, J. Ruhman, and A. Nahum, ``Measurement-induced phase transitions in the dynamics of entanglement,'' Phys. Rev. X 9, 031009 (2019).
https://doi.org/10.1103/PhysRevX.9.031009
[71] Y. Li, X. Chen, and M. P. A. Fisher, ``Measurement-driven entanglement transition in hybrid quantum circuits,'' Phys. Rev. B 100, 134306 (2019).
https://doi.org/10.1103/PhysRevB.100.134306
[72] M. Szyniszewski, A. Romito, and H. Schomerus, ``Entanglement transition from variable-strength weak measurements,'' Phys. Rev. B 100, 064204 (2019).
https://doi.org/10.1103/PhysRevB.100.064204
[73] 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).
https://doi.org/10.1103/PhysRevLett.125.030505
[74] M. J. Gullans and D. A. Huse, ``Dynamical purification phase transition induced by quantum measurements,'' arXiv e-prints , arXiv:1905.05195 (2019), arXiv:1905.05195 [quant-ph].
arXiv:1905.05195
[75] M. J. Gullans and D. A. Huse, ``Scalable probes of measurement-induced criticality,'' Phys. Rev. Lett. 125, 070606 (2020).
https://doi.org/10.1103/PhysRevLett.125.070606
[76] 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).
https://doi.org/10.1103/PhysRevB.101.060301
[77] 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].
arXiv:2002.12385
[78] Y. Bao, S. Choi, and E. Altman, ``Theory of the phase transition in random unitary circuits with measurements,'' Phys. Rev. B 101, 104301 (2020).
https://doi.org/10.1103/PhysRevB.101.104301
[79] 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).
https://doi.org/10.1103/PhysRevB.101.104302
[80] A. Bera and S. S. Roy, ``Growth of genuine multipartite entanglement in random unitary circuits,'' arXiv e-prints , arXiv:2003.12546 (2020), arXiv:2003.12546 [quant-ph].
arXiv:2003.12546
[81] 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].
arXiv:2003.12721
[82] D. Gottesman, Stabilizer codes and quantum error correction, Ph.D. thesis, California Institute of Technology (1997).
https://doi.org/10.7907/rzr7-dt72
[83] D. Gottesman, ``The Heisenberg Representation of Quantum Computers,'' arXiv e-prints , quant-ph/9807006 (1998), arXiv:quant-ph/9807006 [quant-ph].
arXiv:quant-ph/9807006
[84] S. Aaronson and D. Gottesman, ``Improved simulation of stabilizer circuits,'' Phys. Rev. A 70, 052328 (2004).
https://doi.org/10.1103/PhysRevA.70.052328
[85] L. Piroli, B. Bertini, J. I. Cirac, and T. Prosen, ``Exact dynamics in dual-unitary quantum circuits,'' Phys. Rev. B 101, 094304 (2020).
https://doi.org/10.1103/PhysRevB.101.094304
[86] D. Aharonov, ``Quantum to classical phase transition in noisy quantum computers,'' Phys. Rev. A 62, 062311 (2000).
https://doi.org/10.1103/PhysRevA.62.062311
[87] M. J. Bremner, A. Montanaro, and D. J. Shepherd, ``Achieving quantum supremacy with sparse and noisy commuting quantum computations,'' Quantum 1, 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8
[88] M.-H. Yung and X. Gao, ``Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?'' arXiv e-prints , arXiv:1706.08913 (2017), arXiv:1706.08913 [quant-ph].
arXiv:1706.08913
[89] X. Gao and L. Duan, ``Efficient classical simulation of noisy quantum computation,'' arXiv e-prints , arXiv:1810.03176 (2018), arXiv:1810.03176 [quant-ph].
arXiv:1810.03176
[90] 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].
arXiv:1708.01875
[91] 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].
arXiv:cond-mat/0407066
[92] F. Verstraete and J. I. Cirac, ``Valence-bond states for quantum computation,'' Phys. Rev. A 70, 060302 (2004).
https://doi.org/10.1103/PhysRevA.70.060302
[93] N. Schuch, M. M. Wolf, F. Verstraete, and J. I. Cirac, ``Computational complexity of projected entangled pair states,'' Phys. Rev. Lett. 98, 140506 (2007).
https://doi.org/10.1103/PhysRevLett.98.140506
[94] J. Haferkamp, D. Hangleiter, J. Eisert, and M. Gluza, ``Contracting projected entangled pair states is average-case hard,'' Phys. Rev. Research 2, 013010 (2020).
https://doi.org/10.1103/PhysRevResearch.2.013010
[95] 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].
arXiv:2001.00021
[96] 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.
https://doi.org/10.1016/j.aop.2010.09.012
Cited by
[1] Yaodong Li, Yijian Zou, Paolo Glorioso, Ehud Altman, and Matthew P. A. Fisher, "Cross Entropy Benchmark for Measurement-Induced Phase Transitions", Physical Review Letters 130 22, 220404 (2023).
[2] Meng Zhang, Chao Wang, Shaojun Dong, Hao Zhang, Yongjian Han, and Lixin He, "Entanglement entropy scaling of noisy random quantum circuits in two dimensions", Physical Review A 106 5, 052430 (2022).
[3] Yuchen Guo and Shuo Yang, "Quantum Error Mitigation via Matrix Product Operators", PRX Quantum 3 4, 040313 (2022).
[4] Tibor Rakovszky, C. W. von Keyserlingk, and Frank Pollmann, "Dissipation-assisted operator evolution method for capturing hydrodynamic transport", Physical Review B 105 7, 075131 (2022).
[5] Elmer V. H. Doggen, Yuval Gefen, Igor V. Gornyi, Alexander D. Mirlin, and Dmitry G. Polyakov, "Evolution of many-body systems under ancilla quantum measurements", Physical Review B 107 21, 214203 (2023).
[6] Beatriz C. Dias, Domagoj Perković, Masudul Haque, Pedro Ribeiro, and Paul A. McClarty, "Quantum noise as a symmetry-breaking field", Physical Review B 108 6, L060302 (2023).
[7] 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).
[8] Ivan H. Deutsch, "Harnessing the Power of the Second Quantum Revolution", PRX Quantum 1 2, 020101 (2020).
[9] Oliver Lunt, Jonas Richter, and Arijeet Pal, Quantum Science and Technology 251 (2022) ISBN:978-3-031-03997-3.
[10] Zhi Li, Shengqi Sang, and Timothy H. Hsieh, "Entanglement dynamics of noisy random circuits", Physical Review B 107 1, 014307 (2023).
[11] A. Zabalo, M. J. Gullans, J. H. Wilson, R. Vasseur, A. W. W. Ludwig, S. Gopalakrishnan, David A. Huse, and J. H. Pixley, "Operator Scaling Dimensions and Multifractality at Measurement-Induced Transitions", Physical Review Letters 128 5, 050602 (2022).
[12] 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).
[13] I.A. Aloisio, G.A.L. White, C.D. Hill, and K. Modi, "Sampling Complexity of Open Quantum Systems", PRX Quantum 4 2, 020310 (2023).
[14] 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).
[15] Hai Wang, Jue Nan, Tao Zhang, Xingze Qiu, Wenlan Chen, and Xiaopeng Li, "Kernel function based quantum algorithms for finite temperature quantum simulation", Physical Review B 108 8, 085102 (2023).
[16] D. Wellnitz, G. Preisser, V. Alba, J. Dubail, and J. Schachenmayer, "Rise and Fall, and Slow Rise Again, of Operator Entanglement under Dephasing", Physical Review Letters 129 17, 170401 (2022).
[17] Weitang Li, Jonathan Allcock, Lixue Cheng, Shi-Xin Zhang, Yu-Qin Chen, Jonathan P. Mailoa, Zhigang Shuai, and Shengyu Zhang, "TenCirChem: An Efficient Quantum Computational Chemistry Package for the NISQ Era", Journal of Chemical Theory and Computation 19 13, 3966 (2023).
[18] Minzhao Liu, Junyu Liu, Yuri Alexeev, and Liang Jiang, "Estimating the randomness of quantum circuit ensembles up to 50 qubits", npj Quantum Information 8 1, 137 (2022).
[19] Changhun Oh, Liang Jiang, and Bill Fefferman, "Spoofing Cross-Entropy Measure in Boson Sampling", Physical Review Letters 131 1, 010401 (2023).
[20] 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).
[21] J. Helsen, I. Roth, E. Onorati, A.H. Werner, and J. Eisert, "General Framework for Randomized Benchmarking", PRX Quantum 3 2, 020357 (2022).
[22] Michael Kolodrubetz, "Optimality of Lindblad unfolding in measurement phase transitions", Physical Review B 107 14, L140301 (2023).
[23] M. Szyniszewski, A. Romito, and H. Schomerus, "Universality of Entanglement Transitions from Stroboscopic to Continuous Measurements", Physical Review Letters 125 21, 210602 (2020).
[24] Jordi Tura, "Imperfections Lower the Simulation Cost of Quantum Computers", Physics 13, 183 (2020).
[25] Kaelan Donatella, Zakari Denis, Alexandre Le Boité, and Cristiano Ciuti, "Continuous-time dynamics and error scaling of noisy highly entangling quantum circuits", Physical Review A 104 6, 062407 (2021).
[26] Alexander Zlokapa, Benjamin Villalonga, Sergio Boixo, and Daniel A. Lidar, "Boundaries of quantum supremacy via random circuit sampling", npj Quantum Information 9 1, 36 (2023).
[27] Meng Zhang, Chao Wang, and Yongjian Han, "Noisy Random Quantum Circuit Sampling and its Classical Simulation", Advanced Quantum Technologies 6 7, 2300030 (2023).
[28] Guillermo Preisser, David Wellnitz, Thomas Botzung, and Johannes Schachenmayer, "Comparing bipartite entropy growth in open-system matrix-product simulation methods", Physical Review A 108 1, 012616 (2023).
[29] Maurits S. J. Tepaske and David J. Luitz, "Compressed quantum error mitigation", Physical Review B 107 20, L201114 (2023).
[30] Giuliano Chiriacò, Mikheil Tsitsishvili, Dario Poletti, Rosario Fazio, and Marcello Dalmonte, "Diagrammatic method for many-body non-Markovian dynamics: Memory effects and entanglement transitions", Physical Review B 108 7, 075151 (2023).
[31] Markus Schmitt and Zala Lenarčič, "From observations to complexity of quantum states via unsupervised learning", Physical Review B 106 4, L041110 (2022).
[32] Matthew P.A. Fisher, Vedika Khemani, Adam Nahum, and Sagar Vijay, "Random Quantum Circuits", Annual Review of Condensed Matter Physics 14 1, 335 (2023).
[33] J. A. Montañez-Barrera, Michael R. von Spakovsky, Cesar E. Damian Ascencio, and Sergio Cano-Andrade, "Decoherence predictions in a superconducting quantum processor using the steepest-entropy-ascent quantum thermodynamics framework", Physical Review A 106 3, 032426 (2022).
[34] Anbang Wang, Jingning Zhang, and Ying Li, "Error-mitigated deep-circuit quantum simulation of open systems: Steady state and relaxation rate problems", Physical Review Research 4 4, 043140 (2022).
[35] Qi Zhang and Guang-Ming Zhang, "Noise-Induced Entanglement Transition in One-Dimensional Random Quantum Circuits", Chinese Physics Letters 39 5, 050302 (2022).
[36] Dmitry I. Lyakh, Thien Nguyen, Daniel Claudino, Eugene Dumitrescu, and Alexander J. McCaskey, "ExaTN: Scalable GPU-Accelerated High-Performance Processing of General Tensor Networks at Exascale", Frontiers in Applied Mathematics and Statistics 8, 838601 (2022).
[37] Aniket Rath, Vittorio Vitale, Sara Murciano, Matteo Votto, Jérôme Dubail, Richard Kueng, Cyril Branciard, Pasquale Calabrese, and Benoît Vermersch, "Entanglement Barrier and its Symmetry Resolution: Theory and Experimental Observation", PRX Quantum 4 1, 010318 (2023).
[38] Mikheil Tsitsishvili, Dario Poletti, Marcello Dalmonte, and Giuliano Chiriacò, "Measurement induced transitions in non-Markovian free fermion ladders", arXiv:2307.06624, (2023).
[39] Baptiste Anselme Martin, Thomas Ayral, François Jamet, Marko J. Rančić, and Pascal Simon, "Combining Matrix Product States and Noisy Quantum Computers for Quantum Simulation", arXiv:2305.19231, (2023).
[40] Boaz Barak, Chi-Ning Chou, and Xun Gao, "Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits", arXiv:2005.02421, (2020).
[41] 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, (2021).
[42] Yuxuan Yan, Zhenyu Du, Junjie Chen, and Xiongfeng Ma, "Limitations of Noisy Quantum Devices in Computational and Entangling Power", arXiv:2306.02836, (2023).
[43] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Fault-tolerant quantum speedup from constant depth quantum circuits", arXiv:2005.11539, (2020).
[44] Shuvro Chowdhury, Kerem Y. Camsari, and Supriyo Datta, "Emulating Quantum Interference with Generalized Ising Machines", arXiv:2007.07379, (2020).
[45] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Fault-tolerant quantum speedup from constant depth quantum circuits", Physical Review Research 2 3, 033444 (2020).
[46] Maxime Oliva, "An entanglement-aware quantum computer simulation algorithm", arXiv:2307.16870, (2023).
The above citations are from Crossref's cited-by service (last updated successfully 2023-09-21 15:36:16) and SAO/NASA ADS (last updated successfully 2023-09-21 15:36:17). 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.