A Fast Quantum Algorithm for the Affine Boolean Function Identification
arXiv:1407.6402
Abstract
Bernstein-Vazirani algorithm (the one-query algorithm) can identify a completely specified linear Boolean function using a single query to the oracle with certainty. The first aim of the paper is to show that if the provided Boolean function is affine, then one more query to the oracle (the two-query algorithm) is required to identify the affinity of the function with certainty. The second aim of the paper is to show that if the provided Boolean function is incompletely defined, then the one-query and the two-query algorithms can be used as bounded-error quantum polynomial algorithms to identify certain classes of incompletely defined linear and affine Boolean functions respectively with probability of success at least .
arXiv comment12 pages, 3 figures
References in corpus (5)
- Quantum Mechanics helps in searching for a needle in a haystack
- A quantum algorithm to approximate the linear structures of Boolean functions
- Quantum tests for the linearity and permutation invariance of Boolean functions
- Quantum algorithms for testing Boolean functions
- Improved quantum test for linearity of a Boolean function