The complexity of quantum support vector machines

Finding practically relevant problems where quantum computation offers a speedup compared to the best known classical algorithms is one of the central challenges in the field. Quantifying a speedup requires a provable convergence rate of the quantum algorithms, which restricts us to studying algorithms that can be analyzed rigorously. The impressive recent progress on building quantum computers gives us a new possibility: We can use heuristic quantum algorithms that can be run on current devices to demonstrate the speedup empirically. This however requires a hardware friendly implementation, i.e., a moderate number of qubits and shallow circuits. In recent years, more and more evidence has been found supporting machine learning tasks as good candidates for demonstrating quantum advantage [1-4]. In particular, the so-called supervised learning setting, where in the simplest case the goal is to learn a binary classifier of classical data, received much attention. The reasons are manifold: (i) The algorithms only require classical access to data.