Simulating boson sampling in lossy architectures

Raúl García-Patrón; Jelmer J. Renema; Valery Shchesnovich

doi:10.22331/q-2019-08-05-169

Simulating boson sampling in lossy architectures

Raúl García-Patrón¹, Jelmer J. Renema^2,3, and Valery Shchesnovich⁴

¹Centre for Quantum Information and Communication, Ecole Polytechnique de Bruxelles, CP 165, Université Libre de Bruxelles, 1050 Brussels, Belgium
²Clarendon Laboratory, Department of Physics, University of Oxford, Oxford OX1 3PU, United Kingdom
³University of Twente, PO Box 217, 7500 AE Enschede, The Netherlands
⁴Centro de Ciências Naturais e Humanas, Universidade Federal do ABC, Santo André, SP, 09210-170 Brazil.

Published:	2019-08-05, volume 3, page 169
Eprint:	arXiv:1712.10037v3
Doi:	https://doi.org/10.22331/q-2019-08-05-169
Citation:	Quantum 3, 169 (2019).

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

Abstract

Photon losses are among the strongest imperfections affecting multi-photon interference. Despite their importance, little is known about their effect on boson sampling experiments. In this work we show that using classical computers, one can efficiently simulate multi-photon interference in all architectures that suffer from an exponential decay of the transmission with the depth of the circuit, such as integrated photonic circuits or optical fibers. We prove that either the depth of the circuit is large enough that it can be simulated by thermal noise with an algorithm running in polynomial time, or it is shallow enough that a tensor network simulation runs in quasi-polynomial time. This result suggests that in order to implement a quantum advantage experiment with single-photons and linear optics new experimental platforms may be needed.

Popular summary

Demonstrating the computational advantage of a quantum over a digital computation is considered the next and most important milestone in the field of quantum computation. Such a demonstration would take the form of a competition, where the quantum and classical computers race to solve a specific computational problem. In the recent years few proposals have emerged as candidates to demonstrate the power of quantum computing. One of this problems is $\textit{boson sampling}$, which is a quantum device using the interference of particles of light (photons) to encode a computation that is believed to be difficult to carry out classically. During the operation of a realistic boson sampler, some photons can be lost to the computation – scattered out of the machine or absorbed in it. An important open question was whether this imperfect quantum computation was still hard for the classical computer to emulate. This question is answered in this work for most known architectures, which suffer from an exponential decay of the transmission with the depth of the circuit, such as integrated photonic circuits or optical fibres. This result suggests that in order to implement a quantum advantage experiment with single-photons and linear optics new experimental platforms may be needed.

► BibTeX data

