# Spot the Difference: Distinguishing Boson Sampling Experiments from Classical Simulations

This is a Perspective on "Distinguishing noisy boson sampling from classical simulations" by Valery Shchesnovich, published in Quantum 5, 423 (2021).

By Alexandra E. Moylett (Riverlane, St Andrews House, 59 St Andrews Street, Cambridge CB2 3BZ, UK).

## Quantum Advantage from Linear Optics

Quantum computing has promised advantages in a wide variety of problems, including simulating physical systems, optimisation problems and machine learning [1]. But these algorithms require large numbers of fault tolerant qubits, and are therefore infeasible on current hardware. So what can we do to highlight the power of quantum computing now? This is the question posed by the area of research known as Quantum Advantage: is there a problem which is easy to solve on a near-term quantum computer, yet intractable on a classical computer? Many problems have been proposed for this, including sampling from random quantum circuits, sampling from quantum circuits with a particular structure, and, the subject of this work, Boson Sampling [2].

Boson Sampling was originally proposed by Aaronson and Arkhipov in 2010, and is the problem of sampling from the output of a linear optical interferometer [3]. More concretely, if we have $n$ photons input into an $m$-mode interferometer implementing some unitary transformation $U \in SU(m)$, Boson Sampling is the task of sampling where the photons will come out. The first thing we can note about this model of quantum computing is that it is non-universal: photons are non-interacting, so without feed-forward or postselection in this model we cannot implement a two-qubit gate. However, photons can still interfere with each other in non-classical ways, most famously demonstrated by the Hong-Ou-Mandel dip [4]. So if we cannot perform universal quantum computation, can we still do something which is hard to simulate classically?

Aaronson and Arkhipov answered this affirmatively, showing that Boson Samplers can still demonstrate a quantum advantage [3]. To prove this, Aaronson and Arkhipov explained how the probability of seeing a given output from an $n$-photon $m$-mode interferometer is related to the permanent of an $n\times n$ submatrix of $U$. Computing the permanent of such a matrix is $\#P$-Hard, so an efficient algorithm for doing so would lead to significant consequences in Computational Complexity Theory, including a proof that $P=NP$. From this Aaronson and Arkhipov showed that, assuming various conjectures about matrix permanents hold and that $m = O(n^2)$, it is impossible for a classical computer to efficiently sample from this output distribution, or even from an $\epsilon$-close distribution in total variation distance.

In the years since, Boson Sampling has been a subject of interest among quantum photonics researchers. Early demonstrations ranged from 3-6 photons [5,6,7,8,9,10], with more recent work showing up to 14 output photons [11]. A particularly exciting development came in 2020, where a group led by Lu and Pan demonstrated a variant known as Gaussian Boson Sampling with up to 76 detected photons, which is claimed to be beyond the limit of what is classically simulable [12].

## Classical Simulations from Photonic Imperfections

But even if Boson Sampling becomes classically intractable for sufficiently large $m$ and $n$, an important question is at what point will we actually see an advantage? If we want a fair race, we need to compare the best Boson Sampling experiments to the best classical algorithms. This has led to the development of several classical algorithms for Boson Sampling [13,14,15,16,17,18,19,20].

One particular detail that these classical algorithms take advantage of is that Boson Sampling experiments suffer from practical imperfections. Such imperfections include:

• loss, where a photon is generated at the start of the interferometer but not detected at the end
• and distinguishability, where photons are generated at different wavelengths, polarisations, or even at different times, and as a result no longer interfere with each other.

In extreme cases, either of these imperfections can lead to a point where the experiment becomes trivial to classically simulate. If there is significant loss, one can simply simulate a vastly reduced number of photons. And if all the photons are fully distinguishable from each other, each photon can be simulated individually.

A particular classical algorithm which takes advantage of these imperfections was first proposed by Renema et al. [15], and subsequently improved in work by Renema, Shchesnovich and García-Patrón [16]. Here, these imperfections are characterised by parameters $\xi$ and $\eta$, which denote the probability of an individual photon being indistinguishable from other photons, and the probability of an individual photon not being lost, respectively. With knowledge of these parameters, one can simulate such an experiment up to accuracy $\epsilon$ by instead simulating a Boson Sampling experiment with $k$ ideal photons and $n-k$ fully distinguishable photons. The time complexity for this algorithm is exponential in terms of $k$, where $k$ is dependent on $\xi$, $\eta$, and $\epsilon$. Crucially, $k$ is not dependent on $m$ or $n$, so the algorithm’s runtime will only increase at most polynomially as the size of our interferometer increases. As a result, it is not sufficient to simply make larger interferometers with more photons; if we don’t work on improving these imperfections as well, then we will not achieve a quantum advantage.

## How to Spot the Difference

