Quantifying computational advantage of Grover’s algorithm with the trace speed

Abstract Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed an...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Valentin Gebhart, Luca Pezzè, Augusto Smerzi
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2021
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/d6b0b61ac3d9426e9f5be5d58874ebfa
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:d6b0b61ac3d9426e9f5be5d58874ebfa
record_format	dspace
spelling	oai:doaj.org-article:d6b0b61ac3d9426e9f5be5d58874ebfa2021-12-02T14:12:43ZQuantifying computational advantage of Grover’s algorithm with the trace speed10.1038/s41598-020-80153-z2045-2322https://doaj.org/article/d6b0b61ac3d9426e9f5be5d58874ebfa2021-01-01T00:00:00Zhttps://doi.org/10.1038/s41598-020-80153-zhttps://doaj.org/toc/2045-2322Abstract Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover’s search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.Valentin GebhartLuca PezzèAugusto SmerziNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 11, Iss 1, Pp 1-7 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Valentin Gebhart Luca Pezzè Augusto Smerzi Quantifying computational advantage of Grover’s algorithm with the trace speed
description	Abstract Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover’s search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.
format	article
author	Valentin Gebhart Luca Pezzè Augusto Smerzi
author_facet	Valentin Gebhart Luca Pezzè Augusto Smerzi
author_sort	Valentin Gebhart
title	Quantifying computational advantage of Grover’s algorithm with the trace speed
title_short	Quantifying computational advantage of Grover’s algorithm with the trace speed
title_full	Quantifying computational advantage of Grover’s algorithm with the trace speed
title_fullStr	Quantifying computational advantage of Grover’s algorithm with the trace speed
title_full_unstemmed	Quantifying computational advantage of Grover’s algorithm with the trace speed
title_sort	quantifying computational advantage of grover’s algorithm with the trace speed
publisher	Nature Portfolio
publishDate	2021
url	https://doaj.org/article/d6b0b61ac3d9426e9f5be5d58874ebfa
work_keys_str_mv	AT valentingebhart quantifyingcomputationaladvantageofgroversalgorithmwiththetracespeed AT lucapezze quantifyingcomputationaladvantageofgroversalgorithmwiththetracespeed AT augustosmerzi quantifyingcomputationaladvantageofgroversalgorithmwiththetracespeed
_version_	1718391814367477760

Quantifying computational advantage of Grover’s algorithm with the trace speed

Ejemplares similares