The complexity of quantum support vector machines
- URL: http://arxiv.org/abs/2203.00031v2
- Date: Sun, 7 Jan 2024 19:12:32 GMT
- Title: The complexity of quantum support vector machines
- Authors: Gian Gentinetta, Arne Thomsen, David Sutter, Stefan Woerner
- Abstract summary: Quantum support vector machines employ quantum circuits to define the kernel function.
We show that the dual problem can be solved in $O(M4.67/varepsilon2)$ quantum circuit evaluations.
- Score: 1.7887848708497243
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum support vector machines employ quantum circuits to define the kernel
function. It has been shown that this approach offers a provable exponential
speedup compared to any known classical algorithm for certain data sets. The
training of such models corresponds to solving a convex optimization problem
either via its primal or dual formulation. Due to the probabilistic nature of
quantum mechanics, the training algorithms are affected by statistical
uncertainty, which has a major impact on their complexity. We show that the
dual problem can be solved in $O(M^{4.67}/\varepsilon^2)$ quantum circuit
evaluations, where $M$ denotes the size of the data set and $\varepsilon$ the
solution accuracy compared to the ideal result from exact expectation values,
which is only obtainable in theory. We prove under an empirically motivated
assumption that the kernelized primal problem can alternatively be solved in
$O(\min \{ M^2/\varepsilon^6, \, 1/\varepsilon^{10} \})$ evaluations by
employing a generalization of a known classical algorithm called Pegasos.
Accompanying empirical results demonstrate these analytical complexities to be
essentially tight. In addition, we investigate a variational approximation to
quantum support vector machines and show that their heuristic training achieves
considerably better scaling in our experiments.
Related papers
- Addressing the Readout Problem in Quantum Differential Equation Algorithms with Quantum Scientific Machine Learning [14.379311972506791]
We show that the readout of exact quantum states poses a bottleneck due to the complexity of tomography.
Treating outputs of quantum differential equation solvers as quantum data, we demonstrate that low-dimensional output can be extracted.
We apply this quantum scientific machine learning approach to classify solutions for shock wave detection and turbulence modeling.
arXiv Detail & Related papers (2024-11-21T16:09:08Z) - Improved quantum algorithm for calculating eigenvalues of differential operators and its application to estimating the decay rate of the perturbation distribution tail in stochastic inflation [0.0]
We propose a quantum algorithm for estimating the first eigenvalue of a differential operator $mathcalL$ on $mathbbRd$.
We then consider the application of our method to a problem in a theoretical framework for cosmic inflation known as quantum inflation.
arXiv Detail & Related papers (2024-10-03T07:56:20Z) - Benchmarking of quantum fidelity kernels for Gaussian process regression [1.7287035469433212]
Quantum computing algorithms have been shown to produce performant quantum kernels for machine-learning classification problems.
We show that quantum kernels can achieve the same, though not better, expressivity as classical kernels for regression problems.
arXiv Detail & Related papers (2024-07-22T18:19:48Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - Dense outputs from quantum simulations [5.295277584890625]
The quantum dense output problem is the process of evaluating time-accumulated observables from time-dependent quantum dynamics.
This problem arises frequently in applications such as quantum control and spectroscopic computation.
We present a range of algorithms designed to operate on both early and fully fault-tolerant quantum platforms.
arXiv Detail & Related papers (2023-07-26T18:16:51Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions.
The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix.
We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
arXiv Detail & Related papers (2023-04-12T18:10:47Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Validation tests of GBS quantum computers give evidence for quantum
advantage with a decoherent target [62.997667081978825]
We use positive-P phase-space simulations of grouped count probabilities as a fingerprint for verifying multi-mode data.
We show how one can disprove faked data, and apply this to a classical count algorithm.
arXiv Detail & Related papers (2022-11-07T12:00:45Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits.
We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
arXiv Detail & Related papers (2022-07-07T08:04:15Z) - Estimating Gibbs partition function with quantumClifford sampling [6.656454497798153]
We develop a hybrid quantum-classical algorithm to estimate the partition function.
Our algorithm requires only a shallow $mathcalO(1)$-depth quantum circuit.
Shallow-depth quantum circuits are considered vitally important for currently available NISQ (Noisy Intermediate-Scale Quantum) devices.
arXiv Detail & Related papers (2021-09-22T02:03:35Z) - Preparation of excited states for nuclear dynamics on a quantum computer [117.44028458220427]
We study two different methods to prepare excited states on a quantum computer.
We benchmark these techniques on emulated and real quantum devices.
These findings show that quantum techniques designed to achieve good scaling on fault tolerant devices might also provide practical benefits on devices with limited connectivity and gate fidelity.
arXiv Detail & Related papers (2020-09-28T17:21:25Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.