Srinivasan Arunachalam
Skip Abstract Section
Abstract
This paper surveys quantum learning theory: the theoretical aspects of machine learning using quantum computers. We describe the main results known for three models of learning: exact learning from membership queries, and Probably Approximately Correct (PAC) and agnostic learning from classical or quantum examples.
- J. Adcock, E. Allen, M. Day, S. Frick, J. Hinchliff, M. Johnson, S. Morley-Short, S. Pallister, A. Price, and S. Stanisic. Advances in quantum machine learning, 9 Dec 2015. arXiv:1512.02900.Google Scholar
- S. Aaronson. Ten semi-grand challenges for quantum computing theory. http://www.scottaaronson.com/writings/qchallenge.html, 2005.Google Scholar
- S. Aaronson. The learnability of quantum states. Proceedings of the Royal Society of London, 463(2088), 2007. quant-ph/0608142.Google Scholar
- S. Aaronson. Quantum machine learning algorithms: Read the fine print. Nature Physics, 11(4):291--293, April 2015.Google ScholarCross Ref
- M. Anthony and P. Bartlett. Function learning from interpolation. Combinatorics, Probability, and Computing, 9(3):213--225, 2000. Earlier version in EuroCOLT'95. Google ScholarDigital Library
- M. Anthony and P. L. Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 2009. Google ScholarDigital Library
- E. Aïmeur, G. Brassard, and S. Gambs. Machine learning in a quantum world. In Proceedings of Advances in Artificial Intelligence, 19th Conference of the Canadian Society for Computational Studies of Intelligence, volume 4013 of Lecture Notes in Artificial Intelligence, pages 431--442, 2006. Google ScholarDigital Library
- E. Aïmeur, G. Brassard, and S. Gambs. Quantum speed-up for unsupervised learning. Machine Learning, 90(2):261--287, 2013. Google ScholarDigital Library
- S. Aaronson and L. Chen. Complexity-theoretic foundations of quantum supremacy experiments. arXiv:1612.05903, 2016.Google Scholar
- A. Ambainis, K. Iwama, A. Kawachi, H. Masuda, R. H. Putra, and S. Yamashita. Quantum identification of Boolean oracles. In Proceedings of 30th Annual Symposium on Theoretical Aspects of Computer Science (STACS'04), pages 105--116, 2004. arXiv:quant-ph/0403056.Google ScholarCross Ref
- A. Ambainis, K. Iwama, A. Kawachi, R. Raymond, and S. Yamashita. Improved algorithms for quantum identification of Boolean oracles. Theoretical Computer Science, 378(1):41--53, 2007. Google ScholarDigital Library
- A. Ambainis, K. Iwama, M. Nakanishi, H. Nishimura, R. Raymond, S. Tani, and S. Yamashita. Average/worst-case gap of quantum query complexities by on-set size. 2009. arXiv:0908.2468v1.Google Scholar
- D. Angluin and M. Kharitonov. When won't membership queries help? Journal of Computer and System Sciences, 50(2):336--355, 1995. Earlier version in STOC'91. Google ScholarDigital Library
- A. Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750--767, 2002. Earlier version in STOC'00. quant-ph/0002066. Google ScholarDigital Library
- D. Angluin. Queries and concept learning. Machine Learning, 2(4):319--342, 1987. Google ScholarDigital Library
- A. Ambainis, A. Nayak, A. Ta-Shma, and U. V. Vazirani. Dense quantum coding and quantum nite automata. Journal of the ACM, 49(4):496--511, 2002. Earlier version in STOC'99. Google ScholarDigital Library
- A. Atıcı and R. Servedio. Improved bounds on quantum learning algorithms. Quantum Information Processing, 4(5):355--386, 2005. quant-ph/0411140. Google ScholarDigital Library
- A. Atıcı and R. Servedio. Quantum algorithms for learning and testing juntas. Quantum Information Processing, 6(5):323--348, 2009. arXiv:0707.3479. Google ScholarDigital Library
- S. Arunachalam and R. de Wolf. Optimal quantum sample complexity of learning algorithms, 4 Jul 2016. arXiv:1607.00932. To appear in Proceedings of CCC'17.Google Scholar
- C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510--1523, 1997. quantph/9701001. Google ScholarDigital Library
- N. H. Bshouty, R. Cleve, R. Gavaldà, S. Kannan, and C. Tamon. Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences, 52(3):421--433, 1996. Earlier version in COLT'94. Google ScholarDigital Library
- A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929--965, 1989. Google ScholarDigital Library
- A. Belovs. Quantum algorithms for learning symmetric juntas via the adversary bound. Computational Complexity, 24(2):255--293, 2015. Earlier version in Complexity'14. arXiv:1311.6777. Google ScholarDigital Library
- P. A. Benioff. Quantum mechanical Hamiltonian models of Turing machines. Journal of Statistical Physics, 29(3):515--546, 1982.Google ScholarCross Ref
- G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplication and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pages 53--74. 2002. quant-ph/0005055.Google Scholar
- N. H. Bshouty and J. C. Jackson. Learning DNF over the uniform distribution using a quantum example oracle. SIAM Journal on Computing, 28(3):1136--1153, 1999. Earlier version in COLT'95. Google ScholarDigital Library
- H. Barnum and E. Knill. Reversing quantum dynamics with near-optimal quantum and classical fidelity. Journal of Mathematical Physics, 43:2097--2106, 2002. quantph/0004088.Google ScholarCross Ref
- P. Bartlett and P. M. Long. Prediction, learning, uniform convergence, and scalesensitive dimensions. Journal of Computer and System Sciences, 56(2):174--190, 1998. Google ScholarDigital Library
- E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411--1473, 1997. Earlier version in STOC'93. Google ScholarDigital Library
- J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd. Quantum machine learning, 28 Nov 2016. arXiv:1611.09347.Google Scholar
- H. C. Cheng, M. H. Hsieh, and P. C. Yeh. The learnability of unknown quantum measurements. Quantum Information and Computation, 16(7&8):615--656, 2016. arXiv:1501.00559.Google ScholarDigital Library
- D. Deutsch. Quantum theory, the Church-Turing principle, and the universal quantum Turing machine. In Proceedings of the Royal Society of London, volume A400, pages 97--117, 1985.Google Scholar
- A. Daniely and S. Shalev-Shwartz. Complexity theoretic limitations on learning DNF's. In Proceedings of the 29th Conference on Learning Theory (COLT'16), 2016. Google ScholarDigital Library
- R. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6/7):467--488, 1982.Google ScholarCross Ref
- R. Feynman. Quantum mechanical computers. Optics News, 11:11--20, 1985.Google ScholarCross Ref
- Y. Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256--285, 1995. Earlier version in COLT'90. Google ScholarDigital Library
- D. Gavinsky. Quantum predictive learning and communication complexity with single input. Quantum Information and Computation, 12(7-8):575--588, 2012. Earlier version in COLT'10. arXiv:0812.3429. Google ScholarDigital Library
- O. Goldreich and L. Levin. A hard-core predicate for all one-way functions. In Proceedings of 21st ACM STOC, pages 25--32, 1989. Google ScholarDigital Library
- L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of 28th ACM STOC, pages 212--219, 1996. quant-ph/9605043. Google ScholarDigital Library
- S. Hanneke. The optimal sample complexity of PAC learning. Journal of Machine Learning Research, 17(38):1--15, 2016. arXiv:1507.00473. Google ScholarDigital Library
- D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78--150, 1992. Google ScholarDigital Library
- T. Hegedüs. Generalized teaching dimensions and the query complexity of learning. In Proceedings of the 8th Conference on Learning Theory (COLT'95), pages 108--117, 1995. Google ScholarDigital Library
- J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yi. Sample-optimal tomography of quantum states. In Proceedings of 48th ACM STOC, pages 913--925, 2016. arXiv:1508.01797. Google ScholarDigital Library
- A. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for solving linear systems of equations. Physical Review Letters, 103(15):150502, 2009. arXiv:0811.3171.Google ScholarCross Ref
- M. Hunziker, D. A. Meyer, J. Park, J. Pommersheim, and M. Rothstein. The geometry of quantum learning. Quantum Information Processing, 9(3):321--341, 2010. quantph/0309059. Google ScholarDigital Library
- A. S. Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii, 9(3):3--11, 1973. English translation in Problems of Information Transmission, 9:177--183, 1973.Google Scholar
- J. C. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55(3):414--440, 1997. Earlier version in FOCS'94. Google ScholarDigital Library
- R. Kothari. Quantum computing and learning theory. Unpublished manuscript, 2012.Google Scholar
- R. Kothari. An optimal quantum algorithm for the oracle identification problem. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), pages 482--493, 2014. arXiv:1311.7685.Google Scholar
- I. Kerenidis and A. Prakash. Quantum recommendation systems. In Innovations in Theoretical Computer Science (ITCS'17), 2017. arXiv:1603.08675.Google Scholar
- A. Klivans and R. Servedio. Learning DNF in time 2~O (n1=3). Journal of Computer and System Sciences, 68(2):303--318, 2004. Earlier version in STOC'01. Google ScholarDigital Library
- M. J. Kearns, R. E. Schapire, and L. Sellie. Toward efficient agnostic learning. Machine Learning, 17(2-3):115--141, 1994. Earlier version in COLT'92. Google ScholarDigital Library
- M. J. Kearns and L. G. Valiant. Cryptographic limitations on learning Boolean formulae and nite automata. Journal of the ACM, 41(1):67--95, 1994. Google ScholarDigital Library
- M. J. Kearns and U. V. Vazirani. An introduction to computational learning theory. MIT Press, 1994. Google ScholarDigital Library
- C. Y.-Y. Lin and H. Lin. Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester. Theory of Computing, 12:1--35, 2016. Earlier version in CCC'15. arXiv:1410.0932.Google ScholarCross Ref
- N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transform, and learnability. Journal of the ACM, 40(3):607--620, 1993. Earlier version in FOCS'89. Google ScholarDigital Library
- S. Lloyd, M. Mohseni, and P. Rebentrost. Quantum algorithms for supervised and unsupervised machine learning, 1 Jul 2013. arXiv:1307.0411.Google Scholar
- S. Lloyd, M. Mohseni, and P. Rebentrost. Quantum principal component analysis. Nature Physics, 10(631--633), 2013. arXiv:1307.0401.Google Scholar
- Y. Manin. Vychislimoe i nevychislimoe (computable and noncomputable). Soviet Radio, pages 13--15, 1980. In Russian.Google Scholar
- Y. Manin. Classical computing, quantum computing, and Shor's factoring algorithm. quant-ph/9903008, 2 Mar 1999.Google Scholar
- A. Montanaro. On the distinguishability of random quantum states. Communications in Mathematical Physics, 273(3):619--636, 2007. quant-ph/0607011.Google ScholarCross Ref
- M. Yu. Moshkov. Conditional tests. Problemy Kibernetzkt, 40:131--170, 1983. In Russian.Google Scholar
- E. Mossel, R. O'Donnell, and R. Servedio. Learning functions of k relevant variables. Journal of Computer and System Sciences, 69(3):421--434, 2004. Earlier version in STOC'03. Google ScholarDigital Library
- M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google ScholarDigital Library
- R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google ScholarDigital Library
- R. O'Donnell and J. Wright. Efficient quantum tomography. In Proceedings of 48th ACM STOC, pages 899--912, 2016. arXiv:1508.01907. Google ScholarDigital Library
- P. Rebentrost, M. Mohseni, and S. Lloyd. Quantum support vector machine for big data classi cation. Physical Review Letters, 113(13), 2013. arXiv:1307.0471.Google Scholar
- S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014. Google ScholarDigital Library
- R. Servedio and S. Gortler. Equivalences and separations between quantum and classical learnability. SIAM Journal on Computing, 33(5):1067--1092, 2004. Combines earlier papers from ICALP'01 and CCC'01. quant-ph/0007036. Google ScholarDigital Library
- P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484--1509, 1997. Earlier version in FOCS'94. quant-ph/9508027. Google ScholarDigital Library
- H. U. Simon. General bounds on the number of examples needed for learning probabilistic concepts. Journal of Computer and System Sciences, 52(2):239--254, 1996. Earlier version in COLT'93. Google ScholarDigital Library
- D. Simon. On the power of quantum computation. SIAM Journal on Computing, 26(5):1474--1483, 1997. Earlier version in FOCS'94. Google ScholarDigital Library
- H. U. Simon. An almost optimal PAC algorithm. In Proceedings of the 28th Conference on Learning Theory (COLT), pages 1552--1563, 2015.Google Scholar
- M. Schuld, I. Sinayskiy, and F. Petruccione. An introduction to quantum machine learning. Contemporary Physics, 56(2):172--185, 2015. arXiv:1409.3097.Google ScholarCross Ref
- M. Talagrand. Sharper bounds for Gaussian and empirical processes. The Annals of Probability, pages 28--76, 1994. {Val84} L. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134--1142, 1984. Google ScholarDigital Library
- V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264--280, 1971. English translation of 1968 Russian paper in Dokl. Akad. Nauk. 181(4).Google ScholarCross Ref
- V. Vapnik and A. Chervonenkis. Theory of pattern recognition. Nauka, USSR, 1974. In Russian.Google Scholar
- K. A. Verbeurgt. Learning DNF under the uniform distribution in quasi-polynomial time. In Proceedings of the 3rd Annual Workshop on Computational Learning Theory (COLT'90), pages 314--326, 1990. Google ScholarDigital Library
- P. Wittek. Quantum Machine Learning: What Quantum Computing Means to Data Mining. Elsevier, 2014.Google Scholar
- N. Wiebe, A. Kapoor, and K. Svore. Quantum deep learning. Quantum Information and Computation, 16(7):541--587, 2016. arXiv:1412.3489.Google ScholarDigital Library
- N. Wiebe, A. Kapoor, and K. M. Svore. Quantum perceptron models, 2016. arXiv:1602.04799.Google Scholar
- R. de Wolf. A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing, 2008. ToC Library, Graduate Surveys 1.Google Scholar
- C. Zhang. An improved lower bound on query complexity for quantum PAC learning. Information Processing Letters, 111(1):40--45, 2010. Google ScholarDigital Library
Index Terms
- Guest Column: A Survey of Quantum Learning Theory
Index terms have been assigned to the content through auto-classification.
Recommendations
Guest Column: Quantum Finite Automata: From Theory to Practice
Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, ...
Guest column: the quantum PCP conjecture
The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computational complexity have tried to identify approaches and develop tools that ...
Guest Column: Adiabatic Quantum Computing Challenges
The paper presents a brief introduction to quantum computing with focus on the adiabatic model which is illustrated with the commercial D-Wave computer. We also include new theory and experimental work done on the D-Wave computer. Finally we discuss a ...
Comments