Quantum machine learning with adaptive linear optics
1Department of Computing and Mathematical Sciences, California Institute of Technology
2Université de Paris, IRIF, CNRS, France
3Laboratoire d'Informatique de Paris 6, CNRS, Sorbonne Université, 4 place Jussieu, 75005 Paris, France
4JFLI, CNRS, National Institute of Informatics, University of Tokyo, Tokyo, Japan
5School of Computational Sciences, Korea Institute for Advanced Study, Seoul 02455, Korea
| Published: | 2021-07-05, volume 5, page 496 |
| Eprint: | arXiv:2102.04579v2 |
| Doi: | https://doi.org/10.22331/q-2021-07-05-496 |
| Citation: | Quantum 5, 496 (2021). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We study supervised learning algorithms in which a quantum device is used to perform a computational subroutine – either for prediction via probability estimation, or to compute a kernel via estimation of quantum states overlap. We design implementations of these quantum subroutines using Boson Sampling architectures in linear optics, supplemented by adaptive measurements. We then challenge these quantum algorithms by deriving classical simulation algorithms for the tasks of output probability estimation and overlap estimation. We obtain different classical simulability regimes for these two computational tasks in terms of the number of adaptive measurements and input photons. In both cases, our results set explicit limits to the range of parameters for which a quantum advantage can be envisaged with adaptive linear optics compared to classical machine learning algorithms: we show that the number of input photons and the number of adaptive measurements cannot be simultaneously small compared to the number of modes. Interestingly, our analysis leaves open the possibility of a near-term quantum advantage with a single adaptive measurement.
Popular summary
► BibTeX data
► References
[1] R. P. Feynman, ``Simulating physics with computers,'' Int. J. Theor. Phys 21, (1982).
https://doi.org/10.1007/BF02650179
[2] P. W. Shor, ``Algorithms for quantum computation: discrete logarithms and factoring,'' in Proceedings 35th annual symposium on foundations of computer science, pp. 124–134, IEEE. 1994.
https://doi.org/10.1109/SFCS.1994.365700
[3] J. Preskill, ``Quantum Computing in the NISQ era and beyond,'' Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79
[4] S. Aaronson and A. Arkhipov, ``The computational Complexity of Linear Optics,'' Theory of Computing 9, 143 (2013).
https://doi.org/10.1145/1993636.1993682
[5] M. J. Bremner, R. Josza, and D. Shepherd, ``Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,'' Proc. R. Soc. A 459, 459 (2010).
https://doi.org/10.1098/rspa.2010.0301
[6] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al., ``Quantum supremacy using a programmable superconducting processor,'' Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5
[7] H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, et al., ``Quantum computational advantage using photons,'' Science 370, 1460–1463 (2020).
https://doi.org/10.1126/science.abe8770
[8] A. W. Harrow, A. Hassidim, and S. Lloyd, ``Quantum algorithm for linear systems of equations,'' Physical Review Letters 103, 150502 (2009).
https://doi.org/10.1103/PhysRevLett.103.150502
[9] M. Schuld, I. Sinayskiy, and F. Petruccione, ``The quest for a Quantum Neural Network,'' Quantum Information Processing 13, 2567–2586 (2014).
https://doi.org/10.1007/s11128-014-0809-8
[10] J. Romero, J. P. Olson, and A. Aspuru-Guzik, ``Quantum autoencoders for efficient compression of quantum data,'' Quantum Science and Technology 2, 045001 (2017).
https://doi.org/10.1088/2058-9565/aa8072
[11] C. Ciliberto, M. Herbster, A. D. Ialongo, M. Pontil, A. Rocchetto, S. Severini, and L. Wossnig, ``Quantum machine learning: a classical perspective,'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 474, 20170551 (2018).
https://doi.org/10.1098/rspa.2017.0551
[12] V. Dunjko and H. J. Briegel, ``Machine learning & artificial intelligence in the quantum domain: a review of recent progress,'' Reports on Progress in Physics 81, 074001 (2018).
https://doi.org/10.1088/1361-6633/aab406
[13] C. Zoufal, A. Lucchi, and S. Woerner, ``Quantum Generative Adversarial Networks for learning and loading random distributions,'' npj Quantum Information 5, 103 (2019).
https://doi.org/10.1038/s41534-019-0223-2
[14] N. Killoran, T. R. Bromley, J. M. Arrazola, M. Schuld, N. Quesada, and S. Lloyd, ``Continuous-variable quantum neural networks,'' Phys. Rev. Research 1, 033063 (2019).
https://doi.org/10.1103/PhysRevResearch.1.033063
[15] E. Farhi and H. Neven, ``Classification with Quantum Neural Networks on Near Term Processors,'' arXiv:1802.06002.
arXiv:1802.06002
[16] K. Beer, D. Bondarenko, T. Farrelly, T. J. Osborne, R. Salzmann, D. Scheiermann, and R. Wolf, ``Training deep quantum neural networks,'' Nature Communications 11, 808 (2020).
https://doi.org/10.1038/s41467-020-14454-2
[17] A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli, and S. Woerner, ``The power of quantum neural networks,'' arXiv:2011.00027. https://doi.org/10.1038/s43588-021-00084-1.
https://doi.org/10.1038/s43588-021-00084-1
arXiv:2011.00027
[18] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, ``Variational Quantum Algorithms,'' arXiv:2012.09265.
arXiv:2012.09265
[19] V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, ``Supervised learning with quantum-enhanced feature spaces,'' Nature 567, 209 (2019).
https://doi.org/10.1038/s41586-019-0980-2
[20] M. Schuld and N. Killoran, ``Quantum machine learning in feature Hilbert spaces,'' Physical review letters 122, 040504 (2019).
https://doi.org/10.1103/PhysRevLett.122.040504
[21] C. Blank, D. K. Park, J.-K. K. Rhee, and F. Petruccione, ``Quantum classifier with tailored quantum kernel,'' npj Quantum Information 6, 41 (2020).
https://doi.org/10.1038/s41534-020-0272-6
[22] K. Bartkiewicz, C. Gneiting, A. Černoch, K. Jiráková, K. Lemr, and F. Nori, ``Experimental kernel-based quantum machine learning in finite feature space,'' Scientific Reports 10, 12356 (2020).
https://doi.org/10.1038/s41598-020-68911-5
[23] Y. Liu, S. Arunachalam, and K. Temme, ``A rigorous and robust quantum speed-up in supervised machine learning,'' arXiv:2010.02174.
arXiv:2010.02174
[24] H.-Y. Huang, M. Broughton, M. Mohseni, R. Babbush, S. Boixo, H. Neven, and J. R. McClean, ``Power of data in quantum machine learning,'' arXiv:2011.01938. https://doi.org/10.1038/s41467-021-22539-9.
https://doi.org/10.1038/s41467-021-22539-9
arXiv:2011.01938
[25] C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, ``Gaussian boson sampling,'' Physical review letters 119, 170501 (2017).
https://doi.org/10.1103/PhysRevLett.119.170501
[26] M. Schuld, K. Brádler, R. Israel, D. Su, and B. Gupt, ``Measuring the similarity of graphs with a Gaussian boson sampler,'' Physical Review A 101, 032314 (2020).
https://doi.org/10.1103/PhysRevA.101.032314
[27] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, ``Barren plateaus in quantum neural network training landscapes,'' Nature Communications 9, (2018).
https://doi.org/10.1038/s41467-018-07090-4
[28] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, ``Cost-Function-Dependent Barren Plateaus in Shallow Quantum Neural Networks,'' arXiv:2001.00550. https://doi.org/10.1038/s41467-021-21728-w.
https://doi.org/10.1038/s41467-021-21728-w
arXiv:2001.00550
[29] S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, ``Noise-Induced Barren Plateaus in Variational Quantum Algorithms,'' arXiv:2007.14384.
arXiv:2007.14384
[30] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest, ``Measurement-based quantum computation,'' Nature Physics 5, 19–26 (2009).
https://doi.org/10.1038/nphys1157
[31] E. Knill, R. Laflamme, and G. J. Milburn, ``A scheme for efficient quantum computation with linear optics,'' Nature 409, 46–52 (2001).
https://doi.org/10.1038/35051009
[32] M. Schuld, ``Supervised quantum machine learning models are kernel methods,'' arXiv:2101.11020.
arXiv:arXiv:2101.11020
[33] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, ``Quantum circuit learning,'' Phys. Rev. A 98, 032309 (2018).
https://doi.org/10.1103/PhysRevA.98.032309
[34] B. M. Terhal and D. P. DiVincenzo, ``Classical simulation of noninteracting-fermion quantum circuits,'' Physical Review A 65, 032325 (2002).
https://doi.org/10.1103/PhysRevA.65.032325
[35] H. Pashayan, S. D. Bartlett, and D. Gross, ``From estimation of quantum probabilities to simulation of quantum circuits,'' Quantum 4, 223 (2020).
https://doi.org/10.22331/q-2020-01-13-223
[36] W. Hoeffding, ``Probability inequalities for sums of bounded random variables,'' Journal of the American statistical association 58, 13–30 (1963).
https://doi.org/10.2307/2282952
[37] M. Van Den Nest, ``Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond,'' Quantum Information & Computation 10, 258–271 (2010), arXiv:0811.0898.
arXiv:0811.0898
[38] D. Dieks, ``Overlap and distinguishability of quantum states,'' Physics Letters A 126, 303–306 (1988).
https://doi.org/10.1016/0375-9601(88)90840-7
[39] M. Fanizza, M. Rosati, M. Skotiniotis, J. Calsamiglia, and V. Giovannetti, ``Beyond the swap test: optimal estimation of quantum state overlap,'' Physical Review Letters 124, 060503 (2020).
https://doi.org/10.1103/PhysRevLett.124.060503
[40] H. Buhrman, R. Cleve, J. Watrous, and R. De Wolf, ``Quantum fingerprinting,'' Physical Review Letters 87, 167902 (2001).
https://doi.org/10.1103/PhysRevLett.87.167902
[41] U. Leonhardt, Essential Quantum Optics. Cambridge University Press, Cambridge, UK, 1st ed., 2010.
https://doi.org/10.1017/CBO9780511806117
[42] V. N. Vapnik, The Nature of Statistical Learning Theory. Springer-Verlag, Berlin, Heidelberg, 1995.
https://doi.org/10.1007/978-1-4757-3264-1
[43] C. J. Burges, ``A Tutorial on Support Vector Machines for Pattern Recognition,'' Data Mining and Knowledge Discovery 2, 121–167 (1998).
https://doi.org/10.1023/A:1009715923555
[44] G. James, D. Witten, T. Hastie, and R. Tibshirani, An Introduction to Statistical Learning: With Applications in R. Springer Publishing Company, Incorporated, 2014.
https://doi.org/10.1007/978-1-4614-7138-7
[45] A. Politi, J. C. Matthews, M. G. Thompson, and J. L. O'Brien, ``Integrated quantum photonics,'' IEEE Journal of Selected Topics in Quantum Electronics 15, 1673–1684 (2009).
https://doi.org/10.1109/JSTQE.2009.2026060
[46] M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani, ``Experimental realization of any discrete unitary operator,'' Physical review letters 73, 58 (1994).
https://doi.org/10.1103/PhysRevLett.73.58
[47] A. E. Moylett and P. S. Turner, ``Quantum simulation of partially distinguishable boson sampling,'' Phys. Rev. A 97, 062329 (2018).
https://doi.org/10.1103/PhysRevA.97.062329
[48] J. M. Arrazola, T. R. Bromley, J. Izaac, C. R. Myers, K. Brádler, and N. Killoran, ``Machine learning method for state preparation and gate synthesis on photonic quantum computers,'' arXiv:1807.10781. https://doi.org/10.1088/2058-9565/aaf59e.
https://doi.org/10.1088/2058-9565/aaf59e
arXiv:1807.10781
[49] K. Heya, Y. Suzuki, Y. Nakamura, and K. Fujii, ``Variational Quantum Gate Optimization,'' arXiv:1810.12745.
arXiv:1810.12745
[50] H. Pashayan, J. J. Wallman, and S. D. Bartlett, ``Estimating outcome probabilities of quantum circuits using quasiprobabilities,'' Physical review letters 115, 070501 (2015).
https://doi.org/10.1103/PhysRevLett.115.070501
[51] S. Bravyi, D. Gosset, and R. Movassagh, ``Classical algorithms for quantum mean values,'' arXiv:1909.11485. https://doi.org/10.1038/s41567-020-01109-8.
https://doi.org/10.1038/s41567-020-01109-8
arXiv:1909.11485
[52] N. Albert and S. Wilf Herbert, Combinatorial algorithms: for computers and calculators. Academic Press, 1978.
https://doi.org/10.1016/C2013-0-11243-3
[53] L. Gurvits, ``On the complexity of mixed discriminants and related problems,'' in International Symposium on Mathematical Foundations of Computer Science, pp. 447–458, Springer. 2005.
https://doi.org/10.1007/11549345_39
[54] S. Aaronson and T. Hance, ``Generalizing and derandomizing Gurvits's approximation algorithm for the permanent,'' arXiv:1212.0025.
arXiv:1212.0025
[55] J. K. Percus, Combinatorial methods, vol. 4. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[56] R. García-Patrón, J. J. Renema, and V. Shchesnovich, ``Simulating boson sampling in lossy architectures,'' Quantum 3, 169 (2019).
https://doi.org/10.22331/q-2019-08-05-169
Cited by
[1] Hamza Hasnaoui, Leonardo Limongi, Taira Giordani, Beatrice Polacchi, Alberto Quaranta, Martino Bernard, Fabio Sciarrino, and Mirko Lobino, "Optical quantum computing", Applied Physics Reviews 13 3, 031306 (2026).
[2] Giovanni Rodari, Tommaso Francalanci, Eugenio Caruccio, Francesco Hoch, Gonzalo Carvacho, Taira Giordani, Nicolò Spagnolo, Riccardo Albiero, Niki Di Giano, Francesco Ceccarelli, Giacomo Corrielli, Andrea Crespi, Roberto Osellame, Ulysse Chabaud, and Fabio Sciarrino, "Observation of Lie algebraic invariants in quantum linear optics", Physical Review Research 7 4, 043325 (2025).
[3] 占浩 Zhan Hao, 胥亮 Xu Liang, and 张利剑 Zhang Lijian, " 多光子干涉在量子计算及量子机器学习中的研究进展（特邀）", Acta Optica Sinica 45 20, 2027020 (2025).
[4] Simone Di Micco, Beatrice Polacchi, Taira Giordani, and Fabio Sciarrino, "Quantum memristor with vacuum-one-photon qubits", Physical Review Research 7 4, 043131 (2025).
[5] Timothée Goubault De Brugière and Nicolas Heurtel, "Fast and memory-efficient strong simulation of noisy adaptive linear optical circuits", Computer Physics Communications 321, 110016 (2026).
[6] Francesco Hoch, Eugenio Caruccio, Giovanni Rodari, Tommaso Francalanci, Alessia Suprano, Taira Giordani, Gonzalo Carvacho, Nicolò Spagnolo, Seid Koudia, Massimiliano Proietti, Carlo Liorni, Filippo Cerocchi, Riccardo Albiero, Niki Di Giano, Marco Gardina, Francesco Ceccarelli, Giacomo Corrielli, Ulysse Chabaud, Roberto Osellame, Massimiliano Dispenza, and Fabio Sciarrino, "Quantum machine learning with Adaptive Boson Sampling via post-selection", Nature Communications 16 1, 902 (2025).
[7] Tommaso Francalanci, Giovanni Rodari, Eugenio Caruccio, Francesco Hoch, Gonzalo Carvacho, Taira Giordani, Nicolò Spagnolo, Riccardo Albiero, Niki Di Giano, Giacomo Corrielli, Francesco Ceccarelli, Roberto Osellame, Ulysse Chabaud, and Fabio Sciarrino, "Generalized photon-bunching bounds in linear and non-linear quantum optical dynamics", Optica 13 6, 1137 (2026).
[8] Jiahao Huang, Min Zhuang, Jungeng Zhou, Yi Shen, and Chaohong Lee, "Quantum Metrology Assisted by Machine Learning", Advanced Quantum Technologies 8 4, 2300329 (2025).
[9] Rawad Mezher, Ana Filipa Carvalho, and Shane Mansfield, "Solving graph problems with single photons and linear optics", Physical Review A 108 3, 032405 (2023).
[10] Han-Sen Zhong, Yu-Hao Deng, Jian Qin, Hui Wang, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Dian Wu, Si-Qiu Gong, Hao Su, 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, Jelmer J. Renema, Chao-Yang Lu, and Jian-Wei Pan, "Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light", Physical Review Letters 127 18, 180502 (2021).
[11] Rawad Mezher, Ana Filipa Carvalho, and Shane Mansfield, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 274 (2023) ISBN:979-8-3503-4323-6.
[12] Changhun Oh and Youngrong Lim, "Classical Algorithms for Measurement-Adaptive Gaussian Circuits", PRX Quantum 7 1, 010329 (2026).
[13] Konrad Wojciechowski, Krzysztof Kurowski, Mateusz Slysz, and Tomasz Pecyna, "Open QBench: A benchmarking framework for evaluating quantum computing platforms", Quantum Information Processing 25 3, 98 (2026).
[14] Dominik Hangleiter and Jens Eisert, "Computational advantage of quantum random sampling", Reviews of Modern Physics 95 3, 035001 (2023).
[15] Hao Zhan, Ben Wang, Minghao Mi, Jie Xie, Liang Xu, Aonan Zhang, and Lijian Zhang, "Experimental benchmarking of quantum state overlap estimation strategies with photonic systems", Light: Science & Applications 14 1, 83 (2025).
[16] Wentao Chen, Yao Lu, Shuaining Zhang, Kuan Zhang, Guanhao Huang, Mu Qiao, Xiaolu Su, Jialiang Zhang, Jing-Ning Zhang, Leonardo Banchi, M. S. Kim, and Kihwan Kim, "Scalable and programmable phononic network with trapped ions", Nature Physics 19 6, 877 (2023).
[17] Beng Yee Gan, Daniel Leykam, and Dimitris G. Angelakis, "Fock state-enhanced expressivity of quantum machine learning models", EPJ Quantum Technology 9 1, 16 (2022).
[18] Soohyun Park, Hankyul Baek, and Joongheon Kim, "Quantum Reinforcement Learning for Spatio-Temporal Prioritization in Metaverse", IEEE Access 12, 54732 (2024).
[19] Ulysse Chabaud, Roohollah Ghobadi, Salman Beigi, and Saleh Rahimi-Keshari, "Phase-space negativity as a computational resource for quantum kernel methods", Quantum 8, 1519 (2024).
[20] Alexia Salavrakos, Nicolas Maring, Pierre-Emmanuel Emeriau, and Shane Mansfield, "Photon-native quantum algorithms", Materials for Quantum Technology 5 2, 023001 (2025).
[21] C Bowie, S Shrapnel, and M J Kewming, "Quantum kernel evaluation via Hong–Ou–Mandel interference", Quantum Science and Technology 9 1, 015001 (2024).
[22] Léo Monbroussou, Eliott Z. Mamon, Hugo Thomas, Verena Yacoub, Ulysse Chabaud, and Elham Kashefi, "Toward quantum advantage with photonic state injection", Physical Review Research 7 3, 033051 (2025).
[23] James Mills and Rawad Mezher, "Mitigating photon loss in linear optical quantum circuits", Quantum 10, 2030 (2026).
[24] Soohyun Park, Hankyul Baek, and Joongheon Kim, "Spatio-Temporal Multi-Metaverse Dynamic Streaming for Hybrid Quantum-Classical Systems", IEEE/ACM Transactions on Networking 32 6, 5279 (2024).
[25] Alexey Melnikov, Mohammad Kordzanganeh, Alexander Alodjants, and Ray-Kuang Lee, "Quantum machine learning: from physics to software engineering", Advances in Physics: X 8 1, 2165452 (2023).
[26] Michael G Jabbour and Leonardo Novo, "Complexity of Gaussian quantum optics with a limited number of non-linearities", Quantum Science and Technology 10 4, 045021 (2025).
[27] Léo. Monbroussou, Beatrice Polacchi, Verena Yacoub, Eugenio Caruccio, Giovanni Rodari, Francesco Hoch, Gonzalo Carvacho, Nicolò Spagnolo, Taira Giordani, Mattia Bossi, Abhiram Rajan, Niki Di Giano, Riccardo Albiero, Francesco Ceccarelli, Roberto Osellame, Elham Kashefi, and Fabio Sciarrino, "Photonic quantum convolutional neural networks with adaptive state injection", Advanced Photonics 7, 066012 (2025).
[28] Leonardo Novo, Marco Robbio, Ernesto F. Galvão, and Nicolas J. Cerf, "Native linear-optical protocol for efficient multivariate trace estimation", arXiv:2601.14204, (2026).
[29] Kamil Bradler and Hugo Wallner, "Certain properties and applications of shallow bosonic circuits", arXiv:2112.09766, (2021).
[30] Ulysse Chabaud, "Continuous Variable Quantum Advantages and Applications in Quantum Optics", arXiv:2102.05227, (2021).
[31] Rawad Mezher and Shane Mansfield, "Assessing the quality of near-term photonic quantum devices", arXiv:2202.04735, (2022).
The above citations are from Crossref's cited-by service (last updated successfully 2026-07-15 14:03:20) and SAO/NASA ADS (last updated successfully 2026-07-15 14:03:21). 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.
Pingback: Feedfoward Operations