Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2104.12212 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918022314196992 |
|---|---|
| author | Dutta, Suman Maitra, Subhamoy Mukherjee, Chandra Sekhar |
| author_facet | Dutta, Suman Maitra, Subhamoy Mukherjee, Chandra Sekhar |
| contents | Here we revisit the quantum algorithms for obtaining Forrelation [Aaronson et al, 2015] values to evaluate some of the well-known cryptographically significant spectra of Boolean functions, namely the Walsh spectrum, the cross-correlation spectrum and the autocorrelation spectrum. We introduce the existing 2-fold Forrelation formulation with bent duality based promise problems as desirable instantiations. Next we concentrate on the $3$-fold version through two approaches. First, we judiciously set-up some of the functions in $3$-fold Forrelation, so that given an oracle access, one can sample from the Walsh Spectrum of $f$. Using this, we obtain improved results than what we obtain from the Deutsch-Jozsa algorithm, and in turn it has implications in resiliency checking. Furthermore, we use similar idea to obtain a technique in estimating the cross-correlation (and thus autocorrelation) value at any point, improving upon the existing algorithms. Finally, we tweak the quantum algorithm with superposition of linear functions to obtain a cross-correlation sampling technique. To the best of our knowledge, this is the first cross-correlation sampling algorithm with constant query complexity. This also provides a strategy to check if two functions are uncorrelated of degree $m$. We further modify this using Dicke states so that the time complexity reduces, particularly for constant values of $m$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_12212 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Following Forrelation -- Quantum Algorithms in Exploring Boolean Functions' Spectra Dutta, Suman Maitra, Subhamoy Mukherjee, Chandra Sekhar Quantum Physics Computational Complexity Here we revisit the quantum algorithms for obtaining Forrelation [Aaronson et al, 2015] values to evaluate some of the well-known cryptographically significant spectra of Boolean functions, namely the Walsh spectrum, the cross-correlation spectrum and the autocorrelation spectrum. We introduce the existing 2-fold Forrelation formulation with bent duality based promise problems as desirable instantiations. Next we concentrate on the $3$-fold version through two approaches. First, we judiciously set-up some of the functions in $3$-fold Forrelation, so that given an oracle access, one can sample from the Walsh Spectrum of $f$. Using this, we obtain improved results than what we obtain from the Deutsch-Jozsa algorithm, and in turn it has implications in resiliency checking. Furthermore, we use similar idea to obtain a technique in estimating the cross-correlation (and thus autocorrelation) value at any point, improving upon the existing algorithms. Finally, we tweak the quantum algorithm with superposition of linear functions to obtain a cross-correlation sampling technique. To the best of our knowledge, this is the first cross-correlation sampling algorithm with constant query complexity. This also provides a strategy to check if two functions are uncorrelated of degree $m$. We further modify this using Dicke states so that the time complexity reduces, particularly for constant values of $m$. |
| title | Following Forrelation -- Quantum Algorithms in Exploring Boolean Functions' Spectra |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2104.12212 |