Quantifying computational advantage of Grover´s algorithm with the trace speed
Anno: 2021
Autori: Gebhart V.; Pezzè L.; Smerzi A.
Affiliazione autori: INO CNR, QSTAR, Largo Enrico Fermi 2, I-50125 Florence, Italy; LENS, Largo Enrico Fermi 2, I-50125 Florence, Italy; Univ Napoli Federico II, Via Cinthia 21, I-80126 Naples, Italy.
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.
Giornale/Rivista: SCIENTIFIC REPORTS
Volume: 11 (1) Da Pagina: 1288-1 A: 1288-7
Maggiori informazioni: The authors acknowledge financial support from the European Union´s Horizon 2020 research and innovation programme-Qombs Project, FET Flagship on Quantum Technologies Grant no. 820419.Parole chiavi: quantum algorithmsDOI: 10.1038/s41598-020-80153-zCitazioni: 7dati da “WEB OF SCIENCE” (of Thomson Reuters) aggiornati al: 2025-05-04Riferimenti tratti da Isi Web of Knowledge: (solo abbonati) Link per visualizzare la scheda su IsiWeb: Clicca quiLink per visualizzare la citazioni su IsiWeb: Clicca qui
