Quantum tests for the linearity and permutation invariance of Boolean functions
arXiv:1106.4831 · doi:10.1103/PhysRevA.84.062329
Abstract
The goal in function property testing is to determine whether a black-box Boolean function has a certain property or is epsilon-far from having that property. The performance of the algorithm is judged by how many calls need to be made to the black box in order to determine, with high probability, which of the two alternatives is the case. Here we present two quantum algorithms, the first to determine whether the function is linear and the second to determine whether it is symmetric (invariant under permutations of the arguments). Both require O(epsilon^{-2/3}) calls to the oracle, which is better than known classical algorithms. In addition, in the case of linearity testing, if the function is linear, the quantum algorithm identifies which linear function it is. The linearity test combines the Bernstein-Vazirani algorithm and amplitude amplification, while the test to determine whether a function is symmetric uses projective measurements and amplitude amplification.
Replaced with published version
References in corpus (3)
Cited by in corpus (12)
- A Survey of Quantum Property Testing
- Optimal quantum tomography of permutationally invariant qubits
- A quantum algorithm to approximate the linear structures of Boolean functions
- Testing Boolean Functions Properties
- Quantum and Randomised Algorithms for Non-linearity Estimation
- Quantum Proofs of Proximity
- A quantum algorithm to estimate the Gowers norm and linearity testing of Boolean functions
- Quantum algorithms for the Goldreich-Levin learning problem
- A quantum algorithm for approximating the influences of Boolean functions and its applications
- Using Bernstein-Vazirani Algorithm to Attack Block Ciphers
- Quantum differential cryptanalysis to the block ciphers
- A Fast Quantum Algorithm for the Affine Boolean Function Identification