Quadratic Quantum Speedup for Perceptron Training

Abstract

Perceptrons, which perform binary classification, are the fundamental building blocks of neural networks. Given a data set of size~$N$ and margin~$\gamma$ (how well the given data are separated), the query complexity of the best-known quantum training algorithm scales as either $(\nicefrac{\sqrt{N}}{γ^2})\log(\nicefrac1{γ^2)}$ or $\nicefrac{N}{\sqrtγ}$, which is achieved by a hybrid of classical and quantum search. In this paper, we improve the version space quantum training method for perceptrons such that the query complexity of our algorithm scales as $\sqrt{\nicefrac{N}γ}$. This is achieved by constructing an oracle for the perceptrons using quantum counting of the number of data elements that are correctly classified. We show that query complexity to construct such an oracle has a quadratic improvement over classical methods. Once such an oracle is constructed, bounded-error quantum search can be used to search over the hyperplane instances. The optimality of our algorithm is proven by reducing the evaluation of a two-level AND-OR tree (for which the query complexity lower bound is known) to a multi-criterion search. Our quantum training algorithm can be generalized to train more complex machine learning models such as neural networks, which are built on a large number of perceptrons.

arXiv comment9 pages, 3 figures

References in corpus (19)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum machine learning in feature Hilbert spaces
• Quantum principal component analysis
• Quantum generative adversarial learning
• Quantum-enhanced machine learning
• Quantum Boltzmann Machine
• An Artificial Neuron Implemented on an Actual Quantum Processor
• A divide-and-conquer algorithm for quantum state preparation
• Trainability of Dissipative Perceptron-Based Quantum Neural Networks
• Simulating a perceptron on a quantum computer
• Quantum machine learning for quantum anomaly detection
• Unitary quantum perceptron as efficient universal approximator
• A Review on Quantum Search Algorithms
• A Grover-search Based Quantum Learning Scheme for Classification
• Generalized Grover's algorithm for multiple phase inversion states
• Direct implementation of a perceptron in superconducting circuit quantum hardware
• Implementing perceptron models with qubits

Cited by in corpus (3)

• Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
• QuForge: A Library for Qudits Simulation
• On Quantum Perceptron Learning via Quantum Search