Achieving quantum supremacy with sparse and noisy commuting quantum computations

Michael J. Bremner1, Ashley Montanaro2, and Dan J. Shepherd3

1Centre for Quantum Computation and Communication Technology, Centre for Quantum Software and Information, Faculty of Engineering and Information Technology, University of Technology Sydney, NSW 2007, Australia
2School of Mathematics, University of Bristol, UK
33NCSC, Hubble Road, Cheltenham, UK

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.

► BibTeX data

► References

[1] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing, 9 (4): 143-252, 2013. arXiv:1011.3245.
https://doi.org/10.1145/1993636.1993682
arXiv:1011.3245

[2] 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.
https://doi.org/10.1109/SFCS.1994.365708

[3] A. Arkhipov. BosonSampling is robust to small errors in the network matrix. Phys. Rev. A, 92: 062326, 2015. arXiv:1412.2516.
https://doi.org/10.1103/PhysRevA.92.062326
arXiv:1412.2516

[4] 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.
https://doi.org/10.1145/225058.225140

[5] 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.
https://doi.org/10.1098/rspa.2012.0686
arXiv:1207.2307

[6] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert. Architectures for quantum simulation showing quantum supremacy, 2017. arXiv:1703.00466.
arXiv:1703.00466

[7] S. Boixo, S. Isakov, V. Smelyanskiy, R. Babbush, N. Ding, Z. Jian, J. Martinis, and H. Neven. Characterizing quantum supremacy in near-term devices, 2016. arXiv:1608.00263.
arXiv:1608.00263

[8] B. Bollobás. The distribution of the maximum degree of a random graph. Discrete Mathematics, 32: 201-203, 1980.
https://doi.org/10.1016/0012-365X(80)90054-0

[9] C. Brand, H. Dell, and M. Roth. Fine-grained dichotomies for the Tutte plane and Boolean #CSP, 2016. arXiv:1606.06581.
arXiv:1606.06581

[10] 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.
https://doi.org/10.1098/rspa.2010.0301
arXiv:1005.1407

[11] 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.
https://doi.org/10.1103/PhysRevLett.117.080501
arXiv:1504.07999

[12] W. Brown and O. Fawzi. Scrambling speed of random quantum circuits, 2012. arXiv:1210.6644.
arXiv:1210.6644

[13] W. Brown and O. Fawzi. Decoupling with random quantum circuits. Comm. Math. Phys., 340 (3): 867-900, 2015. arXiv:1307.0632.
https://doi.org/10.1007/s00220-015-2470-1
arXiv:1307.0632

[14] 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.
https://doi.org/10.1109/FOCS.2006.50
arXiv:quant-ph/0604141

[15] 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.
https://doi.org/10.1007/978-3-662-47672-7_31
arXiv:1511.02910

[16] R. Diestel. Graph Theory. Springer, 2010.

[17] D. Dubhashi and A. Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.

[18] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm, 2014. arXiv:1411.4028.
arXiv:1411.4028

[19] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem, 2014. arXiv:1412.6062.
arXiv:1412.6062

[20] E. Farhi and A. Harrow. Quantum supremacy through the Quantum Approximate Optimization Algorithm, 2016. arXiv:1602.07674.
arXiv:1602.07674

[21] K. Fujii and S. Tamate. Computational quantum-classical boundary of noisy commuting quantum circuits. Scientific Reports, 6: 25598, 2016. arXiv:1406.6932.
https://doi.org/10.1038/srep25598
arXiv:1406.6932

[22] 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.
https://doi.org/10.1103/PhysRevLett.118.040502
arXiv:1607.04947

[23] 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.
https://doi.org/10.1088/2058-9565/2/1/015004
arXiv:1602.00703

[24] G. Kalai. The quantum computer puzzle. Notices of the AMS, 63 (5): 508-516, 2016. arXiv:1605.00992.
https://doi.org/10.1090/noti1380
arXiv:1605.00992

[25] G. Kalai and G. Kindler. Gaussian noise sensitivity and BosonSampling, 2014. arXiv:1409.3093.
arXiv:1409.3093

[26] 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.
https://doi.org/10.1007/978-3-540-70575-8_69
arXiv:0802.1464

[27] E. Kushilevitz and Y. Mansour. Learning decision trees using the Fourier spectrum. In Proc. 23rd Annual ACM Symp. Theory of Computing, 1991, pages 455-464.
https://doi.org/10.1137/0222080

[28] A. Leverrier and R. García-Patrón. Analysis of circuit imperfections in BosonSampling. Quantum Inf. Comput., 15: 0489-0512, 2015. arXiv:1309.4687.
arXiv:1309.4687

[29] I. Markov and Y. Shi. Simulating quantum computation by contracting tensor networks. SIAM J. Comput., 38: 963-981, 2008. quant-ph/​0511069.
https://doi.org/10.1137/050644756
arXiv:quant-ph/0511069

