Notice: Undefined index: date in /home/www/wordpress/wp-content/plugins/o3po/includes/class-o3po-arxiv.php on line 189

Notice: Undefined index: size in /home/www/wordpress/wp-content/plugins/o3po/includes/class-o3po-arxiv.php on line 190

Notice: Undefined index: date in /home/www/wordpress/wp-content/plugins/o3po/includes/class-o3po-arxiv.php on line 189

Notice: Undefined index: size in /home/www/wordpress/wp-content/plugins/o3po/includes/class-o3po-arxiv.php on line 190

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

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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.

[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.

[3] A. Arkhipov. BosonSampling is robust to small errors in the network matrix. Phys. Rev. A, 92: 062326, 2015. 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.

[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.

[6] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert. Architectures for quantum simulation showing quantum supremacy, 2017. 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.

[8] B. Bollobás. The distribution of the maximum degree of a random graph. Discrete Mathematics, 32: 201–203, 1980.

[9] C. Brand, H. Dell, and M. Roth. Fine-grained dichotomies for the Tutte plane and Boolean #CSP, 2016. 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.

[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.

[12] W. Brown and O. Fawzi. Scrambling speed of random quantum circuits, 2012. 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.

[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.

[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.

[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.

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

[20] E. Farhi and A. Harrow. Quantum supremacy through the Quantum Approximate Optimization Algorithm, 2016. 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.

[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.

[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.

[24] G. Kalai. The quantum computer puzzle. Notices of the AMS, 63 (5): 508–516, 2016. arXiv:1605.00992.

[25] G. Kalai and G. Kindler. Gaussian noise sensitivity and BosonSampling, 2014. 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.

[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.

[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.

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

[30] M. Marvian and D. Lidar. Error suppression for Hamiltonian-based quantum computation using subsystem codes, 2016. 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.

[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.

[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.

[35] A. Razborov. An upper bound on the threshold quantum decoherence rate. Quantum Inf. Comput., 4 (3): 222–228, 2004. 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.

[38] M. Schwarz and M. Van den Nest. Simulating quantum circuits with sparse output distributions, 2013. 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.

[40] D. Shepherd. Binary matroids and quantum probability distributions, 2010. 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.

[42] D. R. Simon. On the power of quantum computation. SIAM J. Comput., 26: 1474–1483, 1997.

[43] S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20 (5): 865–877, 1991.

[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.

Cited by

[1] Benjamin Villalonga, Sergio Boixo, Bron Nelson, Christopher Henze, Eleanor Rieffel, Rupak Biswas, and Salvatore Mandrà, "A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware", npj Quantum Information 5 1, 86 (2019).

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

[3] Iskren Vankov, Daniel Mills, Petros Wallden, and Elham Kashefi, "Methods for classically simulating noisy networked quantum architectures", Quantum Science and Technology 5 1, 014001 (2020).

[4] James R. Seddon, Bartosz Regula, Hakop Pashayan, Yingkai Ouyang, and Earl T. Campbell, "Quantifying Quantum Speedups: Improved Classical Simulation From Tighter Magic Monotones", PRX Quantum 2 1, 010345 (2021).

[5] 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", Algorithms 12 2, 34 (2019).

[6] Daniel Stilck França and Raul García-Patrón, "Limitations of optimization algorithms on noisy quantum devices", Nature Physics 17 11, 1221 (2021).

[7] 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).

[8] 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).

[9] Nolan J. Coble and Matthew Coudron, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) 598 (2022) ISBN:978-1-6654-2055-6.

[10] Mansoor A. Khan, Muhammad N. Aman, and Biplab Sikdar, "Beyond Bits: A Review of Quantum Embedding Techniques for Efficient Information Processing", IEEE Access 12, 46118 (2024).

[11] Brian Barch, Razieh Mohseninia, and Daniel Lidar, "Low overhead universality and quantum supremacy using only Z control", Physical Review Research 3 3, 033207 (2021).

[12] Daniel Mills, Seyon Sivarajah, Travis L. Scholten, and Ross Duncan, "Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack", Quantum 5, 415 (2021).

[13] Vojtěch Havlíček, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta, "Supervised learning with quantum-enhanced feature spaces", Nature 567 7747, 209 (2019).

[14] Theodoros Kapourniotis and Animesh Datta, "Nonadaptive fault-tolerant verification of quantum supremacy with noise", Quantum 3, 164 (2019).

[15] Shihao Zhang, Junda Wu, and Lvzhou Li, "Characterization, synthesis, and optimization of quantum circuits over multiple-control Z -rotation gates: A systematic study", Physical Review A 108 2, 022603 (2023).

[16] Xi Chen, Bin Cheng, Zhaokai Li, Xinfang Nie, Nengkun Yu, Man-Hong Yung, and Xinhua Peng, "Experimental cryptographic verification for near-term quantum cloud computing", Science Bulletin 66 1, 23 (2021).

[17] Mariami Gachechiladze, Otfried Gühne, and Akimasa Miyake, "Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states", Physical Review A 99 5, 052304 (2019).

[18] Sergey Bravyi, David Gosset, and Yinchen Liu, Proceedings of the 56th Annual ACM Symposium on Theory of Computing 561 (2024) ISBN:9798400703836.

[19] Alexandra Nagy and Vincenzo Savona, "Variational Quantum Monte Carlo Method with a Neural-Network Ansatz for Open Quantum Systems", Physical Review Letters 122 25, 250501 (2019).

[20] Kathleen E. Hamilton, Tyler Kharazi, Titus Morris, Alexander J. McCaskey, Ryan S. Bennink, and Raphael C. Pooser, 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) 430 (2020) ISBN:978-1-7281-8969-7.

[21] Louis Paletta, Anthony Leverrier, Alain Sarlette, Mazyar Mirrahimi, and Christophe Vuillot, "Robust sparse IQP sampling in constant depth", Quantum 8, 1337 (2024).

[22] Hakop Pashayan, Stephen D. Bartlett, and David Gross, "From estimation of quantum probabilities to simulation of quantum circuits", Quantum 4, 223 (2020).

[23] 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).

[24] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao, and Shashank Virmani, "Efficient classical simulation of cluster state quantum circuits with alternative inputs", Quantum 8, 1243 (2024).

[25] Quantum Computing 125 (2023) ISBN:9781394157815.

[26] 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).

[27] Nishad Maskara, Abhinav Deshpande, Adam Ehrenberg, Minh C. Tran, Bill Fefferman, and Alexey V. Gorshkov, "Complexity Phase Diagram for Interacting and Long-Range Bosonic Hamiltonians", Physical Review Letters 129 15, 150604 (2022).

[28] Dolev Bluvstein, Simon J. Evered, Alexandra A. Geim, Sophie H. Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, J. Pablo Bonilla Ataides, Nishad Maskara, Iris Cong, Xun Gao, Pedro Sales Rodriguez, Thomas Karolyshyn, Giulia Semeghini, Michael J. Gullans, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin, "Logical quantum processor based on reconfigurable atom arrays", Nature 626 7997, 58 (2024).

[29] Sebastian Leontica and David Amaro, "Exploring the neighborhood of 1-layer QAOA with instantaneous quantum polynomial circuits", Physical Review Research 6 1, 013071 (2024).

[30] Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani, Proceedings of the 55th Annual ACM Symposium on Theory of Computing 945 (2023) ISBN:9781450399135.

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

[32] 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).

[33] Thorsten B. Wahl and Sergii Strelchuk, "Simulating Quantum Circuits Using Efficient Tensor Network Contraction Algorithms with Subexponential Upper Bound", Physical Review Letters 131 18, 180601 (2023).

[34] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão, "Random Quantum Circuits Anticoncentrate in Log Depth", PRX Quantum 3 1, 010333 (2022).

[35] Nathan Killoran, Josh Izaac, Nicolás Quesada, Ville Bergholm, Matthew Amy, and Christian Weedbrook, "Strawberry Fields: A Software Platform for Photonic Quantum Computing", Quantum 3, 129 (2019).

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

[37] Man-Hong Yung, Xun Gao, and Joonsuk Huh, " Universal bound on sampling bosons in linear optics and its computational implications", National Science Review 6 4, 719 (2019).

[38] Brian Coyle, Daniel Mills, Vincent Danos, and Elham Kashefi, "The Born supremacy: quantum advantage and training of an Ising Born machine", npj Quantum Information 6 1, 60 (2020).

[39] 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).

[40] Niraj Kumar, Iordanis Kerenidis, and Eleni Diamanti, "Experimental demonstration of quantum advantage for one-way communication complexity surpassing best-known classical protocol", Nature Communications 10 1, 4152 (2019).

[41] J. Haferkamp, D. Hangleiter, A. Bouland, B. Fefferman, J. Eisert, and J. Bermejo-Vega, "Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics", Physical Review Letters 125 25, 250501 (2020).

[42] 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).

[43] V. S. Shchesnovich, "On the classical complexity of sampling from quantum interference of indistinguishable bosons", International Journal of Quantum Information 18 07, 2050044 (2020).

[44] 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).

[45] Stuart Hadfield, "On the Representation of Boolean and Real Functions as Hamiltonians for Quantum Computing", ACM Transactions on Quantum Computing 2 4, 1 (2021).

[46] Jacob D. Biamonte, Mauro E. S. Morales, and Dax Enshan Koh, "Entanglement scaling in quantum advantage benchmarks", Physical Review A 101 1, 012349 (2020).

[47] Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel, "Quantum advantage with noisy shallow circuits", Nature Physics 16 10, 1040 (2020).

[48] Turbasu Chatterjee, Arnav Das, Shah Ishmam Mohtashim, Amit Saha, and Amlan Chakrabarti, "Qurzon: A Prototype for a Divide and Conquer-Based Quantum Compiler for Distributed Quantum Systems", SN Computer Science 3 4, 323 (2022).

[49] Paul Konstantin Fährmann, Johannes Jakob Meyer, and Jens Eisert, Chancen und Risiken von Quantentechnologien 47 (2022) ISBN:978-3-658-37533-1.

[50] Y. S. Teo, "Robustness of optimized numerical estimation schemes for noisy variational quantum algorithms", Physical Review A 109 1, 012620 (2024).

[51] Balamurugan K S, Sivakami A, Mathankumar M, Yalla Jnan Devi Satya prasad, and Irfan Ahmad, "Quantum computing basics, applications and future perspectives", Journal of Molecular Structure 1308, 137917 (2024).

[52] 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).

[53] Leonardo Novo, Juani Bermejo-Vega, and Raúl García-Patrón, "Quantum advantage from energy measurements of many-body quantum systems", Quantum 5, 465 (2021).

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

[55] Fabio Valerio Massoli, Lucia Vadicamo, Giuseppe Amato, and Fabrizio Falchi, "A Leap among Quantum Computing and Quantum Neural Networks: A Survey", ACM Computing Surveys 55 5, 1 (2023).

[56] Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) 1308 (2022) ISBN:978-1-6654-2055-6.

[57] 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).

