Provable advantages of kernel-based quantum learners and quantum preprocessing based on Grover's algorithm

• URL: http://arxiv.org/abs/2309.14406v1
• Date: Mon, 25 Sep 2023 18:00:00 GMT
• Title: Provable advantages of kernel-based quantum learners and quantum preprocessing based on Grover's algorithm
• Authors: Till Muser, Elias Zapusek, Vasilis Belis, Florentin Reiter
• Abstract summary: We find a speedup utilizing Grover's algorithm in the kernel of a support vector machine. We also show that combining quantum computation in a preprocessing step with classical methods for classification further improves classification performance.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There is an ongoing effort to find quantum speedups for learning problems. Recently, [Y. Liu et al., Nat. Phys. $\textbf{17}$, 1013--1017 (2021)] have proven an exponential speedup for quantum support vector machines by leveraging the speedup of Shor's algorithm. We expand upon this result and identify a speedup utilizing Grover's algorithm in the kernel of a support vector machine. To show the practicality of the kernel structure we apply it to a problem related to pattern matching, providing a practical yet provable advantage. Moreover, we show that combining quantum computation in a preprocessing step with classical methods for classification further improves classifier performance.

Related papers

• Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD [0.0]
  We introduce the first quantum algorithms for code sieving by designing quantum variants of the aforementioned sieving subroutine. Our quantum-walk algorithm exploits the structure of the underlying search problem by adding a layer of locality-sensitive filtering. Our analysis highlights that the framework should be adapted in order to outperform the state-of-the-art of quantum ISD algorithms.
  arXiv  Detail & Related papers  (2024-08-29T11:47:33Z)
• Fast Algorithms and Implementations for Computing the Minimum Distance of Quantum Codes [43.96687298077534]
  The distance of a stabilizer quantum code determines the number of errors that can be detected and corrected. We present three new fast algorithms and implementations for computing the symplectic distance of the associated classical code.
  arXiv  Detail & Related papers  (2024-08-20T11:24:30Z)
• Quartic quantum speedups for planted inference [44.820711784498]
  We describe a quantum algorithm for the Planted Noisy $k$XOR problem. Our work suggests that some constructions are susceptible to super-quadratic quantum attacks.
  arXiv  Detail & Related papers  (2024-06-27T17:54:28Z)
• Quantum Machine Learning: Quantum Kernel Methods [0.0]
  Kernel methods are a powerful and popular technique in classical Machine Learning. The use of a quantum feature space that can only be calculated efficiently on a quantum computer potentially allows for deriving a quantum advantage. A data dependent projected quantum kernel was shown to provide significant advantage over classical kernels.
  arXiv  Detail & Related papers  (2024-05-02T23:45:29Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Quantum speedup of leverage score sampling and its application [0.0]
  In this paper, we propose a quantum algorithm to accelerate the computation of leverage scores. As an application, we propose a new quantum algorithm for rigid regression problems with vector solution outputs.
  arXiv  Detail & Related papers  (2023-01-15T14:40:18Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum Alphatron: quantum advantage for learning with kernels and noise [2.94944680995069]
  We provide quantum versions of the Alphatron in the fault-tolerant setting. We discuss the quantum advantage in the context of learning of two-layer neural networks.
  arXiv  Detail & Related papers  (2021-08-26T09:36:20Z)
• Quantum K-medians Algorithm Using Parallel Euclidean Distance Estimator [0.0]
  This paper proposes an efficient quantum k-medians clustering algorithm using the powerful quantum Euclidean estimator algorithm. The proposed quantum k-medians algorithm has provided an exponential speed up as compared to the classical version of it.
  arXiv  Detail & Related papers  (2020-12-21T06:38:20Z)

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.