mlsanityData to 7 Oct 2026

Discrete Randomized Smoothing Meets Quantum Computing

arXiv 2408.00895 ↗First posted 1 Aug 2024cs.LG quant-phcited by 2

Not on the map. Why?

Abstract (arXiv)

Breakthroughs in machine learning (ML) and advances in quantum computing (QC) drive the interdisciplinary field of quantum machine learning to new levels. However, due to the susceptibility of ML models to adversarial attacks, practical use raises safety-critical concerns. Existing Randomized Smoothing (RS) certification methods for classical machine learning models are computationally intensive. In this paper, we propose the combination of QC and the concept of discrete randomized smoothing to speed up the stochastic certification of ML models for discrete data. We show how to encode all the perturbations of the input binary data in superposition and use Quantum Amplitude Estimation (QAE) to obtain a quadratic reduction in the number of calls to the model that are required compared to traditional randomized smoothing techniques. In addition, we propose a new binary threat model to allow for an extensive evaluation of our approach on images, graphs, and text.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 27 of its 45 references that are in the map. First posted on arXiv 1 Aug 2024.

Builds on

27 of 45 references.

References · 27

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2021Diffusion Models Beat GANs on Image Synthesiscited by 8,185
  3. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  4. 2022LaMDA: Language Models for Dialog Applicationscited by 1,218
  5. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  6. 2020A Survey on Visual Transformercited by 653
  7. 2019Provably Powerful Graph Networkscited by 385
  8. 2018On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Modelscited by 322
  9. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  10. 2020Can Graph Neural Networks Count Substructures?cited by 235
  11. 2024Attacking Large Language Models with Projected Gradient Descentcited by 91
  12. 2020Quantum noise protects quantum classifiers against adversariescited by 68
15 more
  1. 2019Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifierscited by 65
  2. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  3. 2020Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Frameworkcited by 45
  4. 2021Optical Adversarial Attackcited by 43
  5. 2020Certifying Confidence via Randomized Smoothingcited by 36
  6. 2020Optimal Provable Robustness of Quantum Classification via Quantum Hypothesis Testingcited by 23
  7. 2023Revisiting Robustness in Graph Machine Learningcited by 19
  8. 2022Certified Robustness of Quantum Classifiers against Adversarial Examples through Quantum Noisecited by 17
  9. 2022Enhancing Quantum Adversarial Robustness by Randomized Encodingscited by 16
  10. 2013The cost of using exact confidence intervals for a binomial proportioncited by 11
  11. 2022Localized Randomized Smoothing for Collective Robustness Certificationcited by 10
  12. 2019Quantum Approximate Counting, Simplifiedcited by 6
  13. 2023Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustnesscited by 4
  14. 2023Expressivity of Graph Neural Networks Through the Lens of Adversarial Robustnesscited by 1
  15. 2024Quadratic Advantage with Quantum Randomized Smoothing Applied to Time-Series Analysiscited by 1

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 1.

2 papers.

  1. 2025Adversarial Robustness of Partitioned Quantum Classifierscited by 2
  2. 2024Certifiably Robust Encoding Schemescited by 1