An infinite hierarchy of multi-copy quantum learning tasks

• URL: http://arxiv.org/abs/2510.08070v1
• Date: Thu, 09 Oct 2025 10:57:42 GMT
• Title: An infinite hierarchy of multi-copy quantum learning tasks
• Authors: Jan Nöller, Viet T. Tran, Mariami Gachechiladze, Richard Kueng,
• Abstract summary: Learning properties of quantum states from measurement data is a fundamental challenge in quantum information.<n>We show that for every prime c we construct explicit learning tasks of degree c, which are exponentially hard with (c - 1)-copy measurements but efficiently solvable with c-copy measurements.
• Score: 0.1909020214605419
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning properties of quantum states from measurement data is a fundamental challenge in quantum information. The sample complexity of such tasks depends crucially on the measurement primitive. While shadow tomography achieves sample-efficient learning by allowing entangling measurements across many copies, it requires prohibitively deep circuits. At the other extreme, two-copy measurements already yield exponential advantages over single-copy strategies in tasks such as Pauli tomography. In this work we show that such sharp separations extend far beyond the two-copy regime: for every prime c we construct explicit learning tasks of degree c, which are exponentially hard with (c - 1)-copy measurements but efficiently solvable with c-copy measurements. Our protocols are not only sample-efficient but also realizable with shallow circuits. Extending further, we show that such finite-degree tasks exist for all square-free integers c, pointing toward a general principle underlying their existence. Together, our results reveal an infinite hierarchy of multi-copy learning problems, uncovering new phase transitions in sample complexity and underscoring the role of reliable quantum memory as a key resource for exponential quantum advantage.

Related papers

• Exponential Advantage from One More Replica in Estimating Nonlinear Properties of Quantum States [16.185988658474635]
  We prove that estimation of $mathrmtr(rhok O)$ for a broad class of observables $O$ is exponentially hard for any protocol restricted to $(k-1)$-replica joint measurements.<n>Results establish, for the first time, an exponential separation between $(k-1)$- and $k$-replica protocols for any integer $k>2$.
  arXiv  Detail & Related papers  (2025-09-28T17:46:43Z)
• Exponential Separations between Quantum Learning with and without Purification [0.7908933308312488]
  In quantum learning tasks, quantum memory can offer exponential reductions in statistical complexity compared to any single-copy strategies.<n>We show that such exponential reductions can also be achieved by having access to the purification of the target mixed state.
  arXiv  Detail & Related papers  (2024-10-23T09:47:43Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Learning Properties of Quantum States Without the I.I.D. Assumption [7.537220883022466]
  We develop a framework for learning properties of quantum states beyond the assumption of independent and identically distributed (i.i.d.) input states. We use rigorous quantum information theory to prove our main results.
  arXiv  Detail & Related papers  (2024-01-30T11:45:38Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• Limitations of measure-first protocols in quantum machine learning [2.209921757303168]
  We study a natural supervised learning setting where quantum states constitute data points, and the labels stem from an unknown measurement. We show that there exist problems that can be efficiently learned by fully-quantum protocols but which require exponential resources for measure-first protocols. Our result underscores the role of quantum data processing in machine learning and highlights scenarios where quantum advantages appear.
  arXiv  Detail & Related papers  (2023-11-21T14:03:29Z)
• Multimodal deep representation learning for quantum cross-platform verification [60.01590250213637]
  Cross-platform verification, a critical undertaking in the realm of early-stage quantum computing, endeavors to characterize the similarity of two imperfect quantum devices executing identical algorithms. We introduce an innovative multimodal learning approach, recognizing that the formalism of data in this task embodies two distinct modalities. We devise a multimodal neural network to independently extract knowledge from these modalities, followed by a fusion operation to create a comprehensive data representation.
  arXiv  Detail & Related papers  (2023-11-07T04:35:03Z)
• Learning Quantum Processes with Quantum Statistical Queries [0.0]
  We initiate the study of learning quantum processes from quantum statistical queries.<n>We present an efficient average-case algorithm along with a nearly matching lower bound with respect to the number of observables to be predicted.<n>We apply our learning algorithm to attack an authentication protocol using Classical-Readout Quantum Physically Unclonable Functions.
  arXiv  Detail & Related papers  (2023-10-03T14:15:20Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Scalable approach to many-body localization via quantum data [69.3939291118954]
  Many-body localization is a notoriously difficult phenomenon from quantum many-body physics. We propose a flexible neural network based learning approach that circumvents any computationally expensive step. Our approach can be applied to large-scale quantum experiments to provide new insights into quantum many-body physics.
  arXiv  Detail & Related papers  (2022-02-17T19:00:09Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)

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.