The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.
 N. Alon, A. Frieze, and D. Welsh. Polynomial time randomized approximation schemes for the Tutte polynomial of dense graphs. In Proc. 35th Annual Symp. Foundations of Computer Science, 1994, page 24.
 S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. Journal of Computer and System Sciences, 58: 193-210, 1999.
 R. Beals, S. Brierley, O. Gray, A. Harrow, S. Kutin, N. Linden, D. Shepherd, and M. Stather. Efficient distributed quantum computing. Proc. Roy. Soc. A, 469: 20120686, 2013. arXiv:1207.2307.
 M. Bremner, R. Jozsa, and D. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Roy. Soc. Ser. A, 467 (2126): 459-472, 2011. arXiv:1005.1407.
 M. Bremner, A. Montanaro, and D. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett., 117: 080501, 2016. arXiv:1504.07999.
 H. Buhrman, R. Cleve, M. Laurent, N. Linden, A. Schrijver, and F. Unger. New limits on fault-tolerant quantum computation. In Proc. 47th Annual Symp. Foundations of Computer Science, 2006, pages 411-419. quant-ph/0604141.
 R. Curticapean. Block interpolation: A framework for tight exponential-time counting complexity. In Proc. 42nd International Conference on Automata, Languages and Programming (ICALP'15), 2015, pages 380-392. arXiv:1511.02910.
 R. Diestel. Graph Theory. Springer, 2010.
 D. Dubhashi and A. Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.
 K. Fujii and S. Tamate. Computational quantum-classical boundary of noisy commuting quantum circuits. Scientific Reports, 6: 25598, 2016. arXiv:1406.6932.
 X. Gao, S.-T. Wang, and L.-M. Duan. Quantum supremacy for simulating a translation-invariant Ising spin model. Phys. Rev. Lett., 118: 040502, 2017. arXiv:1607.04947.
 D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert. Direct certification of a class of quantum simulations. Quantum Science and Technology, 1 (2), 2017. arXiv:1602.00703.
 J. Kempe, O. Regev, F. Unger, and R. de Wolf. Upper bounds on the noise threshold for fault-tolerant quantum computing. In Proc. 35th International Conference on Automata, Languages and Programming (ICALP'08), 2008, pages 845-856. arXiv:0802.1464.
 I. Markov and Y. Shi. Simulating quantum computation by contracting tensor networks. SIAM J. Comput., 38: 963-981, 2008. quant-ph/0511069.
 T. Morimae, K. Fujii, and J. Fitzsimons. On the hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett., 112: 130502, 2014. arXiv:1312.2496.
 R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.
 S. Rahimi-Keshari, T. Ralph, and C. Caves. Sufficient conditions for efficient classical simulation of quantum optics. Phys. Rev. X, 6: 021039, 2016. arXiv:1511.06526.
 T. Richardson and R. Urbanke. Modern Coding Theory. Cambridge University Press, 2008.
 V. Shchesnovich. Tight bound on trace distance between a realistic device with partially indistinguishable bosons and the ideal BosonSampling. Phys. Rev. A, 91: 063842, 2015. arXiv:1501.00850.
 D. Shepherd and M. J. Bremner. Temporally unstructured quantum computation. Proc. Roy. Soc. Ser. A, 465 (2105): 1413-1439, 2009. arXiv:0809.0847.
 S. Virmani, S. Huelga, and M. Plenio. Classical simulability, entanglement breaking, and quantum computation thresholds. Phys. Rev. A, 71: 042328, 2005. quant-ph/0408076.
 Daniel Mills, Anna Pappa, Theodoros Kapourniotis, Elham Kashefi, "Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)", Electronic Proceedings in Theoretical Computer Science 266, 209 (2018).
 Sergey Bravyi, David Gosset, Robert König, "Quantum advantage with shallow circuits", Science 362, 308 (2018).
 Aram W. Harrow, Ashley Montanaro, "Quantum computational supremacy", Nature 549, 203 (2017).
 Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani, "Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error", Physical Review Letters 120, 200502 (2018).
 Jonathan Olson, "The role of complexity theory in quantum optics—a tutorial for BosonSampling", Journal of Optics 20, 123501 (2018).
 Alexandra E. Moylett, Peter S. Turner, "Quantum simulation of partially distinguishable boson sampling", Physical Review A 97, 062329 (2018).
 Yosi Atia, Dorit Aharonov, "Fast-forwarding of Hamiltonians and exponentially precise measurements", Nature Communications 8, 1572 (2017).
 Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh Vazirani, "On the complexity and verification of quantum random circuit sampling", Nature Physics (2018).
 Juan Miguel Arrazola, Eleni Diamanti, Iordanis Kerenidis, "Quantum superiority for verifying NP-complete problems with linear optics", npj Quantum Information 4, 56 (2018).
 Tameem Albash, Victor Martin-Mayor, Itay Hen, "Temperature Scaling Law for Quantum Annealing Optimizers", Physical Review Letters 119, 110502 (2017).
 Alex Neville, Chris Sparrow, Raphaël Clifford, Eric Johnston, Patrick M. Birchall, Ashley Montanaro, Anthony Laing, "Classical boson sampling algorithms with superior performance to near-term experiments", Nature Physics 13, 1153 (2017).
 Bartłomiej Gardas, Sebastian Deffner, "Quantum fluctuation theorem for error diagnostics in quantum annealers", Scientific Reports 8, 17191 (2018).
 A. Elben, B. Vermersch, M. Dalmonte, J. I. Cirac, P. Zoller, "Rényi Entropies from Random Quenches in Atomic Hubbard and Spin Models", Physical Review Letters 120, 050406 (2018).
 Vedran Dunjko, Hans J Briegel, "Machine learning & artificial intelligence in the quantum domain: a review of recent progress", Reports on Progress in Physics 81, 074001 (2018).
 Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, Jens Eisert, "Architectures for Quantum Simulation Showing a Quantum Speedup", Physical Review X 8, 021010 (2018).
 Jacob Miller, Stephen Sanders, Akimasa Miyake, "Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification", Physical Review A 96, 062320 (2017).
 Juan Miguel Arrazola, Thomas R. Bromley, Patrick Rebentrost, "Quantum approximate optimization with Gaussian boson sampling", Physical Review A 98, 012322 (2018).
 C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya, R. Barends, B. Burkett, Y. Chen, Z. Chen, A. Fowler, B. Foxen, M. Giustina, R. Graff, E. Jeffrey, T. Huang, J. Kelly, P. Klimov, E. Lucero, J. Mutus, M. Neeley, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, H. Neven, J. M. Martinis, "A blueprint for demonstrating quantum supremacy with superconducting qubits", Science 360, 195 (2018).
 Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, Hartmut Neven, "Characterizing quantum supremacy in near-term devices", Nature Physics 14, 595 (2018).
 Man-Hong Yung, "Quantum supremacy: some fundamental concepts", National Science Review (2018).
 Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, Jens Eisert, "Anticoncentration theorems for schemes showing a quantum speedup", Quantum 2, 65 (2018).
(The above data is from Crossref's cited-by service. Unfortunately not all publishers provide suitable and complete citation data so that some citing works or bibliographic details may be missing.)
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.