Physics – Quantum Physics
Scientific paper
2011-06-23
Physical Review A 84, 062329 (2011)
Physics
Quantum Physics
Replaced with published version
Scientific paper
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.
Andersson Erika
Hillery Mark
No associations
LandOfFree
Quantum tests for the linearity and permutation invariance of Boolean functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum tests for the linearity and permutation invariance of Boolean functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum tests for the linearity and permutation invariance of Boolean functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-393363