Loading…
A new sure-success generalization of Grover iteration and its application to weight decision problem of Boolean functions
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...
Saved in:
Published in: | Quantum information processing 2013-11, Vol.12 (11), p.3395-3409 |
---|---|
Main Authors: | , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | 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. |
---|---|
ISSN: | 1570-0755 1573-1332 |
DOI: | 10.1007/s11128-013-0606-9 |