Quantum Perceptron Models

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(\sqrt{N})$. The second algorithm illustrates how the classical mistake bound of $O(\frac{1}{{\gamma }^2})$ can be further improved to $O(\frac{1}{\sqrt{\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.

References in corpus (4)

• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum algorithms for supervised and unsupervised machine learning
• Adiabatic quantum algorithm for search engine ranking

Cited by in corpus (29)

• Quantum Machine Learning
• Efficient Learning for Deep Quantum Neural Networks
• Quantum computing for finance: overview and prospects
• An Artificial Neuron Implemented on an Actual Quantum Processor
• Amplitude estimation without phase estimation
• A quantum linear system algorithm for dense matrices
• Quantum machine learning over infinite dimensions
• Towards understanding the power of quantum kernels in the NISQ era
• Quantum linear systems algorithms: a primer
• Faster Amplitude Estimation
• Quantum Machine Learning for Finance
• A Survey of Quantum Learning Theory
• Quantum Differentially Private Sparse Regression Learning
• Sublinear quantum algorithms for training linear and kernel-based classifiers
• Optimal Quantum Sample Complexity of Learning Algorithms
• Quantum Bandits
• Classical Artificial Neural Network Training Using Quantum Walks as a Search Procedure
• Simulation of a Variational Quantum Perceptron using Grover's Algorithm
• Discriminating Quantum States with Quantum Machine Learning
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
• Image Compression and Classification Using Qubits and Quantum Deep Learning
• A model of interacting quantum neurons with a dynamic synapse
• Dissipative Quantum Hopfield Network: A numerical analysis
• Can biological quantum networks solve NP-hard problems?
• Quantum Divide-and-Conquer Anchoring for Separable Non-negative Matrix Factorization
• Data science and Machine learning in the Clouds: A Perspective for the Future
• Quantum Perceptron Revisited: Computational-Statistical Tradeoffs
• Implementation of a Hamming-Distance-Like Genomic Quantum Classifier Using Inner Products on IBMQX4 and IBMQX16