Entangling and disentangling in Grover's search algorithm

J 2019

Entangling and disentangling in Grover's search algorithm

PAN, Minghua; Daowen QIU; Paulo MATEUS a Jozef GRUSKA

Základní údaje

Originální název

Entangling and disentangling in Grover's search algorithm

Autoři

PAN, Minghua; Daowen QIU; Paulo MATEUS a Jozef GRUSKA (703 Slovensko, domácí)

Vydání

Theoretical Computer Science, Amsterdam, Elsevier, 2019, 0304-3975

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.747

Kód RIV

RIV/00216224:14330/19:00113867

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.1016/j.tcs.2018.10.001

UT WoS

000469907500009

EID Scopus

2-s2.0-85055153956

Klíčová slova anglicky

Entanglement dynamics; Grover's search algorithm; Geometric measure of entanglement

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 5. 11. 2021 14:39, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Entanglement is believed to be crucial in making quantum algorithms more powerful than their classical counterparts for certain computational tasks. In Grover's search algorithm, the Grover's operator iteration G can be decomposed into two basic operators, i.e., G = RO, where O is so called the Oracle operator and R is the Reflection operator. To probe the production/depletion of entanglement from basic operator level, we investigate the roles the Oracle and the Reflection operators play in the entanglement dynamics during Grover's search algorithm application. Using geometric measure of entanglement (GME), we show that the Oracle operator is an entangling operator which almost always produces (increases) entanglement while the Reflection operator is a disentangling operator which mainly depletes (decreases) entanglement. We explicitly demonstrate that there exists a turning point during the Grover's iteration application with the following properties. Before that turning point, the entanglement is almost always increased when the Oracle operator is applied, and the effect of the Reflection operator on the level of entanglement can be almost ignored. However, after the turning point, both the Oracle and the Reflection operators play important roles to the entanglement, more exactly, the Reflection operator significantly decreases entanglement while the Oracle operator increases entanglement. All these results are carefully demonstrated.

Citovat

PAN, Minghua; Daowen QIU; Paulo MATEUS a Jozef GRUSKA. Entangling and disentangling in Grover's search algorithm. Theoretical Computer Science. Amsterdam: Elsevier, 2019, roč. 773, 14 June 2019, s. 138-152. ISSN 0304-3975. Dostupné z: https://doi.org/10.1016/j.tcs.2018.10.001.

@article{1652880,
   author = {Pan, Minghua and Qiu, Daowen and Mateus, Paulo and Gruska, Jozef},
   article_location = {Amsterdam},
   article_number = {14 June 2019},
   doi = {https://doi.org/10.1016/j.tcs.2018.10.001},
   keywords = {Entanglement dynamics; Grover's search algorithm; Geometric measure of entanglement},
   language = {eng},
   issn = {0304-3975},
   journal = {Theoretical Computer Science},
   title = {Entangling and disentangling in Grover's search algorithm},
   url = {http://dx.doi.org/10.1016/j.tcs.2018.10.001},
   volume = {773},
   year = {2019}
}

TY  - JOUR
ID  - 1652880
AU  - Pan, Minghua - Qiu, Daowen - Mateus, Paulo - Gruska, Jozef
PY  - 2019
TI  - Entangling and disentangling in Grover's search algorithm
JF  - Theoretical Computer Science
VL  - 773
IS  - 14 June 2019
SP  - 138-152
EP  - 138-152
PB  - Elsevier
SN  - 03043975
KW  - Entanglement dynamics
KW  - Grover's search algorithm
KW  - Geometric measure of entanglement
UR  - http://dx.doi.org/10.1016/j.tcs.2018.10.001
L2  - http://dx.doi.org/10.1016/j.tcs.2018.10.001
N2  - Entanglement is believed to be crucial in making quantum algorithms more powerful than their classical counterparts for certain computational tasks. In Grover's search algorithm, the Grover's operator iteration G can be decomposed into two basic operators, i.e., G = RO, where O is so called the Oracle operator and R is the Reflection operator. To probe the production/depletion of entanglement from basic operator level, we investigate the roles the Oracle and the Reflection operators play in the entanglement dynamics during Grover's search algorithm application. Using geometric measure of entanglement (GME), we show that the Oracle operator is an entangling operator which almost always produces (increases) entanglement while the Reflection operator is a disentangling operator which mainly depletes (decreases) entanglement. We explicitly demonstrate that there exists a turning point during the Grover's iteration application with the following properties. Before that turning point, the entanglement is almost always increased when the Oracle operator is applied, and the effect of the Reflection operator on the level of entanglement can be almost ignored. However, after the turning point, both the Oracle and the Reflection operators play important roles to the entanglement, more exactly, the Reflection operator significantly decreases entanglement while the Oracle operator increases entanglement. All these results are carefully demonstrated.
ER  -

PAN, Minghua; Daowen QIU; Paulo MATEUS a Jozef GRUSKA. Entangling and disentangling in Grover's search algorithm. \textit{Theoretical Computer Science}. Amsterdam: Elsevier, 2019, roč.~773, 14 June 2019, s.~138-152. ISSN~0304-3975. Dostupné z: https://doi.org/10.1016/j.tcs.2018.10.001.

Přehled o publikaci