Show/Hide Menu
Hide/Show Apps
anonymousUser
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Frequently Asked Questions
Frequently Asked Questions
Communities & Collections
Communities & Collections
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
Journal
QUANTUM INFORMATION PROCESSING
DOI
https://doi.org/10.1007/s11128-013-0606-9
Collections
Department of Physics, Article