Cloning is as Hard as Learning for Stabilizer States

• URL: http://arxiv.org/abs/2604.15269v1
• Date: Thu, 16 Apr 2026 17:41:16 GMT
• Title: Cloning is as Hard as Learning for Stabilizer States
• Abstract summary: We show that for $n$-qubit stabilizer states, the optimal sample complexity of cloning is $(n)$.<n>Our results provide a more fine-grained perspective on No-Cloning theorems, opening up connections from foundations to quantum learning theory and quantum cryptography.
• Score: 2.3784921682219635
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $n$-qubit stabilizer states, we show that the optimal sample complexity of cloning is $Θ(n)$. 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.

Related papers

• Optimal copy complexity of quantum state cloning [0.16992697670497803]
  We show the optimal complexity for $d$-dimensional states of at least $1-varepsilon$.<n>We also show that high-fidelity tomography can be coherently converted into cloning with comparable error.
  arXiv  Detail & Related papers  (2026-08-25T12:29:10Z)
• Quantum Incremental Learning with Mixed State Prototypes [53.319426778720434]
  We introduce a novel quantum incremental learning framework based on trainable mixed-state prototypes.<n>Our model achieves high-dimensional feature concentration using a minimal number of qubits.
  arXiv  Detail & Related papers  (2026-08-11T04:22:42Z)
• Revisiting the Role of State Texture in Gate Identification and Fixed-Point Resource Theories [40.119993515374325]
  We revisit a protocol for identifying controlled-NOT gates versus single-qubit-only gates in quantum circuits.<n>We show that a more general fidelity-based formulation succeeds for nearly all laboratory bases.<n>We introduce a family of "fixed-point resource theories" that includes fixed-point instances of the theories of state texture, genuine coherence, purity, and athermality.
  arXiv  Detail & Related papers  (2026-02-26T00:22:58Z)
• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
  We study sequential decision making under distributional adversaries that can adaptively choose data-generating distributions from a fixed family $U$.<n>We provide a near complete characterization of families $U$ that admit learnability in terms of a notion known as generalized smoothness.<n>We show that the generalized smoothness also characterizes private learnability under distributional constraints.
  arXiv  Detail & Related papers  (2026-02-24T06:15:59Z)
• Learning at the Edge of Causality: Optimal Learning-Sample Complexity from No-Signaling Constraints [0.3277163122167433]
  We study what ultimately fixes the sample cost of quantum learning.<n>Standard quantum theory forbids such a unknown-state reflection.<n>No-signaling acts as a regulator of learnability.
  arXiv  Detail & Related papers  (2026-01-19T01:52:15Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• Bisimulation Learning [55.859538562698496]
  We compute finite bisimulations of state transition systems with large, possibly infinite state space. Our technique yields faster verification results than alternative state-of-the-art tools in practice.
  arXiv  Detail & Related papers  (2024-05-24T17:11:27Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.<n>We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Quantum state complexity meets many-body scars [0.0]
  Scar eigenstates in a many-body system refer to a small subset of non-thermal finite energy density eigenstates embedded into an otherwise thermal spectrum. We probe these small sets of special eigenstates starting from particular initial states by computing the spread complexity associated to time evolution of the PXP hamiltonian.
  arXiv  Detail & Related papers  (2023-05-16T18:10:46Z)
• Quantum Pseudoentanglement [4.3053817709507]
  Entanglement is a quantum resource, in some ways analogous to randomness in classical computation. We give a construction of pseudoentangled states with entanglement entropy arbitrarily close to $log n$ across every cut. We discuss applications of this result to Matrix Product State testing, entanglement distillation, and the complexity of the AdS/CFT correspondence.
  arXiv  Detail & Related papers  (2022-11-01T21:04:49Z)
• Chaos is a Ladder: A New Theoretical Understanding of Contrastive Learning via Augmentation Overlap [64.60460828425502]
  We propose a new guarantee on the downstream performance of contrastive learning. Our new theory hinges on the insight that the support of different intra-class samples will become more overlapped under aggressive data augmentations. We propose an unsupervised model selection metric ARC that aligns well with downstream accuracy.
  arXiv  Detail & Related papers  (2022-03-25T05:36:26Z)
• General stabilizer approach for constructing highly entangled graph states [0.0]
  Highly entangled multipartite states such as k-uniform (kUNI) and absolutely maximally entangled (AME) states serve as critical resources in quantum networking and other quantum information applications. Here, we substantially broaden the class of known k-UNI and AME states by introducing a method for explicitly constructing such states that combines classical error correcting codes and qudit graph states.
  arXiv  Detail & Related papers  (2021-11-15T19:06:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.