Provable Adversarial Robustness in the Quantum Model

• URL: http://arxiv.org/abs/2112.09625v1
• Date: Fri, 17 Dec 2021 16:54:18 GMT
• Title: Provable Adversarial Robustness in the Quantum Model
• Authors: Khashayar Barooti, Grzegorz G{\l}uch, Ruediger Urbanke
• Abstract summary: We consider a model similar to the quantum PAC-learning model introduced by Bshouty and Jackson. Our reduction guarantees that in order to solve the adversarial problem in our model it suffices to consider a single distance notion.
• Score: 0.966840768820136
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern machine learning systems have been applied successfully to a variety of tasks in recent years but making such systems robust against adversarially chosen modifications of input instances seems to be a much harder problem. It is probably fair to say that no fully satisfying solution has been found up to date and it is not clear if the standard formulation even allows for a principled solution. Hence, rather than following the classical path of bounded perturbations, we consider a model similar to the quantum PAC-learning model introduced by Bshouty and Jackson [1995]. Our first key contribution shows that in this model we can reduce adversarial robustness to the conjunction of two classical learning theory problems, namely (Problem 1) the problem of finding generative models and (Problem 2) the problem of devising classifiers that are robust with respect to distributional shifts. Our second key contribution is that the considered framework does not rely on specific (and hence also somewhat arbitrary) threat models like $\ell_p$ bounded perturbations. Instead, our reduction guarantees that in order to solve the adversarial robustness problem in our model it suffices to consider a single distance notion, i.e. the Hellinger distance. From the technical perspective our protocols are heavily based on the recent advances on delegation of quantum computation, e.g. Mahadev [2018]. Although the considered model is quantum and therefore not immediately applicable to ``real-world'' situations, one might hope that in the future either one can find a way to embed ``real-world'' problems into a quantum framework or that classical algorithms can be found that are capable of mimicking their powerful quantum counterparts.

Related papers

• Computational supremacy in quantum simulation [22.596358764113624]
  We show that superconducting quantum annealing processors can generate samples in close agreement with solutions of the Schr"odinger equation. We conclude that no known approach can achieve the same accuracy as the quantum annealer within a reasonable timeframe.
  arXiv  Detail & Related papers  (2024-03-01T19:00:04Z)
• A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Models [62.997667081978825]
  We build over a proposed framework for evaluating the generalization performance of generative models. We establish the first comparative race towards practical quantum advantage (PQA) between classical and quantum generative models. Our results suggest that QCBMs are more efficient in the data-limited regime than the other state-of-the-art classical generative models.
  arXiv  Detail & Related papers  (2023-03-27T22:48:28Z)
• 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)
• Quantum Algorithms for Geologic Fracture Networks [0.09236074230806578]
  We introduce two quantum algorithms for solving fractured flow. One is designed for future quantum computers which operate without error, but we demonstrate that current hardware is too noisy for adequate performance. The second algorithm, designed to be noise resilient, already performs well for problems of small to medium size.
  arXiv  Detail & Related papers  (2022-10-21T02:23:23Z)
• Generative model for learning quantum ensemble via optimal transport loss [0.9404723842159504]
  We propose a quantum generative model that can learn quantum ensemble. The proposed model paves the way for a wide application such as the health check of quantum devices.
  arXiv  Detail & Related papers  (2022-10-19T17:35:38Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• 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)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  A central component of variational quantum algorithms (VQA) is the state-preparation circuit, also known as ansatz or variational form. Here, we show that this approach is not always advantageous by introducing ans"atze that incorporate symmetry-breaking unitaries. This work constitutes a first step towards the development of a more general class of symmetry-breaking ans"atze with applications to physics and chemistry problems.
  arXiv  Detail & Related papers  (2020-08-03T18:00:05Z)
• Compressed variational quantum eigensolver for the Fermi-Hubbard model [0.05076419064097732]
  The Fermi-Hubbard model is a plausible target to be solved by a quantum computer. Here we use a simple method which compresses the first nontrivial subcase of the Hubbard model. We implement this method on a superconducting quantum hardware platform.
  arXiv  Detail & Related papers  (2020-06-01T18:12:12Z)

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.