So what can we do to ensure that we have an advantage over these classical algorithms? Can the classical algorithms produce an output which is the same as our imperfect experiment, or at least close enough that to us they look identical? Or is there a way to distinguish an actual Boson Sampling experiment from a classical simulation?

This is the question posed in recent work by Shchesnovich [21], which showed that in fact it is possible to distinguish the output of a Boson Sampling experiment from that of the algorithm by Renema, Shchesnovich and García-Patrón [16]. To do this, we select a subset of $L$ output modes. Let us use $P_L$ to denote the probability of detecting zero photons in these modes in an experiment, and $\tilde{P_L}$ for the corresponding probability in a classical simulation. Shchesnovich showed that there is a lower bound for the difference between these two probabilities $|P_L-\tilde{P_L}| \geq \Delta$.

This gives us a way of determining if a collection of samples is from a classical simulation or a real Boson Sampling experiment. First, we use the samples to estimate the probability of seeing zero photons in these $L$ modes, $P_L$. Next, we use a classical computer to estimate the values $\tilde{P_L}$ and $\Delta$. And finally, we check if the inequality $|P_L-\tilde{P_L}| \geq \Delta$ holds: if it does then our samples are likely from an actual experiment, and if it doesn’t then they are probably from a classical simulation. Shchesnovich showed that for fixed distinguishability and loss, and for a classical simulator with fixed $k$, the number of samples required depends only on $n/m$, the ratio of photons to modes. Since $m=O(n^2)$ for Boson Sampling, this ratio can be upper-bounded by some constant value. Therefore, as the number of photons and the size of our interferometer increases, the number of samples and computation time required to distinguish an experiment’s output from a classical simulation only increases polynomially.

## Conclusion and Outlook

We have now reached the era in quantum computing where we are seeing the first claims of a quantum device performing a computation which is classically infeasible. As we see these claims appear, it is important that we ask just how well classical computers can perform, and if there are ways that quantum computers can stand out. The recent result by Shchesnovich works towards answering the latter of these questions, giving a metric by which Boson Sampling experiments can distinguish themselves from classical simulations.

There are still interesting questions to explore here. Shchesnovich considered a particular family of classical algorithms, but there are other classical algorithms for simulating Boson Sampling for which the method discussed above might not work [17,18,19,20]. There has also been recent interest in developing classical algorithms to simulate Gaussian Boson Sampling [22,23,24,25,26], the variant used by Lu, Pan et al. to demonstrate a quantum advantage [12]. It remains open to see if similar methods can also be used to distinguish Gaussian Boson Sampling experiments from their classical simulations.

### ► References

[1] Ashley Montanaro. Quantum algorithms: an overview. npj Quantum Information, 2(1):1–8, January 2016. Publisher: Nature Publishing Group. doi:10.1038/​npjqi.2015.23. Preprint: arXiv:1511.04206 [quant-ph].
https:/​/​doi.org/​10.1038/​npjqi.2015.23
arXiv:1511.04206

[2] Aram W. Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549(7671):203–209, September 2017. Publisher: Nature Publishing Group. doi:10.1038/​nature23458. Preprint: arXiv:1809.07442 [quant-ph].
https:/​/​doi.org/​10.1038/​nature23458
arXiv:1809.07442

[3] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing, STOC '11, pages 333–342, New York, NY, USA, June 2011. Association for Computing Machinery. doi:10.1145/​1993636.1993682. Preprint: arXiv:1011.3245 [quant-ph].
https:/​/​doi.org/​10.1145/​1993636.1993682
arXiv:1011.3245

[4] C. K. Hong, Z. Y. Ou, and L. Mandel. Measurement of subpicosecond time intervals between two photons by interference. Physical Review Letters, 59(18):2044–2046, November 1987. Publisher: American Physical Society. doi:10.1103/​PhysRevLett.59.2044.
https:/​/​doi.org/​10.1103/​PhysRevLett.59.2044

[5] Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari, Justin Dove, Scott Aaronson, Timothy C. Ralph, and Andrew G. White. Photonic Boson Sampling in a Tunable Circuit. Science, 339(6121):794–798, February 2013. Publisher: American Association for the Advancement of Science Section: Report. doi:10.1126/​science.1231440. Preprint: arXiv:1212.2234 [quant-ph].
https:/​/​doi.org/​10.1126/​science.1231440
arXiv:1212.2234

[6] Justin B. Spring, Benjamin J. Metcalf, Peter C. Humphreys, W. Steven Kolthammer, Xian-Min Jin, Marco Barbieri, Animesh Datta, Nicholas Thomas-Peter, Nathan K. Langford, Dmytro Kundys, James C. Gates, Brian J. Smith, Peter G. R. Smith, and Ian A. Walmsley. Boson Sampling on a Photonic Chip. Science, 339(6121):798–801, February 2013. Publisher: American Association for the Advancement of Science Section: Report. doi:10.1126/​science.1231692. Preprint: arXiv:1212.2622 [quant-ph].
https:/​/​doi.org/​10.1126/​science.1231692
arXiv:1212.2622

