Key questions for the quantum machine learner to ask themselves

Summary: A series of questions that we should ask ourselves when developing quantum algorithms for machine learning; what the definition of quantum ML is, what is the proper quantum analogue of QML algorithms is, how one should compare QML to traditional ML and what fundamental limitations emerge when trying to build QML protocols.

• Q1: definition of QML

  • For computer scientists, the aim of of QML is to reduce the complexity in terms of either samples (sample complexity) or the number of operations

  • For data scientists the goal for quantum computer is to provide a richer class of models for the data by incorporating quantum effects and optimizing a test loss function

  • For quantum input, it is difficult to compare the costs of quantum and classical machine learning problems

  • The wide range input models that can be considered in QML complicates the search for quantum advantages for machine learning tasks or finding new forms of machine learning that may not have clear classical analogues.

• Q2: classical analogues

  • The struggle is very much akin to understanding the classical limit of quantum mechanics. There are two main correspondences that often are used to understand the classical limit of quantum mechanics: the Ehrenfest and the Liouville correspondence

  • Check input model(how the data is represented and fed into a quantum algorithm). Classically, there are a number of such input models; database model, streaming model or online learning. Representations include bit, amplitude or variational encoding.

  • Check for the output problem, wherein the cost of extracting desired information from the solution dominates the cost of a quantum algorithm.

Recap: Random matrix theory

Important refs: 22, 32, 36, 43, 65