We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A quantum algorithm to estimate the Gowers U2 norm and linearity testing of Boolean functions.
- Authors
Jothishwaran, C. A.; Tkachenko, Anton; Gangopadhyay, Sugata; Riera, Constanza; Stănică, Pantelimon
- 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 ϵ -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.
- Subjects
ALGORITHMS; BOOLEAN functions
- Publication
Quantum Information Processing, 2020, Vol 19, Issue 9, pN.PAG
- ISSN
1570-0755
- Publication type
Article
- DOI
10.1007/s11128-020-02817-z