[30] M. Marvian and D. Lidar. Error suppression for Hamiltonian-based quantum computation using subsystem codes, 2016. arXiv:1606.03795.
arXiv:1606.03795

[31] 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.
https://doi.org/10.1103/PhysRevLett.112.130502
arXiv:1312.2496

[32] R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.

[33] J. Preskill. Quantum computing and the entanglement frontier, 2012. arXiv:1203.5813.
arXiv:1203.5813

[34] 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.
https://doi.org/10.1103/PhysRevX.6.021039
arXiv:1511.06526

[35] A. Razborov. An upper bound on the threshold quantum decoherence rate. Quantum Inf. Comput., 4 (3): 222-228, 2004. quant-ph/​0310136.
arXiv:quant-ph/0310136

[36] T. Richardson and R. Urbanke. Modern Coding Theory. Cambridge University Press, 2008.

[37] C. Schnorr and A. Shamir. An optimal sorting algorithm for mesh connected computers. In Proc. 18th Annual ACM Symp. Theory of Computing, 1986, pages 255-263.
https://doi.org/10.1145/12130.12156

[38] M. Schwarz and M. Van den Nest. Simulating quantum circuits with sparse output distributions, 2013. arXiv:1310.6749.
arXiv:1310.6749

[39] 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.
https://doi.org/10.1103/PhysRevA.91.063842
arXiv:1501.00850

[40] D. Shepherd. Binary matroids and quantum probability distributions, 2010. arXiv:1005.1744.
arXiv:1005.1744

[41] D. Shepherd and M. J. Bremner. Temporally unstructured quantum computation. Proc. Roy. Soc. Ser. A, 465 (2105): 1413-1439, 2009. arXiv:0809.0847.
https://doi.org/10.1098/rspa.2008.0443
arXiv:0809.0847

[42] D. R. Simon. On the power of quantum computation. SIAM J. Comput., 26: 1474-1483, 1997.
https://doi.org/10.1137/S0097539796298637

[43] S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20 (5): 865-877, 1991.
https://doi.org/10.1137/0220053

[44] S. Virmani, S. Huelga, and M. Plenio. Classical simulability, entanglement breaking, and quantum computation thresholds. Phys. Rev. A, 71: 042328, 2005. quant-ph/​0408076.
https://doi.org/10.1103/PhysRevA.71.042328
arXiv:quant-ph/0408076

Cited by

[1] Dax Enshan Koh, "Further extensions of Clifford circuits and their classical simulation complexities", arXiv:1512.07892 (2015).

[2] Theodoros Kapourniotis and Animesh Datta, "Nonadaptive fault-tolerant verification of quantum supremacy with noise", arXiv:1703.09568 (2017).

[3] Scott Aaronson and Lijie Chen, "Complexity-Theoretic Foundations of Quantum Supremacy Experiments", arXiv:1612.05903 (2016).

[4] Hang Li, Xun Gao, Tao Xin, Man-Hong Yung, and Guilu Long, "Experimental Study of Forrelation in Nuclear Spins", arXiv:1612.01652 (2016).

[5] Alex Neville, Chris Sparrow, Raphaël Clifford, Eric Johnston, Patrick M. Birchall, Ashley Montanaro, and Anthony Laing, "No imminent quantum supremacy by boson sampling", arXiv:1705.00686 (2017).

[6] Kyle E. C. Booth, Minh Do, J. Christopher Beck, Eleanor Rieffel, Davide Venturelli, and Jeremy Frank, "Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation", arXiv:1803.06775 (2018).

[7] Tomoyuki Morimae, Keisuke Fujii, and Harumichi Nishimura, "Power of one nonclean qubit", Physical Review A 95 4, 042336 (2017).

[8] Man-Hong Yung and Xun Gao, "Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?", arXiv:1706.08913 (2017).

[9] Daniel Mills, Anna Pappa, Theodoros Kapourniotis, and Elham Kashefi, "Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation", arXiv:1704.01998 (2017).

[10] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas, "From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz", arXiv:1709.03489 (2017).

[11] Keisuke Fujii, "Noise Threshold of Quantum Supremacy", arXiv:1610.03632 (2016).

[12] Aram Harrow and Saeed Mehraban, "Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates", arXiv:1809.06957 (2018).

[13] Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, and Hartmut Neven, "Simulation of low-depth quantum circuits as complex undirected graphical models", arXiv:1712.05384 (2017).

[14] Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven, "Characterizing Quantum Supremacy in Near-Term Devices", arXiv:1608.00263 (2016).

[15] Mithuna Yoganathan, Richard Jozsa, and Sergii Strelchuk, "Quantum advantage of unitary Clifford circuits with magic state inputs", arXiv:1806.03200 (2018).

