Simulating boson sampling in lossy architectures

Raúl García-Patrón1, Jelmer J. Renema2,3, and Valery Shchesnovich4

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

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


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.

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

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

[2] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing, 9: 143–252, 2013. 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.

[4] A. Arkhipov and G. Kuperberg. The bosonic birthday paradox. Geometry & Topology Monographs, 18: 1, 2012. 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.

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

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

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

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

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

[11] L. Chakhmakhchyan and N. J. Cerf. Boson sampling with gaussian measurements. Phys. Rev. A, 96: 032326, 2017. 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.

[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:/​/​​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.

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

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

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

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

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

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

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

[22] R. Jozsa. On the simulation of quantum circuits. arXiv, page 0603163, 2006. URL https:/​/​​abs/​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.

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

[26] I. Krasikov. Nonnegative quadratic forms and bounds on orthogonal polynomials. J. Approx. Theory, 111: 31–49, 2001. 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.

[28] L.G.Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8: 189–201, 1979. 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.

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

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

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

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

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

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

[36] S. Ostlund and S. Rommer. Thermodynamic limit of density matrix renormalization. Phys. Rev. Lett., 75: 3537–3540, 1995. 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.

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

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

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

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

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

[44] J. Renema, V. Shchesnovich, and R. Garcia-Patron. Classical simulability of noisy boson sampling. arXiv, page 809.01953, 2018a. URL https:/​/​​abs/​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.

[46] T. Rudolph. Why I am optimistic about the silicon-photonic route to quantum computing. APL Photonics, 2: 030901, 2017. 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.

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

[49] K. Temme and P. Wocjan. Efficient computation of the permanent of block factorizable matrices. arXiv, page 1208.6589, 2012. URL https:/​/​​abs/​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.

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

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

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

[54] G. Vidal. Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett., 91: 147902, 2003. 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.

[56] S. R. White. Density matrix formulation for quantum renormalization groups. Phys. Rev. Lett., 69: 2863–2866, 1992. 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.

Cited by

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[15] Valery Shchesnovich, "On the classical complexity of sampling from quantum interference of indistinguishable bosons", arXiv:1904.02013.

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

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

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

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

1 thought on “Simulating boson sampling in lossy architectures

  1. Pingback: Perspective in Quantum Views by Alex Neville "Simulating lossy multiphoton linear optics experiments"