Name
Abstract | ||
|---|---|---|
We demonstrate how quantum computation can provide non-trivial improvements in the computational and statistical complexity of the perceptron model. We develop two quantum algorithms for perceptron learning. The first algorithm exploits quantum information processing to determine a separating hyperplane using a number of steps sublinear in the number of data points N, namely O(root N). The second algorithm illustrates how the classical mistake bound of O(1/gamma(2)) can be further improved to O(1/root gamma) through quantum means, where gamma denotes the margin. Such improvements are achieved through the application of quantum amplitude amplification to the version space interpretation of the perceptron model. |
Year | Venue | DocType |
|---|---|---|
2016 | ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 29 (NIPS 2016) | Journal |
Volume | ISSN | Citations |
29 | 1049-5258 | 10 |
PageRank | References | Authors |
0.59 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nathan Wiebe | 1 | 43 | 4.67 |
| Ashish Kapoor | 2 | 1833 | 119.72 |
| Krysta M. Svore | 3 | 826 | 53.76 |