[58] Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang, "Effects of quantum resources and noise on the statistical complexity of quantum circuits", Quantum Science and Technology 8 2, 025013 (2023).

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

[60] Mohammadreza Noormandipour and Hanchen Wang, ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 8607 (2022) ISBN:978-1-6654-0540-9.

[61] Ramis Movassagh, "The hardness of random quantum circuits", Nature Physics 19 11, 1719 (2023).

[62] Laura Clinton, Johannes Bausch, and Toby Cubitt, "Hamiltonian simulation algorithms for near-term quantum hardware", Nature Communications 12 1, 4989 (2021).

[63] John C. Napp, Rolando L. La Placa, Alexander M. Dalzell, Fernando G. S. L. Brandão, and Aram W. Harrow, "Efficient Classical Simulation of Random Shallow 2D Quantum Circuits", Physical Review X 12 2, 021021 (2022).

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

[65] Michael Streif and Martin Leib, "Forbidden subspaces for level-1 quantum approximate optimization algorithm and instantaneous quantum polynomial circuits", Physical Review A 102 4, 042416 (2020).

[66] Rawad Mezher, James Mills, and Elham Kashefi, "Mitigating errors by quantum verification and postselection", Physical Review A 105 5, 052608 (2022).

[67] Ying Li, Ze-Yao Han, Chao-Jian Li, Jin Lü, Xiao Yuan, and Bu-Jiao Wu, "Review on quantum advantages of sampling problems", Acta Physica Sinica 70 21, 210201 (2021).

