From orthogonal projections to a generalized quantum search

A quantum algorithm with certainty is introduced in order to find a marked pre-image of an element which is known to be in the image domain of an orthogonal projection operator. The analysis of our algorithm is made by using properties of the Moebius transformations acting on the complex projective...

Full description

Saved in:
Bibliographic Details
Published in:Quantum information processing 2013, Vol.12 (1), p.1-20
Main Authors: Bautista-Ramos, César, Guillén-Galván, Carlos, Rangel-Huerta, Alejandro
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Cryptography
Data Structures and Information Theory
Exact sciences and technology
Information systems. Data bases
Information, signal and communications theory
Mathematical Physics
Memory organisation. Data processing
Physics
Physics and Astronomy
Quantum Computing
Quantum Information Technology
Quantum Physics
Signal and communications theory
Software
Spintronics
Telecommunications and information theory
Theoretical computing
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!
Description
Summary:A quantum algorithm with certainty is introduced in order to find a marked pre-image of an element which is known to be in the image domain of an orthogonal projection operator. The analysis of our algorithm is made by using properties of the Moebius transformations acting on the complex projective line. This new algorithm closely resembles the quantum amplitude amplification algorithm, however it is proven that our algorithm is a proper generalization of the latter (with generalized phases), in such a way that the quantum search engine of the main operator of quantum amplification is included as a particular case. In order to show that there exist search problems that can be solved by our proposal but cannot be by applying the quantum amplitude amplification algorithm, we modify our algorithm as a cryptographic authentification protocol. This protocol results to be robust enough against attacks based on the quantum amplitude amplification algorithm. As a byproduct, we show a condition where it is impossible to find exactly a pre-image of an orthoghonal projection. This result generalizes the fact that, it is impossible to find a target state exactly by using quantum amplification on a three dimensional invariant subspace.
ISSN:1570-0755
1573-1332
DOI:10.1007/s11128-011-0355-6