[7] Max Tillmann, Borivoje Dakić, René Heilmann, Stefan Nolte, Alexander Szameit, and Philip Walther. Experimental boson sampling. Nature Photonics, 7(7):540–544, July 2013. Publisher: Nature Publishing Group. doi:10.1038/​nphoton.2013.102. Preprint: arXiv:1212.2240 [quant-ph].
https:/​/​doi.org/​10.1038/​nphoton.2013.102
arXiv:1212.2240

[8] Andrea Crespi, Roberto Osellame, Roberta Ramponi, Daniel J. Brod, Ernesto F. Galvão, Nicolò Spagnolo, Chiara Vitelli, Enrico Maiorino, Paolo Mataloni, and Fabio Sciarrino. Integrated multimode interferometers with arbitrary designs for photonic boson sampling. Nature Photonics, 7(7):545–549, July 2013. Publisher: Nature Publishing Group. doi:10.1038/​nphoton.2013.112. Preprint: arXiv:1212.2783 [quant-ph].
https:/​/​doi.org/​10.1038/​nphoton.2013.112
arXiv:1212.2783

[9] Jacques Carolan, Christopher Harrold, Chris Sparrow, Enrique Martín-López, Nicholas J. Russell, Joshua W. Silverstone, Peter J. Shadbolt, Nobuyuki Matsuda, Manabu Oguma, Mikitaka Itoh, Graham D. Marshall, Mark G. Thompson, Jonathan C. F. Matthews, Toshikazu Hashimoto, Jeremy L. O’Brien, and Anthony Laing. Universal linear optics. Science, 349(6249):711–716, August 2015. Publisher: American Association for the Advancement of Science Section: Research Article. doi:10.1126/​science.aab3642. Preprint: arXiv:1505.01182 [quant-ph].
https:/​/​doi.org/​10.1126/​science.aab3642
arXiv:1505.01182

[10] Hui Wang, Yu He, Yu-Huai Li, Zu-En Su, Bo Li, He-Liang Huang, Xing Ding, Ming-Cheng Chen, Chang Liu, Jian Qin, Jin-Peng Li, Yu-Ming He, Christian Schneider, Martin Kamp, Cheng-Zhi Peng, Sven Höfling, Chao-Yang Lu, and Jian-Wei Pan. High-efficiency multiphoton boson sampling. Nature Photonics, 11(6):361–365, June 2017. Publisher: Nature Publishing Group. doi:10.1038/​nphoton.2017.63. Preprint: arXiv:1612.06956 [quant-ph].
https:/​/​doi.org/​10.1038/​nphoton.2017.63
arXiv:1612.06956

[11] Hui Wang, Jian Qin, Xing Ding, Ming-Cheng Chen, Si Chen, Xiang You, Yu-Ming He, Xiao Jiang, L. You, Z. Wang, C. Schneider, Jelmer J. Renema, Sven Höfling, Chao-Yang Lu, and Jian-Wei Pan. Boson Sampling with 20 Input Photons and a 60-Mode Interferometer in a $10^{14}$-Dimensional Hilbert Space. Physical Review Letters, 123(25):250503, December 2019. Publisher: American Physical Society. doi:10.1103/​PhysRevLett.123.250503. Preprint: arXiv:1910.09930 [quant-ph].
https:/​/​doi.org/​10.1103/​PhysRevLett.123.250503
arXiv:1910.09930

[12] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, 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, Chao-Yang Lu, and Jian-Wei Pan. Quantum computational advantage using photons. Science, 370(6523):1460–1463, December 2020. Publisher: American Association for the Advancement of Science Section: Report. doi:10.1126/​science.abe8770. Preprint: arXiv:2012.01625 [quant-ph].
https:/​/​doi.org/​10.1126/​science.abe8770
arXiv:2012.01625

[13] Alex Neville, Chris Sparrow, Raphaël Clifford, Eric Johnston, Patrick M. Birchall, Ashley Montanaro, and Anthony Laing. Classical boson sampling algorithms with superior performance to near-term experiments. Nature Physics, 13(12):1153–1157, December 2017. Publisher: Nature Publishing Group. doi:10.1038/​nphys4270. Preprint: arXiv:1705.00686 [quant-ph].
https:/​/​doi.org/​10.1038/​nphys4270
arXiv:1705.00686

