Smooth input preparation for quantum and quantum-inspired machine learning

Quantum Machine Intelligence, vol. 3

Abstract

Abstract Machine learning has recently emerged as a fruitful area for finding potential quantum computational advantage. Many of the quantum-enhanced machine learning algorithms critically hinge upon the ability to efficiently produce states proportional to high-dimensional data points stored in a quantum accessible memory. Even given query access to exponentially many entries stored in a database, the construction of which is considered a one-off overhead, it has been argued that the cost of preparing such amplitude-encoded states may offset any exponential quantum advantage. Here we prove using smoothed analysis that if the data analysis algorithm is robust against small entry-wise input perturbation, state preparation can always be achieved with constant queries. This criterion is typically satisfied in realistic machine learning applications, where input data is subjective to moderate noise. Our results are equally applicable to the recent seminal progress in quantum-inspired algorithms, where specially constructed databases suffice for polylogarithmic classical algorithm in low-rank cases. The consequence of our finding is that for the purpose of practical machine learning, polylogarithmic processing time is possible under a general and flexible input model with quantum algorithms or quantum-inspired classical algorithms in the low-rank cases.

Authors 5

1. Zhikuan Zhao corresponding

   Centre for Quantum Technologies · Singapore University of Technology and Design · National University of Singapore · ETH Zurich

   Affiliation as printed

   Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore, 117543, Singapore

   Department of Computer Science, ETH Zurich, Universitatstrasse 6, 8092, Zurich, Switzerland

   Singapore University of Technology and Design, 8 Somapah Road, Singapore, 487372, Singapore

2. Jack Fitzsimons

   Centre for Quantum Technologies · Singapore University of Technology and Design · National University of Singapore · University of Oxford

   Affiliation as printed

   Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore, 117543, Singapore

   Department of Engineering Science, University of Oxford, Oxford, OX1 3PJ, UK

   Horizon Quantum Computing, 79 Ayer Rajah Crescent, Singapore, 139955, Singapore

   Singapore University of Technology and Design, 8 Somapah Road, Singapore, 487372, Singapore

3. Patrick Rebentrost

   Centre for Quantum Technologies · National University of Singapore

   Affiliation as printed

   Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore, 117543, Singapore

4. Vedran Dunjko Aachen

   Leiden University · Max Planck Institute of Quantum Optics

   Affiliation as printed

   LIACS, Leiden University, Niels Bohrweg 1, 2333 CA, Leiden, The Netherlands

   Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Str. 1, 85748, Garching, Germany

5. Joseph F. Fitzsimons

   Centre for Quantum Technologies · Singapore University of Technology and Design · National University of Singapore · University of Oxford

   Affiliation as printed

   Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore, 117543, Singapore

   Department of Engineering Science, University of Oxford, Oxford, OX1 3PJ, UK

   Horizon Quantum Computing, 79 Ayer Rajah Crescent, Singapore, 139955, Singapore

   Singapore University of Technology and Design, 8 Somapah Road, Singapore, 487372, Singapore