scientific article; zbMATH DE number 7008327

Srinivasan Arunachalam, Ronald de Wolf

Publication date: 30 January 2019

Full work available at URL: http://jmlr.csail.mit.edu/papers/v19/18-195.html

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

lower bounds quantum computing PAC learning sample complexity

Computational learning theory (68Q32) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (7)

Quantum learning Boolean linear functions w.r.t. product distributions ⋮ Learning bounds for quantum circuits in the agnostic setting ⋮ Learning quantum finite automata with queries ⋮ Quantum science and quantum technology ⋮ Unnamed Item ⋮ Quantum learning of concentrated Boolean functions ⋮ A quantum algorithm of K-means toward practical use

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
The quantum query complexity of learning multilinear polynomials
On the distinguishability of random quantum states
The geometry of quantum learning
New bounds on classical and quantum one-way communication complexity
Decision theoretic generalizations of the PAC model for neural net and other learning applications
Sample size lower bounds in PAC learning by Algorithmic Complexity Theory
Sharper bounds for Gaussian and empirical processes
Toward efficient agnostic learning
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
Improved lower bounds for learning from noisy examples: An information-theoretic approach
General bounds on the number of examples needed for learning probabilistic concepts
An improved lower bound on query complexity for quantum PAC learning
Quantum speed-up for unsupervised learning
Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model
Fast learning rates in statistical inference through aggregation
Quantum algorithms for learning and testing juntas
Improved bounds on quantum learning algorithms
Learnability and the Vapnik-Chervonenkis dimension
The learnability of quantum states
Optimal measurements for the dihedral hidden subgroup problem
A theory of the learnable
Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
Cryptographic limitations on learning Boolean formulae and finite automata
Quantum Complexity Theory
On quantum detection and the square-root measurement
Equivalences and Separations Between Quantum and Classical Learnability
Designing optimal quantum detectors via semidefinite programming
Reversing quantum dynamics with near-optimal quantum and classical fidelity
Neural Network Learning
Analysis of Boolean Functions
Understanding Machine Learning
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: