Private learning implies quantum stability

• URL: http://arxiv.org/abs/2102.07171v1
• Date: Sun, 14 Feb 2021 15:13:25 GMT
• Title: Private learning implies quantum stability
• Authors: Srinivasan Arunachalam, Yihui Quek, John Smolin
• Abstract summary: Learning an unknown $n$-qubit quantum state $rho$ is a fundamental challenge in quantum computing. We prove a sequence of (information-theoretic) implications from differentially-private PAC learning, to communication complexity, to online learning and then to quantum stability.
• Score: 5.435793655810987
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning an unknown $n$-qubit quantum state $\rho$ is a fundamental challenge in quantum computing. Information-theoretically, it is known that tomography requires exponential in $n$ many copies of $\rho$ to estimate it up to trace distance. Motivated by computational learning theory, Aaronson et al. introduced many (weaker) learning models: the PAC model of learning states (Proceedings of Royal Society A'07), shadow tomography (STOC'18) for learning "shadows" of a state, a model that also requires learners to be differentially private (STOC'19) and the online model of learning states (NeurIPS'18). In these models it was shown that an unknown state can be learned "approximately" using linear-in-$n$ many copies of rho. But is there any relationship between these models? In this paper we prove a sequence of (information-theoretic) implications from differentially-private PAC learning, to communication complexity, to online learning and then to quantum stability. Our main result generalizes the recent work of Bun, Livni and Moran (Journal of the ACM'21) who showed that finite Littlestone dimension (of Boolean-valued concept classes) implies PAC learnability in the (approximate) differentially private (DP) setting. We first consider their work in the real-valued setting and further extend their techniques to the setting of learning quantum states. Key to our results is our generic quantum online learner, Robust Standard Optimal Algorithm (RSOA), which is robust to adversarial imprecision. We then show information-theoretic implications between DP learning quantum states in the PAC model, learnability of quantum states in the one-way communication model, online learning of quantum states, quantum stability (which is our conceptual contribution), various combinatorial parameters and give further applications to gentle shadow tomography and noisy quantum state learning.

Related papers

• Computational Complexity of Learning Efficiently Generatable Pure States [11.180439223883962]
  We study the computational complexity of quantum state learning. We show that if unknown quantum states are promised to be pure states and efficiently generateable, then there exists a quantum time algorithm. We also observe the connection between the hardness of learning quantum states and quantum cryptography.
  arXiv  Detail & Related papers  (2024-10-06T06:25:36Z)
• 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)
• Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
  The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process. We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable. Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs. We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
  arXiv  Detail & Related papers  (2024-05-12T09:05:13Z)
• Exponential learning advantages with conjugate states and minimal quantum memory [0.0]
  We investigate a new learning resource which could be available to quantum computers in the future. For a certain shadow tomography task, we find that measurements on only copies of $rho otimes rhoast$ can be exponentially more powerful than measurements on $rhootimes K$. We believe the advantage may find applications in improving quantum simulation, learning from quantum sensors, and uncovering new physical phenomena.
  arXiv  Detail & Related papers  (2024-03-06T05:04:45Z)
• Provable learning of quantum states with graphical models [4.004283689898333]
  We show that certain quantum states can be learned with a sample complexity textitexponentially better than naive tomography. Our results allow certain quantum states to be learned with a sample complexity textitexponentially better than naive tomography.
  arXiv  Detail & Related papers  (2023-09-17T10:36:24Z)
• QKSAN: A Quantum Kernel Self-Attention Network [53.96779043113156]
  A Quantum Kernel Self-Attention Mechanism (QKSAM) is introduced to combine the data representation merit of Quantum Kernel Methods (QKM) with the efficient information extraction capability of SAM. A Quantum Kernel Self-Attention Network (QKSAN) framework is proposed based on QKSAM, which ingeniously incorporates the Deferred Measurement Principle (DMP) and conditional measurement techniques. Four QKSAN sub-models are deployed on PennyLane and IBM Qiskit platforms to perform binary classification on MNIST and Fashion MNIST.
  arXiv  Detail & Related papers  (2023-08-25T15:08:19Z)
• ShadowNet for Data-Centric Quantum System Learning [188.683909185536]
  We propose a data-centric learning paradigm combining the strength of neural-network protocols and classical shadows. Capitalizing on the generalization power of neural networks, this paradigm can be trained offline and excel at predicting previously unseen systems. We present the instantiation of our paradigm in quantum state tomography and direct fidelity estimation tasks and conduct numerical analysis up to 60 qubits.
  arXiv  Detail & Related papers  (2023-08-22T09:11:53Z)
• A didactic approach to quantum machine learning with a single qubit [68.8204255655161]
  We focus on the case of learning with a single qubit, using data re-uploading techniques. We implement the different proposed formulations in toy and real-world datasets using the qiskit quantum computing SDK.
  arXiv  Detail & Related papers  (2022-11-23T18:25:32Z)
• 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)
• Exploring Quantum Perceptron and Quantum Neural Network structures with a teacher-student scheme [0.0]
  Near-term quantum devices can be used to build quantum machine learning models, such as quantum kernel methods and quantum neural networks (QNN) to perform classification tasks. The aim of this work is to systematically compare different QNN architectures and to evaluate their relative expressive power with a teacher-student scheme. We focus particularly on a quantum perceptron model inspired by the recent work of Tacchino et. al. citeTacchino1 and compare it to the data re-uploading scheme that was originally introduced by P'erez-Salinas et. al. cite
  arXiv  Detail & Related papers  (2021-05-04T13:13:52Z)
• Quantum statistical query learning [6.434862450258459]
  We propose a learning model called the quantum statistical learning QSQ model. Our model can be seen as a restriction of the quantum PAC learning model. We show that learnability in QSQ model implies learnability in quantum private PAC model.
  arXiv  Detail & Related papers  (2020-02-19T15:36: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.