1QC Ware Corp., Palo Alto, USA e Parigi, Francia.
2Goldman, Sachs & Co., New York, USA.
3Università di Stanford, Palo Alto, USA.
4CWI Amsterdam, Paesi Bassi.
5CNRS, Université Paris, Francia.
Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.
Astratto
Progettiamo e analizziamo due nuovi algoritmi di bassa profondità per la stima dell'ampiezza (AE) ottenendo un compromesso ottimale tra l'accelerazione quantistica e la profondità del circuito. Per $beta in (0,1]$, i nostri algoritmi richiedono $N= tilde{O}( frac{1}{ epsilon^{1+beta}})$ chiamate oracle e richiedono che l'oracolo venga chiamato in sequenza $D= O( frac{1}{ epsilon^{1-beta}})$ volte per eseguire la stima dell'ampiezza all'interno dell'errore additivo $epsilon$. Questi algoritmi interpolano tra l'algoritmo classico $(beta=1)$ e l'algoritmo quantistico standard ($ beta=0$) e ottenere un compromesso $ND= O(1/epsilon^{2})$. Questi algoritmi avvicinano alla realizzazione gli speedup quantistici per i metodi Monte Carlo, poiché possono fornire accelerazioni con circuiti meno profondi.
Il primo algoritmo (Power law AE) utilizza schemi di power law nel framework introdotto da Suzuki et al [24]. L'algoritmo funziona per $beta in (0,1]$ e ha garanzie di correttezza dimostrabile quando la funzione di verosimiglianza soddisfa le condizioni di regolarità richieste per il teorema di Bernstein Von-Mises.Il secondo algoritmo (QoPrime AE) utilizza il teorema cinese del resto per combinare stime di profondità inferiori per ottenere una maggiore precisione.L'algoritmo funziona per $beta =q/k$ discreti dove $k geq 2$ è il numero di moduli coprimi distinti utilizzati dall'algoritmo e $1 leq q leq k-1$, e ha un prova di correttezza completamente rigorosa Analizziamo entrambi gli algoritmi in presenza di rumore depolarizzante e forniamo confronti numerici con algoritmi di stima dell'ampiezza allo stato dell'arte.
Riepilogo popolare
L'algoritmo AE standard richiede query $O(1/epsilon)$ a un circuito Oracle che viene eseguito in sequenza volte $O(1/epsilon)$ per ottenere una precisione $O(epsilon)$. In questo lavoro, affrontiamo la questione degli accelerazioni nell'impostazione a breve termine in cui il computer quantistico è limitato in profondità per le query fatte all'oracolo. Forniamo un algoritmo dimostrabilmente corretto che raggiunge un compromesso della forma $O(ND) = O(1/epsilon^{2})$ dove $N$ è il numero totale di query Oracle e $D$ la profondità massima del interrogazione.
I risultati dimostrano la possibilità di un aumento di $D$-fold rispetto agli algoritmi classici quando il computer quantistico è in grado di interrogare l'oracolo a profondità $D$. La nuova idea algoritmica è quella di sfruttare il teorema cinese del resto per aumentare la precisione delle stime AE.
► dati BibTeX
► Riferimenti
, 4 S. Aaronson e P. Rall, "Quantum approssimativo conteggio, semplificato", in Symposium on Simplicity in Algorithms. SIAM, 2020, pp. 24–32. [In linea]. Disponibile: https://dx.doi.org/10.1137/1.9781611976014.5 0pt.
https: / / doi.org/ 10.1137 / 1.9781611976014.5 mila
, DS Abrams e CP Williams, "Algoritmi quantistici veloci per integrali numerici e processi stocastici", arXiv:quant-ph/9908083, 1999.
arXiv: Quant-ph / 9908083
, 4 A. Ambainis, "Amplificazione dell'ampiezza del tempo variabile e algoritmi quantistici per problemi di algebra lineare", in STACS'12 (29th Symposium on Theoretical Aspects of Computer Science), vol. 14. LIPics, 2012, pp. 636–647. [In linea]. Disponibile: https://dx.doi.org/10.4230/LIPICs.STACS.2012.636 0pt.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2012.636
, A. Bouland, W. van Dam, H. Joorati, I. Kerenidis e A. Prakash, "Prospettive e sfide della finanza quantistica", preprint arXiv arXiv:2011.06492, 2020.
arXiv: 2011.06492
, G. Brassard, F. Dupuis, S. Gambs e A. Tapp, "Un algoritmo quantistico ottimale per approssimare la media e la sua applicazione per approssimare la mediana di un insieme di punti su una distanza arbitraria", arXiv:1106.4267, 2011.
arXiv: 1106.4267
, 4 G. Brassard, P. Hoyer, M. Mosca e A. Tapp, “Quantum amplitude amplification and estimation,” Contemporary Mathematics, vol. 305, pp. 53–74, 2002. [In linea]. Disponibile: https://dx.doi.org/10.1090/conm/305/05215 0pt.
https: / / doi.org/ 10.1090 / conm / 305 / 05215
, 4 G. Brassard, P. Høyer e A. Tapp, "Quantum counting", in International Colloquium on Automata, Languages, and Programming. Springer, 1998, pp. 820–831. [In linea]. Disponibile: https://dx.doi.org/10.1007/BFb0055105 0pt.
https: / / doi.org/ 10.1007 / BFb0055105
, P. Burchard, "Limiti inferiori per il conteggio quantico parallelo", preprint arXiv arXiv:1910.04555, 2019.
arXiv: 1910.04555
, P. Erdös e JL Selfridge, "Complete prime subsets of consecutivi interi", Atti della Manitoba Conference on Numerical Mathematics, Winnipeg, p. 13, 1971.
, 4 C. Ferrie, CE Granade e DG Cory, "Come campionare al meglio una distribuzione di probabilità periodica, o sull'accuratezza delle strategie di ricerca hamiltoniana", Quantum Information Processing, vol. 12, n. 1, pp. 611–623, 2013. [In linea]. Disponibile: https://dx.doi.org/10.1007/s11128-012-0407-6 0pt.
https://doi.org/10.1007/s11128-012-0407-6
, 4 D. Grinko, J. Gacon, C. Zoufal e S. Woerner, "Estimazione dell'ampiezza quantistica iterativa", preprint arXiv arXiv:1912.05559, 2019. [Online]. Disponibile: https://dx.doi.org/10.1038/s41534-021-00379-1 0pt.
https://doi.org/10.1038/s41534-021-00379-1
arXiv: 1912.05559
, 4 LK Grover, "Un framework per algoritmi meccanici quantistici veloci", in Atti del trentesimo simposio annuale ACM sulla teoria dell'informatica, 1998, pp. 53–62. [In linea]. Disponibile: https://dx.doi.org/10.1145/276698.276712 0pt.
https: / / doi.org/ 10.1145 / 276698.276712 mila
, Y. Hamoudi e F. Magniez, "Quantum Chebyshev's inequality and applications", nel 46° Colloquio internazionale su automi, linguaggi e programmazione (ICALP 2019). Castello Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
, 4 AW Harrow, A. Hassidim e S. Lloyd, "Algoritmo quantistico per sistemi di equazioni lineari", lettere di revisione fisica, vol. 103, n. 15, pag. 150502, 2009. [In linea]. Disponibile: https://dx.doi.org/10.1007/978-3-642-27848-8_771-1 0pt.
https://doi.org/10.1007/978-3-642-27848-8_771-1
, C. Hipp e R. Michel, “Sul Bernstein-v. Approssimazione sbagliata delle distribuzioni posteriori", The Annals of Statistics, pp. 972–980, 1976.
, 4 W. Hoeffding, "Disuguaglianze di probabilità per somme di variabili casuali limitate", in The collect works di Wassily Hoeffding. Springer, 1994, pp. 409–426. [In linea]. Disponibile: https://doi.org/10.2307/2282952 0pt.
https: / / doi.org/ 10.2307 / 2282952 mila
, 4 S. Jeffery, F. Magniez e R. De Wolf, "Algoritmi di query quantistiche parallele ottimali", Algorithmica, vol. 79, n. 2, pp. 509–529, 2017. [In linea]. Disponibile: https://dx.doi.org/10.1007/s00453-016-0206-z 0pt.
https: / / doi.org/ 10.1007 / s00453-016-0206-z
, I. Kerenidis, J. Landman, A. Luongo e A. Prakash, "q-means: Un algoritmo quantistico per l'apprendimento automatico senza supervisione", Atti dei sistemi di elaborazione delle informazioni neurali (NeurIPS), 2019.
, AY Kitaev, "Misure quantistiche e problema dello stabilizzatore abeliano", preprint arXiv quant-ph/9511026, 1995.
arXiv: Quant-ph / 9511026
, DE Koh, G. Wang, PD Johnson e Y. Cao, "Un framework per l'ingegneria delle funzioni di verosimiglianza quantistica per la stima delle aspettative", preprint arXiv arXiv:2006.09349, 2020.
arXiv: 2006.09349
, 4 T. Li e X. Wu, "Quantum query complex of entropy estimation", IEEE Transactions on Information Theory, vol. 65, n. 5, pp. 2899–2921, 2018. [In linea]. Disponibile: https://dx.doi.org/10.1109/TIT.2018.2883306 0pt.
https: / / doi.org/ 10.1109 / TIT.2018.2883306
, 4 A. Montanaro, "Quantum speedup of Monte Carlo Methods", Atti della Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 471, n. 2181, pag. 20150301, 2015. [In linea]. Disponibile: https://dx.doi.org/10.1098/rspa.2015.0301 0pt.
https: / / doi.org/ 10.1098 / rspa.2015.0301
, 4 J. Preskill, "Quantum computing nell'era NISQ e oltre", Quantum, vol. 2, pag. 79, 2018. [In linea]. Disponibile: https://dx.doi.org/10.22331/q-2018-08-06-79 0pt.
https://doi.org/10.22331/q-2018-08-06-79
, 4 Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera e N. Yamamoto, "Stima dell'ampiezza senza stima di fase", Quantum Information Processing, vol. 19, n. 2, pag. 75, 2020. [In linea]. Disponibile: https://dx.doi.org/10.1007/s11128-019-2565-2 0pt.
https://doi.org/10.1007/s11128-019-2565-2
, 4 T. Tanaka, Y. Suzuki, S. Uno, R. Raymond, T. Onodera e N. Yamamoto, "Stima dell'ampiezza tramite la massima verosimiglianza su computer quantistico rumoroso", preprint arXiv arXiv:2006.16223, 2020. [Online]. Disponibile: https://dx.doi.org/10.1007/s11128-021-03215-9 0pt.
https://doi.org/10.1007/s11128-021-03215-9
arXiv: 2006.16223
, 4 D. Wang, O. Higgott e S. Brierley, "Accelerated variational quantum eigensolver", Physical review letters, vol. 122, n. 14, pag. 140504, 2019. [In linea]. Disponibile: https://doi.org/10.1103/PhysRevLett.122.140504 0pt.
https: / / doi.org/ 10.1103 / PhysRevLett.122.140504
, 4 N. Wiebe, A. Kapoor e KM Svore, "Algoritmi quantistici per i metodi del vicino più vicino per l'apprendimento supervisionato e non supervisionato", Quantum Information & Computation, vol. 15, n. 3-4, pp. 316–356, 2015. [In linea]. Disponibile: https://dx.doi.org/10.26421/QIC15.3-4-7 0pt.
https: / / doi.org/ 10.26421 / QIC15.3-4-7
, 4 C. Zalka, "L'algoritmo di ricerca quantistica di Grover è ottimale", Physical Review A, vol. 60, n. 4, pag. 2746, 1999. [In linea]. Disponibile: https://dx.doi.org/10.1103/PhysRevA.60.2746 0pt.
https: / / doi.org/ 10.1103 / PhysRevA.60.2746
Citato da
[1] Adam Callison e Nicholas Cancelliere, "Algoritmi ibridi quantistici-classici nell'era quantistica rumorosa a scala intermedia e oltre", Revisione fisica A 106 1, 010101 (2022).
[2] Tudor Giurgica-Tiron, Sonika Johri, Iordanis Kerenidis, Jason Nguyen, Neal Pisenti, Anupam Prakash, Ksenia Sosnova, Ken Wright e William Zeng, "Stima dell'ampiezza a bassa profondità su un computer quantistico a ioni intrappolati", arXiv: 2109.09685, Ricerca sulla revisione fisica 4 3, 033034 (2022).
[3] Bo Yang, Rudy Raymond e Shumpei Uno, "Efficiente mitigazione dell'errore di lettura quantistica per risultati di misurazione sparsi di dispositivi quantistici a breve termine", Revisione fisica A 106 1, 012423 (2022).
[4] Dylan Herman, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro, Yue Sun, Marco Pistoia e Yuri Alexeev, "A Survey of Quantum Computing for Finance", arXiv: 2201.02773.
[5] Thais de Lima Silva, Márcio M. Taddei, Stefano Carrazza e Leandro Aolita, "Evoluzione del tempo immaginario frammentato per processori di segnali quantistici in fase iniziale", arXiv: 2110.13180.
[6] Prasanth Shyamsudar, "Amplificazione dell'ampiezza quantica non booleana e stima della media quantistica", arXiv: 2102.04975.
[7] Koichi Miyamoto, Gonzalo Morrás, Takahiro S. Yamamoto, Sachiko Kuroyanagi e Savvas Nesseris, "Filtraggio abbinato a onde gravitazionali mediante integrazione Monte Carlo quantistica e amplificazione di ampiezza quantistica", arXiv: 2205.05966.
[8] Shouvanik Chakrabarti, Rajiv Krishnakumar, Guglielmo Mazzola, Nikitas Stamatopoulos, Stefan Woerner e William J. Zeng, "A Threshold for Quantum Advantage in Derivative Pricing", arXiv: 2012.03819.
[9] Kirill Plekhanov, Matthias Rosenkranz, Mattia Fiorentini e Michael Lubasch, "Stima dell'ampiezza quantistica variazionale", arXiv: 2109.03687.
[10] MC Braun, T. Decker, N. Hegemann e SF Kerstan, "Error Resilient Quantum Amplitude Estimation from Parallel Quantum Phase Estimation", arXiv: 2204.01337.
[11] Javier Alcazar, Andrea Cadarso, Amara Katabarwa, Marta Mauri, Borja Peropadre, Guoming Wang e Yudong Cao, “Algoritmo quantistico per aggiustamenti della valutazione del credito”, Nuovo Journal of Physics 24 2, 023036 (2022).
[12] Jonas Landman, "Algoritmi quantistici per l'apprendimento automatico non supervisionato e le reti neurali", arXiv: 2111.03598.
[13] Amara Katabarwa, Alex Kunitsa, Borja Peropadre e Peter Johnson, "Ridurre il tempo di esecuzione e l'errore in VQE utilizzando circuiti quantistici più profondi e più rumorosi", arXiv: 2110.10664.
[14] Zhicheng Zhang, Qisheng Wang e Mingsheng Ying, "Algoritmo quantistico parallelo per la simulazione hamiltoniana", arXiv: 2105.11889.
[15] Koichi Miyamoto, "Algoritmo quantistico per il calcolo dei contributi di rischio in un portafoglio di crediti", arXiv: 2201.11394.
[16] Rhea Parekh, Andrea Ricciardi, Ahmed Darwish e Stephen DiAdamo, "Algoritmi quantistici e simulazione per il calcolo quantistico parallelo e distribuito", arXiv: 2106.06841.
[17] Koichi Miyamoto, "Prezzo delle opzioni bermudiane mediante stima dell'ampiezza quantistica e interpolazione di Chebyshev", arXiv: 2108.09014.
[18] Tomoki Tanaka, Shumpei Uno, Tamiya Onodera, Naoki Yamamoto e Yohichi Suzuki, "Stima dell'ampiezza quantistica rumorosa senza stima del rumore", Revisione fisica A 105 1, 012411 (2022).
[19] Alberto Manzano, Daniele Musso, Álvaro Leitao, Andrés Gómez, Carlos Vázquez, Gustavo Ordóñez e María Rodríguez-Nogueiras, "Quantum Arithmetic for Directly Embedded Arrays", arXiv: 2107.13872.
[20] Amit Saha, Turbasu Chatterjee, Anupam Chattopadhyay e Amlan Chakrabarti, "Operazioni aritmetiche quantistiche migliorate basate su Qutrit intermedie con applicazione sui prezzi derivati finanziari", arXiv: 2205.15822.
[21] Koichi Miyamoto, “Algoritmi quantistici per la differenziazione numerica dei valori attesi rispetto ai parametri”, Elaborazione delle informazioni quantistiche 21 3, 109 (2022).
[22] Joran van Apeldoorn e Tijn de Vos, "Un quadro per le query quantistiche distribuite nel modello CONGEST", arXiv: 2202.10969.
Le citazioni sopra sono di Il servizio citato da Crossref (ultimo aggiornamento riuscito 2022-07-19 15:37:00) e ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2022-07-19 15:37:01). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.
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.
