Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Information Processing

Polynomial-time quantum algorithms for finding the linear structures of Boolean function

Wanqing Wu, Huanguo Zhang, Houzhen Wang, Shaowu Mao

Published Feb 3, 2015• 6 citations
Publisher
DOI
10.1007/s11128-015-0940-1

Related papers

Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms

Raitis Ozols, Rūsiņš Freivalds, Jevgeņijs Ivanovs +5 more

Lecture notes in computer science•Jan 1, 2005•3 citations

Quantum algorithms to check Resiliency, Symmetry and Linearity of a Boolean function

Kaushik Chakraborty, Anupam Chattopadhyay, Subhamoy Maitra

•Jan 1, 2013•0 citations

A quantum algorithm to approximate the linear structures of Boolean functions

Hongwei Li, Li Yang

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δfof a Boolean functionf. Smaller differential uniformity is, shorter time is needed.

arXiv:1404.0611•Mathematical Structures in Computer Science•Feb 9, 2016•27 citations

Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions

Xuexuan Hao, Fengrong Zhang, Shixiong Xia +1 more

Quantum Information Processing•Jul 30, 2020•7 citations

Investigating the linear structure of Boolean functions based on Simon's period-finding quantum algorithm

Li Yang, Hongwei Li

It is believed that there is no efficient classical algorithm to determine the linear structure of Boolean function. We investigate an extension of Simon's period-finding quantum algorithm, and propose an efficient quantum algorithm to determine the linear structure of Boolean function.

arXiv:1306.2008•Jun 9, 2013•3 citations

A quantum algorithm for approximating the influences of Boolean functions and its applications

Hongwei Li, Li Yang

arXiv:1409.1416•Quantum Information Processing•Mar 4, 2015•32 citations
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δfof a Boolean functionf. Smaller differential uniformity is, shorter time is needed.