[68] Daniel Stilck França and Raul Garcia-Patron, "A game of quantum advantage: linking verification and simulation", Quantum 6, 753 (2022).

[69] 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).

[70] Tameem Albash, Victor Martin-Mayor, and Itay Hen, "Analog errors in Ising machines", Quantum Science and Technology 4 2, 02LT03 (2019).

[71] Antonio D. Corcoles, Abhinav Kandala, Ali Javadi-Abhari, Douglas T. McClure, Andrew W. Cross, Kristan Temme, Paul D. Nation, Matthias Steffen, and Jay M. Gambetta, "Challenges and Opportunities of Near-Term Quantum Computing Systems", Proceedings of the IEEE 108 8, 1338 (2020).

[72] Man-Hong Yung, "Quantum supremacy: some fundamental concepts", National Science Review 6 1, 22 (2019).

[73] Min-Gang Zhou, Xiao-Yu Cao, Yu-Shuo Lu, Yang Wang, Yu Bao, Zhao-Ying Jia, Yao Fu, Hua-Lei Yin, and Zeng-Bing Chen, "Experimental Quantum Advantage with Quantum Coupon Collector", Research 2022, 2022/9798679 (2022).

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

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

[76] Martin Kliesch and Ingo Roth, "Theory of Quantum System Certification", PRX Quantum 2 1, 010201 (2021).

