{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T10:20:30Z","timestamp":1774952430319,"version":"3.50.1"},"reference-count":45,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T00:00:00Z","timestamp":1589414400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We present a comprehensive study of the impact of non-uniform, i.e. path-dependent, photonic losses on the computational complexity of linear-optical processes. Our main result states that, if each beam splitter in a network induces some loss probability, non-uniform network designs cannot circumvent the efficient classical simulations based on losses.To achieve our result we obtain new intermediate results that can be of independent interest. First we show that, for any network of lossy beam-splitters, it is possible to extract a layer of non-uniform losses that depends on the network geometry. We prove that, for every input mode of the network it is possible to commute<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>s<\/mml:mi><mml:mi>i<\/mml:mi><\/mml:msub><\/mml:math>layers of losses to the input, where<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>s<\/mml:mi><mml:mi>i<\/mml:mi><\/mml:msub><\/mml:math>is the length of the shortest path connecting the<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>i<\/mml:mi><\/mml:math>th input to any output. We then extend a recent classical simulation algorithm due to P. Clifford and R. Clifford to allow for arbitrary<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math>-photon input Fock states (i.e. to include collision states). Consequently, we identify two types of input states where boson sampling becomes classically simulable: (A) when<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math>input photons occupy a constant number of input modes; (B) when all but<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>O<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>log<\/mml:mi><mml:mo>\u2061<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>photons are concentrated on a single input mode, while an additional<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>O<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>log<\/mml:mi><mml:mo>\u2061<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>modes contain one photon each.<\/jats:p>","DOI":"10.22331\/q-2020-05-14-267","type":"journal-article","created":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T15:47:41Z","timestamp":1589471261000},"page":"267","source":"Crossref","is-referenced-by-count":34,"title":["Classical simulation of linear optics subject to nonuniform losses"],"prefix":"10.22331","volume":"4","author":[{"given":"Daniel Jost","family":"Brod","sequence":"first","affiliation":[{"name":"Instituto de F\u00edsica, Universidade Federal Fluminense, Niter\u00f3i, RJ, 24210-340, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Oszmaniec","sequence":"additional","affiliation":[{"name":"International Centre for Theory of Quantum Technologies, University of Gdansk, Wita Stwosza 63, 80-308 Gdansk, Poland"},{"name":"Center for Theoretical Physics, Polish Academy of Sciences, Al. Lotnik\u00f3w 32\/46, 02-668 Warszawa, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2020,5,14]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"A. Harrow and A. Montanaro. Quantum computational supremacy. Nature, 549: 203\u2013209, 2017. 10.1038\/nature23458.","DOI":"10.1038\/nature23458"},{"key":"1","doi-asserted-by":"publisher","unstructured":"S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing, 4: 143\u2013252, 2013. 10.4086\/toc.2013.v009a004.","DOI":"10.4086\/toc.2013.v009a004"},{"key":"2","doi-asserted-by":"publisher","unstructured":"D. J. Brod, E. F. Galv\u00e3o, A. Crespi, R. Osellame, N. Spagnolo, and F. Sciarrino. Photonic implementation of boson sampling: a review. Advanced Photonics, 1 (3): 1\u201314, 2019. 10.1117\/1.AP.1.3.034001.","DOI":"10.1117\/1.AP.1.3.034001"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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 (6121): 794, 2013. 10.1126\/science.1231440.","DOI":"10.1126\/science.1231440"},{"key":"4","doi-asserted-by":"publisher","unstructured":"A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galv\u00e3o, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino. Integrated multimode interferometers with arbitrary designs for photonic Boson Sampling. Nat. Photon., 7 (7): 545\u2013549, 2013. 10.1038\/nphoton.2013.112.","DOI":"10.1038\/nphoton.2013.112"},{"key":"5","doi-asserted-by":"publisher","unstructured":"J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X.-M. Jin, M. 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 (6121): 798, 2013. 10.1126\/science.1231692.","DOI":"10.1126\/science.1231692"},{"key":"6","doi-asserted-by":"publisher","unstructured":"M. Tillmann, B. Daki\u0107, R. Heilmann, S. Nolte, A. Szameit, and P. Walther. Experimental Boson Sampling. Nat. Photon., 7 (7): 540\u2013544, 2013. 10.1038\/nphoton.2013.102.","DOI":"10.1038\/nphoton.2013.102"},{"key":"7","doi-asserted-by":"publisher","unstructured":"N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galv\u00e3o, and F. Sciarrino. Experimental validation of photonic Boson Sampling. Nat. Photon., 8 (8): 615\u2013620, 2014. 10.1038\/nphoton.2014.135.","DOI":"10.1038\/nphoton.2014.135"},{"key":"8","doi-asserted-by":"publisher","unstructured":"J. Carolan, J. D. A. Meinecke, P. J. Shadbolt, N. J. Russell, N. Ismail, K. W\u00f6rhoff, T. Rudolph, M. G. Thompson, J. L. O'Brien, J. C. F. Matthews, and A. Laing. On the experimental verification of quantum complexity in linear optics. Nat. Photon., 8 (8): 621\u2013626, 2014. 10.1038\/nphoton.2014.152.","DOI":"10.1038\/nphoton.2014.152"},{"key":"9","doi-asserted-by":"publisher","unstructured":"J. Carolan, C. Harrold, C. Sparrow, E. Mart\u00edn-L\u00f3pez, 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 (6249): 711, 2015. 10.1126\/science.aab3642.","DOI":"10.1126\/science.aab3642"},{"key":"10","doi-asserted-by":"publisher","unstructured":"M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galv\u00e3o, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino. Experimental scattershot Boson Sampling. Science Advances, 1 (3): e1400255, 2015. 10.1126\/sciadv.1400255.","DOI":"10.1126\/sciadv.1400255"},{"key":"11","doi-asserted-by":"publisher","unstructured":"J. C. Loredo, M. A. Broome, P. Hilaire, O. Gazzano, I. Sagnes, A. Lemaitre, M. P. Almeida, P. Senellart, and A. G. White. Boson Sampling with single-photon fock states from a bright solid-state source. Phys. Rev. Lett., 118: 130503, 2017. 10.1103\/PhysRevLett.118.130503.","DOI":"10.1103\/PhysRevLett.118.130503"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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\u00f6fling, Chao-Yang Lu, and Jian-Wei Pan. Time-bin-encoded Boson Sampling with a single-photon device. Phys. Rev. Lett., 118: 190501, 2017. 10.1103\/PhysRevLett.118.190501.","DOI":"10.1103\/PhysRevLett.118.190501"},{"key":"13","doi-asserted-by":"publisher","unstructured":"H. Wang, Y. He, Y.-H. Li, Z.-E. Su, B. Li, H.-L. Huang, X. Ding, M.-C. Chen, C. Liu, J. Qin, J.-P. Li, Y.-M. He, C. Schneider, M. Kamp, C.-Z. Peng, S. H\u00f6fling, C.-Y. Lu, and J.-W. Pan. High-efficiency multiphoton boson sampling. Nat. Photon., 11: 361\u2013365, 2017. 10.1038\/nphoton.2017.63.","DOI":"10.1038\/nphoton.2017.63"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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\u00f6fling, Chao-Yang Lu, and Jian-Wei Pan. Toward scalable Boson Sampling with photon loss. Phys. Rev. Lett., 120: 230502, 2018a. 10.1103\/PhysRevLett.120.230502.","DOI":"10.1103\/PhysRevLett.120.230502"},{"key":"15","unstructured":"A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing. Classical boson sampling algorithms with superior performance to near-term experiments. Nature Physics, 13: 1153, 2017. doi:10.1038\/nphys4270."},{"key":"16","doi-asserted-by":"publisher","unstructured":"P. Clifford and R. Clifford. The classical complexity of Boson Sampling. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, page 146, 2018. 10.1137\/1.9781611975031.10.","DOI":"10.1137\/1.9781611975031.10"},{"key":"17","doi-asserted-by":"crossref","unstructured":"W. Roga and M. Takeoka. Classical simulation of boson sampling with sparse output. 2019. arXiv:1904.05494.","DOI":"10.1038\/s41598-020-71892-0"},{"key":"18","doi-asserted-by":"publisher","unstructured":"J. Wu, Y. Liu, B. Zhang, X. Jin, Y. Wang, H. Wang, and X. Yang. A benchmark test of boson sampling on Tianhe-2 supercomputer. National Science Review, 5: 715, 2018. 10.1093\/nsr\/nwy079.","DOI":"10.1093\/nsr\/nwy079"},{"key":"19","doi-asserted-by":"publisher","unstructured":"A. M. Dalzell, A. W. Harrow, D. E. Koh, and R. L. La Placa. How many qubits are needed for quantum computational supremacy? 2018. arXiv:1805.05224. 10.22331\/q-2020-05-11-264.","DOI":"10.22331\/q-2020-05-11-264"},{"key":"20","doi-asserted-by":"publisher","unstructured":"S. Aaronson and D. J. Brod. BosonSampling with lost photons. Phys. Rev. A, 93 (1): 012335, 2016. 10.1103\/PhysRevA.93.012335.","DOI":"10.1103\/PhysRevA.93.012335"},{"key":"21","doi-asserted-by":"publisher","unstructured":"R. Garc\u00eda-Patr\u00f3n, J. J. Renema, and V. Shchesnovich. Simulating boson sampling in lossy architectures. Quantum, 3: 169, 2019. 10.22331\/q-2019-08-05-169.","DOI":"10.22331\/q-2019-08-05-169"},{"key":"22","doi-asserted-by":"publisher","unstructured":"M. Oszmaniec and D. Brod. Classical simulation of photonic linear optics with lost particles. New Journal of Physics, 20 (9): 092002, 2018. 10.1088\/1367-2630\/aadfa8.","DOI":"10.1088\/1367-2630\/aadfa8"},{"key":"23","unstructured":"J. Renema, V. Shchesnovich, and R. Garc\u00eda-Patr\u00f3n. Classical simulability of noisy boson sampling. 2018. arXiv:1809.01953."},{"key":"24","doi-asserted-by":"publisher","unstructured":"A. E. Moylett, R. Garc\u00eda-Patr\u00f3n, J. Renema, and P. Turner. Classically simulating near-term partially-distinguishable and lossy boson sampling. Quantum Science and Technology, 5 (1): 015001, 2019. 10.1088\/2058-9565\/ab5555.","DOI":"10.1088\/2058-9565\/ab5555"},{"key":"25","doi-asserted-by":"publisher","unstructured":"A. Arkhipov. BosonSampling is robust against small errors in the network matrix. Phys. Rev. A, 92: 062326, 2015. 10.1103\/PhysRevA.92.062326.","DOI":"10.1103\/PhysRevA.92.062326"},{"key":"26","doi-asserted-by":"crossref","unstructured":"A. Leverrier and R. Garc\u00eda-Patr\u00f3n. Analysis of circuit imperfections in BosonSampling. Quant. Inf. Comp., 15: 489, 2014.","DOI":"10.26421\/QIC15.5-6-8"},{"key":"27","doi-asserted-by":"publisher","unstructured":"S. Rahimi-Keshari, T. C. Ralph, and C. M. Caves. Sufficient conditions for efficient classical simulation of quantum optics. Phys. Rev. X, 6 (2): 021039, 2016. 10.1103\/PhysRevX.6.021039.","DOI":"10.1103\/PhysRevX.6.021039"},{"key":"28","doi-asserted-by":"publisher","unstructured":"J. J. Renema, A. Menssen, W. R. Clements, G. Triginer, W. S. Kolthammer, and I. A. Walmsley. Efficient algorithm for boson sampling with partially distinguishable photons. Phys. Rev. Lett., 120: 220502, 2018. 10.1103\/PhysRevLett.120.220502.","DOI":"10.1103\/PhysRevLett.120.220502"},{"key":"29","unstructured":"G. Kalai and G. Kindler. Gaussian Noise Sensitivity and BosonSampling. 2014. arXiv:1409.3093."},{"key":"30","doi-asserted-by":"publisher","unstructured":"M. Reck, A. Zeilinger, H. Bernstein, and P. Bertani. Experimental realization of any discrete unitary operator. Phys. Rev. Lett., 73: 58, 1994. 10.1103\/PhysRevLett.73.58.","DOI":"10.1103\/PhysRevLett.73.58"},{"key":"31","doi-asserted-by":"publisher","unstructured":"F. Arute et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505\u2013510, 2019. 10.1038\/s41586-019-1666-5.","DOI":"10.1038\/s41586-019-1666-5"},{"key":"32","doi-asserted-by":"publisher","unstructured":"S. Boixo, S. Isakov, V. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. Bremner, J. Martinis, and H. Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14 (6): 595\u2013600, 2018. 10.1038\/s41567-018-0124-x.","DOI":"10.1038\/s41567-018-0124-x"},{"key":"33","doi-asserted-by":"publisher","unstructured":"H. Wang, J. Qin, X. Ding, M.-C. Chen, S. Chen, X. You, Y.-M. He, X. Jiang, L. You, Z. Wang, C. Schneider, J. Renema, S. H\u00f6fling, C.-Y. Lu, and J.-W. Pan. Boson Sampling with 20 input photons and a 60-mode interferometer in a $1{0}^{14}$-dimensional Hilbert space. Phys. Rev. Lett., 123: 250503, 2019. 10.1103\/PhysRevLett.123.250503.","DOI":"10.1103\/PhysRevLett.123.250503"},{"key":"34","doi-asserted-by":"publisher","unstructured":"A. E. Moylett and P. S. Turner. Quantum simulation of partially distinguishable boson sampling. Phys. Rev. A, 97: 062329, 2018. 10.1103\/PhysRevA.97.062329.","DOI":"10.1103\/PhysRevA.97.062329"},{"key":"35","doi-asserted-by":"publisher","unstructured":"S. Chin and J. Huh. Generalized concurrence in boson sampling. Sci. Rep., 8: 6101, 2018. 10.1038\/s41598.","DOI":"10.1038\/s41598"},{"key":"36","doi-asserted-by":"publisher","unstructured":"V. S. Shchesnovich. Asymptotic evaluation of bosonic probability amplitudes in linear unitary networks in the case of large number of bosons. International Journal of Quantum Information, 11 (05): 1350045, 2013. 10.1142\/S0219749913500457.","DOI":"10.1142\/S0219749913500457"},{"key":"37","doi-asserted-by":"publisher","unstructured":"A. Bouland and S. Aaronson. Generation of universal linear optics by any beam splitter. Phys. Rev. A, 89: 062316, 2014. 10.1103\/PhysRevA.89.062316.","DOI":"10.1103\/PhysRevA.89.062316"},{"key":"38","doi-asserted-by":"crossref","unstructured":"A. Sawicki. Universality of beamsplitters. Quantum Inf. Comput., 16 (3 and 4): 0291\u20130312, 2016.","DOI":"10.26421\/QIC16.3-4-6"},{"key":"39","doi-asserted-by":"publisher","unstructured":"A. Sawicki and K. Karnas. Universality of Single-Qudit Gates. Annales Henri Poincare, 18 (11): 3515\u20133552, 2017. 10.1007\/s00023-017-0604-z.","DOI":"10.1007\/s00023-017-0604-z"},{"key":"40","doi-asserted-by":"publisher","unstructured":"N. Tischler, C. Rockstuhl, and K. S\u0142owik. Quantum optical realization of arbitrary linear transformations allowing for loss and gain. Phys. Rev. X, 8: 021017, 2018. 10.1103\/PhysRevX.8.021017.","DOI":"10.1103\/PhysRevX.8.021017"},{"key":"41","doi-asserted-by":"publisher","unstructured":"W. R. Clements, P. C. Humphreys, B. J. Metcalf, W. S. Kolthammer, and I. A. Walmsley. Optimal design for universal multiport interferometers. Optica, 3 (12): 1460\u20131465, 2016. 10.1364\/OPTICA.3.001460.","DOI":"10.1364\/OPTICA.3.001460"},{"key":"42","doi-asserted-by":"publisher","unstructured":"C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex. Gaussian Boson Sampling. Phys. Rev. Lett., 119: 170501, 2017. 10.1103\/PhysRevLett.119.170501.","DOI":"10.1103\/PhysRevLett.119.170501"},{"key":"43","doi-asserted-by":"publisher","unstructured":"H. Qi, D. J. Brod, N. Quesada, and R. Garc\u00eda-Patr\u00f3n. Regimes of classical simulability for noisy Gaussian boson sampling. Phys. Rev. Lett., 124: 100502, 2020. 10.1103\/PhysRevLett.124.100502.","DOI":"10.1103\/PhysRevLett.124.100502"},{"key":"44","doi-asserted-by":"publisher","unstructured":"J. Wang, S. Paesani, Y. Ding, R. Santagati, P. Skrzypczyk, A. Salavrakos, J. Tura, R. Augusiak, L. Man\u010dinska, D. Bacco, D. Bonneau, J. Silverstone, Q. Gong, A. Ac\u00edn, K. Rottwitt, L. Oxenl\u00f8we, J. O\u2019Brien, A. Laing, and M. Thompson. Multidimensional quantum entanglement with large-scale integrated optics. Science, 360 (6386): 285\u2013291, 2018b. 10.1126\/science.aar7053.","DOI":"10.1126\/science.aar7053"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-05-14-267\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,3,14]],"date-time":"2021-03-14T10:31:56Z","timestamp":1615717916000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-05-14-267\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,14]]},"references-count":45,"URL":"https:\/\/doi.org\/10.22331\/q-2020-05-14-267","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,14]]},"article-number":"267"}}