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
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] Ulysse Chabaud, “Continuous Variable Quantum Advantages and Applications in Quantum Optics”, arXiv:2102.05227.
The above citations are from SAO/NASA ADS (last updated successfully 2021-07-05 15:52:05). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2021-07-05 15:52:03: Could not fetch cited-by data for 10.22331/q-2021-07-05-496 from Crossref. This is normal if the DOI was registered recently.
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.
PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Source: https://quantum-journal.org/papers/q-2021-07-05-496/
