Classical simulation of linear optics subject to nonuniform losses

Daniel Jost Brod; Michał Oszmaniec

doi:10.22331/q-2020-05-14-267

Classical simulation of linear optics subject to nonuniform losses

Daniel Jost Brod¹ and Michał Oszmaniec^2,3

¹Instituto de Física, Universidade Federal Fluminense, Niterói, RJ, 24210-340, Brazil
²International Centre for Theory of Quantum Technologies, University of Gdansk, Wita Stwosza 63, 80-308 Gdansk, Poland
³Center for Theoretical Physics, Polish Academy of Sciences, Al. Lotników 32/46, 02-668 Warszawa, Poland

Published:	2020-05-14, volume 4, page 267
Eprint:	arXiv:1906.06696v4
Doi:	https://doi.org/10.22331/q-2020-05-14-267
Citation:	Quantum 4, 267 (2020).

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

Abstract

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 $s_i$ layers of losses to the input, where $s_i$ is the length of the shortest path connecting the $i$th input to any output. We then extend a recent classical simulation algorithm due to P. Clifford and R. Clifford to allow for arbitrary $n$-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 $n$ input photons occupy a constant number of input modes; (B) when all but $O(\log n)$ photons are concentrated on a single input mode, while an additional $O(\log n)$ modes contain one photon each.

► BibTeX data

