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] Dominik Hangleiter and Jens Eisert, "Computational advantage of quantum random sampling", Reviews of Modern Physics 95 3, 035001 (2023).
[2] 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).
[3] 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).
[4] Rawad Mezher, Ana Filipa Carvalho, and Shane Mansfield, "Solving graph problems with single photons and linear optics", Physical Review A 108 3, 032405 (2023).
[5] 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).
[6] C Bowie, S Shrapnel, and M J Kewming, "Quantum kernel evaluation via Hong–Ou–Mandel interference", Quantum Science and Technology 9 1, 015001 (2024).
[7] 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).
[8] Rawad Mezher and Shane Mansfield, "Assessing the quality of near-term photonic quantum devices", arXiv:2202.04735, (2022).
[9] Ulysse Chabaud, "Continuous Variable Quantum Advantages and Applications in Quantum Optics", arXiv:2102.05227, (2021).
[10] Kamil Bradler and Hugo Wallner, "Certain properties and applications of shallow bosonic circuits", arXiv:2112.09766, (2021).
The above citations are from Crossref's cited-by service (last updated successfully 2023-11-29 18:37:28) and SAO/NASA ADS (last updated successfully 2023-11-29 18:37:29). 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.