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

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 36 references that are in the map.
- First posted on arXiv 25 Jul 2024.

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

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [The power of quantum neural networks](https://mlsanity.com/paper/2011.00027/) (2020)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Quantum noise protects quantum classifiers against adversaries](https://mlsanity.com/paper/2003.09416/) (2020)
- [Quantum Adversarial Machine Learning](https://mlsanity.com/paper/2001.00030/) (2019)
- [Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers](https://mlsanity.com/paper/1906.04948/) (2019)
- [Benchmarking Adversarially Robust Quantum Machine Learning at Scale](https://mlsanity.com/paper/2211.12681/) (2022)
- [Provably Robust Conformal Prediction with Improved Efficiency](https://mlsanity.com/paper/2404.19651/) (2024)
- [Optimal Provable Robustness of Quantum Classification via Quantum Hypothesis Testing](https://mlsanity.com/paper/2009.10064/) (2020)
- [Robustness Verification of Quantum Classifiers](https://mlsanity.com/paper/2008.07230/) (2020)
- [Certified Robustness of Quantum Classifiers against Adversarial Examples through Quantum Noise](https://mlsanity.com/paper/2211.00887/) (2022)
- [Predominant Aspects on Security for Quantum Machine Learning: Literature Review](https://mlsanity.com/paper/2401.07774/) (2024)
- [Verifying Fairness in Quantum Machine Learning](https://mlsanity.com/paper/2207.11173/) (2022)
- [Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness](https://mlsanity.com/paper/2305.00472/) (2023)
- [Deterministic Preparation of Dicke States](https://mlsanity.com/paper/1904.07358/) (2019)

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

- [Discrete Randomized Smoothing Meets Quantum Computing](https://mlsanity.com/paper/2408.00895/) (2024)

## Abstract (arXiv)

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.