On computational complexity and average-case hardness of shallow-depth boson sampling
Summarize this article with:
AbstractBoson Sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quantum devices. However, noise in experimental implementations poses a significant challenge, potentially rendering Boson Sampling classically simulable and compromising its classical intractability. Numerous studies have proposed classical algorithms that can efficiently simulate Boson Sampling under various noise models, particularly as noise rates increase with circuit depth. To address this challenge, we investigate the viability of achieving quantum computational advantage through Boson Sampling implemented with shallow-depth linear optical circuits. In particular, as the average-case hardness of estimating output probabilities of Boson Sampling is a crucial ingredient in demonstrating its classical intractability, we make progress on establishing the average-case hardness of Boson Sampling confined to logarithmic-depth regimes. We also obtain the average-case hardness for logarithmic-depth Fock-state Boson Sampling subject to lossy environments and for the logarithmic-depth Gaussian Boson Sampling. By providing complexity-theoretical backgrounds for the classical simulation hardness of logarithmic-depth Boson Sampling, we expect that our findings will mark a crucial step towards a more noise-tolerant demonstration of quantum advantage with shallow-depth Boson Sampling.Popular summaryBoson Sampling is a leading candidate for near-term demonstrations of quantum advantage. However, noise in any realistic implementations remains significant challenge, which can render Boson Sampling classically simulable and hinder the achievement of quantum advantage. We address this challenge by studying the classical hardness for shallow-depth Boson Sampling, particularly focusing on logarithmic-depth linear-optical circuits that substantially reduce the accumulation of noise. We develop rigorous complexity-theoretic arguments establishing average-case #P-hardness of estimating output probabilities of shallow-depth Boson Sampling for certain level of imprecision. We further extend these arguments to obtain analogous average-case hardness results for Gaussian Boson Sampling and for lossy Boson Sampling. We expect that our results provide a foundational step toward further hardness results on shallow-depth Boson Sampling with improved robustness, thereby facilitate near-term quantum-advantage demonstrations based on shallow-depth Boson-Sampling experiments.► BibTeX data@article{Go2026computational, doi = {10.22331/q-2026-03-13-2026}, url = {https://doi.org/10.22331/q-2026-03-13-2026}, title = {On computational complexity and average-case hardness of shallow-depth boson sampling}, author = {Go, Byeongseon and Oh, Changhun and Jeong, Hyunseok}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2026}, month = mar, year = {2026} }► References [1] 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). doi: 10.1145/1993636.1993682. https://doi.org/10.1145/1993636.1993682 [2] Craig S Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, and Igor Jex. ``Gaussian boson sampling''. Physical review letters 119, 170501 (2017). doi: 10.1103/PhysRevLett.119.170501. https://doi.org/10.1103/PhysRevLett.119.170501 [3] Abhinav Deshpande, Arthur Mehta, Trevor Vincent, Nicolás Quesada, Marcel Hinsche, Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi, Jens Eisert, et al. ``Quantum computational advantage via high-dimensional gaussian boson sampling''. Science advances 8, eabi7894 (2022). doi: 10.1126/sciadv.abi7894. https://doi.org/10.1126/sciadv.abi7894 [4] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al. ``Quantum computational advantage using photons''. Science 370, 1460–1463 (2020). doi: 10.1126/science.abe8770. https://doi.org/10.1126/science.abe8770 [5] Han-Sen Zhong, Yu-Hao Deng, Jian Qin, Hui Wang, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Dian Wu, Si-Qiu Gong, Hao Su, et al. ``Phase-programmable Gaussian boson sampling using stimulated squeezed light''. Physical review letters 127, 180502 (2021). doi: 10.1103/PhysRevLett.127.180502. https://doi.org/10.1103/PhysRevLett.127.180502 [6] Lars S Madsen, Fabian Laudenbach, Mohsen Falamarzi Askarani, Fabien Rortais, Trevor Vincent, Jacob FF Bulmer, Filippo M Miatto, Leonhard Neuhaus, Lukas G Helt, Matthew J Collins, et al. ``Quantum computational advantage with a programmable photonic processor''. Nature 606, 75–81 (2022). doi: 10.1038/s41586-022-04725-x. https://doi.org/10.1038/s41586-022-04725-x [7] Yu-Hao Deng, Yi-Chao Gu, Hua-Liang Liu, Si-Qiu Gong, Hao Su, Zhi-Jiong Zhang, Hao-Yang Tang, Meng-Hao Jia, Jia-Min Xu, Ming-Cheng Chen, et al. ``Gaussian boson sampling with pseudo-photon-number-resolving detectors and quantum computational advantage''. Physical review letters 131, 150601 (2023). doi: 10.1103/PhysRevLett.131.150601. https://doi.org/10.1103/PhysRevLett.131.150601 [8] Jelmer Renema, Valery Shchesnovich, and Raul Garcia-Patron. ``Classical simulability of noisy boson sampling'' (2018). doi: 10.48550/arXiv.1809.01953. arXiv:1809.01953. https://doi.org/10.48550/arXiv.1809.01953 arXiv:1809.01953 [9] Jelmer J Renema, Adrian Menssen, William R Clements, Gil Triginer, William S Kolthammer, and Ian A Walmsley. ``Efficient classical algorithm for boson sampling with partially distinguishable photons''. Physical review letters 120, 220502 (2018). doi: 10.1103/PhysRevLett.120.220502. https://doi.org/10.1103/PhysRevLett.120.220502 [10] Alexandra E Moylett, Raúl García-Patrón, Jelmer J Renema, and Peter S Turner. ``Classically simulating near-term partially-distinguishable and lossy boson sampling''. Quantum Science and Technology 5, 015001 (2019). doi: 10.1088/2058-9565/ab5555. https://doi.org/10.1088/2058-9565/ab5555 [11] Jelmer J Renema. ``Simulability of partially distinguishable superposition and gaussian boson sampling''. Physical Review A 101, 063840 (2020). doi: 10.1103/PhysRevA.101.063840. https://doi.org/10.1103/PhysRevA.101.063840 [12] Junheng Shi and Tim Byrnes. ``Effect of partial distinguishability on quantum supremacy in gaussian boson sampling''. npj Quantum Information 8, 54 (2022). doi: 10.1038/s41534-022-00557-9. https://doi.org/10.1038/s41534-022-00557-9 [13] SN van den Hoven, E Kanis, and JJ Renema. ``Efficient classical algorithm for simulating boson sampling with inhomogeneous partial distinguishability'' (2024). doi: 10.48550/arXiv.2406.17682. arXiv:2406.17682. https://doi.org/10.48550/arXiv.2406.17682 arXiv:2406.17682 [14] Valery S Shchesnovich. ``Noise in boson sampling and the threshold of efficient classical simulatability''. Physical Review A 100, 012340 (2019). doi: 10.1103/PhysRevA.100.012340. https://doi.org/10.1103/PhysRevA.100.012340 [15] Michał Oszmaniec and Daniel J Brod. ``Classical simulation of photonic linear optics with lost particles''. New Journal of Physics 20, 092002 (2018). doi: 10.1088/1367-2630/aadfa8. https://doi.org/10.1088/1367-2630/aadfa8 [16] Raúl García-Patrón, Jelmer J Renema, and Valery Shchesnovich. ``Simulating boson sampling in lossy architectures''. Quantum 3, 169 (2019). doi: 10.22331/q-2019-08-05-169. https://doi.org/10.22331/q-2019-08-05-169 [17] Haoyu Qi, Daniel J Brod, Nicolás Quesada, and Raúl García-Patrón. ``Regimes of classical simulability for noisy gaussian boson sampling''. Physical review letters 124, 100502 (2020). doi: 10.1103/PhysRevLett.124.100502. https://doi.org/10.1103/PhysRevLett.124.100502 [18] Daniel Jost Brod and Michał Oszmaniec. ``Classical simulation of linear optics subject to nonuniform losses''. Quantum 4, 267 (2020). doi: 10.22331/q-2020-05-14-267. https://doi.org/10.22331/q-2020-05-14-267 [19] 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'' (2021). doi: 10.48550/arXiv.2109.11525. arXiv:2109.11525. https://doi.org/10.48550/arXiv.2109.11525 arXiv:2109.11525 [20] Changhun Oh, Kyungjoo Noh, Bill Fefferman, and Liang Jiang. ``Classical simulation of lossy boson sampling using matrix product operators''. Physical Review A 104, 022407 (2021). doi: 10.1103/PhysRevA.104.022407. https://doi.org/10.1103/PhysRevA.104.022407 [21] Jacob FF Bulmer, Bryn A Bell, Rachel S Chadwick, Alex E Jones, Diana Moise, Alessandro Rigazzi, Jan Thorbecke, Utz-Uwe Haus, Thomas Van Vaerenbergh, Raj B Patel, et al. ``The boundary for quantum advantage in gaussian boson sampling''. Science advances 8, eabl9236 (2022). doi: 10.1126/sciadv.abl9236. https://doi.org/10.1126/sciadv.abl9236 [22] Minzhao Liu, Changhun Oh, Junyu Liu, Liang Jiang, and Yuri Alexeev. ``Simulating lossy gaussian boson sampling with matrix-product operators''. Physical Review A 108, 052604 (2023). doi: 10.1103/PhysRevA.108.052604. https://doi.org/10.1103/PhysRevA.108.052604 [23] Changhun Oh, Liang Jiang, and Bill Fefferman. ``On classical simulation algorithms for noisy boson sampling'' (2023). doi: 10.48550/arXiv.2301.11532. arXiv:2301.11532. https://doi.org/10.48550/arXiv.2301.11532 arXiv:2301.11532 [24] Changhun Oh, Minzhao Liu, Yuri Alexeev, Bill Fefferman, and Liang Jiang. ``Classical algorithm for simulating experimental gaussian boson sampling''. Nature PhysicsPages 1–8 (2024). doi: 10.1038/s41567-024-02535-8. https://doi.org/10.1038/s41567-024-02535-8 [25] Changhun Oh. ``Classical simulability of constant-depth linear-optical circuits with noise''. npj Quantum Information 11, 126 (2025). doi: 10.1038/s41534-025-01041-w. https://doi.org/10.1038/s41534-025-01041-w [26] Changhun Oh. ``Recent theoretical and experimental progress on boson sampling''. Current Optics and Photonics 9, 1–18 (2025). doi: 10.3807/COPP.2025.9.1.1. https://doi.org/10.3807/COPP.2025.9.1.1 [27] Daniel Grier, Daniel J Brod, Juan Miguel Arrazola, Marcos Benicio de Andrade Alonso, and Nicolás Quesada. ``The complexity of bipartite gaussian boson sampling''. Quantum 6, 863 (2022). doi: 10.22331/q-2022-11-28-863. https://doi.org/10.22331/q-2022-11-28-863 [28] Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu. ``Noise and the frontier of quantum supremacy''. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Pages 1308–1317. IEEE (2022). doi: 10.1109/FOCS52979.2021.00127. https://doi.org/10.1109/FOCS52979.2021.00127 [29] Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, and Michal Oszmaniec. ``Complexity-theoretic foundations of bosonsampling with a linear number of modes'' (2023). doi: 10.48550/arXiv.2312.00286. arXiv:2312.00286. https://doi.org/10.48550/arXiv.2312.00286 arXiv:2312.00286 [30] Adam Bouland, Ishaun Datta, Bill Fefferman, and Felipe Hernandez. ``On the average-case hardness of bosonsampling'' (2024). doi: 10.48550/arXiv.2411.04566. arXiv:2411.04566. https://doi.org/10.48550/arXiv.2411.04566 arXiv:2411.04566 [31] Karol Zyczkowski and Marek Kus. ``Random unitary matrices''. Journal of Physics A: Mathematical and General 27, 4235 (1994). doi: 10.1088/0305-4470/27/12/028. https://doi.org/10.1088/0305-4470/27/12/028 [32] Nicholas J Russell, Levon Chakhmakhchyan, Jeremy L O’Brien, and Anthony Laing. ``Direct dialling of haar random unitary matrices''. New journal of physics 19, 033007 (2017). doi: 10.1088/1367-2630/aa60ed. https://doi.org/10.1088/1367-2630/aa60ed [33] Daniel J Brod. ``Complexity of simulating constant-depth bosonsampling''. Physical Review A 91, 042316 (2015). doi: 10.1103/PhysRevA.91.042316. https://doi.org/10.1103/PhysRevA.91.042316 [34] Guifré Vidal. ``Efficient classical simulation of slightly entangled quantum computations''. Physical review letters 91, 147902 (2003). doi: 10.1103/PhysRevLett.91.147902. https://doi.org/10.1103/PhysRevLett.91.147902 [35] Haoyu Qi, Diego Cifuentes, Kamil Brádler, Robert Israel, Timjan Kalajdzievski, and Nicolás Quesada. ``Efficient sampling from shallow gaussian quantum-optical circuits with local interactions''. Physical Review A 105, 052412 (2022). doi: 10.1103/PhysRevA.105.052412. https://doi.org/10.1103/PhysRevA.105.052412 [36] Abhinav Deshpande, Bill Fefferman, Minh C Tran, Michael Foss-Feig, and Alexey V Gorshkov. ``Dynamical phase transitions in sampling complexity''. Physical review letters 121, 030501 (2018). doi: 10.1103/PhysRevLett.121.030501. https://doi.org/10.1103/PhysRevLett.121.030501 [37] Changhun Oh, Youngrong Lim, Bill Fefferman, and Liang Jiang. ``Classical simulation of boson sampling based on graph structure''.
Physical Review Letters 128, 190501 (2022). doi: 10.1103/PhysRevLett.128.190501. https://doi.org/10.1103/PhysRevLett.128.190501 [38] Zoltán Kolarovszki, Ágoston Kaposi, Tamás Kozsik, and Zoltán Zimborás. ``Simulating sparse and shallow gaussian boson sampling''.
In International Conference on Computational Science. Pages 209–223. Springer (2023). doi: 10.1007/978-3-031-36030-5_17. https://doi.org/10.1007/978-3-031-36030-5_17 [39] Chao Shen, Zhen Zhang, and L-M Duan. ``Scalable implementation of boson sampling with trapped ions''. Physical review letters 112, 050504 (2014). doi: 10.1103/PhysRevLett.112.050504. https://doi.org/10.1103/PhysRevLett.112.050504 [40] Wentao Chen, Yao Lu, Shuaining Zhang, Kuan Zhang, Guanhao Huang, Mu Qiao, Xiaolu Su, Jialiang Zhang, Jing-Ning Zhang, Leonardo Banchi, et al. ``Scalable and programmable phononic network with trapped ions''. Nature PhysicsPages 1–7 (2023). doi: 10.1038/s41567-023-01952-5. https://doi.org/10.1038/s41567-023-01952-5 [41] 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). doi: 10.1038/s41567-018-0318-2. https://doi.org/10.1038/s41567-018-0318-2 [42] Ramis Movassagh. ``The hardness of random quantum circuits''. Nature PhysicsPages 1–6 (2023). doi: 10.1038/s41567-023-02131-2. https://doi.org/10.1038/s41567-023-02131-2 [43] Yasuhiro Kondo, Ryuhei Mori, and Ramis Movassagh. ``Quantum supremacy and hardness of estimating output probabilities of quantum circuits''. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Pages 1296–1307. IEEE (2022). doi: 10.1109/FOCS52979.2021.00126. https://doi.org/10.1109/FOCS52979.2021.00126 [44] Hari Krovi. ``Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent'' (2022). doi: 10.48550/arXiv.2206.05642. arXiv:2206.05642. https://doi.org/10.48550/arXiv.2206.05642 arXiv:2206.05642 [45] Alex Arkhipov and Greg Kuperberg. ``The bosonic birthday paradox''. Geometry & Topology Monographs 18, 10–2140 (2012). doi: 10.2140/gtm.2012.18.1. https://doi.org/10.2140/gtm.2012.18.1 [46] Tri Dao, Nimit S Sohoni, Albert Gu, Matthew Eichhorn, Amit Blonder, Megan Leszczynski, Atri Rudra, and Christopher Ré. ``Kaleidoscope: An efficient, learnable representation for all structured linear maps'' (2020). doi: 10.48550/arXiv.2012.14966. arXiv:2012.14966. https://doi.org/10.48550/arXiv.2012.14966 arXiv:2012.14966 [47] Byeongseon Go, Changhun Oh, Liang Jiang, and Hyunseok Jeong. ``Exploring shallow-depth boson sampling: Toward a scalable quantum advantage''. Physical Review A 109, 052613 (2024). doi: 10.1103/PhysRevA.109.052613. https://doi.org/10.1103/PhysRevA.109.052613 [48] Larry Stockmeyer. ``On approximation algorithms for# p''. SIAM Journal on Computing 14, 849–861 (1985). doi: 10.1137/0214060. https://doi.org/10.1137/0214060 [49] Seinosuke Toda. ``Pp is as hard as the polynomial-time hierarchy''. SIAM Journal on Computing 20, 865–877 (1991). doi: 10.1137/0220053. https://doi.org/10.1137/0220053 [50] Austin P Lund, Anthony Laing, Saleh Rahimi-Keshari, Terry Rudolph, Jeremy L O’Brien, and Timothy C Ralph. ``Boson sampling from a gaussian state''. Physical review letters 113, 100502 (2014). doi: 10.1103/PhysRevLett.113.100502. https://doi.org/10.1103/PhysRevLett.113.100502 [51] Keisuke Fujii. ``Noise threshold of quantum supremacy'' (2016). doi: 10.48550/arXiv.1610.03632. arXiv:1610.03632. https://doi.org/10.48550/arXiv.1610.03632 arXiv:1610.03632 [52] Robert Raussendorf and Hans J Briegel. ``A one-way quantum computer''. Physical review letters 86, 5188 (2001). doi: 10.1103/PhysRevLett.86.5188. https://doi.org/10.1103/PhysRevLett.86.5188 [53] Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. ``Universal blind quantum computation''. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. Pages 517–526. IEEE (2009). doi: 10.1109/FOCS.2009.36. https://doi.org/10.1109/FOCS.2009.36 [54] Andrew M Childs, Debbie W Leung, and Michael A Nielsen. ``Unified derivations of measurement-based schemes for quantum computation''. Physical Review A 71, 032318 (2005). doi: 10.1103/PhysRevA.71.032318. https://doi.org/10.1103/PhysRevA.71.032318 [55] Emanuel Knill, Raymond Laflamme, and Gerald J Milburn. ``A scheme for efficient quantum computation with linear optics''. nature 409, 46–52 (2001). doi: 10.1038/35051009. https://doi.org/10.1038/35051009 [56] Emanuel Knill. ``Quantum gates using linear optics and postselection''. Physical Review A 66, 052306 (2002). doi: 10.1103/PhysRevA.66.052306. https://doi.org/10.1103/PhysRevA.66.052306 [57] 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). doi: 10.1103/PhysRevLett.117.080501. https://doi.org/10.1103/PhysRevLett.117.080501 [58] Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert. ``Anticoncentration theorems for schemes showing a quantum speedup''. Quantum 2, 65 (2018). doi: 10.22331/q-2018-05-22-65. https://doi.org/10.22331/q-2018-05-22-65 [59] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert. ``Architectures for quantum simulation showing a quantum speedup''. Physical Review X 8, 021010 (2018). doi: 10.1103/PhysRevX.8.021010. https://doi.org/10.1103/PhysRevX.8.021010 [60] Alexander M Dalzell, Nicholas Hunter-Jones, and Fernando GSL Brandão. ``Random quantum circuits anticoncentrate in log depth''. PRX Quantum 3, 010333 (2022). doi: 10.1103/PRXQuantum.3.010333. https://doi.org/10.1103/PRXQuantum.3.010333 [61] Sheldon M Ross. ``Introduction to probability models''. Academic press. (2014). doi: 10.1016/C2012-0-03564-8. https://doi.org/10.1016/C2012-0-03564-8 [62] Peter Clifford and Raphaël Clifford. ``The classical complexity of boson sampling''. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Pages 146–155. SIAM (2018). doi: 10.1137/1.9781611975031.10. https://doi.org/10.1137/1.9781611975031.10Cited byCould not fetch Crossref cited-by data during last attempt 2026-03-13 14:51:24: Could not fetch cited-by data for 10.22331/q-2026-03-13-2026 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-13 14:51:25: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractBoson Sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quantum devices. However, noise in experimental implementations poses a significant challenge, potentially rendering Boson Sampling classically simulable and compromising its classical intractability. Numerous studies have proposed classical algorithms that can efficiently simulate Boson Sampling under various noise models, particularly as noise rates increase with circuit depth. To address this challenge, we investigate the viability of achieving quantum computational advantage through Boson Sampling implemented with shallow-depth linear optical circuits. In particular, as the average-case hardness of estimating output probabilities of Boson Sampling is a crucial ingredient in demonstrating its classical intractability, we make progress on establishing the average-case hardness of Boson Sampling confined to logarithmic-depth regimes. We also obtain the average-case hardness for logarithmic-depth Fock-state Boson Sampling subject to lossy environments and for the logarithmic-depth Gaussian Boson Sampling. By providing complexity-theoretical backgrounds for the classical simulation hardness of logarithmic-depth Boson Sampling, we expect that our findings will mark a crucial step towards a more noise-tolerant demonstration of quantum advantage with shallow-depth Boson Sampling.Popular summaryBoson Sampling is a leading candidate for near-term demonstrations of quantum advantage. However, noise in any realistic implementations remains significant challenge, which can render Boson Sampling classically simulable and hinder the achievement of quantum advantage. We address this challenge by studying the classical hardness for shallow-depth Boson Sampling, particularly focusing on logarithmic-depth linear-optical circuits that substantially reduce the accumulation of noise. We develop rigorous complexity-theoretic arguments establishing average-case #P-hardness of estimating output probabilities of shallow-depth Boson Sampling for certain level of imprecision. We further extend these arguments to obtain analogous average-case hardness results for Gaussian Boson Sampling and for lossy Boson Sampling. We expect that our results provide a foundational step toward further hardness results on shallow-depth Boson Sampling with improved robustness, thereby facilitate near-term quantum-advantage demonstrations based on shallow-depth Boson-Sampling experiments.► BibTeX data@article{Go2026computational, doi = {10.22331/q-2026-03-13-2026}, url = {https://doi.org/10.22331/q-2026-03-13-2026}, title = {On computational complexity and average-case hardness of shallow-depth boson sampling}, author = {Go, Byeongseon and Oh, Changhun and Jeong, Hyunseok}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2026}, month = mar, year = {2026} }► References [1] 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). doi: 10.1145/1993636.1993682. https://doi.org/10.1145/1993636.1993682 [2] Craig S Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, and Igor Jex. ``Gaussian boson sampling''. Physical review letters 119, 170501 (2017). doi: 10.1103/PhysRevLett.119.170501. https://doi.org/10.1103/PhysRevLett.119.170501 [3] Abhinav Deshpande, Arthur Mehta, Trevor Vincent, Nicolás Quesada, Marcel Hinsche, Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi, Jens Eisert, et al. ``Quantum computational advantage via high-dimensional gaussian boson sampling''. Science advances 8, eabi7894 (2022). doi: 10.1126/sciadv.abi7894. https://doi.org/10.1126/sciadv.abi7894 [4] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al. ``Quantum computational advantage using photons''. Science 370, 1460–1463 (2020). doi: 10.1126/science.abe8770. https://doi.org/10.1126/science.abe8770 [5] Han-Sen Zhong, Yu-Hao Deng, Jian Qin, Hui Wang, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Dian Wu, Si-Qiu Gong, Hao Su, et al. ``Phase-programmable Gaussian boson sampling using stimulated squeezed light''. Physical review letters 127, 180502 (2021). doi: 10.1103/PhysRevLett.127.180502. https://doi.org/10.1103/PhysRevLett.127.180502 [6] Lars S Madsen, Fabian Laudenbach, Mohsen Falamarzi Askarani, Fabien Rortais, Trevor Vincent, Jacob FF Bulmer, Filippo M Miatto, Leonhard Neuhaus, Lukas G Helt, Matthew J Collins, et al. ``Quantum computational advantage with a programmable photonic processor''. Nature 606, 75–81 (2022). doi: 10.1038/s41586-022-04725-x. https://doi.org/10.1038/s41586-022-04725-x [7] Yu-Hao Deng, Yi-Chao Gu, Hua-Liang Liu, Si-Qiu Gong, Hao Su, Zhi-Jiong Zhang, Hao-Yang Tang, Meng-Hao Jia, Jia-Min Xu, Ming-Cheng Chen, et al. ``Gaussian boson sampling with pseudo-photon-number-resolving detectors and quantum computational advantage''. Physical review letters 131, 150601 (2023). doi: 10.1103/PhysRevLett.131.150601. https://doi.org/10.1103/PhysRevLett.131.150601 [8] Jelmer Renema, Valery Shchesnovich, and Raul Garcia-Patron. ``Classical simulability of noisy boson sampling'' (2018). doi: 10.48550/arXiv.1809.01953. arXiv:1809.01953. https://doi.org/10.48550/arXiv.1809.01953 arXiv:1809.01953 [9] Jelmer J Renema, Adrian Menssen, William R Clements, Gil Triginer, William S Kolthammer, and Ian A Walmsley. ``Efficient classical algorithm for boson sampling with partially distinguishable photons''. Physical review letters 120, 220502 (2018). doi: 10.1103/PhysRevLett.120.220502. https://doi.org/10.1103/PhysRevLett.120.220502 [10] Alexandra E Moylett, Raúl García-Patrón, Jelmer J Renema, and Peter S Turner. ``Classically simulating near-term partially-distinguishable and lossy boson sampling''. Quantum Science and Technology 5, 015001 (2019). doi: 10.1088/2058-9565/ab5555. https://doi.org/10.1088/2058-9565/ab5555 [11] Jelmer J Renema. ``Simulability of partially distinguishable superposition and gaussian boson sampling''. Physical Review A 101, 063840 (2020). doi: 10.1103/PhysRevA.101.063840. https://doi.org/10.1103/PhysRevA.101.063840 [12] Junheng Shi and Tim Byrnes. ``Effect of partial distinguishability on quantum supremacy in gaussian boson sampling''. npj Quantum Information 8, 54 (2022). doi: 10.1038/s41534-022-00557-9. https://doi.org/10.1038/s41534-022-00557-9 [13] SN van den Hoven, E Kanis, and JJ Renema. ``Efficient classical algorithm for simulating boson sampling with inhomogeneous partial distinguishability'' (2024). doi: 10.48550/arXiv.2406.17682. arXiv:2406.17682. https://doi.org/10.48550/arXiv.2406.17682 arXiv:2406.17682 [14] Valery S Shchesnovich. ``Noise in boson sampling and the threshold of efficient classical simulatability''. Physical Review A 100, 012340 (2019). doi: 10.1103/PhysRevA.100.012340. https://doi.org/10.1103/PhysRevA.100.012340 [15] Michał Oszmaniec and Daniel J Brod. ``Classical simulation of photonic linear optics with lost particles''. New Journal of Physics 20, 092002 (2018). doi: 10.1088/1367-2630/aadfa8. https://doi.org/10.1088/1367-2630/aadfa8 [16] Raúl García-Patrón, Jelmer J Renema, and Valery Shchesnovich. ``Simulating boson sampling in lossy architectures''. Quantum 3, 169 (2019). doi: 10.22331/q-2019-08-05-169. https://doi.org/10.22331/q-2019-08-05-169 [17] Haoyu Qi, Daniel J Brod, Nicolás Quesada, and Raúl García-Patrón. ``Regimes of classical simulability for noisy gaussian boson sampling''. Physical review letters 124, 100502 (2020). doi: 10.1103/PhysRevLett.124.100502. https://doi.org/10.1103/PhysRevLett.124.100502 [18] Daniel Jost Brod and Michał Oszmaniec. ``Classical simulation of linear optics subject to nonuniform losses''. Quantum 4, 267 (2020). doi: 10.22331/q-2020-05-14-267. https://doi.org/10.22331/q-2020-05-14-267 [19] 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'' (2021). doi: 10.48550/arXiv.2109.11525. arXiv:2109.11525. https://doi.org/10.48550/arXiv.2109.11525 arXiv:2109.11525 [20] Changhun Oh, Kyungjoo Noh, Bill Fefferman, and Liang Jiang. ``Classical simulation of lossy boson sampling using matrix product operators''. Physical Review A 104, 022407 (2021). doi: 10.1103/PhysRevA.104.022407. https://doi.org/10.1103/PhysRevA.104.022407 [21] Jacob FF Bulmer, Bryn A Bell, Rachel S Chadwick, Alex E Jones, Diana Moise, Alessandro Rigazzi, Jan Thorbecke, Utz-Uwe Haus, Thomas Van Vaerenbergh, Raj B Patel, et al. ``The boundary for quantum advantage in gaussian boson sampling''. Science advances 8, eabl9236 (2022). doi: 10.1126/sciadv.abl9236. https://doi.org/10.1126/sciadv.abl9236 [22] Minzhao Liu, Changhun Oh, Junyu Liu, Liang Jiang, and Yuri Alexeev. ``Simulating lossy gaussian boson sampling with matrix-product operators''. Physical Review A 108, 052604 (2023). doi: 10.1103/PhysRevA.108.052604. https://doi.org/10.1103/PhysRevA.108.052604 [23] Changhun Oh, Liang Jiang, and Bill Fefferman. ``On classical simulation algorithms for noisy boson sampling'' (2023). doi: 10.48550/arXiv.2301.11532. arXiv:2301.11532. https://doi.org/10.48550/arXiv.2301.11532 arXiv:2301.11532 [24] Changhun Oh, Minzhao Liu, Yuri Alexeev, Bill Fefferman, and Liang Jiang. ``Classical algorithm for simulating experimental gaussian boson sampling''. Nature PhysicsPages 1–8 (2024). doi: 10.1038/s41567-024-02535-8. https://doi.org/10.1038/s41567-024-02535-8 [25] Changhun Oh. ``Classical simulability of constant-depth linear-optical circuits with noise''. npj Quantum Information 11, 126 (2025). doi: 10.1038/s41534-025-01041-w. https://doi.org/10.1038/s41534-025-01041-w [26] Changhun Oh. ``Recent theoretical and experimental progress on boson sampling''. Current Optics and Photonics 9, 1–18 (2025). doi: 10.3807/COPP.2025.9.1.1. https://doi.org/10.3807/COPP.2025.9.1.1 [27] Daniel Grier, Daniel J Brod, Juan Miguel Arrazola, Marcos Benicio de Andrade Alonso, and Nicolás Quesada. ``The complexity of bipartite gaussian boson sampling''. Quantum 6, 863 (2022). doi: 10.22331/q-2022-11-28-863. https://doi.org/10.22331/q-2022-11-28-863 [28] Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu. ``Noise and the frontier of quantum supremacy''. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Pages 1308–1317. IEEE (2022). doi: 10.1109/FOCS52979.2021.00127. https://doi.org/10.1109/FOCS52979.2021.00127 [29] Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, and Michal Oszmaniec. ``Complexity-theoretic foundations of bosonsampling with a linear number of modes'' (2023). doi: 10.48550/arXiv.2312.00286. arXiv:2312.00286. https://doi.org/10.48550/arXiv.2312.00286 arXiv:2312.00286 [30] Adam Bouland, Ishaun Datta, Bill Fefferman, and Felipe Hernandez. ``On the average-case hardness of bosonsampling'' (2024). doi: 10.48550/arXiv.2411.04566. arXiv:2411.04566. https://doi.org/10.48550/arXiv.2411.04566 arXiv:2411.04566 [31] Karol Zyczkowski and Marek Kus. ``Random unitary matrices''. Journal of Physics A: Mathematical and General 27, 4235 (1994). doi: 10.1088/0305-4470/27/12/028. https://doi.org/10.1088/0305-4470/27/12/028 [32] Nicholas J Russell, Levon Chakhmakhchyan, Jeremy L O’Brien, and Anthony Laing. ``Direct dialling of haar random unitary matrices''. New journal of physics 19, 033007 (2017). doi: 10.1088/1367-2630/aa60ed. https://doi.org/10.1088/1367-2630/aa60ed [33] Daniel J Brod. ``Complexity of simulating constant-depth bosonsampling''. Physical Review A 91, 042316 (2015). doi: 10.1103/PhysRevA.91.042316. https://doi.org/10.1103/PhysRevA.91.042316 [34] Guifré Vidal. ``Efficient classical simulation of slightly entangled quantum computations''. Physical review letters 91, 147902 (2003). doi: 10.1103/PhysRevLett.91.147902. https://doi.org/10.1103/PhysRevLett.91.147902 [35] Haoyu Qi, Diego Cifuentes, Kamil Brádler, Robert Israel, Timjan Kalajdzievski, and Nicolás Quesada. ``Efficient sampling from shallow gaussian quantum-optical circuits with local interactions''. Physical Review A 105, 052412 (2022). doi: 10.1103/PhysRevA.105.052412. https://doi.org/10.1103/PhysRevA.105.052412 [36] Abhinav Deshpande, Bill Fefferman, Minh C Tran, Michael Foss-Feig, and Alexey V Gorshkov. ``Dynamical phase transitions in sampling complexity''. Physical review letters 121, 030501 (2018). doi: 10.1103/PhysRevLett.121.030501. https://doi.org/10.1103/PhysRevLett.121.030501 [37] Changhun Oh, Youngrong Lim, Bill Fefferman, and Liang Jiang. ``Classical simulation of boson sampling based on graph structure''.
Physical Review Letters 128, 190501 (2022). doi: 10.1103/PhysRevLett.128.190501. https://doi.org/10.1103/PhysRevLett.128.190501 [38] Zoltán Kolarovszki, Ágoston Kaposi, Tamás Kozsik, and Zoltán Zimborás. ``Simulating sparse and shallow gaussian boson sampling''.
In International Conference on Computational Science. Pages 209–223. Springer (2023). doi: 10.1007/978-3-031-36030-5_17. https://doi.org/10.1007/978-3-031-36030-5_17 [39] Chao Shen, Zhen Zhang, and L-M Duan. ``Scalable implementation of boson sampling with trapped ions''. Physical review letters 112, 050504 (2014). doi: 10.1103/PhysRevLett.112.050504. https://doi.org/10.1103/PhysRevLett.112.050504 [40] Wentao Chen, Yao Lu, Shuaining Zhang, Kuan Zhang, Guanhao Huang, Mu Qiao, Xiaolu Su, Jialiang Zhang, Jing-Ning Zhang, Leonardo Banchi, et al. ``Scalable and programmable phononic network with trapped ions''. Nature PhysicsPages 1–7 (2023). doi: 10.1038/s41567-023-01952-5. https://doi.org/10.1038/s41567-023-01952-5 [41] 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). doi: 10.1038/s41567-018-0318-2. https://doi.org/10.1038/s41567-018-0318-2 [42] Ramis Movassagh. ``The hardness of random quantum circuits''. Nature PhysicsPages 1–6 (2023). doi: 10.1038/s41567-023-02131-2. https://doi.org/10.1038/s41567-023-02131-2 [43] Yasuhiro Kondo, Ryuhei Mori, and Ramis Movassagh. ``Quantum supremacy and hardness of estimating output probabilities of quantum circuits''. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Pages 1296–1307. IEEE (2022). doi: 10.1109/FOCS52979.2021.00126. https://doi.org/10.1109/FOCS52979.2021.00126 [44] Hari Krovi. ``Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent'' (2022). doi: 10.48550/arXiv.2206.05642. arXiv:2206.05642. https://doi.org/10.48550/arXiv.2206.05642 arXiv:2206.05642 [45] Alex Arkhipov and Greg Kuperberg. ``The bosonic birthday paradox''. Geometry & Topology Monographs 18, 10–2140 (2012). doi: 10.2140/gtm.2012.18.1. https://doi.org/10.2140/gtm.2012.18.1 [46] Tri Dao, Nimit S Sohoni, Albert Gu, Matthew Eichhorn, Amit Blonder, Megan Leszczynski, Atri Rudra, and Christopher Ré. ``Kaleidoscope: An efficient, learnable representation for all structured linear maps'' (2020). doi: 10.48550/arXiv.2012.14966. arXiv:2012.14966. https://doi.org/10.48550/arXiv.2012.14966 arXiv:2012.14966 [47] Byeongseon Go, Changhun Oh, Liang Jiang, and Hyunseok Jeong. ``Exploring shallow-depth boson sampling: Toward a scalable quantum advantage''. Physical Review A 109, 052613 (2024). doi: 10.1103/PhysRevA.109.052613. https://doi.org/10.1103/PhysRevA.109.052613 [48] Larry Stockmeyer. ``On approximation algorithms for# p''. SIAM Journal on Computing 14, 849–861 (1985). doi: 10.1137/0214060. https://doi.org/10.1137/0214060 [49] Seinosuke Toda. ``Pp is as hard as the polynomial-time hierarchy''. SIAM Journal on Computing 20, 865–877 (1991). doi: 10.1137/0220053. https://doi.org/10.1137/0220053 [50] Austin P Lund, Anthony Laing, Saleh Rahimi-Keshari, Terry Rudolph, Jeremy L O’Brien, and Timothy C Ralph. ``Boson sampling from a gaussian state''. Physical review letters 113, 100502 (2014). doi: 10.1103/PhysRevLett.113.100502. https://doi.org/10.1103/PhysRevLett.113.100502 [51] Keisuke Fujii. ``Noise threshold of quantum supremacy'' (2016). doi: 10.48550/arXiv.1610.03632. arXiv:1610.03632. https://doi.org/10.48550/arXiv.1610.03632 arXiv:1610.03632 [52] Robert Raussendorf and Hans J Briegel. ``A one-way quantum computer''. Physical review letters 86, 5188 (2001). doi: 10.1103/PhysRevLett.86.5188. https://doi.org/10.1103/PhysRevLett.86.5188 [53] Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. ``Universal blind quantum computation''. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. Pages 517–526. IEEE (2009). doi: 10.1109/FOCS.2009.36. https://doi.org/10.1109/FOCS.2009.36 [54] Andrew M Childs, Debbie W Leung, and Michael A Nielsen. ``Unified derivations of measurement-based schemes for quantum computation''. Physical Review A 71, 032318 (2005). doi: 10.1103/PhysRevA.71.032318. https://doi.org/10.1103/PhysRevA.71.032318 [55] Emanuel Knill, Raymond Laflamme, and Gerald J Milburn. ``A scheme for efficient quantum computation with linear optics''. nature 409, 46–52 (2001). doi: 10.1038/35051009. https://doi.org/10.1038/35051009 [56] Emanuel Knill. ``Quantum gates using linear optics and postselection''. Physical Review A 66, 052306 (2002). doi: 10.1103/PhysRevA.66.052306. https://doi.org/10.1103/PhysRevA.66.052306 [57] 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). doi: 10.1103/PhysRevLett.117.080501. https://doi.org/10.1103/PhysRevLett.117.080501 [58] Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert. ``Anticoncentration theorems for schemes showing a quantum speedup''. Quantum 2, 65 (2018). doi: 10.22331/q-2018-05-22-65. https://doi.org/10.22331/q-2018-05-22-65 [59] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert. ``Architectures for quantum simulation showing a quantum speedup''. Physical Review X 8, 021010 (2018). doi: 10.1103/PhysRevX.8.021010. https://doi.org/10.1103/PhysRevX.8.021010 [60] Alexander M Dalzell, Nicholas Hunter-Jones, and Fernando GSL Brandão. ``Random quantum circuits anticoncentrate in log depth''. PRX Quantum 3, 010333 (2022). doi: 10.1103/PRXQuantum.3.010333. https://doi.org/10.1103/PRXQuantum.3.010333 [61] Sheldon M Ross. ``Introduction to probability models''. Academic press. (2014). doi: 10.1016/C2012-0-03564-8. https://doi.org/10.1016/C2012-0-03564-8 [62] Peter Clifford and Raphaël Clifford. ``The classical complexity of boson sampling''. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Pages 146–155. SIAM (2018). doi: 10.1137/1.9781611975031.10. https://doi.org/10.1137/1.9781611975031.10Cited byCould not fetch Crossref cited-by data during last attempt 2026-03-13 14:51:24: Could not fetch cited-by data for 10.22331/q-2026-03-13-2026 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-13 14:51:25: No response from ADS or unable to decode the received json data when getting the list of citing works.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.