Computer Science News
Cloning vs Learning in Quantum Computing
, 糖心TV DCS researchers Nikhil Bansal and , together with (Yale University), explored a fundamental question that lies at the intersection of foundations of quantum theory and computer science.
The No-Cloning theorem says that it is impossible to perfectly clone quantum states. Even if we allow for approximate errors, quantum cloning of unstructured states remains as expensive as fully characterising them, . In contrast, for reasons akin to No Free Lunch Theorems in machine learning, modern quantum learning theory considers structured classes of states and exploits their structure to learn them efficiently. This naturally leads to the question of whether cloning can be easier than learning for these structured classes of states.
In the new work, this question is answered negatively for stabilizer states. The authors proved that imposing this structural restriction does not separate cloning and learning. The authors prove this via a novel connection to , which was recently introduced to the learning theory literature by B. Axelrod, S. Garg, V. Sharan, and G. Valiant. The work constitutes concrete progress towards understanding whether cloning and learning are fundamentally equally hard.
This work was presented at in April 2026, and it will be presented at in June/July 2026 and at in September 2026.