Back to Search
Start Over
Quantum and Randomised Algorithms for Non-linearity Estimation
- Source :
- ACM Transactions on Quantum Computing. 2:1-27
- Publication Year :
- 2021
- Publisher :
- Association for Computing Machinery (ACM), 2021.
-
Abstract
- Non-linearity of a Boolean function indicates how far it is from any linear function. Despite there being several strong results about identifying a linear function and distinguishing one from a sufficiently non-linear function, we found a surprising lack of work on computing the non-linearity of a function. The non-linearity is related to the Walsh coefficient with the largest absolute value; however, the naive attempt of picking the maximum after constructing a Walsh spectrum requires $\Theta(2^n)$ queries to an $n$-bit function. We improve the scenario by designing highly efficient quantum and randomised algorithms to approximate the non-linearity allowing additive error, denoted $\lambda$, with query complexities that depend polynomially on $\lambda$. We prove lower bounds to show that these are not very far from the optimal ones. The number of queries made by our randomised algorithm is linear in $n$, already an exponential improvement, and the number of queries made by our quantum algorithm is surprisingly independent of $n$. Our randomised algorithm uses a Goldreich-Levin style of navigating all Walsh coefficients and our quantum algorithm uses a clever combination of Deutsch-Jozsa, amplitude amplification and amplitude estimation to improve upon the existing quantum versions of the Goldreich-Levin technique.<br />Comment: Accepted in ACM Transactions on Quantum Computing
- Subjects :
- FOS: Computer and information sciences
Quantum Physics
Linear function (calculus)
Computer Science - Cryptography and Security
Computer science
FOS: Physical sciences
020206 networking & telecommunications
Absolute value
02 engineering and technology
General Medicine
Function (mathematics)
Computer Science::Computational Complexity
01 natural sciences
Exponential function
Amplitude amplification
0103 physical sciences
0202 electrical engineering, electronic engineering, information engineering
Quantum algorithm
Quantum Physics (quant-ph)
010306 general physics
Boolean function
Cryptography and Security (cs.CR)
Algorithm
Quantum
Subjects
Details
- ISSN :
- 26436817 and 26436809
- Volume :
- 2
- Database :
- OpenAIRE
- Journal :
- ACM Transactions on Quantum Computing
- Accession number :
- edsair.doi.dedup.....c32938e6b71ed772fd245e64ed4031b6