License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.25
URN: urn:nbn:de:0030-drops-75241
Go to the corresponding LIPIcs Volume Portal

Arunachalam, Srinivasan ; de Wolf, Ronald

Optimal Quantum Sample Complexity of Learning Algorithms

LIPIcs-CCC-2017-25.pdf (0.7 MB)


In learning theory, the VC dimension of a concept class C is the most common way to measure its "richness". A fundamental result says that the number of examples needed to learn an unknown target concept c in C under an unknown distribution D, is tightly determined by the VC dimension d of the concept class C. Specifically, in the PAC model

Theta(d/eps + log(1/delta)/eps)

examples are necessary and sufficient for a learner to output, with probability 1-delta, a hypothesis h that is eps-close to the target concept c (measured under D). In the related agnostic model, where the samples need not come from a c in C, we know that

Theta(d/eps^2 + log(1/delta)/eps^2)

examples are necessary and sufficient to output an hypothesis h in C whose error is at most eps worse than the error of the best concept in C.

Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson, who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio, improved by Zhang, showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is

Omega(d^{1-eta}/eps + d + log(1/delta)/eps) for arbitrarily small constant eta>0.

Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a log(d/eps) factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the "Pretty Good Measurement" on the quantum state identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class C.

BibTeX - Entry

  author =	{Srinivasan Arunachalam and Ronald de Wolf},
  title =	{{Optimal Quantum Sample Complexity of Learning Algorithms}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{25:1--25:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{Ryan O'Donnell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-75241},
  doi =		{10.4230/LIPIcs.CCC.2017.25},
  annote =	{Keywords: Quantum computing, PAC learning, agnostic learning, VC dimension}

Keywords: Quantum computing, PAC learning, agnostic learning, VC dimension
Collection: 32nd Computational Complexity Conference (CCC 2017)
Issue Date: 2017
Date of publication: 01.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI