Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuadratic Quantum Speedup for Perceptron Training
82
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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 $( icefrac{sqrt{N}}{gamma^2})log( icefrac1{gamma^2)}$ or $ icefrac{N}{sqrt{gamma}}$, 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{ icefrac{N}{gamma}}$. 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.
rate research
Read More
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.
A recent breakthrough by Ambainis, Balodis, Iraids, Kokainis, Pr=usis and Vihrovs (SODA19) showed how to construct faster quantum algorithms for the Traveling Salesman Problem and a few other NP-hard problems by combining in a novel way quantum search with classical dynamic programming. In this paper, we show how to apply this approach to the minimum Steiner tree problem, a well-known NP-hard problem, and construct the first quantum algorithm that solves this problem faster than the best known classical algorithms. More precisely, the complexity of our quantum algorithm is $mathcal{O}(1.812^kpoly(n))$, where $n$ denotes the number of vertices in the graph and $k$ denotes the number of terminals. In comparison, the best known classical algorithm has complexity $mathcal{O}(2^kpoly(n))$.
One of the main milestones in quantum information science is to realise quantum devices that exhibit an exponential computational advantage over classical ones without being universal quantum computers, a state of affairs dubbed quantum speedup, or sometimes quantum computational supremacy. The known schemes heavily rely on mathematical assumptions that are plausible but unproven, prominently results on anticoncentration of random prescriptions. In this work, we aim at closing the gap by proving two anticoncentration theorems and accompanying hardness results, one for circuit-based schemes, the other for quantum quench-type schemes for quantum simulations. Compared to the few other known such results, these results give rise to a number of comparably simple, physically meaningful and resource-economical schemes showing a quantum speedup in one and two spatial dimensions. At the heart of the analysis are tools of unitary designs and random circuits that allow us to conclude that universal random circuits anticoncentrate as well as an embedding of known circuit-based schemes in a 2D translation-invariant architecture.
Quantum machine learning algorithms could provide significant speed-ups over their classical counterparts; however, whether they could also achieve good generalization remains unclear. Recently, two quantum perceptron models which give a quadratic improvement over the classical perceptron algorithm using Grovers search have been proposed by Wiebe et al. arXiv:1602.04799 . While the first model reduces the complexity with respect to the size of the training set, the second one improves the bound on the number of mistakes made by the perceptron. In this paper, we introduce a hybrid quantum-classical perceptron algorithm with lower complexity and better generalization ability than the classical perceptron. We show a quadratic improvement over the classical perceptron in both the number of samples and the margin of the data. We derive a bound on the expected error of the hypothesis returned by our algorithm, which compares favorably to the one obtained with the classical online perceptron. We use numerical experiments to illustrate the trade-off between computational complexity and statistical accuracy in quantum perceptron learning and discuss some of the key practical issues surrounding the implementation of quantum perceptron models into near-term quantum devices, whose practical implementation represents a serious challenge due to inherent noise. However, the potential benefits make correcting this worthwhile.
With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, employing diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically-infeasible instances of factoring and quantum chemistry.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