@article{GarciaPatron2019simulatingboson,
  doi = {10.22331/q-2019-08-05-169},
  url = {https://doi.org/10.22331/q-2019-08-05-169},
  title = {Simulating boson sampling in lossy architectures},
  author = {Garc{\'{i}}a-Patr{\'{o}}n, Ra{\'{u}}l and Renema, Jelmer J. and Shchesnovich, Valery},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {3},
  pages = {169},
  month = aug,
  year = {2019}
}

► References

[1] S. Aaronson. A linear-optical proof that the permanent is #P-hard. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467: 3393–3405, 2011. 10.1098/rspa.2011.0232.
https://doi.org/10.1098/rspa.2011.0232

[2] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing, 9: 143–252, 2013. 10.4086/toc.2013.v009a004.
https://doi.org/10.4086/toc.2013.v009a004

[3] S. Aaronson and D. J. Brod. Boson sampling with lost photons. Phys. Rev. A, 93: 012335, 2016. 10.1103/PhysRevA.93.012335.
https://doi.org/10.1103/PhysRevA.93.012335

[4] A. Arkhipov and G. Kuperberg. The bosonic birthday paradox. Geometry & Topology Monographs, 18: 1, 2012. 10.2140/gtm.2012.18.1.
https://doi.org/10.2140/gtm.2012.18.1

[5] A. D. Barbour and P. Hall. On the rate of poisson convergence. Mathematical Proceedings of the Cambridge Philosophical Society, 95: 473–480, 1984. 10.1017/S0305004100061806.
https://doi.org/10.1017/S0305004100061806

[6] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert. Architectures for quantum simulation showing a quantum speedup. Phys. Rev. X, 8: 021010, 2018. 10.1103/PhysRevX.8.021010.
https://doi.org/10.1103/PhysRevX.8.021010

[7] M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White. Photonic boson sampling in a tunable circuit. Science, 339: 794–798, 2013. 10.1126/science.1231440.
https://doi.org/10.1126/science.1231440

[8] E. R. Caianiello. On quantum field theory i: explicit solution of dyson's equation in electrodynamics without use of feynman graphs. Il Nuovo Cimento, 10: 1634–1652, 1953. 10.1007/BF02781659.
https://doi.org/10.1007/BF02781659

[9] R. A. Campos, B. E. A. Saleh, and M. C. Teich. Quantum-mechanical lossless beam splitter: SU(2) symmetry and photon statistics. Phys. Rev. A, 40: 1371–1384, 1989. 10.1103/PhysRevA.40.1371.
https://doi.org/10.1103/PhysRevA.40.1371

[10] J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing. Universal linear optics. Science, 349: 711–716, 2015. 10.1126/science.aab3642.
https://doi.org/10.1126/science.aab3642

[11] L. Chakhmakhchyan and N. J. Cerf. Boson sampling with gaussian measurements. Phys. Rev. A, 96: 032326, 2017. 10.1103/PhysRevA.96.032326.
https://doi.org/10.1103/PhysRevA.96.032326

[12] W. R. Clements, P. C. Humphreys, B. J. Metcalf, W. S. Kolthammer, and I. A. Walmsley. Optimal design for universal multiport interferometers. Optica, 3: 1460–1465, 2016. 10.1364/OPTICA.3.001460.
https://doi.org/10.1364/OPTICA.3.001460

[13] P. Clifford and R. Clifford. The classical complexity of boson sampling. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 146–155, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathematics. ISBN 978-1-6119-7503-1. URL http://dl.acm.org/citation.cfm?id=3174304.3175276.
http://dl.acm.org/citation.cfm?id=3174304.3175276

[14] A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvão, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino. Experimental boson sampling. Nat. Photonics, 7: 540, 2013. 10.1038/nphoton.2013.112.
https://doi.org/10.1038/nphoton.2013.112

[15] H. Defienne, M. Barbieri, I. A. Walmsley, B. J. Smith, and S. Gigan. Two-photon quantum walk in a multimode fiber. Science Advances, 2, 2016. 10.1126/sciadv.1501054.
https://doi.org/10.1126/sciadv.1501054

[16] R. Laflamme E. Knill and G. J. Millburn. A scheme for efficient quantum computation with linear optics. Nature, 409: 46, 2001. 10.1038/35051009.
https://doi.org/10.1038/35051009

[17] V. Giovannetti, A. S. Holevo, and R. Garcia-Patron. A solution of gaussian optimizer conjecture for quantum channels. Communications in Mathematical Physics, 334: 1553–1571, 2015. 10.1007/s00220-014-2150-6.
https://doi.org/10.1007/s00220-014-2150-6

[18] R. J. Glauber. Quantum Theory of Optical Coherence: Selected Papers and Lectures. Wiley-VCH Verlag, Weinheim, Germany, 10th edition, 2007. ISBN 9783527610075. 10.1002/9783527610075.
https://doi.org/10.1002/9783527610075

[19] N. C. Harris, D. Bunandar, M. Pant, G. R. Steinbrecher J. Mower, M. Prabhu, T. Baehr-Jones, M. Hochberg, and D. Englund. Large-scale quantum photonic circuits in silicon. Nanophotonics, 5: 456, 2016. 10.1515/nanoph-2015-0146.
https://doi.org/10.1515/nanoph-2015-0146

[20] Y. He, X. Ding, Z.-E. Su, H.-L. Huang, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, W.-J. Zhang, S.-J. Chen, C. Schneider, M. Kamp, L.-X. You, Z. Wang, S. Höfling, Chao-Yang Lu, and J.-W. Pan. Time-bin-encoded boson sampling with a single-photon device. Phys. Rev. Lett., 118: 190501, 2017. 10.1103/PhysRevLett.118.190501.
https://doi.org/10.1103/PhysRevLett.118.190501

[21] M. J. R. Heck, J. F. Bauters, M. L. Davenport, D. T. Spencer, and J. E. Bowers. Ultra-low loss waveguide platform and its integration with silicon photonics. Laser & Photonics Reviews, 8: 667–686, 2014. 10.1002/lpor.201300183.
https://doi.org/10.1002/lpor.201300183

[22] R. Jozsa. On the simulation of quantum circuits. arXiv, page 0603163, 2006. URL https://arxiv.org/abs/quant-ph/0603163.
arXiv:quant-ph/0603163

[23] M. S. Kim, W. Son, V. Bužek, and P. L. Knight. Entanglement by a beam splitter: Nonclassicality as a prerequisite for entanglement. Phys. Rev. A, 65: 032323, 2002. 10.1103/PhysRevA.65.032323.
https://doi.org/10.1103/PhysRevA.65.032323

[24] D. E. Knuth. The Art of Computer Programming, Volume 1 (3rd Ed.): Fundamental Algorithms. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1997. ISBN 0-201-89683-4.

[25] P. Kok, W. J. Munro, K. Nemoto, T. C. Ralph, J. P. Dowling, and G. J. Milburn. Linear optical quantum computing with photonic qubits. Rev. Mod. Phys., 79: 135–174, 2007. 10.1103/RevModPhys.79.135.
https://doi.org/10.1103/RevModPhys.79.135

[26] I. Krasikov. Nonnegative quadratic forms and bounds on orthogonal polynomials. J. Approx. Theory, 111: 31–49, 2001. 10.1006/jath.2001.3570.
https://doi.org/10.1006/jath.2001.3570

[27] F. Lacerda, J. M. Renes, and V. B. Scholz. Coherent-state constellations and polar codes for thermal gaussian channels. Phys. Rev. A, 95: 062343, 2017. 10.1103/PhysRevA.95.062343.
https://doi.org/10.1103/PhysRevA.95.062343

[28] L.G.Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8: 189–201, 1979. 10.1016/0304-3975(79)90044-6.
https://doi.org/10.1016/0304-3975(79)90044-6

[29] M. Lubasch, A. Valido, J. Renema, W. S. Kolthammer, D. Jaksch, M. S. Kim, I. Walmsley, and R. García-Patrón. Tensor network states in time-bin quantum optics. Phys. Rev. A, 97: 062304, 2018. 10.1103/PhysRevA.97.062304.
https://doi.org/10.1103/PhysRevA.97.062304

[30] A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O'Brien, and T. C. Ralph. Boson sampling from a gaussian state. Phys. Rev. Lett., 113: 100502, 2014. 10.1103/PhysRevLett.113.100502.
https://doi.org/10.1103/PhysRevLett.113.100502

[31] A. P. Lund, S. Rahimi-Keshari, and T. C. Ralph. Exact boson sampling using gaussian continuous-variable measurements. Phys. Rev. A, 96: 022301, 2017. 10.1103/PhysRevA.96.022301.
https://doi.org/10.1103/PhysRevA.96.022301

[32] A. Mari and J. Eisert. Positive wigner functions render classical simulation of quantum computation efficient. Phys. Rev. Lett., 109: 230503, 2012. 10.1103/PhysRevLett.109.230503.
https://doi.org/10.1103/PhysRevLett.109.230503

[33] A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing. Experimental boson sampling. Nature Physics, 13: 1153, 2017. 10.1038/nphys4270.
https://doi.org/10.1038/nphys4270

[34] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, New York, NY, USA, 10th edition, 2011. ISBN 1107002176, 9781107002173. 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[35] R. Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 349: 117 – 158, 2014. 10.1016/j.aop.2014.06.013.
https://doi.org/10.1016/j.aop.2014.06.013

[36] S. Ostlund and S. Rommer. Thermodynamic limit of density matrix renormalization. Phys. Rev. Lett., 75: 3537–3540, 1995. 10.1103/PhysRevLett.75.3537.
https://doi.org/10.1103/PhysRevLett.75.3537

[37] Michał Oszmaniec and Daniel J Brod. Classical simulation of photonic linear optics with lost particles. New Journal of Physics, 20: 092002, 2018. 10.1088/1367-2630/aadfa8.
https://doi.org/10.1088/1367-2630/aadfa8

[38] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac. Matrix product state representations. Quantum Info. Comput., 7: 401–430, 2007.

[39] R. Prevedel, P. Walther, F. Tiefenbacher, P. Böhi, R. Kaltenbaek, T. Jennewein, and A. Zeilinger. High-speed linear optics quantum computing using active feed-forward. Nature, 445: 65–69, 2007. 10.1038/nature05346.
https://doi.org/10.1038/nature05346

[40] S. Rahimi-Keshari, M. A. Broome, R. Fickler, A. Fedrizzi, T. C. Ralph, and A. G. White. Direct characterization of linear-optical networks. Opt. Express, 21: 13450–13458, 2013. 10.1364/OE.21.013450.
https://doi.org/10.1364/OE.21.013450

[41] S. Rahimi-Keshari, A. P. Lund, and T. C. Ralph. What can quantum optics say about computational complexity theory? Phys. Rev. Lett., 114: 060501, 2015. 10.1103/PhysRevLett.114.060501.
https://doi.org/10.1103/PhysRevLett.114.060501

[42] S. Rahimi-Keshari, T. C. Ralph, and C. M. Caves. Sufficient conditions for efficient classical simulation of quantum optics. Phys. Rev. X, 6: 021039, 2016. 10.1103/PhysRevX.6.021039.
https://doi.org/10.1103/PhysRevX.6.021039

[43] M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani. Experimental realization of any discrete unitary operator. Phys. Rev. Lett., 73: 58–61, 1994. 10.1103/PhysRevLett.73.58.
https://doi.org/10.1103/PhysRevLett.73.58

[44] J. Renema, V. Shchesnovich, and R. Garcia-Patron. Classical simulability of noisy boson sampling. arXiv, page 809.01953, 2018a. URL https://arxiv.org/abs/1809.01953.
arXiv:1809.01953

[45] J. J. Renema, A. Menssen, W. R. Clements, G. Triginer, W. S. Kolthammer, and I. A. Walmsley. Efficient classical algorithm for boson sampling with partially distinguishable photons. Phys. Rev. Lett., 120: 220502, 2018b. 10.1103/PhysRevLett.120.220502.
https://doi.org/10.1103/PhysRevLett.120.220502

[46] T. Rudolph. Why I am optimistic about the silicon-photonic route to quantum computing. APL Photonics, 2: 030901, 2017. 10.1063/1.4976737.
https://doi.org/10.1063/1.4976737

[47] J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X.-M. Jin, Ma. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley. Boson sampling on a photonic chip. Science, 339: 798–801, 2013. 10.1126/science.1231692.
https://doi.org/10.1126/science.1231692

[48] C. Taballione, T. A. W. Wolterink, J. Lugani, A. Eckstein, B. A. Bell, R. Grootjans, I. Visscher, J. J. Renema, D. Geskus, C. G. H. Roeloffzen, I. A. Walmsley, P. W. H. Pinkse, and K.-J. Boller. 8x8 programmable quantum photonic processor based on silicon nitride waveguides. In Frontiers in Optics / Laser Science. Optical Society of America, 2018. 10.1364/FIO.2018.JTu3A.58.
https://doi.org/10.1364/FIO.2018.JTu3A.58

[49] K. Temme and P. Wocjan. Efficient computation of the permanent of block factorizable matrices. arXiv, page 1208.6589, 2012. URL https://arxiv.org/abs/1208.6589.
arXiv:1208.6589

[50] K. Temme, M. J. Kastoryano, M. B. Ruskai, M. M. Wolf, and F. Verstraete. The $\chi^2$-divergence and mixing times of quantum markov processes. Journal of Mathematical Physics, 51: 122201, 2010. 10.1063/1.3511335.
https://doi.org/10.1063/1.3511335

[51] M. Tillmann, B. Dakić, R. Heilmann, S. Nolte, A. Szameit, and P. Walther. Experimental boson sampling. Nat. Photonics, 7: 540, 2013. 10.1038/nphoton.2013.102.
https://doi.org/10.1038/nphoton.2013.102

[52] V. Veitch, C. Ferrie, D. Gross, and J. Emerson. Negative quasi-probability as a resource for quantum computation. New Journal of Physics, 14: 113011, 2012. 10.1088/1367-2630/14/11/113011.
https://doi.org/10.1088/1367-2630/14/11/113011

[53] F. Verstraete, D. Porras, and J. I. Cirac. Density matrix renormalization group and periodic boundary conditions: A quantum information perspective. Phys. Rev. Lett., 93: 227205, 2004. 10.1103/PhysRevLett.93.227205.
https://doi.org/10.1103/PhysRevLett.93.227205

[54] G. Vidal. Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett., 91: 147902, 2003. 10.1103/PhysRevLett.91.147902.
https://doi.org/10.1103/PhysRevLett.91.147902

[55] H. Wang, W. Li, X. Jiang, Y.-M. He, Y.-H. Li, X. Ding, M.-C. Chen, J. Qin, C.-Z. Peng, C. Schneider, M. Kamp, W.-J. Zhang, H. Li, L.-X. You, Z. Wang, J. P. Dowling, S. Höfling, C.-Y. Lu, and J.-W. Pan. Toward scalable boson sampling with photon loss. Phys. Rev. Lett., 120: 230502, 2018. 10.1103/PhysRevLett.120.230502.
https://doi.org/10.1103/PhysRevLett.120.230502

[56] S. R. White. Density matrix formulation for quantum renormalization groups. Phys. Rev. Lett., 69: 2863–2866, 1992. 10.1103/PhysRevLett.69.2863.
https://doi.org/10.1103/PhysRevLett.69.2863

[57] Y. Wu and S. Verdú. The impact of constellation cardinality on gaussian channel capacity. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 620–628, 2010. 10.1109/ALLERTON.2010.5706965.
https://doi.org/10.1109/ALLERTON.2010.5706965

Cited by

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

[2] Jordi Tura, "Photon losses create tension for Gaussian boson sampling", Nature Physics 20 9, 1371 (2024).

[3] Alexandra E. Moylett, "Spot the Difference: Distinguishing Boson Sampling Experiments from Classical Simulations", Quantum Views 5, 53 (2021).

[4] E.N. Bashmakova, S.B. Korolev, and T.Yu. Golubeva, "Comparison of Controlled-Z operation and beam-splitter transformation for generation of squeezed Fock states by measurement", Physics Letters A 526, 129964 (2024).

[5] Changhun Oh, Youngrong Lim, Bill Fefferman, and Liang Jiang, "Classical Simulation of Boson Sampling Based on Graph Structure", Physical Review Letters 128 19, 190501 (2022).

[6] Jihua Zhang and Andrey A. Sukhorukov, "Complex structure and efficient characterization of multiphoton split states in integrated circuits", Physical Review A 107 6, 062615 (2023).

[7] 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, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Jelmer J. Renema, Chao-Yang Lu, and Jian-Wei Pan, "Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light", Physical Review Letters 127 18, 180502 (2021).

[8] Nicolò Spagnolo, Daniel J. Brod, Ernesto F. Galvão, and Fabio Sciarrino, "Non-linear Boson Sampling", npj Quantum Information 9 1, 3 (2023).

[9] Abhinav Deshpande, Arthur Mehta, Trevor Vincent, Nicolás Quesada, Marcel Hinsche, Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi, Jens Eisert, Dominik Hangleiter, Bill Fefferman, and Ish Dhand, "Quantum computational advantage via high-dimensional Gaussian boson sampling", Science Advances 8 1, eabi7894 (2022).

[10] S. N. van den Hoven, E. Kanis, and J. J. Renema, "Efficient classical algorithm for simulating boson sampling with heterogeneous partial distinguishability", Physical Review A 111 5, 052448 (2025).

[11] Changhun Oh, Kyungjoo Noh, Bill Fefferman, and Liang Jiang, "Classical simulation of lossy boson sampling using matrix product operators", Physical Review A 104 2, 022407 (2021).

[12] Malaquias Correa Anguita, Anita Camillini, Sara Marzban, Marco Robbio, Benoit Seron, Leonardo Novo, and Jelmer J Renema, "Experimental validation of boson sampling using detector binning", Quantum Science and Technology 10 3, 035062 (2025).

[13] Alex Neville, "Simulating lossy multiphoton linear optics experiments", Quantum Views 3, 19 (2019).

[14] Taira Giordani, Valerio Mannucci, Nicolò Spagnolo, Marco Fumero, Arianna Rampini, Emanuele Rodolà, and Fabio Sciarrino, "Certification of Gaussian Boson Sampling via graphs feature vectors and kernels", Quantum Science and Technology 8 1, 015005 (2023).

[15] V. S. Shchesnovich and M. E. O. Bezerra, "Distinguishability theory for time-resolved photodetection and boson sampling", Physical Review A 101 5, 053853 (2020).

[16] Gregory Morse, Tomasz Rybotycki, Ágoston Kaposi, Zoltán Kolarovszki, Uroš Stojčić, Tamás Kozsik, Oskar Mencer, Michał Oszmaniec, Zoltán Zimborás, and Péter Rakyta, "High performance Boson sampling simulation via data-flow engines", New Journal of Physics 26 3, 033033 (2024).

[17] Changhun Oh, Minzhao Liu, Yuri Alexeev, Bill Fefferman, and Liang Jiang, "Classical algorithm for simulating experimental Gaussian boson sampling", Nature Physics 20 9, 1461 (2024).

[18] I. S. Yeremenko, M. A. Dmytruk, and A. A. Semenov, "Realistic photon-number resolution in Gaussian boson sampling", Physical Review A 110 4, 043715 (2024).

[19] Changhun Oh, "Classical simulability of constant-depth linear-optical circuits with noise", npj Quantum Information 11 1, 126 (2025).

[20] Thomas Schuster, Chao Yin, Xun Gao, and Norman Y. Yao, "A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits", Physical Review X 15 4, 041018 (2025).

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

[22] Anna Romanova, Konstantin Katamadze, Grant Avosopiants, Leon Biguaa, Nikolay Skryabin, Alexander Kalinkin, Ivan Dyakonov, Yurii Bogdanov, and Sergei Kulik, "Time-domain Hong–Ou–Mandel interference of quasi-thermal fields and its application in linear optical circuit characterization", Optics Letters 47 18, 4708 (2022).

[23] Tamal Guha, Mir Alimuddin, Sumit Rout, Amit Mukherjee, Some Sankar Bhattacharya, and Manik Banik, "Quantum Advantage for Shared Randomness Generation", Quantum 5, 569 (2021).

[24] Martin Esmann, Stephen C. Wein, and Carlos Antón‐Solanas, "Solid‐State Single‐Photon Sources: Recent Advances for Novel Quantum Materials", Advanced Functional Materials 34 30, 2315936 (2024).

[25] Mikhail V. Umanskii and Alexey N. Rubtsov, "Classical Modeling of a Lossy Gaussian Bosonic Sampler", Entropy 26 6, 493 (2024).

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

[27] Benoit Seron and Antoine Restivo, "BosonSampling.jl: A Julia package for quantum multi-photon interferometry", Quantum 8, 1378 (2024).

[28] Samo Novák and Raúl García-Patrón, "Laplace expansions and tree decompositions: A faster polytime algorithm for shallow nearest-neighbor boson sampling", Physical Review A 113 3, 032428 (2026).

[29] Hamza Hasnaoui, Leonardo Limongi, Taira Giordani, Beatrice Polacchi, Alberto Quaranta, Martino Bernard, Fabio Sciarrino, and Mirko Lobino, "Optical quantum computing", Applied Physics Reviews 13 3, 031306 (2026).

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

[31] Magdalena Parýzková, Craig S. Hamilton, Igor Jex, Michael Stefszky, and Christine Silberhorn, "Input phase noise in Gaussian boson sampling", Physical Review A 114 2, 022203 (2026).

[32] Daniel Jost Brod and Michał Oszmaniec, "Classical simulation of linear optics subject to nonuniform losses", Quantum 4, 267 (2020).

[33] Ulysse Chabaud, Damian Markham, and Adel Sohbi, "Quantum machine learning with adaptive linear optics", Quantum 5, 496 (2021).

[34] Giacomo Franceschetto and Arno Ricou, "Demonstration of quantum projective simulation on a single-photon-based quantum computer", Physical Review A 110 6, 062613 (2024).

[35] Samo Novák, David D. Roberts, Alexander Makarovskiy, Raúl García-Patrón, and William R. Clements, "Boundaries for quantum advantage with single photons and loop-based time-bin interferometers", Quantum 9, 1915 (2025).

[36] Zoltán Kolarovszki, Tomasz Rybotycki, Péter Rakyta, Ágoston Kaposi, Boldizsár Poór, Szabolcs Jóczik, Dániel T. R. Nagy, Henrik Varga, Kareem H. El-Safty, Gregory Morse, Michał Oszmaniec, Tamás Kozsik, and Zoltán Zimborás, "Piquasso: A Photonic Quantum Computer Simulation Software Platform", Quantum 9, 1708 (2025).

[37] Byeongseon Go, Changhun Oh, and Hyunseok Jeong, "On computational complexity and average-case hardness of shallow-depth boson sampling", Quantum 10, 2026 (2026).

[38] Alexander S. Dellios, Margaret D. Reid, and Peter D. Drummond, "Simulating Gaussian boson sampling quantum computers", AAPPS Bulletin 33 1, 31 (2023).

[39] Wentao Chen, Yao Lu, Shuaining Zhang, Kuan Zhang, Guanhao Huang, Mu Qiao, Xiaolu Su, Jialiang Zhang, Jing-Ning Zhang, Leonardo Banchi, M. S. Kim, and Kihwan Kim, "Scalable and programmable phononic network with trapped ions", Nature Physics 19 6, 877 (2023).

[40] Byeongseon Go, Changhun Oh, and Hyunseok Jeong, "Quantum Computational Advantage of Noisy Boson Sampling with Partially Distinguishable Photons", PRX Quantum 6 3, 030362 (2025).

[41] Ulysse Chabaud, Frédéric Grosshans, Elham Kashefi, and Damian Markham, "Efficient verification of Boson Sampling", Quantum 5, 578 (2021).

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

[43] Minzhao Liu, Changhun Oh, Junyu Liu, Liang Jiang, and Yuri Alexeev, "Simulating lossy Gaussian boson sampling with matrix-product operators", Physical Review A 108 5, 052604 (2023).

[44] R. van der Meer, J. J. Renema, B. Brecht, C. Silberhorn, and P. W. H. Pinkse, "Optimizing spontaneous parametric down-conversion sources for boson sampling", Physical Review A 101 6, 063821 (2020).

[45] 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 5, 052412 (2022).

[46] Francesco Hoch, Simone Piacentini, Taira Giordani, Zhen-Nan Tian, Mariagrazia Iuliano, Chiara Esposito, Anita Camillini, Gonzalo Carvacho, Francesco Ceccarelli, Nicolò Spagnolo, Andrea Crespi, Fabio Sciarrino, and Roberto Osellame, "Reconfigurable continuously-coupled 3D photonic circuit for Boson Sampling experiments", npj Quantum Information 8 1, 55 (2022).

[47] Gabriele Bressanini, Hyukjoon Kwon, and M. S. Kim, "Noise thresholds for classical simulability of nonlinear boson sampling", Physical Review A 106 4, 042413 (2022).

[48] Changhun Oh and Youngrong Lim, "Classical Algorithms for Measurement-Adaptive Gaussian Circuits", PRX Quantum 7 1, 010329 (2026).

[49] Kyungjoo Noh, S. M. Girvin, and Liang Jiang, "Encoding an Oscillator into Many Oscillators", Physical Review Letters 125 8, 080503 (2020).

[50] Milica Banic, Luca Zatti, Marco Liscidini, and J. E. Sipe, "Two strategies for modeling nonlinear optics in lossy integrated photonic structures", Physical Review A 106 4, 043707 (2022).

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

[52] J. F. F. Bulmer, S. Paesani, R. S. Chadwick, and N. Quesada, "Threshold detection statistics of bosonic states", Physical Review A 106 4, 043712 (2022).

[53] Mikhail Umanskii and Alexey N. Rubtsov, "Classical Modelling of a Bosonic Sampler with Photon Collisions", Entropy 25 2, 210 (2023).

[54] Ken Mochizuki and Ryusuke Hamazaki, "Distinguishability transitions in nonunitary boson-sampling dynamics", Physical Review Research 5 1, 013177 (2023).

[55] Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernández, and Michał Oszmaniec, "Complexity-Theoretic Foundations of BosonSampling with a Linear Number of Modes", Physical Review X 16 2, 021059 (2026).

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

[57] Yukuan Zhao, Xiao-Ye Xu, Chuan-Feng Li, and Guang-Can Guo, "Boosting Gaussian boson sampling using optical parametric amplification networks", Physical Review A 113 6, 062433 (2026).

[58] Raphael A. Abrahao, Arman Mansouri, and Austin P. Lund, "Boson sampling with Gaussian input states: Toward efficient scaling and certification", Physical Review A 110 5, 052437 (2024).

[59] Rawad Mezher, Ana Filipa Carvalho, and Shane Mansfield, "Solving graph problems with single photons and linear optics", Physical Review A 108 3, 032405 (2023).

[60] Yuan Liu, Shraddha Singh, Kevin C. Smith, Eleanor Crane, John M. Martyn, Alec Eickbusch, Alexander Schuckert, Richard D. Li, Jasmine Sinanan-Singh, Micheline B. Soley, Takahiro Tsunoda, Isaac L. Chuang, Nathan Wiebe, and Steven M. Girvin, "Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications", PRX Quantum 7 1, 010201 (2026).

[61] Trevor Vincent, Lee J. O'Riordan, Mikhail Andrenkov, Jack Brown, Nathan Killoran, Haoyu Qi, and Ish Dhand, "Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction", Quantum 6, 709 (2022).

[62] Jacob F. F. 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, Ian A. Walmsley, and Anthony Laing, "The boundary for quantum advantage in Gaussian boson sampling", Science Advances 8 4, eabl9236 (2022).

[63] Yang Ji, Mei-Ling Chen, Xun Huang, Yong-Zheng Wu, and Bing Lan, "Simulation of random photon loss in boson sampling of different optical networks", Acta Physica Sinica 71 19, 190301 (2022).

[64] He-Liang Huang, Wan-Su Bao, and Chu Guo, "Simulating the dynamics of single photons in boson sampling devices with matrix product states", Physical Review A 100 3, 032305 (2019).

[65] N. Quesada, L. G. Helt, M. Menotti, M. Liscidini, and J. E. Sipe, "Beyond photon pairs—nonlinear quantum photonics in the high-gain regime: a tutorial", Advances in Optics and Photonics 14 3, 291 (2022).

[66] Ravitej Uppu, Freja T. Pedersen, Ying Wang, Cecilie T. Olesen, Camille Papon, Xiaoyan Zhou, Leonardo Midolo, Sven Scholz, Andreas D. Wieck, Arne Ludwig, and Peter Lodahl, "Scalable integrated single-photon source", Science Advances 6 50, eabc8268 (2020).

[67] James Mills and Rawad Mezher, "Mitigating photon loss in linear optical quantum circuits", Quantum 10, 2030 (2026).

[68] Stephen C. Wein, "Simulating photon counting from dynamic quantum emitters by exploiting zero-photon measurements", Physical Review A 109 2, 023713 (2024).

[69] Ulysse Chabaud and Mattia Walschaers, "Resources for Bosonic Quantum Computational Advantage", Physical Review Letters 130 9, 090602 (2023).

[70] Benoit Seron, Leonardo Novo, Alex Arkhipov, and Nicolas J. Cerf, "Efficient validation of Boson Sampling from binned photon-number distributions", Quantum 8, 1479 (2024).

[71] Byeongseon Go, Changhun Oh, Liang Jiang, and Hyunseok Jeong, "Exploring shallow-depth boson sampling: Toward a scalable quantum advantage", Physical Review A 109 5, 052613 (2024).

[72] Massimo Frigerio, Antoine Debray, Nicolas Treps, and Mattia Walschaers, "Resourcefulness of non-classical continuous-variable quantum gates", Quantum 10, 2155 (2026).

[73] 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 10, 100502 (2020).

[74] Tian-Yu Yang, Yi-Xin Shen, Zhou-Kai Cao, and Xiang-Bin Wang, "Post-selection in noisy Gaussian boson sampling: part is better than whole", Quantum Science and Technology 8 4, 045020 (2023).

[75] Aaron W. Young, Shawn Geller, William J. Eckner, Nathan Schine, Scott Glancy, Emanuel Knill, and Adam M. Kaufman, "An atomic boson sampler", Nature 629 8011, 311 (2024).

[76] G.S. Thekkadath, S. Sempere-Llagostera, B.A. Bell, R.B. Patel, M.S. Kim, and I.A. Walmsley, "Experimental Demonstration of Gaussian Boson Sampling with Displacement", PRX Quantum 3 2, 020336 (2022).

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

[78] Denis Stanev, Taira Giordani, Nicolò Spagnolo, and Fabio Sciarrino, "Validation of a noisy Gaussian boson sampler via graph theory", Advanced Photonics Nexus 4 01, 016011 (2025).

[79] Mateusz Slysz, Krzysztof Kurowski, and Jan Węglarz, Lecture Notes in Computer Science 13827, 177 (2023) ISBN:978-3-031-30444-6.

[80] Timothée Goubault De Brugière and Nicolas Heurtel, "Fast and memory-efficient strong simulation of noisy adaptive linear optical circuits", Computer Physics Communications 321, 110016 (2026).

[81] Francesco Hoch, Eugenio Caruccio, Giovanni Rodari, Tommaso Francalanci, Alessia Suprano, Taira Giordani, Gonzalo Carvacho, Nicolò Spagnolo, Seid Koudia, Massimiliano Proietti, Carlo Liorni, Filippo Cerocchi, Riccardo Albiero, Niki Di Giano, Marco Gardina, Francesco Ceccarelli, Giacomo Corrielli, Ulysse Chabaud, Roberto Osellame, Massimiliano Dispenza, and Fabio Sciarrino, "Quantum machine learning with Adaptive Boson Sampling via post-selection", Nature Communications 16 1, 902 (2025).

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

[83] A.P. Lund and T.C. Ralph, Encyclopedia of Mathematical Physics 42 (2025) ISBN:9780323957069.

[84] S. V. Tarasov and Vl. V. Kocharovsky, "Boson sampling with self-generation of squeezing via interaction of photons and atoms", Physical Review A 113 3, 032615 (2026).

[85] 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 1, 015001 (2020).

[86] Marco Fellous-Asiani, Moein Naseri, Chandan Datta, Alexander Streltsov, and Michał Oszmaniec, "Scalable noisy quantum circuits for biased-noise qubits", npj Quantum Information 11 1, 145 (2025).

[87] Dario Cilluffo, Matthias Kost, Nicola Lorenzoni, and Martin B. Plenio, "Heisenberg picture tensor network formalism for optical circuits", Physical Review Research 8 2, 023098 (2026).

[88] Fulvio Flamini, Nicolò Spagnolo, and Fabio Sciarrino, "Photonic quantum information processing: a review", Reports on Progress in Physics 82 1, 016001 (2019).

[89] Hui Wang, Wei Li, Xiao Jiang, Y.-M. He, Y.-H. Li, X. Ding, M.-C. Chen, J. Qin, C.-Z. Peng, C. Schneider, M. Kamp, W.-J. Zhang, H. Li, L.-X. You, Z. Wang, J. P. Dowling, S. Höfling, Chao-Yang Lu, and Jian-Wei Pan, "Toward Scalable Boson Sampling with Photon Loss", Physical Review Letters 120 23, 230502 (2018).

[90] Michał Oszmaniec and Daniel J. Brod, "Classical simulation of photonic linear optics with lost particles", New Journal of Physics 20 9, 092002 (2018).

[91] William R. Clements, Jelmer J. Renema, Andreas Eckstein, Antonio A. Valido, Adriana Lita, Thomas Gerrits, Sae Woo Nam, W. Steven Kolthammer, Joonsuk Huh, and Ian A. Walmsley, "Approximating vibronic spectroscopy with imperfect quantum optics", Journal of Physics B Atomic Molecular Physics 51 24, 245503 (2018).

[92] Jinli Chen, Chaohan Cui, Ben Lawrie, Yongzhou Xue, Saikat Guha, Matt Eichenfield, Huan Zhao, and Xiaodong Yan, "Low-dimensional solid-state single-photon emitters", Nanophotonics 14 11, 1687 (2025).

[93] Leonardo Banchi, W. Steven Kolthammer, and M. S. Kim, "Multiphoton Tomography with Linear Optics and Photon Counting", Physical Review Letters 121 25, 250402 (2018).

[94] V. S. Shchesnovich, "Noise in boson sampling and the threshold of efficient classical simulatability", Physical Review A 100 1, 012340 (2019).

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

[96] Emilio Annoni and Stephen C. Wein, "Incoherent behavior of partially distinguishable photons", arXiv:2502.05047, (2025).

[97] Haoyu Qi, Lukas G. Helt, Daiqin Su, Zachary Vernon, and Kamil Brádler, "Linear multiport photonic interferometers: loss analysis of temporally-encoded architectures", arXiv:1812.07015, (2018).

[98] Jelmer J. Renema, "Marginal probabilities in boson samplers with arbitrary input states", arXiv:2012.14917, (2020).

[99] Benoit Seron, Leonardo Novo, Alex Arkhipov, and Nicolas J. Cerf, "Efficient validation of Boson Sampling from binned photon-number distributions", arXiv:2212.09643, (2022).

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

[101] Magdalena Parýzková, Craig S. Hamilton, Igor Jex, Michael Stefszky, and Christine Silberhorn, "Input phase noise in Gaussian Boson sampling", arXiv:2512.19596, (2025).

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

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.

Simulating boson sampling in lossy architectures

Abstract

Popular summary

► BibTeX data

► References

Cited by

1 thought on “Simulating boson sampling in lossy architectures”