Loading...
Loading...

Go to the content (press return)

On the query complexity of quantum learners

Author
Castro, J.
Type of activity
Report
Date
2005-06
Code
LSI-05-28-R
Repository
http://hdl.handle.net/2117/84843 Open in new window
Abstract
This paper introduces a framework for quantum exact learning via queries, the so-called quantum protocol. It is shown that usual protocols in the classical learning setting have quantum counterparts. A combinatorial notion, the general halving dimension, is also introduced. Given a quantum protocol and a target concept class, the general halving dimension provides a lower bound on the number of queries that a quantum algorithm needs to learn. For usual protocols, this lower bound is also valid e...
Citation
Castro, J. "On the query complexity of quantum learners". 2005.
Keywords
Learning, Quantum protocol, Queries
Group of research
LARCA - Laboratory of Relational Algorithmics, Complexity and Learnability

Participants

Attachments