Machine learning is now widely used almost everywhere, primarily for forecasting. In the broadest sense, the machine learning objective may be summarized as an approximation problem, and the issues solved by various training methods can be reduced to finding the optimal value of an unknown function or restoring a function. At the moment, we have only experimental samples of quantum computers based on classical-quantum logic, when quantum gates are used instead of ordinary logic gates, and probabilistic quantum bits are used instead of deterministic bits. Namely, the probabilistic nature problems that provide for the determination of a certain optimal state from a large set of possible ones on which quantum computers can achieve “quantum supremacy” – an extraordinary (by many orders of magnitude) reduction in the time required to solve the task. The main idea of the work is to identify the possibility of achieving, if not quantum supremacy, then at least a quantum advantage when solving machine learning problems on a quantum computer.