Classical simulation of linear optics subject to nonuniform losses

Daniel Jost Brod1 and Michał Oszmaniec2,3

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

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


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

► References

[1] A. Harrow and A. Montanaro. Quantum computational supremacy. Nature, 549: 203–209, 2017. 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[18] W. Roga and M. Takeoka. Classical simulation of boson sampling with sparse output. 2019. 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.

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

[21] S. Aaronson and D. J. Brod. BosonSampling with lost photons. Phys. Rev. A, 93 (1): 012335, 2016. 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.

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

[24] J. Renema, V. Shchesnovich, and R. García-Patrón. Classical simulability of noisy boson sampling. 2018. 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.

[26] A. Arkhipov. BosonSampling is robust against small errors in the network matrix. Phys. Rev. A, 92: 062326, 2015. 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.

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

[30] G. Kalai and G. Kindler. Gaussian Noise Sensitivity and BosonSampling. 2014. 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.

[32] F. Arute et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 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.

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

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

[36] S. Chin and J. Huh. Generalized concurrence in boson sampling. Sci. Rep., 8: 6101, 2018. 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.

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

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

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

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

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

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

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

Cited by

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

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

[3] Raphael A. Abrahao and Austin P. Lund, "Boson Sampling with efficient scaling and efficient verification", arXiv:1812.08978.

The above citations are from SAO/NASA ADS (last updated successfully 2021-01-16 04:48:50). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2021-01-16 04:48:48).