Quadratic Advantage with Quantum Randomized Smoothing Applied to Time-Series Analysis
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913445401591808 |
|---|---|
| author | Franco, Nicola Kempkes, Marie Spiegelberg, Jakob Lorenz, Jeanette Miriam |
| author_facet | Franco, Nicola Kempkes, Marie Spiegelberg, Jakob Lorenz, Jeanette Miriam |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_18021 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quadratic Advantage with Quantum Randomized Smoothing Applied to Time-Series Analysis Franco, Nicola Kempkes, Marie Spiegelberg, Jakob Lorenz, Jeanette Miriam Quantum Physics Artificial Intelligence Machine Learning 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. |
| title | Quadratic Advantage with Quantum Randomized Smoothing Applied to Time-Series Analysis |
| topic | Quantum Physics Artificial Intelligence Machine Learning |
| url | https://arxiv.org/abs/2407.18021 |