A new sure-success generalization of Grover iteration and its application to weight decision problem of Boolean functions

Date

2013-11-01

Author

Uyanik, K.
Turgut, Sadi

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

4
views

0
downloads

In two recent papers, a sure-success version of the Grover iteration has been applied to solve the weight decision problem of a Boolean function and it is shown that it is quadratically faster than any classical algorithm (Braunstein et al. in J Phys A Math Theor 40:8441, 2007; Choi and Braunstein in Quantum Inf Process 10:177, 2011). In this paper, a new approach is proposed to generalize the Grover's iteration so that it becomes exact and its application to the same problem is studied. The regime where a small number of iterations is applied is the main focus of this work. This task is accomplished by presenting the conditions on the decidability of the weights where the decidability problem is reduced to a system of algebraic equations of a single variable. Thus, it becomes easier to decide on distinguishability by solving these equations analytically and, if not possible, numerically. In addition, it is observed that the number of iterations scale as the square root of the iteration number of the corresponding classical probabilistic algorithms.

Subject Keywords

Signal Processing, Theoretical Computer Science, Modelling and Simulation, Electrical and Electronic Engineering, Electronic, Optical and Magnetic Materials, Statistical and Nonlinear Physics

URI

https://hdl.handle.net/11511/41798

Collections

Department of Physics, Article