Quadratic Advantage with Quantum Randomized Smoothing Applied to Time-Series Analysis

• URL: http://arxiv.org/abs/2407.18021v1
• Date: Thu, 25 Jul 2024 13:15:16 GMT
• Title: Quadratic Advantage with Quantum Randomized Smoothing Applied to Time-Series Analysis
• Authors: Nicola Franco, Marie Kempkes, Jakob Spiegelberg, Jeanette Miriam Lorenz,
• Abstract summary: We present an analysis of quantum randomized smoothing, how data encoding and perturbation modeling approaches can be matched to achieve meaningful robustness certificates. We show how constrained $k$-distant Hamming weight perturbations are a suitable noise distribution here, and elucidate how they can be constructed on a quantum computer. This may allow quantum computers to efficiently scale randomized smoothing to more complex tasks beyond the reach of classical methods.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As quantum machine learning continues to develop at a rapid pace, the importance of ensuring the robustness and efficiency of quantum algorithms cannot be overstated. Our research presents an analysis of quantum randomized smoothing, how data encoding and perturbation modeling approaches can be matched to achieve meaningful robustness certificates. By utilizing an innovative approach integrating Grover's algorithm, a quadratic sampling advantage over classical randomized smoothing is achieved. This strategy necessitates a basis state encoding, thus restricting the space of meaningful perturbations. We show how constrained $k$-distant Hamming weight perturbations are a suitable noise distribution here, and elucidate how they can be constructed on a quantum computer. The efficacy of the proposed framework is demonstrated on a time series classification task employing a Bag-of-Words pre-processing solution. The advantage of quadratic sample reduction is recovered especially in the regime with large number of samples. This may allow quantum computers to efficiently scale randomized smoothing to more complex tasks beyond the reach of classical methods.

Related papers

• Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms [0.0]
  We show how many techniques from randomized linear algebra can be adapted to work under this weaker assumption. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms.
  arXiv  Detail & Related papers  (2023-04-11T02:09:13Z)
• Quantum Conformal Prediction for Reliable Uncertainty Quantification in Quantum Machine Learning [47.991114317813555]
  Quantum models implement implicit probabilistic predictors that produce multiple random decisions for each input through measurement shots. This paper proposes to leverage such randomness to define prediction sets for both classification and regression that provably capture the uncertainty of the model.
  arXiv  Detail & Related papers  (2023-04-06T22:05:21Z)
• Optimizing quantum noise-induced reservoir computing for nonlinear and chaotic time series prediction [2.5427629797261297]
  We make advancements to the quantum noise-induced reservoir, in which reservoir noise is used as a resource to generate expressive, nonlinear signals. We show that with only a single noise model and small memory capacities, excellent simulation results were obtained on nonlinear benchmarks.
  arXiv  Detail & Related papers  (2023-03-09T18:40:03Z)
• Efficient estimation of trainability for variational quantum circuits [43.028111013960206]
  We find an efficient method to compute the cost function and its variance for a wide class of variational quantum circuits. This method can be used to certify trainability for variational quantum circuits and explore design strategies that can overcome the barren plateau problem.
  arXiv  Detail & Related papers  (2023-02-09T14:05:18Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Simulating the Mott transition on a noisy digital quantum computer via Cartan-based fast-forwarding circuits [62.73367618671969]
  Dynamical mean-field theory (DMFT) maps the local Green's function of the Hubbard model to that of the Anderson impurity model. Quantum and hybrid quantum-classical algorithms have been proposed to efficiently solve impurity models. This work presents the first computation of the Mott phase transition using noisy digital quantum hardware.
  arXiv  Detail & Related papers  (2021-12-10T17:32:15Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• A Neural-Network Variational Quantum Algorithm for Many-Body Dynamics [15.435967947933404]
  We propose a neural-network variational quantum algorithm to simulate the time evolution of quantum many-body systems. The proposed algorithm can be efficiently implemented in near-term quantum computers with low measurement cost.
  arXiv  Detail & Related papers  (2020-08-31T02:54:09Z)
• Quantum-enhanced analysis of discrete stochastic processes [0.8057006406834467]
  We propose a quantum algorithm for calculating the characteristic function of a Discrete processes (DSP) It completely defines its probability distribution, using the number of quantum circuit elements that grows only linearly with the number of time steps. The algorithm takes all trajectories into account and hence eliminates the need of importance sampling.
  arXiv  Detail & Related papers  (2020-08-14T16:07:35Z)

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.