Robust sparse IQP sampling in constant depth

Louis Paletta; Anthony Leverrier; Alain Sarlette; Mazyar Mirrahimi; Christophe Vuillot

doi:10.22331/q-2024-05-06-1337

Robust sparse IQP sampling in constant depth

Louis Paletta¹, Anthony Leverrier², Alain Sarlette^1,3, Mazyar Mirrahimi¹, and Christophe Vuillot⁴

¹Laboratoire de Physique de l'Ecole normale supérieure, ENS-PSL, CNRS, Inria, Centre Automatique et Systèmes (CAS), Mines Paris, Université PSL, Sorbonne Université, Université Paris Cité, Paris, France
²Inria Paris, France
³Department of Electronics and Information Systems, Ghent University, Belgium
⁴Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

Published:	2024-05-06, volume 8, page 1337
Eprint:	arXiv:2307.10729v4
Doi:	https://doi.org/10.22331/q-2024-05-06-1337
Citation:	Quantum 8, 1337 (2024).

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

Abstract

Between NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation, we propose a scheme to achieve a provable superpolynomial quantum advantage (under some widely accepted complexity conjectures) that is robust to noise with minimal error correction requirements. We choose a class of sampling problems with commuting gates known as sparse IQP (Instantaneous Quantum Polynomial-time) circuits and we ensure its fault-tolerant implementation by introducing the tetrahelix code. This new code is obtained by merging several tetrahedral codes (3D color codes) and has the following properties: each sparse IQP gate admits a transversal implementation, and the depth of the logical circuit can be traded for its width. Combining those, we obtain a depth-1 implementation of any sparse IQP circuit up to the preparation of encoded states. This comes at the cost of a space overhead which is only polylogarithmic in the width of the original circuit. We furthermore show that the state preparation can also be performed in constant depth with a single step of feed-forward from classical computation. Our construction thus exhibits a robust superpolynomial quantum advantage for a sampling problem implemented on a constant depth circuit with a single round of measurement and feed-forward.

Featured image: Construction of the tetrahelix code by merging 3D color codes in lattice surgery language. The tetrahelix codes then yields transversal sparse IQP gates that can be implemented in parallel.

Popular summary

► BibTeX data

@article{Paletta2024robustsparseiqp,
  doi = {10.22331/q-2024-05-06-1337},
  url = {https://doi.org/10.22331/q-2024-05-06-1337},
  title = {Robust sparse {IQP} sampling in constant depth},
  author = {Paletta, Louis and Leverrier, Anthony and Sarlette, Alain and Mirrahimi, Mazyar and Vuillot, Christophe},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1337},
  month = may,
  year = {2024}
}

► References

[1] Austin P Lund, Michael J Bremner, and Timothy C Ralph. ``Quantum sampling problems, bosonsampling and quantum supremacy''. npj Quantum Information 3, 1–8 (2017).
https://doi.org/10.1038/s41534-017-0018-2

[2] Ramis Movassagh. ``The hardness of random quantum circuits''. Nature Physics 19, 1719–1724 (2023).
https://doi.org/10.1038/s41567-023-02131-2

[3] Scott Aaronson and Alex Arkhipov. ``The computational complexity of linear optics''. In Proceedings of the forty-third annual ACM symposium on Theory of computing. Pages 333–342. (2011).
https://doi.org/10.1145/1993636.1993682

[4] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh 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

[5] Dan Shepherd and Michael J Bremner. ``Temporally unstructured quantum computation''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 1413–1439 (2009).
https://doi.org/10.1098/rspa.2008.0443

[6] Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani. ``A polynomial-time classical algorithm for noisy random circuit sampling''. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Pages 945–957. (2023).
https://doi.org/10.1145/3564246.3585234

[7] Yiqing Zhou, E Miles Stoudenmire, and Xavier Waintal. ``What limits the simulation of quantum computers?''. Physical Review X 10, 041038 (2020).
https://doi.org/10.1103/PhysRevX.10.041038

[8] John C Napp, Rolando L La Placa, Alexander M Dalzell, Fernando GSL Brandao, and Aram W Harrow. ``Efficient classical simulation of random shallow 2d quantum circuits''. Physical Review X 12, 021021 (2022).
https://doi.org/10.1103/PhysRevX.12.021021

