Name
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 lower and upper bounds on the number of queries that a quantum algorithm needs to learn. For usual protocols, the lower bound is also valid even if only involution oracle teachers are considered. Under some protocols, the quantum upper bound improves the classical one. The general halving dimension also approximates the query complexity of ordinary randomized learners. From these bounds we conclude that quantum devices can allow moderate improvements on the query complexity. However, any quantum polynomially query learnable concept class must be also polynomially learnable in the classical setting. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11894841_10 | ALT |
Keywords | Field | DocType |
query complexity,general halving dimension,quantum protocol,quantum device,usual protocol,so-called quantum protocol,quantum counterpart,quantum polynomially query learnable,quantum exact learning,query superpositions,quantum algorithm,lower bound,upper bound | Quantum,Superposition principle,Concept class,Computer science,Upper and lower bounds,Quantum computer,Oracle,Quantum sort,Quantum algorithm,Artificial intelligence,Machine learning | Conference |
Volume | ISSN | ISBN |
4264 | 0302-9743 | 3-540-46649-5 |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jorge Castro | 1 | 34 | 3.27 |