News
View the latest news from departments within the Faculty of Science, Engineering and Medicine below.
Faculty of Science, Engineering and Medicine News Read more from Faculty of Science, Engineering and Medicine News
Computer Science News Read more from 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.