[9] 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, 010334 (2024).
https://doi.org/10.1103/PRXQuantum.5.010334

[10] Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma. ``Effect of non-unital noise on random circuit sampling'' (2023). arXiv:2306.16659.
arXiv:2306.16659

[11] John Preskill. ``Quantum computing in the nisq era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[12] Bryan Eastin and Emanuel Knill. ``Restrictions on transversal encoded quantum gate sets''. Physical Review Letters 102, 110502 (2009).
https://doi.org/10.1103/PhysRevLett.102.110502

[13] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham. ``Fault-tolerant quantum speedup from constant depth quantum circuits''. Physical Review Research 2, 033444 (2020).
https://doi.org/10.1103/PhysRevResearch.2.033444

[14] Craig Gidney and Martin Ekerå. ``How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits''. Quantum 5, 433 (2021).
https://doi.org/10.22331/q-2021-04-15-433

[15] Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel. ``Quantum advantage with noisy shallow circuits''. Nature Physics 16, 1040–1045 (2020).
https://doi.org/10.1038/s41567-020-0948-z

[16] Michael J Bremner, Richard Jozsa, and Dan 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

[17] Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. ``Average-case complexity versus approximate simulation of commuting quantum computations''. Physical Review Letters 117, 080501 (2016).
https://doi.org/10.1103/PhysRevLett.117.080501

[18] Michael J Bremner, Ashley Montanaro, and Dan 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

[19] Leslie Ann Goldberg and Heng Guo. ``The complexity of approximating complex-valued ising and tutte partition functions''. computational complexity 26, 765–833 (2017).
https://doi.org/10.1007/s00037-017-0162-2

[20] Keisuke Fujii and Tomoyuki Morimae. ``Commuting quantum circuits and complexity of ising partition functions''. New Journal of Physics 19, 033003 (2017).
https://doi.org/10.1088/1367-2630/aa5fdb

[21] Daniel Gottesman. ``Fault-tolerant quantum computation with constant overhead'' (2014). arXiv:1310.2984.
arXiv:1310.2984

[22] Peter Høyer and Robert Špalek. ``Quantum fan-out is powerful''. Theory of computing 1, 81–103 (2005).
https://doi.org/10.4086/toc.2005.v001a005

[23] Dorit Aharonov and Michael Ben-Or. ``Fault-tolerant quantum computation with constant error''. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. Pages 176–188. (1997).
https://doi.org/10.1137/S0097539799359385

[24] Emanuel Knill, Raymond Laflamme, and Wojciech H Zurek. ``Resilient quantum computation''. Science 279, 342–345 (1998).
https://doi.org/10.1126/science.279.5349.342

[25] Hector Bombin and Miguel-Angel Martin-Delgado. ``Topological computation without braiding''. Physical Review Letters 98, 160502 (2007).
https://doi.org/10.1103/PhysRevLett.98.160502

[26] Aleksander Kubica and Michael E Beverland. ``Universal transversal gates with color codes: A simplified approach''. Physical Review A 91, 032330 (2015).
https://doi.org/10.1103/PhysRevA.91.032330

[27] A Robert Calderbank and Peter W Shor. ``Good quantum error-correcting codes exist''. Physical Review A 54, 1098 (1996).
https://doi.org/10.1103/PhysRevA.54.1098

[28] Andrew M Steane. ``Error correcting codes in quantum theory''. Physical Review Letters 77, 793 (1996).
https://doi.org/10.1103/PhysRevLett.77.793

[29] Clare Horsman, Austin G Fowler, Simon Devitt, and Rodney Van 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

[30] Daniel Litinski. ``A game of surface codes: Large-scale quantum computing with lattice surgery''. Quantum 3, 128 (2019).
https://doi.org/10.22331/q-2019-03-05-128

[31] Andrew J. Landahl and Ciaran Ryan-Anderson. ``Quantum computing by color-code lattice surgery'' (2014). arXiv:1407.5103.
arXiv:1407.5103

[32] Héctor Bombín. ``Single-shot fault-tolerant quantum error correction''. Physical Review X 5, 031043 (2015).
https://doi.org/10.1103/PhysRevX.5.031043

