A note on state preparation for quantum machine learning

The intersection between the fields of machine learning and quantum information processing is proving to be a fruitful field for the discovery of new quantum algorithms, which potentially offer an exponential speedup over their classical counterparts. However, many such algorithms require the ability to produce states proportional to vectors stored in quantum memory. Even given access to quantum databases which store exponentially long vectors, 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 argue that specifically in the context of machine learning applications it suffices to prepare a state close to the ideal state only in the -norm, and that this can be achieved with only a constant number of memory queries. In recent years, machine learning has emerged as a rich area for showing quantum speedups [1-6], based in part on the seminal quantum algorithm of Harrow, Hassidim and Lloyd [7] for solving systems of linear equations.