关键词: BV算法, 向量值函数, 线性结构, 高概率差分

Abstract: The Bernstein-Vazirani (BV) algorithm was originally used to solve the coefficients of linear functions, and later researchers proposed an algorithm using the BV algorithm to solve the linear structure of a vector valued function. Firstly, we extend the original problem of solving the linear structure of vector-valued functions, and propose a definition of "weak linear structure". On this basis, we analyze several extensions of linear structure problem and extend the application of BV algorithm. Secondly, based on the extended linear structure problem, we propose a new quantum algorithm which can be applied to find the high-probability difference of block cipher in quantum environment. Compared with the existing algorithm, the proposed algorithm can obtain multiple differences with high probability at one time, and the time complexity can be reduced to .

Key words: BV algorithm, vector-valued function, linear structure, high-probability difference