QML · Quantum Computing
A quantum machine learning advantage is tied to the difficulty of factoring RSA
A preprint proves that a quantum machine learning task is hard for a classical computer if factoring RSA is hard. The hard instances are artificial.
Key points
- Hashimoto and Kawachi prove that learning two versions of a QML task proposed in 2025 is hard for a classical computer if factoring RSA is.
- The hard instances are built with circuits based on Shor's algorithm, not with Hamiltonians of physical systems.
- It is a theoretical preprint, not peer reviewed: it does not demonstrate an advantage with real data.
On 1 October, Sota Hashimoto and Akinori Kawachi, of Mie University (Japan), posted on arXiv a preprint, not yet peer reviewed, which proves that a quantum machine learning (QML) problem is hard for a classical computer, on one condition: that factoring randomly chosen RSA numbers is hard too. It is a rigorous proof of an advantage that until now had only been argued for.
The starting problem
In 2025, Morohoshi, Nakayama, Manabe and Mitarai proposed a task intended to be of practical interest. The Hamiltonian of a quantum system, which describes its energy, is known, but the relationship between that Hamiltonian and what is measured in the experiment is not. From examples, the aim is to learn to predict that measurement. They gave an efficient quantum algorithm for doing so, tested it on a superconducting processor with up to 40 qubits and argued that it would be hard for a classical computer, but left that hardness unproven.
What they prove
Hashimoto and Kawachi construct two specific versions of the task, one of them with the same function used in the 40-qubit experiment, and prove that a classical algorithm that learnt them with small error would make it possible to factor random RSA numbers in polynomial time. As that is assumed to be impossible for a classical computer, learning the task would be impossible too. The hardness holds even if the algorithm knows in advance the function it has to learn.
The trick lies in the Hamiltonians they choose. They build them from a circuit based on Shor’s algorithm, so that each example ultimately answers the question of whether a given bit of the smaller factor of an RSA number is 0 or 1. A quantum computer can run that circuit; a classical one that learnt to predict the answers would have learnt to factor. It is the strategy Kearns and Valiant used in 1994 to prove limits of classical learning from cryptography.
Note · what this work does not say
The hard instances are artificial: the authors themselves make clear that their Hamiltonians are projectors defined by quantum circuits, not local Hamiltonians like those of physical systems. The work does not show that the 40-qubit experiment, or chemistry or materials problems, are hard for a classical computer. It is a theoretical result, with no experiment of its own.
What changes for decision-makers
Little, for now. It is a rigorous separation between quantum and classical learning but, like earlier ones that the authors cite, the advantage comes from hiding a cryptographic problem inside the learning task: it is supplied by Shor’s algorithm, not by learning from data on a real physical system. The authors themselves point out that the argument works with any problem of that kind, not only factoring. The question that matters to anyone investing in QML, whether there is a demonstrable advantage with real data, remains unanswered.