@article{Brod2020classicalsimulation,
  doi = {10.22331/q-2020-05-14-267},
  url = {https://doi.org/10.22331/q-2020-05-14-267},
  title = {Classical simulation of linear optics subject to nonuniform losses},
  author = {Brod, Daniel Jost and Oszmaniec, Micha{\l{}}},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {267},
  month = may,
  year = {2020}
}

► References

[1] A. Harrow and A. Montanaro. Quantum computational supremacy. Nature, 549: 203–209, 2017. 10.1038/nature23458.
https://doi.org/10.1038/nature23458

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

[3] D. J. Brod, E. F. Galvão, A. Crespi, R. Osellame, N. Spagnolo, and F. Sciarrino. Photonic implementation of boson sampling: a review. Advanced Photonics, 1 (3): 1–14, 2019. 10.1117/1.AP.1.3.034001.
https://doi.org/10.1117/1.AP.1.3.034001

[4] 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.
https://doi.org/10.1126/science.1231440

[5] A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvão, 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–549, 2013. 10.1038/nphoton.2013.112.
https://doi.org/10.1038/nphoton.2013.112

[6] 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.
https://doi.org/10.1126/science.1231692

[7] M. Tillmann, B. Dakić, R. Heilmann, S. Nolte, A. Szameit, and P. Walther. Experimental Boson Sampling. Nat. Photon., 7 (7): 540–544, 2013. 10.1038/nphoton.2013.102.
https://doi.org/10.1038/nphoton.2013.102

[8] 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ão, and F. Sciarrino. Experimental validation of photonic Boson Sampling. Nat. Photon., 8 (8): 615–620, 2014. 10.1038/nphoton.2014.135.
https://doi.org/10.1038/nphoton.2014.135

[9] J. Carolan, J. D. A. Meinecke, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, 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–626, 2014. 10.1038/nphoton.2014.152.
https://doi.org/10.1038/nphoton.2014.152

[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 (6249): 711, 2015. 10.1126/science.aab3642.
https://doi.org/10.1126/science.aab3642

[11] M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvão, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino. Experimental scattershot Boson Sampling. Science Advances, 1 (3): e1400255, 2015. 10.1126/sciadv.1400255.
https://doi.org/10.1126/sciadv.1400255

[12] 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.
https://doi.org/10.1103/PhysRevLett.118.130503

[13] 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 Jian-Wei 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

[14] 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öfling, C.-Y. Lu, and J.-W. Pan. High-efficiency multiphoton boson sampling. Nat. Photon., 11: 361–365, 2017. 10.1038/nphoton.2017.63.
https://doi.org/10.1038/nphoton.2017.63

[15] 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, 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.
https://doi.org/10.1103/PhysRevLett.120.230502

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

[17] 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.
https://doi.org/10.1137/1.9781611975031.10

[18] W. Roga and M. Takeoka. Classical simulation of boson sampling with sparse output. 2019. arXiv:1904.05494.
arXiv:1904.05494

[19] 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.
https://doi.org/10.1093/nsr/nwy079

[20] 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.
https://doi.org/10.22331/q-2020-05-11-264
arXiv:1805.05224

[21] S. Aaronson and D. J. Brod. BosonSampling with lost photons. Phys. Rev. A, 93 (1): 012335, 2016. 10.1103/PhysRevA.93.012335.
https://doi.org/10.1103/PhysRevA.93.012335

[22] R. García-Patrón, J. J. Renema, and V. Shchesnovich. Simulating boson sampling in lossy architectures. Quantum, 3: 169, 2019. 10.22331/q-2019-08-05-169.
https://doi.org/10.22331/q-2019-08-05-169

[23] 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.
https://doi.org/10.1088/1367-2630/aadfa8

[24] J. Renema, V. Shchesnovich, and R. García-Patrón. Classical simulability of noisy boson sampling. 2018. arXiv:1809.01953.
arXiv:1809.01953

[25] A. E. Moylett, R. García-Patrón, 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.
https://doi.org/10.1088/2058-9565/ab5555

[26] A. Arkhipov. BosonSampling is robust against small errors in the network matrix. Phys. Rev. A, 92: 062326, 2015. 10.1103/PhysRevA.92.062326.
https://doi.org/10.1103/PhysRevA.92.062326

[27] A. Leverrier and R. García-Patrón. Analysis of circuit imperfections in BosonSampling. Quant. Inf. Comp., 15: 489, 2014.

[28] 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.
https://doi.org/10.1103/PhysRevX.6.021039

[29] 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.
https://doi.org/10.1103/PhysRevLett.120.220502

[30] G. Kalai and G. Kindler. Gaussian Noise Sensitivity and BosonSampling. 2014. arXiv:1409.3093.
arXiv:1409.3093

[31] 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.
https://doi.org/10.1103/PhysRevLett.73.58

[32] F. Arute et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5

[33] 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–600, 2018. 10.1038/s41567-018-0124-x.
https://doi.org/10.1038/s41567-018-0124-x

[34] 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öfling, 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.
https://doi.org/10.1103/PhysRevLett.123.250503

[35] 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.
https://doi.org/10.1103/PhysRevA.97.062329

[36] S. Chin and J. Huh. Generalized concurrence in boson sampling. Sci. Rep., 8: 6101, 2018. 10.1038/s41598.
https://doi.org/10.1038/s41598

[37] 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.
https://doi.org/10.1142/S0219749913500457

[38] 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.
https://doi.org/10.1103/PhysRevA.89.062316

[39] A. Sawicki. Universality of beamsplitters. Quantum Inf. Comput., 16 (3 and 4): 0291–0312, 2016.

[40] A. Sawicki and K. Karnas. Universality of Single-Qudit Gates. Annales Henri Poincare, 18 (11): 3515–3552, 2017. 10.1007/s00023-017-0604-z.
https://doi.org/10.1007/s00023-017-0604-z

[41] N. Tischler, C. Rockstuhl, and K. Słowik. Quantum optical realization of arbitrary linear transformations allowing for loss and gain. Phys. Rev. X, 8: 021017, 2018. 10.1103/PhysRevX.8.021017.
https://doi.org/10.1103/PhysRevX.8.021017

[42] 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–1465, 2016. 10.1364/OPTICA.3.001460.
https://doi.org/10.1364/OPTICA.3.001460

[43] 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.
https://doi.org/10.1103/PhysRevLett.119.170501

[44] H. Qi, D. J. Brod, N. Quesada, and R. García-Patrón. Regimes of classical simulability for noisy Gaussian boson sampling. Phys. Rev. Lett., 124: 100502, 2020. 10.1103/PhysRevLett.124.100502.
https://doi.org/10.1103/PhysRevLett.124.100502

[45] J. Wang, S. Paesani, Y. Ding, R. Santagati, P. Skrzypczyk, A. Salavrakos, J. Tura, R. Augusiak, L. Mančinska, D. Bacco, D. Bonneau, J. Silverstone, Q. Gong, A. Acín, K. Rottwitt, L. Oxenløwe, J. O’Brien, A. Laing, and M. Thompson. Multidimensional quantum entanglement with large-scale integrated optics. Science, 360 (6386): 285–291, 2018b. 10.1126/science.aar7053.
https://doi.org/10.1126/science.aar7053

Cited by

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

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

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

[4] Peter Clifford and Raphaël Clifford, "Faster classical boson sampling", Physica Scripta 99 6, 065121 (2024).

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

[6] J. M. Arrazola, V. Bergholm, K. Brádler, T. R. Bromley, M. J. Collins, I. Dhand, A. Fumagalli, T. Gerrits, A. Goussev, L. G. Helt, J. Hundal, T. Isacsson, R. B. Israel, J. Izaac, S. Jahangiri, R. Janik, N. Killoran, S. P. Kumar, J. Lavoie, A. E. Lita, D. H. Mahler, M. Menotti, B. Morrison, S. W. Nam, L. Neuhaus, H. Y. Qi, N. Quesada, A. Repingon, K. K. Sabapathy, M. Schuld, D. Su, J. Swinarton, A. Száva, K. Tan, P. Tan, V. D. Vaidya, Z. Vernon, Z. Zabaneh, and Y. Zhang, "Quantum circuits with many photons on a programmable nanophotonic chip", Nature 591 7848, 54 (2021).

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

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

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

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

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

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

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

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

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

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

[17] Reinier van der Meer, Michiel de Goede, Ben Kassenberg, Pim Venderbosch, Henk Snijders, Jorn Epping, Caterina Taballione, Hans van den Vlekkert, Jelmer J. Renema, and Pepijn W. H. Pinkse, "Observation of open scattering channels", arXiv:2110.04380, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2024-07-21 01:58:22) and SAO/NASA ADS (last updated successfully 2024-07-21 01:58:23). 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.