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

236
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

Suggestions

OpenMETU
Core

A new likelihood approach to autonomous multiple model estimation Söken, Halil Ersin (Elsevier BV, 2020-04-01) This paper presents an autonomous multiple model (AMM) estimation algorithm for hybrid systems with sudden changes in their parameters. Estimates of Kalman filters (KFs) that are tuned and employed for different system modes are merged based on a newly defined likelihood function without any necessity for filter interaction. The proposed likelihood function is composed of two measures, the filter agility measure and the steady-state error measure. These measures are derived based on filter adaptation rules....
A Hierarchical Partitioning Strategy for an Efficient Parallelization of the Multilevel Fast Multipole Algorithm Ergül, Özgür Salih (Institute of Electrical and Electronics Engineers (IEEE), 2009-06-01) We present a novel hierarchical partitioning strategy for the efficient parallelization of the multilevel fast multipole algorithm (MLFMA) on distributed-memory architectures to solve large-scale problems in electromagnetics. Unlike previous parallelization techniques, the tree structure of MLFMA is distributed among processors by partitioning both clusters and samples of fields at each level. Due to the improved load-balancing, the hierarchical strategy offers a higher parallelization efficiency than previ...
A spectral collocation algorithm for two-point boundary value problem in fiber Raman amplifier equations Tarman, Işık Hakan (Elsevier BV, 2009-04-15) A novel algorithm implementing Chebyshev spectral collocation (pseudospectral) method in combination with Newton's method is proposed for the nonlinear two-point boundary value problem (BVP) arising in solving propagation equations in fiber Raman amplifier. Moreover, an algorithm to train the known linear solution for use as a starting solution for the Newton iteration is proposed and successfully implemented. The exponential accuracy obtained by the proposed Chebyshev pseudospectral method is demonstrated ...
New Prediction for Extended Targets With Random Matrices Granstrom, Karl; Orguner, Umut (Institute of Electrical and Electronics Engineers (IEEE), 2014-04-01) This paper presents a new prediction update for extended targets whose extensions are modeled as random matrices. The prediction is based on several minimizations of the Kullback-Leibler divergence (KL-div) and allows for a kinematic state dependent transformation of the target extension. The results show that the extension prediction is a significant improvement over the previous work carried out on the topic.
Hierarchical parallelisation strategy for multilevel fast multipole algorithm in computational electromagnetics Ergül, Özgür Salih (Institution of Engineering and Technology (IET), 2008-01-03) A hierarchical parallelisation of the multilevel fast multipole algorithm (MLFMA) for the efficient solution of large-scale problems in computational electromagnetics is presented. The tree structure of MLFMA is distributed among the processors by partitioning both the clusters and the samples of the fields appropriately for each level. The parallelisation efficiency is significantly improved compared to previous approaches, where only the clusters or only the fields are partitioned in a level.

Citation Formats

K. Uyanik and S. Turgut, “A new sure-success generalization of Grover iteration and its application to weight decision problem of Boolean functions,” QUANTUM INFORMATION PROCESSING, pp. 3395–3409, 2013, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/41798.