# Discrete Randomized Smoothing Meets Quantum Computing

arXiv: https://arxiv.org/abs/2408.00895 · HTML: https://mlsanity.com/paper/2408.00895/

## Key facts

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

## Builds on (most cited first, 27 of 27)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [LaMDA: Language Models for Dialog Applications](https://mlsanity.com/paper/2201.08239/) (2022)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [A Survey on Visual Transformer](https://mlsanity.com/paper/2012.12556/) (2020)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Attacking Large Language Models with Projected Gradient Descent](https://mlsanity.com/paper/2402.09154/) (2024)
- [Quantum noise protects quantum classifiers against adversaries](https://mlsanity.com/paper/2003.09416/) (2020)
- [Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers](https://mlsanity.com/paper/1906.04948/) (2019)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework](https://mlsanity.com/paper/2002.09169/) (2020)
- [Optical Adversarial Attack](https://mlsanity.com/paper/2108.06247/) (2021)
- [Certifying Confidence via Randomized Smoothing](https://mlsanity.com/paper/2009.08061/) (2020)
- [Optimal Provable Robustness of Quantum Classification via Quantum Hypothesis Testing](https://mlsanity.com/paper/2009.10064/) (2020)
- [Revisiting Robustness in Graph Machine Learning](https://mlsanity.com/paper/2305.00851/) (2023)
- [Certified Robustness of Quantum Classifiers against Adversarial Examples through Quantum Noise](https://mlsanity.com/paper/2211.00887/) (2022)
- [Enhancing Quantum Adversarial Robustness by Randomized Encodings](https://mlsanity.com/paper/2212.02531/) (2022)
- [The cost of using exact confidence intervals for a binomial proportion](https://mlsanity.com/paper/1303.1288/) (2013)
- [Localized Randomized Smoothing for Collective Robustness Certification](https://mlsanity.com/paper/2210.16140/) (2022)
- [Quantum Approximate Counting, Simplified](https://mlsanity.com/paper/1908.10846/) (2019)
- [Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness](https://mlsanity.com/paper/2305.00472/) (2023)
- [Expressivity of Graph Neural Networks Through the Lens of Adversarial Robustness](https://mlsanity.com/paper/2308.08173/) (2023)
- [Quadratic Advantage with Quantum Randomized Smoothing Applied to Time-Series Analysis](https://mlsanity.com/paper/2407.18021/) (2024)

## Built on by (most cited first, 2 of 2)

- [Adversarial Robustness of Partitioned Quantum Classifiers](https://mlsanity.com/paper/2502.20403/) (2025)
- [Certifiably Robust Encoding Schemes](https://mlsanity.com/paper/2408.01200/) (2024)

## 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.