[16] A. P. Lund, Michael J. Bremner, and T. C. Ralph, "Quantum sampling problems, BosonSampling and quantum supremacy", npj Quantum Information 3, 15 (2017).

[17] Sergio Boixo, Vadim N. Smelyanskiy, and Hartmut Neven, "Fourier analysis of sampling from noisy chaotic quantum circuits", arXiv:1708.01875 (2017).

[18] Xun Gao, Sheng-Tao Wang, and L. -M. Duan, "Quantum Supremacy for Simulating a Translation-Invariant Ising Spin Model", Physical Review Letters 118 4, 040502 (2017).

[19] Daniel Mills, Anna Pappa, Theodoros Kapourniotis, and Elham Kashefi, "Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)", Electronic Proceedings in Theoretical Computer Science 266, 209 (2018).

[20] Sergey Bravyi, David Gosset, and Robert König, "Quantum advantage with shallow circuits", Science 362 6412, 308 (2018).

[21] Aram W. Harrow and Ashley Montanaro, "Quantum computational supremacy", Nature 549 7671, 203 (2017).

[22] Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani, "Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error", Physical Review Letters 120 20, 200502 (2018).

[23] Jonathan Olson, "The role of complexity theory in quantum optics—a tutorial for BosonSampling", Journal of Optics 20 12, 123501 (2018).

[24] Alexandra E. Moylett and Peter S. Turner, "Quantum simulation of partially distinguishable boson sampling", Physical Review A 97 6, 062329 (2018).

[25] Yosi Atia and Dorit Aharonov, "Fast-forwarding of Hamiltonians and exponentially precise measurements", Nature Communications 8 1, 1572 (2017).

[26] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani, "On the complexity and verification of quantum random circuit sampling", Nature Physics 15 2, 159 (2019).

[27] Juan Miguel Arrazola, Eleni Diamanti, and Iordanis Kerenidis, "Quantum superiority for verifying NP-complete problems with linear optics", npj Quantum Information 4 1, 56 (2018).

[28] Tameem Albash, Victor Martin-Mayor, and Itay Hen, "Temperature Scaling Law for Quantum Annealing Optimizers", Physical Review Letters 119 11, 110502 (2017).

[29] Alex Neville, Chris Sparrow, Raphaël Clifford, Eric Johnston, Patrick M. Birchall, Ashley Montanaro, and Anthony Laing, "Classical boson sampling algorithms with superior performance to near-term experiments", Nature Physics 13 12, 1153 (2017).

[30] Bartłomiej Gardas and Sebastian Deffner, "Quantum fluctuation theorem for error diagnostics in quantum annealers", Scientific Reports 8 1, 17191 (2018).

[31] Laszlo Gyongyosi and Sandor Imre, "A Survey on quantum computing technology", Computer Science Review 31, 51 (2019).

[32] A. Elben, B. Vermersch, M. Dalmonte, J. I. Cirac, and P. Zoller, "Rényi Entropies from Random Quenches in Atomic Hubbard and Spin Models", Physical Review Letters 120 5, 050406 (2018).

[33] Vedran Dunjko and Hans J Briegel, "Machine learning & artificial intelligence in the quantum domain: a review of recent progress", Reports on Progress in Physics 81 7, 074001 (2018).

[34] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert, "Architectures for Quantum Simulation Showing a Quantum Speedup", Physical Review X 8 2, 021010 (2018).

[35] Jacob Miller, Stephen Sanders, and Akimasa Miyake, "Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification", Physical Review A 96 6, 062320 (2017).

[36] Iris Agresti, Niko Viggianiello, Fulvio Flamini, Nicolò Spagnolo, Andrea Crespi, Roberto Osellame, Nathan Wiebe, and Fabio Sciarrino, "Pattern Recognition Techniques for Boson Sampling Validation", Physical Review X 9 1, 011013 (2019).

[37] Juan Miguel Arrazola, Thomas R. Bromley, and Patrick Rebentrost, "Quantum approximate optimization with Gaussian boson sampling", Physical Review A 98 1, 012322 (2018).

[38] 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, and J. M. Martinis, "A blueprint for demonstrating quantum supremacy with superconducting qubits", Science 360 6385, 195 (2018).

[39] Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven, "Characterizing quantum supremacy in near-term devices", Nature Physics 14 6, 595 (2018).

[40] Man-Hong Yung, "Quantum supremacy: some fundamental concepts", National Science Review (2018).

[41] Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert, "Anticoncentration theorems for schemes showing a quantum speedup", Quantum 2, 65 (2018).

The above citations are from Crossref's cited-by service (last updated 2019-02-20 19:30:38) and SAO/NASA ADS (last updated 2019-02-20 19:30:40). The list may be incomplete as not all publishers provide suitable and complete citation data.

1 thought on “Achieving quantum supremacy with sparse and noisy commuting quantum computations

  1. Pingback: On experimentally relevant quantum speedups – Quantum