Theory and Foundations News
Archive news content can be found here.
Cloning vs Learning in Quantum Computing
In a recent work, Warwick DCS researchers Nikhil Bansal and Matthias C. Caro, together with Gaurav Mahajan (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, as shown by R.F. Werner in 1998. 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 sample amplificationLink opens in a new window, 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 QCTiP Link opens in a new windowin April 2026, and it will be presented at COLT in June/July 2026 and at TQC in September 2026.
Information Asymmetry and Cryptography
In a recent work, visiting undergraduate student Yahel Manor and Warwick DCS researchers Jinqiao Hu and Igor Oliveira addressed a fundamental question relevant to the security of cryptographic protocols.
The symmetry of information principle says that the amount of information that a sequence x of bits reveals about another sequence y is essentially the same in either direction. This is known to hold in an idealised world where computations can take an arbitrarily long time, as demonstrated by A. Kolmogorov and L. Levin in the 1970s. In contrast, modern cryptography is built around deliberate asymmetry—for example, functions of the form y = f(x) that are easy to compute but hard to invert (one-way functions).
The new work shows that, once one moves from the idealised setting of time-unbounded computations to the more realistic world of efficient, randomised computations (algorithms that must run quickly and may use randomness), this symmetry can fail in a strong and unconditional way. In other words, computational constraints can yield information asymmetry. In practical terms, this supports the intuition that information may not be extracted efficiently: knowing y = f(x) may not make x efficiently recoverable to the extent that an (ineffective) symmetry principle would suggest, even when x and y are closely related.
Earlier work formally tied an average-case form of this symmetry failure to the existence of one-way functions, the central primitive in cryptography. By proving new failures of symmetry of information, the authors provide concrete progress towards the computational asymmetry that underpins encryption, digital signatures, and many other cryptographic protocols.
This work will be presented at the 58th Annual ACM Symposium on Theory of Computing (STOC) in June 2026 in Salt Lake City, Utah, USA.
Failure of Symmetry of Information for Randomised Computations
Jinqiao Hu (University of Warwick); Yahel Manor (University of Haifa); Igor C. Oliveira (University of Warwick)
The paper describing this research is available here.
Jinqiao Hu, PhD student in the Department of Computer Science at the University of Warwick, and co-author of the new result.
Martin Costa successfully defends his PhD thesis
Many congratulations to Martin Costa for passing his PhD viva, with Prof Long Tran-Thanh (Warwick) and Dr Christian Konrad (Bristol) as examiners. Martin has worked on two different fundamental topics in algorithms - clustering and edge coloring. His work on clustering led to a Google PhD fellowship, and his work on edge coloring (the topic of his thesis) led to a best paper award at STOC. During his PhD spanning 3 years, Martin published 7 papers in STOC/FOCS/SODA, 2 papers in ICML/NeurIPS, and 1 paper in ICALP. We wish him all the very best for the next stage of his career.