1Facoltà di Matematica, Università di Bristol. n.linden@bristol.ac.uk
2QuSoft, CWI e Università di Amsterdam, Paesi Bassi. rdewolf@cwi.nl
Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.
Astratto
La trasformata quantistica di Fourier (QFT) è una primitiva chiave per il calcolo quantistico che viene tipicamente utilizzata come subroutine all'interno di un calcolo più ampio, ad esempio per la stima della fase. Pertanto, potremmo avere scarso controllo sullo stato immesso nel QFT. Pertanto, nell'implementare un buon QFT, possiamo immaginare che debba funzionare bene su stati di input arbitrari. $Verificare$ questo comportamento corretto nel caso peggiore di un'implementazione QFT sarebbe esponenzialmente difficile (nel numero di qubit) in generale, sollevando la preoccupazione che questa verifica sarebbe impossibile in pratica su qualsiasi sistema di dimensioni utili. In questo articolo dimostriamo che, in effetti, abbiamo solo bisogno di avere buone prestazioni $medie$-$casi$ della QFT per ottenere buone prestazioni $peggiori$-$casi$ per le attività chiave: stima della fase, ricerca del periodo e stima dell'ampiezza . Inoltre diamo una procedura molto efficiente per verificare questo comportamento richiesto nel caso medio della QFT.
Riepilogo popolare
► dati BibTeX
► Riferimenti
, Scott Aaronson e Patrick Rall. Conteggio quantistico approssimativo, semplificato. In Proceedings of 3rd Symposium on Simplicity in Algorithms (SOSA), pagine 24–32, 2020. arXiv:1908.10846.
https: / / doi.org/ 10.1137 / 1.9781611976014.5 mila
arXiv: 1908.10846
, Charles H. Bennett, Ethan Bernstein, Gilles Brassard e Umesh Vazirani. Punti di forza e di debolezza dell'informatica quantistica. SIAM Journal on Computing, 26 (5): 1510–1523, 1997. quant-ph / 9701001.
https: / / doi.org/ 10.1137 / S0097539796300933
arXiv: Quant-ph / 9701001
, Gilles Brassard, Peter Høyer, Michele Mosca e Alain Tapp. Amplificazione e stima dell'ampiezza quantistica. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 di AMS Contemporary Mathematics Series, pagine 53–74. 2002. quant-ph / 0005055.
https: / / doi.org/ 10.1090 / conm / 305 / 05215
arXiv: Quant-ph / 0005055
, Chi-Fang Chen e Fernando GSL Brandão. Concentrazione per errore Trotter. arXiv:2111.05324, 9 novembre 2021.
https:///doi.org/10.48550/arXiv.2111.05324
arXiv: 2111.05324
, Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Algoritmi quantistici rivisitati. In Proceedings of the Royal Society of London, volume A454, pagine 339–354, 1998. quant-ph/9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: Quant-ph / 9708016
, Don Ramaio. Una trasformata di Fourier approssimata utile nella fattorizzazione quantistica. Rapporto di ricerca IBM n. RC19642, quant-ph/0201067, 1994.
https:///doi.org/10.48550/arXiv.quant-ph/0201067
arXiv: Quant-ph / 0201067
, Marcus da Silva, Oliver Landon-Cardinal e David Poulin. Caratterizzazione pratica di dispositivi quantistici senza tomografia. Physical Review Letters, 107:210404, 2011. arXiv:1104.3835.
https: / / doi.org/ 10.1103 / PhysRevLett.107.210404
arXiv: 1104.3835
, Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud e Elham Kashefi. Certificazione quantistica e benchmarking. Nature Reviews Physics, 2:382–390, 2020. arXiv:1910.06343.
https://doi.org/10.1038/s42254-020-0186-4
arXiv: 1910.06343
, Steven T. Flammia e Yi-Kai Liu. Stima diretta della fedeltà da poche misurazioni di Pauli. Physical Review Letters, 106:230501, 2011. arXiv:1104.4695.
https: / / doi.org/ 10.1103 / PhysRevLett.106.230501
arXiv: 1104.4695
, András Gilyén, Srinivasan Arunachalam e Nathan Wiebe. Ottimizzazione degli algoritmi di ottimizzazione quantistica tramite un calcolo del gradiente quantistico più rapido. In Atti del 30° ACM-SIAM SODA, pagine 1425–1444, 2019. arXiv:1711.00465.
https: / / doi.org/ 10.1137 / 1.9781611975482.87 mila
arXiv: 1711.00465
, Lov K. Grover. Un veloce algoritmo di meccanica quantistica per la ricerca nel database. In Proceedings of 28th ACM STOC, pagine 212–219, 1996. quant-ph/9605043.
https: / / doi.org/ 10.1145 / 237814.237866 mila
arXiv: Quant-ph / 9605043
, András Gilyén, Yuan Su, Guang Hao Low e Nathan Wiebe. Trasformazione del valore singolare quantistico e oltre: miglioramenti esponenziali per l'aritmetica della matrice quantistica. In Atti del 51° ACM STOC, pagine 193–204, 2019. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366 mila
arXiv: 1806.01838
, Stephen P. Giordano. Algoritmo quantistico veloce per la stima del gradiente numerico. Physical Review Letters, 95:050501, 2005. quant-ph/0405146.
https: / / doi.org/ 10.1103 / PhysRevLett.95.050501
arXiv: Quant-ph / 0405146
, Alexey Yu. Kitaev. Misure quantistiche e problema dello stabilizzatore abeliano. quant-ph/9511026, 12 nov 1995.
https:///doi.org/10.48550/arXiv.quant-ph/9511026
arXiv: Quant-ph / 9511026
, Noah Linden e Ronald de Wolf. Rilevamento leggero di un piccolo numero di grandi errori in un circuito quantistico. Quantum, 5(436), 2021. arXiv:2009.08840.
https://doi.org/10.22331/q-2021-04-20-436
arXiv: 2009.08840
, Urmila Mahadev. Verifica classica dei calcoli quantistici. In Atti del 59° IEEE FOCS, pagine 259–267, 2018. arXiv:1804.01082.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
arXiv: 1804.01082
, John M. Martyn, Zane M. Rossi, Andrew K. Tan e Isaac L. Chuang. Una grande unificazione degli algoritmi quantistici. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
, Michael A. Nielsen e Isaac L. Chuang. Calcolo quantistico e informazioni quantistiche. Cambridge University Press, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667
, Patrizio Rall. Algoritmi quantistici più veloci e coerenti per la stima di fase, energia e ampiezza. Quantum, 5(566), 2021. arXiv:2103.09717.
https://doi.org/10.22331/q-2021-10-19-566
arXiv: 2103.09717
, Peter W. Short. Algoritmi polinomiali per la fattorizzazione in fattori primi e logaritmi discreti su un computer quantistico. SIAM Journal on Computing, 26(5):1484–1509, 1997. Versione precedente in FOCS'94. quant-ph/9508027.
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: Quant-ph / 9508027
, Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li e Andrew M. Childs. Simulazione hamiltoniana con input casuali. arXiv:2111.04773, 8 novembre 2021.
https:///doi.org/10.48550/arXiv.2111.04773
arXiv: 2111.04773
Citato da
[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén e Giacomo Nannicini, “Tomografia quantistica che utilizza unità di preparazione allo stato”, arXiv: 2207.08800.
Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2022-12-08 04:24:57). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.
On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2022-12-08 04:24:56).
Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.
