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:
[1]

S. Aaronson, BQP and the polynomial hierarchy, In Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC '10), Association for Computing Machinery, New York, NY, USA, (2010), 141–150, arXiv version, arXiv: 0910.4698, (2009). doi: 10.1145/1806689.1806711.  Google Scholar

[2]

S. Aaronson and A. Ambainis, Forrelation: A problem that optimally separates quantum from classical computing, Siam J. Comput., 47 (2018), 982–1038. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC '15), Association for Computing Machinery, New York, NY, USA, DOI: https://doi.org/10.1145/2746539.2746547, (2015), 307–316, arXiv version, arXiv: 1411.5729, (2014). doi: 10.1137/15M1050902.  Google Scholar

[3]

N. Bansal and M. Sinha, k-forrelation optimally separates quantum and classical query complexity, In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC '21), (2021), 1303–1316. arXiv version, arXiv: 2008.07003, (2020). doi: 10.1145/3406325.3451040.  Google Scholar

[4]

D. Bera, S. Maitra and S. Tharrmashastha, Efficient quantum algorithms related to autocorrelation spectrum, In Progress in Cryptology-Indocrypt 2019, Lecture Notes in Computer Science, vol. 11898,415–432, Springer, (2019), arXiv version, arXiv: 1808.04448, (2019). doi: 10.1007/978-3-030-35423-7_21.  Google Scholar

[5]

G. Brassard, P. Hoyer, M. Mosca and A. Tapp, Quantum amplitude amplification and estimation, Quantum Computation and Quantum Information, Samuel J. Lomonaco, Jr. (editor), AMS Contemporary Mathematics, vol. 305 (2002), 53–74, arXiv version, arXiv: quant-ph/0005055, (2000). doi: 10.1090/conm/305/05215.  Google Scholar

[6]

C. Carlet, Two new classes of bent functions, Eurocrypt 1993, Lecture Notes in Computer Science, volume 765 (1994), Springer, 77–101. doi: 10.1007/3-540-48285-7_8.  Google Scholar

[7]

K. Chakraborty and S. Maitra, Application of Grover's algorithm to check non-resiliency of a Boolean function, Cryptography and Communications, 8 (2016), 401-413.  doi: 10.1007/s12095-015-0156-3.  Google Scholar

[8]

D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proceedings of Royal Society London, 439 (1992), 553-558.  doi: 10.1098/rspa.1992.0167.  Google Scholar

[9]

J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D. thesis, U. of Maryland, 1974. Also see "Elementary Hadamard difference sets" in: Proc. Sixth Southeastern Conf. Combinatorics, Graph Theory, and Computing, Winnipeg, (1975). doi: 10.13016/M2MS3K194.  Google Scholar

[10]

L. K. Grover, A fast quantum mechanical algorithm for database search, In Proceedings of the Twenty-Eighth ACM Symposium on Theory of Computing (STOC'96), Association for Computing Machinery, New York, (1996), 212–219, arXiv version, arXiv: quant-ph/9605043, (1996). doi: 10.1145/237814.237866.  Google Scholar

[11]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, North-Holland, Amsterdam, 1977.  Google Scholar

[12]

C. S. Mukherjee, S. Maitra, V. Gaurav and D. Roy, On actual preparing Dicke states on a quantum computer, In IEEE Transactions on Quantum Engineering, 1 (2020), Art no. 3102517, 1-17, arXiv version, arXiv: 2007.01681, (2020). doi: 10.1109/TQE.2020.3041479.  Google Scholar

[13] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, 2011.   Google Scholar
[14]

M. Roetteler, Quantum algorithms for highly non-linear Boolean functions, In the Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (2010), 448–457, arXiv version, arXiv: 0811.3208, (2009). doi: 10.1137/1.9781611973075.37.  Google Scholar

[15]

P. Sarkar and S. Maitra, Cross-correlation analysis of cryptographically useful Boolean functions and S-boxes, Theory of Computing Systems, 35 (2002), 39-57.  doi: 10.1007/s00224-001-1019-1.  Google Scholar

[16]

P. Sarkar and S. Maitra, Construction of nonlinear resilient Boolean functions using 'small' affine functions, IEEE Transactions on Information Theory, 50 (2004), 2185-2193.  doi: 10.1109/TIT.2004.833366.  Google Scholar

[17]

D. R. Simon, On the power of quantum computation, SIAM Journal on Computing, 26 (1997), 1474-1483.  doi: 10.1137/S00975397962986371.  Google Scholar

[18]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, 26 (1997), 1484–1509, arXiv version, arXiv: quant-ph/9508027, (1996). doi: 10.1137/S0097539795293172.  Google Scholar

[19]

P. StanicaB. Mandal and S. Maitra, The connection between quadratic bent-negabent functions and the Kerdock code, Appl. Algebra Eng. Commun. Comput., 30 (2019), 387-401.  doi: 10.1007/s00200-019-00380-4.  Google Scholar

[20]

A. Tal, Towards optimal separations between quantum and randomized query complexities, IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), Durham, NC, USA, (2020), 228-239, arXiv version, arXiv: 1912.12561, (2019). doi: 10.1109/FOCS46700.2020.00030.  Google Scholar

[21]

G.-Z. Xiao and J. L. Massey, A spectral characterization of correlation immune combining functions, IEEE Transactions on Information Theory, 34 (1988), 569–571. doi: 10.1109/18.6037.  Google Scholar

show all references

References:
[1]

S. Aaronson, BQP and the polynomial hierarchy, In Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC '10), Association for Computing Machinery, New York, NY, USA, (2010), 141–150, arXiv version, arXiv: 0910.4698, (2009). doi: 10.1145/1806689.1806711.  Google Scholar

