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


Uyanik K., TURGUT S.

QUANTUM INFORMATION PROCESSING, cilt.12, sa.11, ss.3395-3409, 2013 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 12 Sayı: 11
  • Basım Tarihi: 2013
  • Doi Numarası: 10.1007/s11128-013-0606-9
  • Dergi Adı: QUANTUM INFORMATION PROCESSING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.3395-3409
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.