Quantum computers have the potential to improve existing machine learning models based on classical computers.
A series of works require that an exponential amount of data stored in quantum random access memory [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}.
Due to the quantum data structure, one can obtain exponential speed-up for certain machine learning tasks.
However, the act of storing the exponential amount of data will take exponential time. Furthermore, if we assume a similar data structure for classical machines, then the exponential advantage may not be available [9]}, [10]}, [11]}, [12]}, [13]}.
Another recent line of works focuses on using quantum computers to represent a family of classically intractable functions [14]}, [15]}, [16]}, [17]}. However, computational power provided by data in a machine learning task can also make a classical ML model stronger [18]} and may challenge some of these proposals in practice.