[33] Héctor Bombín. ``Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes''. New Journal of Physics 17, 083002 (2015).
https://doi.org/10.1088/1367-2630/17/8/083002

[34] H Bombin and MA Martin-Delgado. ``Exact topological quantum order in d= 3 and beyond: Branyons and brane-net condensates''. Physical Review B 75, 075103 (2007).
https://doi.org/10.1103/PhysRevB.75.075103

[35] Hector Bombin and Miguel Angel Martin-Delgado. ``Topological quantum distillation''. Physical Review Letters 97, 180501 (2006).
https://doi.org/10.1103/PhysRevLett.97.180501

[36] Christophe Vuillot. ``Fault-tolerant quantum computation: Theory and practice''. PhD thesis. TU Delft. (2020).
https://doi.org/10.4233/uuid:7cb715f4-eaf0-4526-8552-9f97cc864383

[37] AH Boerdijk. ``Some remarks concerning close-packing of equal spheres''. Philips Research Reports 7, 303–313 (1952).

[38] HSM Coxeter and JM Wills. ``Regular complex polytopes''. Jahresbericht der Deutschen Mathematiker Vereinigung 96, 2–2 (1994).
https://doi.org/10.2307/1575843

[39] Christopher Chamberland, Aleksander Kubica, Theodore J Yoder, and Guanyu Zhu. ``Triangular color codes on trivalent graphs with flag qubits''. New Journal of Physics 22, 023019 (2020).
https://doi.org/10.1088/1367-2630/ab68fd

[40] Kaavya Sahay and Benjamin J Brown. ``Decoder for the triangular color code by matching on a möbius strip''. PRX Quantum 3, 010310 (2022).
https://doi.org/10.1103/PRXQuantum.3.010310

[41] Aleksander Kubica and Nicolas Delfosse. ``Efficient color code decoders in $d \ge 2$ dimensions from toric code decoders''. Quantum 7, 929 (2023).
https://doi.org/10.22331/q-2023-02-21-929

[42] Michael E Beverland, Aleksander Kubica, and Krysta M Svore. ``Cost of universality: A comparative study of the overhead of state distillation and code switching with color codes''. PRX Quantum 2, 020341 (2021).
https://doi.org/10.1103/PRXQuantum.2.020341

[43] Hector Bombin. ``Transversal gates and error propagation in 3d topological codes'' (2018). arXiv:1810.09575.
arXiv:1810.09575

[44] Dan Browne, Elham Kashefi, and Simon Perdrix. ``Computational depth complexity of measurement-based quantum computation''. In Theory of Quantum Computation, Communication, and Cryptography: 5th Conference, TQC 2010, Leeds, UK, April 13-15, 2010, Revised Selected Papers 5. Pages 35–46. Springer (2011).
https://doi.org/10.1007/978-3-642-18073-6_4

[45] Keisuke Fujii. ``Noise threshold of quantum supremacy'' (2016). arXiv:1610.03632.
arXiv:1610.03632

[46] Dolev Bluvstein, Simon J Evered, Alexandra A Geim, Sophie H Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, et al. ``Logical quantum processor based on reconfigurable atom arrays''. Nature 626, 58–65 (2024).
https://doi.org/10.1038/s41586-023-06927-3

[47] Gregoire de Gliniasty, Rawad Mezher, and Damian Markham. In preparation.

Cited by

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

[2] Dmitri Maslov, Sergey Bravyi, Felix Tripier, Andrii Maksymov, and Joe Latone, "Fast classical simulation of Harvard/QuEra IQP circuits", arXiv:2402.03211, (2024).

[3] Dominik Hangleiter, Marcin Kalinowski, Dolev Bluvstein, Madelyn Cain, Nishad Maskara, Xun Gao, Aleksander Kubica, Mikhail D. Lukin, and Michael J. Gullans, "Fault-tolerant compiling of classically hard IQP circuits on hypercubes", arXiv:2404.19005, (2024).

[4] Joel Rajakumar, James D. Watson, and Yi-Kai Liu, "Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth", arXiv:2403.14607, (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2024-05-19 03:08:24). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2024-05-19 03:08:22).

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.