We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Quantum algorithms on Walsh transform and Hamming distance for Boolean functions.
- Authors
Xie, Zhengwei; Qiu, Daowen; Cai, Guangya
- Abstract
Walsh spectrum or Walsh transform is an alternative description of Boolean functions. In this paper, we explore quantum algorithms to approximate the absolute value of Walsh transform Wf<inline-graphic></inline-graphic> at a single point z0<inline-graphic></inline-graphic> (i.e., |Wf(z0)|<inline-graphic></inline-graphic>) for n-variable Boolean functions with probability at least 8π2<inline-graphic></inline-graphic> using the number of O(1|Wf(z0)|ε)<inline-graphic></inline-graphic> queries, promised that the accuracy is ε<inline-graphic></inline-graphic>, while the best known classical algorithm requires O(2n)<inline-graphic></inline-graphic> queries. The Hamming distance between Boolean functions is used to study the linearity testing and other important problems. We take advantage of Walsh transform to calculate the Hamming distance between two n-variable Boolean functions f and g using O(1) queries in some cases. Then, we exploit another quantum algorithm which converts computing Hamming distance between two Boolean functions to quantum amplitude estimation (i.e., approximate counting). If Ham(f,g)=t≠0<inline-graphic></inline-graphic>, we can approximately compute Ham(f, g) with probability at least 23<inline-graphic></inline-graphic> by combining our algorithm and Approx-Count(f,ε)algorithm<inline-graphic></inline-graphic> using the expected number of Θ(N(⌊εt⌋+1)+t(N-t)⌊εt⌋+1)<inline-graphic></inline-graphic> queries, promised that the accuracy is ε<inline-graphic></inline-graphic>. Moreover, our algorithm is optimal, while the exact query complexity for the above problem is Θ(N)<inline-graphic></inline-graphic> and the query complexity with the accuracy ε<inline-graphic></inline-graphic> is O(1ε2N/(t+1))<inline-graphic></inline-graphic> in classical algorithm, where N=2n<inline-graphic></inline-graphic>. Finally, we present three exact quantum query algorithms for two promise problems on Hamming distance using O(1) queries, while any classical deterministic algorithm solving the problem uses Ω(2n)<inline-graphic></inline-graphic> queries.
- Subjects
BOOLEAN functions; HAMMING distance; ALGEBRAIC immunity; QUANTUM correlations; QUANTUM computing
- Publication
Quantum Information Processing, 2018, Vol 17, Issue 6, p1
- ISSN
1570-0755
- Publication type
Article
- DOI
10.1007/s11128-018-1885-y