[2]

S. Aaronson and A. Ambainis, Forrelation: A problem that optimally separates quantum from classical computing, Siam J. Comput., 47 (2018), 982–1038. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC '15), Association for Computing Machinery, New York, NY, USA, DOI: https://doi.org/10.1145/2746539.2746547, (2015), 307–316, arXiv version, arXiv: 1411.5729, (2014). doi: 10.1137/15M1050902.  Google Scholar

[3]

N. Bansal and M. Sinha, k-forrelation optimally separates quantum and classical query complexity, In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC '21), (2021), 1303–1316. arXiv version, arXiv: 2008.07003, (2020). doi: 10.1145/3406325.3451040.  Google Scholar

[4]

D. Bera, S. Maitra and S. Tharrmashastha, Efficient quantum algorithms related to autocorrelation spectrum, In Progress in Cryptology-Indocrypt 2019, Lecture Notes in Computer Science, vol. 11898,415–432, Springer, (2019), arXiv version, arXiv: 1808.04448, (2019). doi: 10.1007/978-3-030-35423-7_21.  Google Scholar

[5]

G. Brassard, P. Hoyer, M. Mosca and A. Tapp, Quantum amplitude amplification and estimation, Quantum Computation and Quantum Information, Samuel J. Lomonaco, Jr. (editor), AMS Contemporary Mathematics, vol. 305 (2002), 53–74, arXiv version, arXiv: quant-ph/0005055, (2000). doi: 10.1090/conm/305/05215.  Google Scholar

[6]

C. Carlet, Two new classes of bent functions, Eurocrypt 1993, Lecture Notes in Computer Science, volume 765 (1994), Springer, 77–101. doi: 10.1007/3-540-48285-7_8.  Google Scholar

[7]

K. Chakraborty and S. Maitra, Application of Grover's algorithm to check non-resiliency of a Boolean function, Cryptography and Communications, 8 (2016), 401-413.  doi: 10.1007/s12095-015-0156-3.  Google Scholar

[8]

D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proceedings of Royal Society London, 439 (1992), 553-558.  doi: 10.1098/rspa.1992.0167.  Google Scholar

[9]

J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D. thesis, U. of Maryland, 1974. Also see "Elementary Hadamard difference sets" in: Proc. Sixth Southeastern Conf. Combinatorics, Graph Theory, and Computing, Winnipeg, (1975). doi: 10.13016/M2MS3K194.  Google Scholar

[10]

L. K. Grover, A fast quantum mechanical algorithm for database search, In Proceedings of the Twenty-Eighth ACM Symposium on Theory of Computing (STOC'96), Association for Computing Machinery, New York, (1996), 212–219, arXiv version, arXiv: quant-ph/9605043, (1996). doi: 10.1145/237814.237866.  Google Scholar

[11]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, North-Holland, Amsterdam, 1977.  Google Scholar

[12]

C. S. Mukherjee, S. Maitra, V. Gaurav and D. Roy, On actual preparing Dicke states on a quantum computer, In IEEE Transactions on Quantum Engineering, 1 (2020), Art no. 3102517, 1-17, arXiv version, arXiv: 2007.01681, (2020). doi: 10.1109/TQE.2020.3041479.  Google Scholar

[13] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, 2011.   Google Scholar
[14]

M. Roetteler, Quantum algorithms for highly non-linear Boolean functions, In the Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (2010), 448–457, arXiv version, arXiv: 0811.3208, (2009). doi: 10.1137/1.9781611973075.37.  Google Scholar

[15]

P. Sarkar and S. Maitra, Cross-correlation analysis of cryptographically useful Boolean functions and S-boxes, Theory of Computing Systems, 35 (2002), 39-57.  doi: 10.1007/s00224-001-1019-1.  Google Scholar

[16]

P. Sarkar and S. Maitra, Construction of nonlinear resilient Boolean functions using 'small' affine functions, IEEE Transactions on Information Theory, 50 (2004), 2185-2193.  doi: 10.1109/TIT.2004.833366.  Google Scholar

[17]

D. R. Simon, On the power of quantum computation, SIAM Journal on Computing, 26 (1997), 1474-1483.  doi: 10.1137/S00975397962986371.  Google Scholar

[18]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, 26 (1997), 1484–1509, arXiv version, arXiv: quant-ph/9508027, (1996). doi: 10.1137/S0097539795293172.  Google Scholar

[19]

P. StanicaB. Mandal and S. Maitra, The connection between quadratic bent-negabent functions and the Kerdock code, Appl. Algebra Eng. Commun. Comput., 30 (2019), 387-401.  doi: 10.1007/s00200-019-00380-4.  Google Scholar

[20]

A. Tal, Towards optimal separations between quantum and randomized query complexities, IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), Durham, NC, USA, (2020), 228-239, arXiv version, arXiv: 1912.12561, (2019). doi: 10.1109/FOCS46700.2020.00030.  Google Scholar

[21]

G.-Z. Xiao and J. L. Massey, A spectral characterization of correlation immune combining functions, IEEE Transactions on Information Theory, 34 (1988), 569–571. doi: 10.1109/18.6037.  Google Scholar

Figure 1.  Quantum circuit for implementing the $ 2 $-fold Forrelation problem using $ 2 $ queries
Figure 2.  Quantum circuit for implementing the $ 3 $-fold Forrelation problem using $ 3 $ sequential queries
Figure 3.  Quantum circuit for implementing the $ 3 $-fold Forrelation problem using $ 2 $ parallel queries
Figure 4.  Sampling probabilities of Walsh transform using different algorithms
Figure 5.  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

Article outline

Figures and Tables

[Back to Top]