Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-03T01:28:50.479Z Has data issue: false hasContentIssue false
  • English
  • Français

A quantum algorithm to approximate the linear structures of Boolean functions

Published online by Cambridge University Press:  09 February 2016

HONGWEI LI  and
LI YANG
HONGWEI LI
Affiliation:
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China Email: [email protected] School of Mathematics and Statistics, Henan Institute of Education, Zhengzhou 450046, Henan, China Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing 100093, China Email: [email protected] University of Chinese Academy of Sciences, Beijing 100049, China
LI YANG*
Affiliation:
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China Email: [email protected] Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing 100093, China Email: [email protected]
*
‖Corresponding author.
Get access Rights & Permissions [Opens in a new window]

Abstract

A quantum algorithm to determine approximations of linear structures of Boolean functions is presented and analysed. Similar results have already been published (see Simon's algorithm) but only for some promise versions of the problem, and it has been shown that no exponential quantum speedup can be obtained for the general (no promise) version of the problem. In this paper, no additional promise assumptions are made. The approach presented is based on the method used in the Bernstein–Vazirani algorithm to identify linear Boolean functions and on ideas from Simon's period finding algorithm. A proper combination of these two approaches results here to a polynomial-time approximation to the linear structures set. Specifically, we show how the accuracy of the approximation with high probability changes according to the running time of the algorithm. Moreover, we show that the time required for the linear structure determine problem with high success probability is related to so called relative differential uniformity δf of a Boolean function f. Smaller differential uniformity is, shorter time is needed.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 28 , Issue 1 , January 2018 , pp. 1 - 13
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aharonov, D., Jones, V. and Landau, Z. (2009). A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica 55 395–421. A primary version in STOC 2006 427–436.CrossRefGoogle Scholar
Beals, R., Buhrman, H., Cleve, R., Mosca, M. and Wolf, R.D. (2001). Quantum lower bound by polynomials. Journal of the ACM 48 (4) 778–797 (July). A primary version appeared in FOCS 1998, 352–361.CrossRefGoogle Scholar
Bernstein, E. and Vazirani, U. (1993). Quantum complexity theory. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing, ACM Press 11–20.Google Scholar
Brassard, G., Dupuis, F., Gambs, S. and Tapp, A. (2011). An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance. arXiv: 1106.4267v1 [quant-ph] 21 Jun. 2011.Google Scholar
Brassard, G. and Høyer, P. (1997). An exact quanum polynimial-time algorithm for Simon's problem. In: Proceedings of the 5th Israeli Symposium on the Theory of Computing Systems (ISTCS'97), 12–23.Google Scholar
Brassard, G., Høyer, P., Mosca, M. and Tapp, A. (2002). Quantum amplitude amplification and estimation. Contemporary Mathematics 305 53–74. Also at arXiv: quant-ph/0005055v1 15 May 2000.Google Scholar
Cleve, R., Ekert, A., Macchiavello, C. and Mosca, M. (1998). Quantum algorithms revisited. Proceedings of the Royal Society of London, Series A 454 339–354.Google Scholar
Connor, L. and Klapper, A. (1994). Algebraic nonlinearity and its applications to cryptography. Journal of Cryptology 7 (4) 213–227.Google Scholar
Deutsch, D. and Jozsa, R. (1992). Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London, Series A 439 553–558.Google Scholar
Drucker, A. and Wolf, R.D. (2011). Uniform approximation by (quantum) polynomials. Quantum Information and Computation 11 (3) 215–225. Also at Arxiv: 1008.1599 v3 [quant-ph] 14 Mar 2011.Google Scholar
Dubuc, S. (2001). Characterization of linear structures. Designs, Codes and Cryptography 22 (1) 33–45.Google Scholar
Feng, D.G. and Pei, D.Y. (1999). Introduction to Cryptography (in chinese), Science Press, Beijing.Google Scholar
Feng, D.G. and Xiao, G.Z. (1995). Character of linear structure of Boolean functions. Journal of Electronics (in Chinese) 17 (3) 324–329.Google Scholar
Floess, D., Andersson, E. and Hillery, M. (2013). Quantum algorithms for testing and learning Boolean functions. Mathematical Structures in Computer Science 23 (2) 386–398.Google Scholar
Hillery, M. and Anderson, E. (2011). Quantum tests for the linearity and permutation invariance of Boolean functions. Physical Review A 84 062329.Google Scholar
Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. American Statistical Association Journal 58 (301) 13–30 (March).Google Scholar
Kahn, J., Kalai, G. and Linial, N. (1988). The influence of variables on Boolean functions. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press 68–80.Google Scholar
Lai, X.J. (1995). Additive and linear structure of cryptographic functions. In: Fast Software Encryption, Lecture Notes in Computer Science, volume 1008, Springer-Verlag 75–85.Google Scholar
Nielsen, M.A. and Chuang, I.L. (2010). Quantum Computation and Quantum Information, Cambridge University Press.Google Scholar
Shor, P.W. (1997). Polynomial-time algorithm for prime factorization and discrete logarithms on quantum computer. SIAM Journal on Computing 26 1484–1509. A primary version appeared in FOCS 1994, 124–134.Google Scholar
Simon, D.R. (1997). On the Power of Quantum Computation. SIAM Journal on Computing 26 1474–1483.Google Scholar
O'Donnell, R. (2008). Some topics in analysis of Boolean functions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08), ACM Press, 569–578.Google Scholar