[77] Sukhpal Singh Gill, Adarsh Kumar, Harvinder Singh, Manmeet Singh, Kamalpreet Kaur, Muhammad Usman, and Rajkumar Buyya, "Quantum computing: A taxonomy, systematic review and future directions", Software: Practice and Experience 52 1, 66 (2022).

[78] Ewout van den Berg, Sergey Bravyi, Jay M. Gambetta, Petar Jurcevic, Dmitri Maslov, and Kristan Temme, "Single-shot error mitigation by coherent Pauli checks", Physical Review Research 5 3, 033193 (2023).

[79] Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D. Lukin, Boaz Barak, and Soonwon Choi, "Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage", PRX Quantum 5 1, 010334 (2024).

[80] Valery Shchesnovich, "Distinguishing noisy boson sampling from classical simulations", Quantum 5, 423 (2021).

[81] Dominik Hangleiter, Martin Kliesch, Jens Eisert, and Christian Gogolin, "Sample Complexity of Device-Independently Certified “Quantum Supremacy”", Physical Review Letters 122 21, 210502 (2019).

[82] Kouhei Nakaji and Naoki Yamamoto, "Quantum semi-supervised generative adversarial network for enhanced data classification", Scientific Reports 11 1, 19649 (2021).

[83] Daiqin Su, Robert Israel, Kunal Sharma, Haoyu Qi, Ish Dhand, and Kamil Brádler, "Error mitigation on a near-term quantum photonic device", Quantum 5, 452 (2021).

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

[85] Kaifeng Bu and Dax Enshan Koh, "Efficient Classical Simulation of Clifford Circuits with Nonstabilizer Input States", Physical Review Letters 123 17, 170502 (2019).

[86] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao, "Expressive power of parametrized quantum circuits", Physical Review Research 2 3, 033125 (2020).

[87] Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) 995 (2019) ISBN:978-1-7281-4952-3.

[88] 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).

[89] Dominik Hangleiter and Jens Eisert, "Computational advantage of quantum random sampling", Reviews of Modern Physics 95 3, 035001 (2023).

[90] Changhun Oh, Liang Jiang, and Bill Fefferman, "Spoofing Cross-Entropy Measure in Boson Sampling", Physical Review Letters 131 1, 010401 (2023).

[91] Mithuna Yoganathan, Richard Jozsa, and Sergii Strelchuk, "Quantum advantage of unitary Clifford circuits with magic state inputs", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475 2225, 20180427 (2019).

