Cloning is as Hard as Learning for Stabilizer States
Nikhil Bansal, Matthias C. Caro, Gaurav Mahajan
Abstract
The impossibility of simultaneously cloning non-orthogonal states lies at the foundations of quantum theory. Even when allowing for approximation errors, cloning an arbitrary unknown pure state requires as many initial copies as needed to fully learn the state. Rather than arbitrary unknown states, modern quantum learning theory often considers structured classes of states and exploits such structure to develop learning algorithms that outperform general-state tomography. This raises the question: How do the sample complexities of learning and cloning relate for such structured classes? We answer this question for an important class of states. Namely, for -qubit stabilizer states, we show that the optimal sample complexity of cloning is . Thus, also for this structured class of states, cloning is as hard as learning. To prove these results, we use representation-theoretic tools in the recently proposed Abelian State Hidden Subgroup framework and a new structured version of the recently introduced random purification channel to relate stabilizer state cloning to a variant of the sample amplification problem for probability distributions that was recently introduced in classical learning theory. This allows us to obtain our cloning lower bounds by proving new sample amplification lower bounds for classes of distributions with an underlying linear structure. Our results provide a more fine-grained perspective on No-Cloning theorems, opening up connections from foundations to quantum learning theory and quantum cryptography.
AI Impact Assessments
(3 models)Scientific Impact Assessment
Core Contribution
This paper establishes that approximate cloning of n-qubit stabilizer states requires Θ(n) copies — matching the sample complexity of learning stabilizer states. This is the first "approximate No-Cloning theorem" for a practically relevant structured class of quantum states, moving beyond the classical result that cloning arbitrary unknown pure states is as hard as full state tomography.
The paper makes two intertwined contributions: (1) on the classical side, it shows that sample amplification for structured distribution classes (particularly parity functions and linear subspaces of Boolean functions) is as hard as learning; (2) on the quantum side, it leverages this classical result through a novel technical pipeline to prove cloning lower bounds for stabilizer states. The connection between sample amplification and quantum cloning is the paper's conceptual centerpiece.
Methodological Rigor
The technical approach is sound and multi-layered. The proof pipeline involves several carefully constructed components:
1. General sample amplification lower bounds via a distinguisher-based argument using the teaching dimension and a "consistent learner" distinguisher. The key insight — that seeing n-1 samples versus n samples for parities creates a sharp information-theoretic gap due to linear independence — is simple but powerful. The constant lower bound of 0.14 for parity amplification is clean and relies on the well-known constant lower bound on the probability that n random binary vectors are linearly independent.
2. Optimality of character POVMs for Abelian StateHSPs with non-isomorphic irreps (Theorem 8). This uses Wright's Proposition 2 about block-diagonal states and extends it to multi-copy measurements through a tensor product argument. The proof is concise and correct.
3. Structured random purification channel (Theorem 9), which maps i.i.d. copies of mixed phaseless-stabilizer StateHSP instances to i.i.d. copies of random purifications that are themselves pure stabilizer states. This is the key bridge from mixed-state cloning lower bounds to pure-state cloning lower bounds. The authors also show this can be derived as a special case of the Walter-Witteveen general symmetry framework.
4. Lifting from mixed to pure via showing that g-purifications of the mixed states σ_L are genuinely (4n)-qubit stabilizer states (Lemma 12), proved by explicitly constructing 4n independent commuting stabilizer generators.
The constant factor of 4 in the final result (cloning requires ⌊n/4⌋ copies) is an artifact of the proof technique — going through 2n-qubit mixed states that purify to 4n-qubit stabilizer states. While this doesn't affect the asymptotic Θ(n) result, it leaves room for tightening.
Potential Impact
Quantum foundations and cryptography: The result strengthens our understanding of No-Cloning theorems in a fine-grained, complexity-theoretic sense. The connection to quantum money and unclonable cryptographic primitives is natural — stabilizer states are central to many quantum protocols, and knowing that cloning them is information-theoretically hard (even approximately) has direct implications.
Quantum learning theory: The paper opens a new research direction — studying the cloning-versus-learning question for structured state classes. The framework (Definition 2) and the connection to sample amplification provide a template for future work on other state classes (matrix product states, hypergraph states, output states of shallow circuits).
Classical learning theory: The structured sample amplification framework and the coding-theoretic connections (Theorem 7) are independently interesting. The observation that sample amplification hardness relates to erasure-correction properties of dual codes could stimulate work at the intersection of learning theory and coding theory.
Representation theory applications: The Abelian StateHSP framework, combined with optimality of character POVMs, provides reusable tools for other quantum information problems.
Timeliness & Relevance
The paper is highly timely. It connects several active research threads: the recently proposed Abelian StateHSP framework (Bouland-Giurgică-Tiron-Wright 2025, Hinsche-Eisert-Carrasco 2025), the random purification channel (Tang-Wright-Zhandry 2025), sample amplification (Axelrod et al. 2020/2024), and the growing interest in computational vs. information-theoretic aspects of quantum cloning (Fefferman et al. 2025, Bostanci-Nehoran-Zhandry 2025). The paper sits at a productive nexus.
Strengths
Limitations
Overall Assessment
This is a technically strong paper that establishes an important conceptual connection and proves clean results at the intersection of quantum foundations, learning theory, and cryptography. The main theorem — that stabilizer state cloning is as hard as learning — is natural, well-motivated, and proved through an innovative combination of tools. The framework has clear potential for extensions.
Generated Apr 17, 2026
Comparison History (39)
Paper 2 establishes a fundamental connection between quantum cloning and learning for stabilizer states, proving tight Θ(n) sample complexity bounds. It bridges quantum foundations, learning theory, and cryptography using novel representation-theoretic techniques. Its breadth of impact across multiple fields (quantum information theory, learning theory, cryptography), conceptual novelty in connecting cloning to learning, and foundational nature give it higher impact potential. Paper 1, while practically useful for superconducting qubit engineering, addresses a more incremental hardware design improvement with narrower scope.
Paper 1 demonstrates an exponential quantum space advantage for a practically relevant problem (Shannon entropy estimation) with direct real-world applications in data streams and networking. While Paper 2 offers significant theoretical insights into quantum foundations and learning theory, the exponential separation and near-term applicability presented in Paper 1 represent a more substantial breakthrough with broader potential impact across theoretical computer science and applied fields.
Paper 2 addresses a fundamental question connecting quantum no-cloning theorems with quantum learning theory, establishing tight bounds (Θ(n)) for stabilizer state cloning. It bridges foundations of quantum mechanics, learning theory, and cryptography, using novel representation-theoretic techniques. Its conceptual contribution—showing cloning equals learning complexity for structured state classes—has broad theoretical implications across multiple fields. Paper 1, while practically useful for quantum computing resource optimization, addresses a more specialized algorithmic problem with narrower impact scope.
Paper 1 establishes a fundamental connection between quantum cloning and learning for stabilizer states, proving tight Θ(n) sample complexity bounds. It bridges quantum foundations, learning theory, and cryptography using novel representation-theoretic techniques and introduces connections to classical sample amplification. The breadth of impact across multiple fields (quantum information foundations, computational learning theory, cryptography), the resolution of a natural open question, and the development of new technical tools give it higher potential impact compared to Paper 2, which addresses a more specialized question about randomized measurement efficiency for entanglement certification in bipartite/tripartite systems.
Paper 2 establishes a fundamental limit connecting quantum cloning and learning for stabilizer states, a cornerstone of quantum computing and error correction. This theoretical breakthrough bridges quantum foundations, learning theory, and cryptography, promising broad impact across the rapidly growing field of quantum information science. While Paper 1 offers an innovative methodology for many-body physics, Paper 2's results have wider and more foundational implications for quantum technologies and theory.
Paper 1 addresses a highly relevant bottleneck in near-term quantum computing by incorporating realistic energy constraints into quantum error mitigation. Its dual contribution of establishing fundamental physical limits and providing actionable, energy-efficient purification protocols gives it significant potential for immediate real-world application in developing scalable quantum devices. While Paper 2 offers profound theoretical insights into quantum learning and cryptography, Paper 1's direct impact on the practical viability of quantum computing systems edges it out in overall scientific impact.
Paper 2 addresses fundamental limits in quantum information theory, bridging quantum cloning, learning theory, and cryptography. Establishing the sample complexity of cloning stabilizer states has broad implications across quantum computing and foundational physics, giving it wider scientific impact compared to the more specialized methodological advances in perturbative quantum dynamics presented in Paper 1.
Paper 2 has higher estimated impact: it delivers a tight Θ(n) characterization linking cloning and learning for stabilizer states, bridging quantum foundations, learning theory, and cryptography with rigorous lower-bound techniques (representation theory, Hidden Subgroup framework, sample amplification). The result is broadly relevant to quantum information theory and security assumptions. Paper 1 is novel and useful for simulation (tunable entanglement random states via MPS), but its impact is more specialized to many-body numerics and state-generation benchmarks, whereas Paper 2’s conceptual and technical connections are likely to influence multiple subfields.
Paper 2 establishes fundamental theoretical bounds connecting quantum learning theory, the no-cloning theorem, and cryptography for stabilizer states. Such foundational discoveries generally yield broader, longer-lasting impact across multiple subfields of quantum information science compared to Paper 1, which offers a more specific, albeit practically useful, variational circuit architecture for quantum metrology.
Paper 2 has higher likely scientific impact: it resolves a fundamental question connecting cloning and learning sample complexities for stabilizer states with tight Θ(n) bounds, using novel representation-theoretic techniques and linking to sample amplification in classical learning theory. This is methodologically rigorous and broadly relevant across quantum foundations, quantum learning theory, and cryptography, making it timely for theory and applications in quantum information. Paper 1 is useful and NISQ-motivated, but its impact is narrower (a specific walk variant and a key-generation scheme) and more incremental relative to existing quantum-walk cryptographic proposals.
Paper 2 likely has higher scientific impact: it delivers a clean, broadly relevant theoretical result (Θ(n) sample complexity) connecting cloning, learning, and no-cloning for stabilizer states, with rigorous lower-bound techniques and new links between quantum information, quantum learning theory, and cryptography. Its methods (representation theory, hidden subgroup framework, random purification channel, sample amplification lower bounds) appear broadly reusable and timely given current interest in quantum learning limits. Paper 1 is interesting experimentally but is narrow in scope (small n=4, specific DAGI metric) and its generality and methodological maturity are less established.
Paper 2 likely has higher impact due to broader applicability and timeliness: learning invariant/decoherence-free structures in open quantum dynamics directly targets noisy, realistic quantum platforms and supports tasks in characterization, control, and error mitigation across quantum computing, sensing, and quantum optics. The methodology (MLE over multi-time sequences with *-algebraic constraints and discrete structural hypotheses) is conceptually novel and practically oriented, with demonstrations including a waveguide QED setting. Paper 1 is rigorous and foundational, but focused on stabilizer states; its impact is more specialized despite strong theoretical novelty.
Paper 1 addresses fundamental concepts in quantum mechanics and quantum computing, specifically bridging the No-Cloning theorem with quantum learning theory and cryptography. Its proof that cloning stabilizer states is as hard as learning them provides profound theoretical insights with broad applications across quantum information sciences. In contrast, Paper 2 focuses on a specific method for generating cat-like states in a specific platform, which, while valuable for quantum optics and state generation, has a narrower scope and more specialized impact.
Paper 1 addresses a fundamental question connecting quantum cloning, learning theory, and cryptography, establishing tight bounds (Θ(n)) for stabilizer state cloning and proving it matches learning complexity. It introduces novel representation-theoretic techniques and bridges quantum foundations with modern learning theory. Paper 2 analyzes coherence dynamics in the HHL algorithm using specific coherence measures, which is more incremental and narrower in scope. Paper 1's results have broader implications across quantum information, cryptography, and learning theory, with stronger methodological novelty.
Paper 1 likely has higher impact: it delivers a sharp, quantitative Θ(n) sample-complexity characterization linking cloning and learning for stabilizer states, using novel representation-theoretic machinery and connections to classical sample amplification. The result is broadly relevant to quantum learning theory, cryptography, and foundations, with clear methodological rigor and potential downstream use in limits for quantum protocols. Paper 2 is timely and conceptually interesting for indefinite causal order, but its main contributions are largely definitional/structural (no universal additive relation; proposing “causal coherence”), with likely narrower immediate application and fewer concrete quantitative constraints.
Paper 1 likely has higher impact due to a broadly applicable methodological advance: a tensor-network framework enabling large-deviation analysis and access to conditioned states in monitored many-body quantum systems. This directly addresses a timely, active area (measurement-induced dynamics/trajectory phase transitions) and can be adopted across condensed matter, quantum information, and open-systems theory, with potential computational/experimental relevance. Paper 2 is conceptually strong and rigorous, linking cloning to learning for stabilizer states, but its main result is specialized to a structured class; impact is more focused within quantum learning/foundations/cryptography.
Paper 1 establishes a fundamental result connecting quantum cloning and learning complexity for stabilizer states, bridging quantum foundations, learning theory, and cryptography. It introduces novel representation-theoretic techniques and proves tight bounds (Θ(n)), opening new research directions across multiple subfields. Paper 2 presents a useful engineering advance for quantum state transfer but is more incremental, optimizing control parameters within an established framework. Paper 1's breadth of theoretical impact across quantum information foundations, learning theory, and cryptography gives it significantly higher potential scientific impact.
Paper 1 offers a deeper conceptual advance by tightly characterizing cloning vs. learning sample complexity for stabilizer states (Θ(n)) and introducing new links between no-cloning, quantum learning theory, and distribution sample amplification via representation-theoretic techniques. This is likely to influence multiple subfields (foundations, learning theory, cryptography) and provides rigorous lower bounds with broad theoretical relevance. Paper 2 is timely and practically motivated for photonic state preparation, but its impact is more application-narrow and dependent on experimental feasibility and incremental success-probability improvements.
Paper 1 offers a precise, nontrivial characterization (Θ(n)) of stabilizer-state cloning sample complexity and forges new links between no-cloning, quantum learning theory, representation theory, and classical sample amplification. The results are broadly relevant (foundations, quantum cryptography, learning theory) and methodologically rigorous with clear quantitative guarantees. Paper 2 is conceptually interesting but appears more model-dependent (toy model) and less quantitatively definitive; similar decoherence-based justifications of semiclassical dynamics are an active area, making novelty and immediate cross-field impact less clear from the abstract.
Paper 2 addresses a fundamental theoretical question in quantum mechanics by proving that cloning stabilizer states is as hard as learning them. Its rigorous mathematical approach bridges quantum foundations, learning theory, and cryptography, promising broad and foundational impact. In contrast, Paper 1 describes an open-source implementation of an existing equation for computational chemistry. While practically useful for electronic structure simulations, it represents an engineering and computational advance rather than a fundamental scientific breakthrough, giving Paper 2 a higher potential for deep scientific impact.