Quantum algorithm for the finding of Boolean function's linear structures
Authors:
Preprint
Abstract
We present a quantum algorithm for seeking the linear structures of a Boolean function based on a generalized Bernstein-Vazirani's algorithm and the Simon's algorithm. Bernstein-Vazirani's original algorithm can identify the linear Boolean functions with only one query for a certainty. However, if the function f given to the oracle is not a linear one, the run of the Bernstein- Vazirani algorithm can only result in a vector related to the Walsh spectrum of f. Based on this result and the idea of the Simon's algorithm, we con- struct an efficient quantum algorithm for finding the linear structures of some Boolean functions.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Quantum algorithms for testing and learning Boolean functionsMathematical Structures in Computer Science, 2013
- Quantum lower bounds by polynomialsJournal of the ACM, 2001
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997