Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood

• URL: http://arxiv.org/abs/2505.22743v2
• Date: Tue, 17 Jun 2025 05:24:14 GMT
• Title: Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood
• Authors: Sitan Chen, Weiyuan Gong, Jonas Haferkamp, Yihui Quek,
• Abstract summary: In this work, we establish a general connection between state designs and low-degree hardness.<n>We use this to obtain the first information-computation gaps for learning Gibbs states of random, sparse, non-local Hamiltonians.<n>We also obtain a low-degree hardness result for quantum error mitigation against strategies with single-qubit measurements.
• Score: 9.179660060516916
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In a variety of physically relevant settings for learning from quantum data, designing protocols that can computationally efficiently extract information remains largely an art, and there are important cases where we believe this to be impossible, that is, where there is an information-computation gap. While there is a large array of tools in the classical literature for giving evidence for average-case hardness of statistical inference problems, the corresponding tools in the quantum literature are far more limited. One such framework in the classical literature, the low-degree method, makes predictions about hardness of inference problems based on the failure of estimators given by low-degree polynomials. In this work, we extend this framework to the quantum setting. We establish a general connection between state designs and low-degree hardness. We use this to obtain the first information-computation gaps for learning Gibbs states of random, sparse, non-local Hamiltonians. We also use it to prove hardness for learning random shallow quantum circuit states in a challenging model where states can be measured in adaptively chosen bases. To our knowledge, the ability to model adaptivity within the low-degree framework was open even in classical settings. In addition, we also obtain a low-degree hardness result for quantum error mitigation against strategies with single-qubit measurements. We define a new quantum generalization of the planted biclique problem and identify the threshold at which this problem becomes computationally hard for protocols that perform local measurements. Interestingly, the complexity landscape for this problem shifts when going from local measurements to more entangled single-copy measurements. We show average-case hardness for the "standard" variant of Learning Stabilizers with Noise and for agnostically learning product states.

Related papers

• Few measurement shots challenge generalization in learning to classify entanglement [0.0]
  This paper focuses on hybrid quantum learning techniques where classical machine-learning methods are paired with quantum algorithms. We show that, in some settings, the uncertainty coming from a few measurement shots can be the dominant source of errors. We introduce an estimator based on classical shadows that performs better in the big data, few copy regime.
  arXiv  Detail & Related papers  (2024-11-10T21:20:21Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  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)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Statistical Complexity of Quantum Learning [32.48879688084909]
  This article reviews the complexity of quantum learning using information-theoretic techniques. We focus on data complexity, copy complexity, and model complexity. We highlight the differences between quantum and classical learning by addressing both supervised and unsupervised learning.
  arXiv  Detail & Related papers  (2023-09-20T20:04:05Z)
• Ansatz-Agnostic Exponential Resource Saving in Variational Quantum Algorithms Using Shallow Shadows [5.618657159109373]
  Variational Quantum Algorithms (VQA) have been identified as a promising candidate for the demonstration of near-term quantum advantage. We present a protocol based on shallow shadows that achieves similar levels of savings for almost any shallow ansatz studied in the literature. We show that two important applications in quantum information for which VQAs can be a powerful option, namely variational quantum state preparation and variational quantum circuit synthesis.
  arXiv  Detail & Related papers  (2023-09-09T11:00:39Z)
• Learning the tensor network model of a quantum state using a few single-qubit measurements [0.0]
  The constantly increasing dimensionality of artificial quantum systems demands highly efficient methods for their characterization and benchmarking. Here we present a constructive and numerically efficient protocol which learns a tensor network model of an unknown quantum system.
  arXiv  Detail & Related papers  (2023-09-01T11:11:52Z)
• Classical Verification of Quantum Learning [42.362388367152256]
  We develop a framework for classical verification of quantum learning. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents.
  arXiv  Detail & Related papers  (2023-06-08T00:31:27Z)
• 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)
• Measuring NISQ Gate-Based Qubit Stability Using a 1+1 Field Theory and Cycle Benchmarking [50.8020641352841]
  We study coherent errors on a quantum hardware platform using a transverse field Ising model Hamiltonian as a sample user application. We identify inter-day and intra-day qubit calibration drift and the impacts of quantum circuit placement on groups of qubits in different physical locations on the processor. This paper also discusses how these measurements can provide a better understanding of these types of errors and how they may improve efforts to validate the accuracy of quantum computations.
  arXiv  Detail & Related papers  (2022-01-08T23:12:55Z)
• Hardware-Efficient, Fault-Tolerant Quantum Computation with Rydberg Atoms [55.41644538483948]
  We provide the first complete characterization of sources of error in a neutral-atom quantum computer. We develop a novel and distinctly efficient method to address the most important errors associated with the decay of atomic qubits to states outside of the computational subspace. Our protocols can be implemented in the near-term using state-of-the-art neutral atom platforms with qubits encoded in both alkali and alkaline-earth atoms.
  arXiv  Detail & Related papers  (2021-05-27T23:29:53Z)
• Statistical Limits of Supervised Quantum Learning [90.0289160657379]
  We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning cannot achieve polylogarithmic runtimes in the input dimension. We conclude that, when no further assumptions on the problem are made, quantum machine learning algorithms for supervised learning can have at most speedups over efficient classical algorithms.
  arXiv  Detail & Related papers  (2020-01-28T17:35:32Z)

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.