[92] Sinan Bugu, Fatih Ozaydin, and Tetsuo Kodera, "Surpassing the classical limit in magic square game with distant quantum dots coupled to optical cavities", Scientific Reports 10 1, 22202 (2020).

[93] 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).

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

[95] 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).

[96] Michael de Oliveira, Luís S. Barbosa, and Ernesto F. Galvão, "Quantum advantage in temporally flat measurement-based quantum computation", Quantum 8, 1312 (2024).

[97] Jinkai Tian, Xiaoyu Sun, Yuxuan Du, Shanshan Zhao, Qing Liu, Kaining Zhang, Wei Yi, Wanrong Huang, Chaoyue Wang, Xingyao Wu, Min-Hsiu Hsieh, Tongliang Liu, Wenjing Yang, and Dacheng Tao, "Recent Advances for Quantum Neural Networks in Generative Learning", IEEE Transactions on Pattern Analysis and Machine Intelligence 45 10, 12321 (2023).

[98] Kyungjoo Noh, Liang Jiang, and Bill Fefferman, "Efficient classical simulation of noisy random quantum circuits in one dimension", Quantum 4, 318 (2020).

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

[100] Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho, and Salvatore Mandrà, "Establishing the quantum supremacy frontier with a 281 Pflop/s simulation", Quantum Science and Technology 5 3, 034003 (2020).

[101] Israel Griol-Barres, Sergio Milla, Antonio Cebrián, Yashar Mansoori, and José Millet, "Variational Quantum Circuits for Machine Learning. An Application for the Detection of Weak Signals", Applied Sciences 11 14, 6427 (2021).

[102] 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).

[103] Federico Centrone, Niraj Kumar, Eleni Diamanti, and Iordanis Kerenidis, "Experimental demonstration of quantum advantage for NP verification with limited information", Nature Communications 12 1, 850 (2021).

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

[105] 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).

[106] 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).

[107] 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).

[108] Ramis Movassagh, "Quantum supremacy and random circuits", arXiv:1909.06210, (2019).

[109] Davide Venturelli, Minh Do, Eleanor Rieffel, and Jeremy Frank, "Compiling quantum circuits to realistic hardware architectures using temporal planners", Quantum Science and Technology 3 2, 025004 (2018).

[110] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão, "Random quantum circuits anti-concentrate in log depth", arXiv:2011.12277, (2020).

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

[112] Yasuhiro Kondo, Ryuhei Mori, and Ramis Movassagh, "Quantum supremacy and hardness of estimating output probabilities of quantum circuits", arXiv:2102.01960, (2021).

[113] 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).

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

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

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

[117] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Efficient approximate unitary t-designs from partially invertible universal sets and their application to quantum speedup", arXiv:1905.01504, (2019).

[118] Hang Li, Xun Gao, Tao Xin, Man-Hong Yung, and Guilu Long, "Experimental study of Forrelation in nuclear spins", Science Bulletin 62 7, 497 (2017).

[119] Martin Kliesch and Ingo Roth, "Theory of quantum system certification: a tutorial", arXiv:2010.05925, (2020).

[120] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Fault-tolerant quantum speedup from constant depth quantum circuits", arXiv:2005.11539, (2020).

[121] 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).

[122] Bhupesh Bishnoi, "Quantum Computation", arXiv:2006.02799, (2020).

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

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

[125] Marcel Hinsche, Marios Ioannou, Sofiene Jerbi, Lorenzo Leone, Jens Eisert, and Jose Carrasco, "Efficient distributed inner product estimation via Pauli sampling", arXiv:2405.06544, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-25 08:22:25) and SAO/NASA ADS (last updated successfully 2024-06-25 08:22:26). The list may be incomplete as not all publishers provide suitable and complete citation data.

2 thoughts on “Achieving quantum supremacy with sparse and noisy commuting quantum computations

  1. Pingback: On experimentally relevant quantum speedups – Quantum

  2. Pingback: Perspective in Quantum Views by Bill Fefferman "On experimentally relevant quantum speedups"