Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

A quantum algorithm to estimate the Gowers \(U_2\) norm and linearity testing of Boolean functions

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

We propose a quantum algorithm to estimate the Gowers \(U_2\) norm of a Boolean function, and extend it into a second algorithm to distinguish between linear Boolean functions and Boolean functions that are \(\epsilon \)-far from the set of linear Boolean functions, which seems to perform better than the classical BLR algorithm. Finally, we outline an algorithm to estimate Gowers \(U_3\) norms of Boolean functions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Bera, D., Maitra, S., Tharrmashastha, S.: Efficient quantum algorithms related to autocorrelation spectrum. In: Hao, F., Ruj, S., Gupta, S.S. (eds.) Progress in Cryptology—INDOCRYPT 2019—20th International Conference on Cryptology in India, Hyderabad, India, December 15–18, 2019, LNCS 11898, pp. 415–432. Springer (2019). https://doi.org/10.1007/978-3-030-35423-7_21

  2. Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47(3), 549–595 (1993)

    Article  MathSciNet  Google Scholar 

  3. Carlet, C.: Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications. IEEE Trans. Inf. Theory 54(3), 1262–1272 (2008)

    Article  MathSciNet  Google Scholar 

  4. Chen, V.Y.: The Gowers’ norm in the testing of Boolean functions. Ph.D. thesis, Massachusetts Institute of Technology (2009)

  5. Cusick, T., Stănică, P.: Cryptographic Boolean Functions and Applications, 2nd edn. Elsevier, Amsterdam (2017)

    MATH  Google Scholar 

  6. Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. Ser. A 439, 553–558 (1992)

    Article  ADS  MathSciNet  Google Scholar 

  7. Goldreich, O., Levin, L.: A hard-core predicate for all one-way functions. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 25–32

  8. Gowers, W.T.: A new proof of Szemerédi’s theorem. Geom. Funct. Anal. GAFA 11(3), 465–588 (2001)

    Article  Google Scholar 

  9. Green, B., Tao, T.: An inverse theorem for the Gowers \({U}_3\) norm. Proc. Edinb. Math. Soc. 51, 75–153 (2008)

    Article  Google Scholar 

  10. Hillery, M., Andersson, E.: Quantum tests for the linearity and permutation invariance of Boolean functions. Phys. Rev. A 84, 062329 (2011). https://doi.org/10.1103/PhysRevA.84.062329

    Article  ADS  Google Scholar 

  11. Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58, 13–30 (1963)

    Article  MathSciNet  Google Scholar 

  12. Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transforms and learnability. J. ACM 40(3), 607–620 (1993)

    Article  MathSciNet  Google Scholar 

  13. Maitra, S., Mukhopadhyay, P.: The Deutsch–Jozsa algorithm revisited in the domain of cryptographically significant Boolean functions. Int. J. Quantum Inf. 03(02), 359–370 (2005)

    Article  Google Scholar 

  14. Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information, 10th edn. Cambridge University Press, Cambridge (2011)

    MATH  Google Scholar 

  15. O’Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge (2014)

    Book  Google Scholar 

  16. Rieffel, E., Polak, W.: Quantum Computing: A Gentle Introduction, 1st edn. The MIT Press, Cambridge (2011)

    MATH  Google Scholar 

  17. Valiant, L.: A theory of learnable. Commun. ACM 27(11), 1134–1142 (1984)

    Article  Google Scholar 

  18. Xie, Z., Qiu, D., Cai, G.: Quantum algorithms on Walsh transform and Hamming distance for Boolean functions. Quantum Inf. Process. 17, 139 (2018)

    Article  ADS  MathSciNet  Google Scholar 

Download references

Acknowledgements

Research of C. A. Jothishwaran and Sugata Gangopadhyay is a part of the project “Design and Development of Quantum Computing Toolkit and Capacity Building” sponsored by the Ministry of Electronics and Information Technology (MeitY) of the Government of India.

Author information

Authors and Affiliations

  1. Department of Electronics and Communication Engineering, Indian Institute of Technology Roorkee, Roorkee, 247667, India

    C. A. Jothishwaran

  2. Department of Computer Science and Engineering, Indian Institute of Technology Roorkee, Roorkee, 247667, India

    Sugata Gangopadhyay

  3. Department of Computer Science, Electrical Engineering and Mathematical Sciences, Western Norway University of Applied Sciences, 5020, Bergen, Norway

    Anton Tkachenko & Constanza Riera

  4. Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA, 93943-5216, USA

    Pantelimon Stănică

Authors
  1. C. A. Jothishwaran
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anton Tkachenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sugata Gangopadhyay
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Constanza Riera
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Pantelimon Stănică
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sugata Gangopadhyay.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix: Generalization to higher Gowers norms

Appendix: Generalization to higher Gowers norms

The same technique can be used for other Gowers norms. For instance, we can apply the unitary transformation \(H_n^{\otimes 4}\circ \mathfrak D_F^3\) to the state \(2^{-2n}\sum _{x\in {\mathbb {F}}_2^n}\sum _{a\in {\mathbb {F}}_2^n}\sum _{b\in {\mathbb {F}}_2^n}\sum _{c\in {\mathbb {F}}_2^n}|x\rangle |a\rangle |b\rangle |c\rangle \), where, with notation \(M_i^j=\mathrm{MCNOT}_i^j\) and \(U_F^3=U_F\otimes I\otimes I\otimes I\),

$$\begin{aligned} \mathfrak D_F^3= & {} M_1^3\circ U_F^3\circ M_1^3\circ M_1^4\circ U_F^3\circ M_1^3\circ U_F^3\circ M_1^2\circ U_F^3\circ M_1^4\\&\circ U_F^3\circ M_1^3\circ U_F^3\circ M_1^2\circ U_F^3. \end{aligned}$$

We obtain thus the state \(\sum _{a^{\prime },b^{\prime },b^{\prime },x^{\prime }\in {\mathbb {F}}_2^n}2^{-4n} \sum _{a,b,c,x\in {\mathbb {F}}_2^n}(-1)^{\varDelta _{a,b,c}F(x)}|x,a,b,c\rangle \). Then, \(\mathrm{Pr}[x^{\prime }=a^{\prime }=b^{\prime }=c^{\prime }=0_n]=\left( 2^{-4n}\sum _{a,b,c,x\in {\mathbb {F}}_2^n}(-1)^{\varDelta _{a,b,c}F(x)}\right) ^2\), and, using (11), \(\mathrm{Pr}[x^{\prime }=a^{\prime }=b^{\prime }=c^{\prime }=0_n]= \left( \Vert f\Vert _{U_3}^8\right) ^2=\Vert f\Vert _{U_3}^{16}\).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jothishwaran, C.A., Tkachenko, A., Gangopadhyay, S. et al. A quantum algorithm to estimate the Gowers \(U_2\) norm and linearity testing of Boolean functions. Quantum Inf Process 19, 311 (2020). https://doi.org/10.1007/s11128-020-02817-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-020-02817-z

Keywords

Search

Navigation