American Institute of Mathematical Sciences

doi: 10.3934/amc.2021067
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Following Forrelation – quantum algorithms in exploring Boolean functions' spectra

 1 Applied Statistics Unit, Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India 2 Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India, University of Southern California, USA

*Corresponding author: Subhamoy Maitra

Received  October 2021 Early access January 2022

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 oracle access, one can sample from the Walsh Spectrum of $f$. Using this, we obtain improved results than what one can achieve by exploiting the Deutsch-Jozsa algorithm. In turn, it has implications in resiliency checking. Furthermore, we use a 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 the superposition of linear functions to obtain a cross-correlation sampling technique. This is the first cross-correlation sampling algorithm with constant query complexity to the best of our knowledge. 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$.

Citation: Suman Dutta, Subhamoy Maitra, Chandra Sekhar Mukherjee. Following Forrelation – quantum algorithms in exploring Boolean functions' spectra. Advances in Mathematics of Communications, doi: 10.3934/amc.2021067
References:

show all references

References:
Quantum circuit for implementing the $2$-fold Forrelation problem using $2$ queries
Quantum circuit for implementing the $3$-fold Forrelation problem using $3$ sequential queries
Quantum circuit for implementing the $3$-fold Forrelation problem using $2$ parallel queries
Sampling probabilities of Walsh transform using different algorithms
Quantum circuit for implementing Algorithm 1
 [1] Tingting Pang, Nian Li, Li Zhang, Xiangyong Zeng. Several new classes of (balanced) Boolean functions with few Walsh transform values. Advances in Mathematics of Communications, 2021, 15 (4) : 757-775. doi: 10.3934/amc.2020095 [2] Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048 [3] Samuel T. Blake, Thomas E. Hall, Andrew Z. Tirkel. Arrays over roots of unity with perfect autocorrelation and good ZCZ cross-correlation. Advances in Mathematics of Communications, 2013, 7 (3) : 231-242. doi: 10.3934/amc.2013.7.231 [4] Xiaohui Liu, Jinhua Wang, Dianhua Wu. Two new classes of binary sequence pairs with three-level cross-correlation. Advances in Mathematics of Communications, 2015, 9 (1) : 117-128. doi: 10.3934/amc.2015.9.117 [5] Yu Zhou. On the distribution of auto-correlation value of balanced Boolean functions. Advances in Mathematics of Communications, 2013, 7 (3) : 335-347. doi: 10.3934/amc.2013.7.335 [6] C. T. Cremins, G. Infante. A semilinear $A$-spectrum. Discrete & Continuous Dynamical Systems - S, 2008, 1 (2) : 235-242. doi: 10.3934/dcdss.2008.1.235 [7] Lei Lei, Wenli Ren, Cuiling Fan. The differential spectrum of a class of power functions over finite fields. Advances in Mathematics of Communications, 2021, 15 (3) : 525-537. doi: 10.3934/amc.2020080 [8] Yuhua Sun, Zilong Wang, Hui Li, Tongjiang Yan. The cross-correlation distribution of a $p$-ary $m$-sequence of period $p^{2k}-1$ and its decimated sequence by $\frac{(p^{k}+1)^{2}}{2(p^{e}+1)}$. Advances in Mathematics of Communications, 2013, 7 (4) : 409-424. doi: 10.3934/amc.2013.7.409 [9] Hua Liang, Jinquan Luo, Yuansheng Tang. On cross-correlation of a binary $m$-sequence of period $2^{2k}-1$ and its decimated sequences by $(2^{lk}+1)/(2^l+1)$. Advances in Mathematics of Communications, 2017, 11 (4) : 693-703. doi: 10.3934/amc.2017050 [10] Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201 [11] Sihem Mesnager, Fengrong Zhang. On constructions of bent, semi-bent and five valued spectrum functions from old bent functions. Advances in Mathematics of Communications, 2017, 11 (2) : 339-345. doi: 10.3934/amc.2017026 [12] Dmitry Dolgopyat, Dmitry Jakobson. On small gaps in the length spectrum. Journal of Modern Dynamics, 2016, 10: 339-352. doi: 10.3934/jmd.2016.10.339 [13] Natalija Sergejeva. On the unusual Fucik spectrum. Conference Publications, 2007, 2007 (Special) : 920-926. doi: 10.3934/proc.2007.2007.920 [14] Evan Greif, Daniel Kaplan, Robert S. Strichartz, Samuel C. Wiese. Spectrum of the Laplacian on regular polyhedra. Communications on Pure & Applied Analysis, 2021, 20 (1) : 193-214. doi: 10.3934/cpaa.2020263 [15] Umesh V. Dubey, Vivek M. Mallick. Spectrum of some triangulated categories. Electronic Research Announcements, 2011, 18: 50-53. doi: 10.3934/era.2011.18.50 [16] Tim Alderson, Alessandro Neri. Maximum weight spectrum codes. Advances in Mathematics of Communications, 2019, 13 (1) : 101-119. doi: 10.3934/amc.2019006 [17] Emmanuel Schenck. Exponential gaps in the length spectrum. Journal of Modern Dynamics, 2020, 16: 207-223. doi: 10.3934/jmd.2020007 [18] Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2367-2387. doi: 10.3934/jimo.2020073 [19] Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038 [20] J. Douglas Wright. On the spectrum of the superposition of separated potentials.. Discrete & Continuous Dynamical Systems - B, 2013, 18 (1) : 273-281. doi: 10.3934/dcdsb.2013.18.273

2020 Impact Factor: 0.935

Tools

Article outline

Figures and Tables