[14] Peter Clifford and Raphaël Clifford. The Classical Complexity of Boson Sampling. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pages 146–155. Society for Industrial and Applied Mathematics, January 2018. doi:10.1137/​1.9781611975031.10. Preprint: arXiv:1706.01260 [cs.DS].
https:/​/​doi.org/​10.1137/​1.9781611975031.10
arXiv:1706.01260

[15] Jelmer J. Renema, Adrian Menssen, William R. Clements, Gil Triginer, William S. Kolthammer, and Ian A. Walmsley. Efficient Classical Algorithm for Boson Sampling with Partially Distinguishable Photons. Physical Review Letters, 120(22):220502, May 2018. Publisher: American Physical Society. doi:10.1103/​PhysRevLett.120.220502. Preprint: arXiv:1707.02793 [quant-ph].
https:/​/​doi.org/​10.1103/​PhysRevLett.120.220502
arXiv:1707.02793

[16] Jelmer J. Renema, Valery Shchesnovich, and Raúl García-Patrón. Classical simulability of noisy boson sampling. arXiv:1809.01953 [quant-ph], April 2019.
arXiv:1809.01953

[17] Raúl García-Patrón, Jelmer J. Renema, and Valery Shchesnovich. Simulating boson sampling in lossy architectures. Quantum, 3:169, August 2019. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften. doi:10.22331/​q-2019-08-05-169. Preprint: arXiv:1712.10037 [quant-ph].
https:/​/​doi.org/​10.22331/​q-2019-08-05-169
arXiv:1712.10037

[18] Michał Oszmaniec and Daniel Jost Brod. Classical simulation of photonic linear optics with lost particles. New Journal of Physics, 20(9):092002, September 2018. Publisher: IOP Publishing. doi:10.1088/​1367-2630/​aadfa8. Preprint: arXiv:1801.06166 [quant-ph].
arXiv:1801.06166

[19] Daniel Jost Brod and Michał Oszmaniec. Classical simulation of linear optics subject to nonuniform losses. Quantum, 4:267, May 2020. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften. doi:10.22331/​q-2020-05-14-267. Preprint: arXiv:1906.06696 [quant-ph].
https:/​/​doi.org/​10.22331/​q-2020-05-14-267
arXiv:1906.06696

[20] 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, November 2019. Publisher: IOP Publishing. doi:10.1088/​2058-9565/​ab5555. Preprint: arXiv:1907.00022 [quant-ph].
https:/​/​doi.org/​10.1088/​2058-9565/​ab5555
arXiv:1907.00022

[21] Valery Shchesnovich. Distinguishing noisy boson sampling from classical simulations. Quantum, 5:423, March 2021. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften. doi:10.22331/​q-2021-03-29-423. Preprint: arXiv:1905.11458 [quant-ph].
https:/​/​doi.org/​10.22331/​q-2021-03-29-423
arXiv:1905.11458

[22] Bujiao Wu, Bin Cheng, Fei Jia, Jialin Zhang, Man-Hong Yung, and Xiaoming Sun. Speedup in classical simulation of Gaussian boson sampling. Science Bulletin, 65(10):832–841, May 2020. Publisher: Elsevier B.V. and Science China Press. doi:10.1016/​j.scib.2020.02.012. Preprint: arXiv:1908.10070 [quant-ph].
https:/​/​doi.org/​10.1016/​j.scib.2020.02.012
arXiv:1908.10070

[23] 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, March 2020. Publisher: American Physical Society. doi:10.1103/​PhysRevLett.124.100502. Preprint: arXiv:1905.12075 [quant-ph].
https:/​/​doi.org/​10.1103/​PhysRevLett.124.100502
arXiv:1905.12075

[24] Nicolás Quesada and Juan Miguel Arrazola. Exact simulation of Gaussian boson sampling in polynomial space and exponential time. Physical Review Research, 2(2):023005, April 2020. Publisher: American Physical Society. doi:10.1103/​PhysRevResearch.2.023005. Preprint: arXiv:1908.08068 [quant-ph].
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.023005
arXiv:1908.08068

[25] Nicolás Quesada, Juan Miguel Arrazola, Trevor Vincent, Haoyu Qi, and Raúl García-Patrón. Quadratic speedup for simulating Gaussian boson sampling. arXiv:2010.15595 [quant-ph], February 2021.
arXiv:2010.15595

[26] Jelmer J. Renema. Simulability of partially distinguishable superposition and Gaussian boson sampling. Physical Review A, 101(6):063840, June 2020. doi:10.1103/​PhysRevA.101.063840. Preprint: arXiv:1911.10112 [quant-ph].
https:/​/​doi.org/​10.1103/​PhysRevA.101.063840
arXiv:1911.10112

### Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2022-05-17 23:43:05). On SAO/NASA ADS no data on citing works was found (last attempt 2022-05-17 23:43:06).