Optimal lower bounds for Quantum Learning via Information Theory
- URL: http://arxiv.org/abs/2301.02227v3
- Date: Tue, 27 Feb 2024 23:20:19 GMT
- Title: Optimal lower bounds for Quantum Learning via Information Theory
- Authors: Shima Bab Hadiashar, Ashwin Nayak, Pulkit Sinha
- Abstract summary: We derive optimal lower bounds for quantum sample complexity in both the PAC and models via an information-theoretic approach.
We then turn to a quantum analogue of the Coupon Collector problem, a classic problem from probability theory.
All the aspects of the Quantum Coupon Collector problem we study rest on properties of the spectrum of the associated Gram matrix.
- Score: 3.093890460224435
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Although a concept class may be learnt more efficiently using quantum samples
as compared with classical samples in certain scenarios, Arunachalam and de
Wolf (JMLR, 2018) proved that quantum learners are asymptotically no more
efficient than classical ones in the quantum PAC and Agnostic learning models.
They established lower bounds on sample complexity via quantum state
identification and Fourier analysis. In this paper, we derive optimal lower
bounds for quantum sample complexity in both the PAC and agnostic models via an
information-theoretic approach. The proofs are arguably simpler, and the same
ideas can potentially be used to derive optimal bounds for other problems in
quantum learning theory.
We then turn to a quantum analogue of the Coupon Collector problem, a classic
problem from probability theory also of importance in the study of PAC
learning. Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf (TQC,
2020) characterized the quantum sample complexity of this problem up to
constant factors. First, we show that the information-theoretic approach
mentioned above provably does not yield the optimal lower bound. As a
by-product, we get a natural ensemble of pure states in arbitrarily high
dimensions which are not easily (simultaneously) distinguishable, while the
ensemble has close to maximal Holevo information. Second, we discover that the
information-theoretic approach yields an asymptotically optimal bound for an
approximation variant of the problem. Finally, we derive a sharper lower bound
for the Quantum Coupon Collector problem, via the generalized Holevo-Curlander
bounds on the distinguishability of an ensemble. All the aspects of the Quantum
Coupon Collector problem we study rest on properties of the spectrum of the
associated Gram matrix, which may be of independent interest.
Related papers
- Bosonic Quantum Computational Complexity [0.0]
We lay foundations for such a research program.
We introduce natural complexity classes and problems based on bosonic generalizations of BQP.
We show that the problem of deciding the boundedness of the spectrum of a bosonic Hamiltonian is co-NP-hard.
arXiv Detail & Related papers (2024-10-05T19:43:41Z) - 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) - Learning unitaries with quantum statistical queries [0.0]
We propose several algorithms for learning unitary operators from quantum statistical queries (QSQs)
Our methods hinge on a novel technique for estimating the Fourier mass of a unitary on a subset of Pauli strings with a single quantum statistical query.
We show that quantum statistical queries lead to an exponentially larger sample complexity for certain tasks, compared to separable measurements to the Choi-Jamiolkowski state.
arXiv Detail & Related papers (2023-10-03T17:56:07Z) - A simple formulation of no-cloning and no-hiding that admits efficient
and robust verification [0.0]
Incompatibility is a feature of quantum theory that sets it apart from classical theory.
The no-hiding theorem is another such instance that arises in the context of the black-hole information paradox.
We formulate both of these fundamental features of quantum theory in a single form that is amenable to efficient verification.
arXiv Detail & Related papers (2023-03-05T12:48:11Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical.
We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more.
Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
arXiv Detail & Related papers (2023-03-02T14:18:17Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - 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) - Probably approximately correct quantum source coding [0.0]
Holevo's and Nayak's bounds give an estimate of the amount of classical information that can be stored in a quantum state.
We show two novel applications in quantum learning theory and delegated quantum computation with a purely classical client.
arXiv Detail & Related papers (2021-12-13T17:57:30Z) - A Theoretical Framework for Learning from Quantum Data [15.828697880068704]
We propose a theoretical foundation for learning classical patterns from quantum data.
We present a quantum counterpart of the well-known PAC framework.
We establish upper bounds on the quantum sample complexity quantum concept classes.
arXiv Detail & Related papers (2021-07-13T21:39:47Z)
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.