Group theoretical formulation of a quantum partial search algorithm

Vladimir E. Korepin, Brenno C. Vallilo

Resultado de la investigación: Article

7 Citas (Scopus)

Resumen

Searching and sorting are used as a subroutine in many important algorithms. Quantum algorithm can find a target item in a database faster than any classical algorithm. One can trade accuracy for speed and find a part of the database (a block) containing the target item even faster; this is a partial search. For example, an exact address of the target item is given by a sequence of many bits, but we need to know only some of them. More generally, a partial search considers the problem in which a database is separated into several blocks and we want to find a block with the target item, not the target item itself. In this paper, we reformulate a quantum partial search algorithm in terms of group theory.

Idioma originalEnglish
Páginas (desde-hasta)783-793
Número de páginas11
PublicaciónProgress of Theoretical Physics
Volumen116
N.º5
DOI
EstadoPublished - nov 2006

Huella dactilar

formulations
subroutines
group theory
classifying

ASJC Scopus subject areas

  • Physics and Astronomy (miscellaneous)

Citar esto

@article{607f1be4da3d4fc2840ec98945ccf425,
title = "Group theoretical formulation of a quantum partial search algorithm",
abstract = "Searching and sorting are used as a subroutine in many important algorithms. Quantum algorithm can find a target item in a database faster than any classical algorithm. One can trade accuracy for speed and find a part of the database (a block) containing the target item even faster; this is a partial search. For example, an exact address of the target item is given by a sequence of many bits, but we need to know only some of them. More generally, a partial search considers the problem in which a database is separated into several blocks and we want to find a block with the target item, not the target item itself. In this paper, we reformulate a quantum partial search algorithm in terms of group theory.",
author = "Korepin, {Vladimir E.} and Vallilo, {Brenno C.}",
year = "2006",
month = "11",
doi = "10.1143/PTP.116.783",
language = "English",
volume = "116",
pages = "783--793",
journal = "Progress of Theoretical Physics",
issn = "0033-068X",
publisher = "Yukawa Institute for Theoretical Physics",
number = "5",

}

Group theoretical formulation of a quantum partial search algorithm. / Korepin, Vladimir E.; Vallilo, Brenno C.

En: Progress of Theoretical Physics, Vol. 116, N.º 5, 11.2006, p. 783-793.

Resultado de la investigación: Article

TY - JOUR

T1 - Group theoretical formulation of a quantum partial search algorithm

AU - Korepin, Vladimir E.

AU - Vallilo, Brenno C.

PY - 2006/11

Y1 - 2006/11

N2 - Searching and sorting are used as a subroutine in many important algorithms. Quantum algorithm can find a target item in a database faster than any classical algorithm. One can trade accuracy for speed and find a part of the database (a block) containing the target item even faster; this is a partial search. For example, an exact address of the target item is given by a sequence of many bits, but we need to know only some of them. More generally, a partial search considers the problem in which a database is separated into several blocks and we want to find a block with the target item, not the target item itself. In this paper, we reformulate a quantum partial search algorithm in terms of group theory.

AB - Searching and sorting are used as a subroutine in many important algorithms. Quantum algorithm can find a target item in a database faster than any classical algorithm. One can trade accuracy for speed and find a part of the database (a block) containing the target item even faster; this is a partial search. For example, an exact address of the target item is given by a sequence of many bits, but we need to know only some of them. More generally, a partial search considers the problem in which a database is separated into several blocks and we want to find a block with the target item, not the target item itself. In this paper, we reformulate a quantum partial search algorithm in terms of group theory.

UR - http://www.scopus.com/inward/record.url?scp=33847716637&partnerID=8YFLogxK

U2 - 10.1143/PTP.116.783

DO - 10.1143/PTP.116.783

M3 - Article

AN - SCOPUS:33847716637

VL - 116

SP - 783

EP - 793

JO - Progress of Theoretical Physics

JF - Progress of Theoretical Physics

SN - 0033-068X

IS - 5

ER -