academic

Boundaries for quantum advantage with single photons and loop-based time-bin interferometers

Quantum Journal

16 min read

2 views

0 likes

Boundaries for quantum advantage with single photons and loop-based time-bin interferometers

Summarize this article with:

AbstractLoop-based boson samplers interfere photons in the time degree of freedom using a sequence of delay lines. Since they require few hardware components while also allowing for long-range entanglement, they are strong candidates for demonstrating quantum advantage beyond the reach of classical emulation. We propose a method to exploit this loop-based structure to more efficiently classically sample from such systems. Our algorithm exploits a causal-cone argument to decompose the circuit into smaller effective components that can each be simulated sequentially by calling a state vector simulator as a subroutine. To quantify the complexity of our approach, we develop a new lattice path formalism that allows us to efficiently characterize the state space that must be tracked during the simulation. In addition, we develop a heuristic method that allows us to predict the expected average and worst-case memory requirements of running these simulations. We use these methods to compare the simulation complexity of different families of loop-based interferometers, allowing us to quantify the potential for quantum advantage of single-photon Boson Sampling in loop-based architectures.Featured image: Top: A time-bin boson sampler made of a sequence of optical delay lines (loops) expressed in the spatial-mode representation, where the loops form stair-case like structures. In the progressive decomposition, we push all the measurements as far to the beginning of the circuit as possible, pushing also the relevant beamsplitters. This way we identify causal cones of the output modes, and obtain a sequence of smaller circuits which are easier to simulate. Bottom left: An example of our lattice path formalism that describes the reachable state space of a loop-based system throughout simulation. Here, we show the state space after evolving the input wavefunction through one component and measuring one mode. Each output basis state that can be found with nonzero probability corresponds to a path within a region in the integer lattice, and these are easy to count or enumerate. States corresponding to paths outside the region are not reachable. Bottom right: The numbers of photons in modes correspond to vertical steps taken by the lattice path.Popular summaryBy setting up optical networks and sending in photons, we can realise a modality of quantum computing called 'boson sampling'. This is one of the most cost-effective methods of achieving quantum advantage — building a quantum device that no classical computer in the world can simulate in reasonable time. In this work, we study a promising architecture for boson sampling systems involving single photons and sequences of optical delay lines. We propose a brand new algorithm that simulates these setups component-by-component, while keeping track of the whole quantum state. We develop mathematical tools to help us predict the memory and time requirements of running the new simulation algorithm, even for very large systems that we cannot simulate. We use this to predict at least how large of a hardware setup is needed to achieve quantum advantage, providing a guiding point for future experimental and theoretical effort.► BibTeX data@article{Novak2025boundariesquantum, doi = {10.22331/q-2025-11-17-1915}, url = {https://doi.org/10.22331/q-2025-11-17-1915}, title = {Boundaries for quantum advantage with single photons and loop-based time-bin interferometers}, author = {Nov{\'{a}}k, Samo and Roberts, David D. and Makarovskiy, Alexander and Garc{\'{i}}a-Patr{\'{o}}n, Ra{\'{u}}l and Clements, William R.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1915}, month = nov, year = {2025} }► References [1] Scott Aaronson and Alex Arkhipov. ``The computational complexity of linear optics''. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing. Page 333–342. STOC '11New York, NY, USA (2011). Association for Computing Machinery. https://doi.org/10.1145/1993636.1993682 [2] L. G. Valiant. ``The complexity of computing the permanent''.

Theoretical Computer Science 8, 189–201 (1979). https://doi.org/10.1016/0304-3975(79)90044-6 [3] Michael Reck, Anton Zeilinger, Herbert J. Bernstein, and Philip Bertani. ``Experimental realization of any discrete unitary operator''. Phys. Rev. Lett. 73, 58–61 (1994). https://doi.org/10.1103/PhysRevLett.73.58 [4] William R. Clements, Peter C. Humphreys, Benjamin J. Metcalf, W. Steven Kolthammer, and Ian A. Walmsley. ``Optimal design for universal multiport interferometers''. Optica 3, 1460–1465 (2016). https://doi.org/10.1364/OPTICA.3.001460 [5] Raúl García-Patrón, Jelmer J. Renema, and Valery Shchesnovich. ``Simulating boson sampling in lossy architectures''. Quantum 3, 169 (2019). https://doi.org/10.22331/q-2019-08-05-169 [6] Lars S. Madsen, Fabian Laudenbach, Mohsen Falamarzi Askarani, Fabien Rortais, Trevor Vincent, Jacob F. F. Bulmer, Filippo M. Miatto, Leonhard Neuhaus, Lukas G. Helt, Matthew J. Collins, Adriana E. Lita, Thomas Gerrits, Sae Woo Nam, Varun D. Vaidya, Matteo Menotti, Ish Dhand, Zachary Vernon, Nicolás Quesada, and Jonathan Lavoie. ``Quantum computational advantage with a programmable photonic processor''. Nature 606, 75–81 (2022). https://doi.org/10.1038/s41586-022-04725-x [7] Keith R. Motes, Alexei Gilchrist, Jonathan P. Dowling, and Peter P. Rohde. ``Scalable Boson Sampling with Time-Bin Encoding Using a Loop-Based Architecture''.

Physical Review Letters 113, 120501 (2014). https://doi.org/10.1103/PhysRevLett.113.120501 [8] Michael Lubasch, Antonio A. Valido, Jelmer J. Renema, W. Steven Kolthammer, Dieter Jaksch, M. S. Kim, Ian Walmsley, and Raúl García-Patrón. ``Tensor network states in time-bin quantum optics''. Phys. Rev. A 97, 062304 (2018). https://doi.org/10.1103/PhysRevA.97.062304 [9] Abhinav Deshpande, Arthur Mehta, Trevor Vincent, Nicolás Quesada, Marcel Hinsche, Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi, Jens Eisert, Dominik Hangleiter, Bill Fefferman, and Ish Dhand. ``Quantum computational advantage via high-dimensional gaussian boson sampling''. Science Advances 8, eabi7894 (2022). https://doi.org/10.1126/sciadv.abi7894 [10] Kamil Bradler and Hugo Wallner. ``Certain properties and applications of shallow bosonic circuits'' (2021). arXiv:2112.09766 [quant-ph]. https://doi.org/10.48550/arXiv.2112.09766 arXiv:2112.09766 [11] Peter Clifford and Raphaël Clifford. ``The classical complexity of boson sampling''. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Page 146–155. SODA '18USA (2018). Society for Industrial and Applied Mathematics. https://doi.org/10.5555/3174304.3175276 [12] Changhun Oh, Youngrong Lim, Bill Fefferman, and Liang Jiang. ``Classical Simulation of Boson Sampling Based on Graph Structure''.

Physical Review Letters 128, 190501 (2022). https://doi.org/10.1103/PhysRevLett.128.190501 [13] Samo Novák and Raúl García-Patrón. ``Laplace expansions and tree decompositions: polytime algorithm for shallow nearest-neighbour boson sampling'' (2024). arXiv:2412.18664 [quant-ph]. https://doi.org/10.48550/arXiv.2412.18664 arXiv:2412.18664 [14] Nicolas Heurtel, Shane Mansfield, Jean Senellart, and Benoît Valiron. ``Strong Simulation of Linear Optical Processes''.

Computer Physics Communications 291 (2023). https://doi.org/10.1016/j.cpc.2023.108848 [15] Changhun Oh, Minzhao Liu, Yuri Alexeev, Bill Fefferman, and Liang Jiang. ``Classical algorithm for simulating experimental gaussian boson sampling''. Nature Physics 20, 1461–1468 (2024). https://doi.org/10.1038/s41567-024-02535-8 [16] Byeongseon Go, Changhun Oh, Liang Jiang, and Hyunseok Jeong. ``Exploring shallow-depth boson sampling: Toward a scalable quantum advantage''. Phys. Rev. A 109, 052613 (2024). https://doi.org/10.1103/PhysRevA.109.052613 [17] Byeongseon Go, Changhun Oh, and Hyunseok Jeong. ``On computational complexity and average-case hardness of shallow-depth boson sampling'' (2024). arXiv:2405.01786 [quant-ph]. https://doi.org/10.48550/arXiv.2405.01786 arXiv:2405.01786 [18] Richard A. Campos, Bahaa E. A. Saleh, and Malvin C. Teich. ``Quantum-mechanical lossless beam splitter: Su(2) symmetry and photon statistics''. Phys. Rev. A 40, 1371–1384 (1989). https://doi.org/10.1103/PhysRevA.40.1371 [19] Lorenzo Carosini, Virginia Oddi, Francesco Giorgino, Lena M. Hansen, Benoit Seron, Simone Piacentini, Tobias Guggemos, Iris Agresti, Juan C. Loredo, and Philip Walther. ``Programmable multiphoton quantum interference in a single spatial mode''. Science Advances 10 (2024). https://doi.org/10.1126/sciadv.adj0993 [20] Patrik I. Sund, Ravitej Uppu, Stefano Paesani, and Peter Lodahl. ``Hardware requirements for realizing a quantum advantage with deterministic single-photon sources''. Phys. Rev. A 109, 042613 (2024). https://doi.org/10.1103/PhysRevA.109.042613 [21] Yu 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). https://doi.org/10.1103/PhysRevLett.118.190501 [22] 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 $1{0}^{14}$-dimensional Hilbert space''. Phys. Rev. Lett. 123, 250503 (2019). https://doi.org/10.1103/PhysRevLett.123.250503 [23] Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, and Michal Oszmaniec. ``Complexity-theoretic foundations of BosonSampling with a linear number of modes'' (2023). arXiv:2312.00286 [quant-ph]. https://doi.org/10.48550/arXiv.2312.00286 arXiv:2312.00286 [24] Berwin A. Turlach. ``Bandwidth selection in kernel density estimation: a rewiew'' (1999). Statistic und Oekonometrie 9307, Humboldt Universitaet Berlin. https://ideas.repec.org/p/wop/humbse/9307.html [25] ``Frontier User Guide — OLCF User Documentation'' (2024). https://docs.olcf.ornl.gov/systems/frontier_user_guide.html, accessed 2024-09-05. https://docs.olcf.ornl.gov/systems/frontier_user_guide.html [26] 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 (2018). https://doi.org/10.1103/PhysRevLett.120.220502 [27] Christopher Sparrow. ``Quantum interference in universal linear optical devices for quantum computation and simulation''. PhD thesis.

Imperial College London. (2018). https://doi.org/10.25560/67638 [28] V. S. Shchesnovich. ``Partial indistinguishability theory for multiphoton experiments in multiport devices''. Phys. Rev. A 91, 013844 (2015). https://doi.org/10.1103/PhysRevA.91.013844 [29] Emilio Annoni and Stephen C Wein. ``Incoherent behavior of partially distinguishable photons'' (2025). arXiv:2502.05047. https://doi.org/10.48550/arXiv.2502.05047 arXiv:2502.05047 [30] J.C. Rosales and P.A. García-Sánchez. ``Numerical semigroups''. Developments in Mathematics.

Springer New York. (2009). https://doi.org/10.1007/978-1-4419-0160-6 [31] Richard P. Stanley. ``Enumerative combinatorics''. Number 49, 208 in Cambridge studies in advanced mathematics.

Cambridge University Press. Cambridge, NY (2012). Second edition. https://doi.org/10.1017/CBO9781139058520Cited byCould not fetch Crossref cited-by data during last attempt 2025-11-17 17:17:36: Could not fetch cited-by data for 10.22331/q-2025-11-17-1915 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2025-11-17 17:17:37: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractLoop-based boson samplers interfere photons in the time degree of freedom using a sequence of delay lines. Since they require few hardware components while also allowing for long-range entanglement, they are strong candidates for demonstrating quantum advantage beyond the reach of classical emulation. We propose a method to exploit this loop-based structure to more efficiently classically sample from such systems. Our algorithm exploits a causal-cone argument to decompose the circuit into smaller effective components that can each be simulated sequentially by calling a state vector simulator as a subroutine. To quantify the complexity of our approach, we develop a new lattice path formalism that allows us to efficiently characterize the state space that must be tracked during the simulation. In addition, we develop a heuristic method that allows us to predict the expected average and worst-case memory requirements of running these simulations. We use these methods to compare the simulation complexity of different families of loop-based interferometers, allowing us to quantify the potential for quantum advantage of single-photon Boson Sampling in loop-based architectures.Featured image: Top: A time-bin boson sampler made of a sequence of optical delay lines (loops) expressed in the spatial-mode representation, where the loops form stair-case like structures. In the progressive decomposition, we push all the measurements as far to the beginning of the circuit as possible, pushing also the relevant beamsplitters. This way we identify causal cones of the output modes, and obtain a sequence of smaller circuits which are easier to simulate. Bottom left: An example of our lattice path formalism that describes the reachable state space of a loop-based system throughout simulation. Here, we show the state space after evolving the input wavefunction through one component and measuring one mode. Each output basis state that can be found with nonzero probability corresponds to a path within a region in the integer lattice, and these are easy to count or enumerate. States corresponding to paths outside the region are not reachable. Bottom right: The numbers of photons in modes correspond to vertical steps taken by the lattice path.Popular summaryBy setting up optical networks and sending in photons, we can realise a modality of quantum computing called 'boson sampling'. This is one of the most cost-effective methods of achieving quantum advantage — building a quantum device that no classical computer in the world can simulate in reasonable time. In this work, we study a promising architecture for boson sampling systems involving single photons and sequences of optical delay lines. We propose a brand new algorithm that simulates these setups component-by-component, while keeping track of the whole quantum state. We develop mathematical tools to help us predict the memory and time requirements of running the new simulation algorithm, even for very large systems that we cannot simulate. We use this to predict at least how large of a hardware setup is needed to achieve quantum advantage, providing a guiding point for future experimental and theoretical effort.► BibTeX data@article{Novak2025boundariesquantum, doi = {10.22331/q-2025-11-17-1915}, url = {https://doi.org/10.22331/q-2025-11-17-1915}, title = {Boundaries for quantum advantage with single photons and loop-based time-bin interferometers}, author = {Nov{\'{a}}k, Samo and Roberts, David D. and Makarovskiy, Alexander and Garc{\'{i}}a-Patr{\'{o}}n, Ra{\'{u}}l and Clements, William R.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1915}, month = nov, year = {2025} }► References [1] Scott Aaronson and Alex Arkhipov. ``The computational complexity of linear optics''. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing. Page 333–342. STOC '11New York, NY, USA (2011). Association for Computing Machinery. https://doi.org/10.1145/1993636.1993682 [2] L. G. Valiant. ``The complexity of computing the permanent''.

Springer New York. (2009). https://doi.org/10.1007/978-1-4419-0160-6 [31] Richard P. Stanley. ``Enumerative combinatorics''. Number 49, 208 in Cambridge studies in advanced mathematics.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Boundaries for quantum advantage with single photons and loop-based time-bin interferometers

Tags

Source Information