1QC Ware Corp., Palo Alto, USA och Paris, Frankrike.
2Goldman, Sachs & Co., New York, USA.
3Stanford University, Palo Alto, USA.
4CWI Amsterdam, Nederländerna.
5CNRS, Université Paris, Frankrike.
Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.
Abstrakt
Vi designar och analyserar två nya lågdjupsalgoritmer för amplitudestimering (AE) för att uppnå en optimal avvägning mellan kvanthastigheten och kretsdjupet. För $beta in (0,1]$ kräver våra algoritmer $N= tilde{O}( frac{1}{ epsilon^{1+beta}})$ orakelanrop och kräver att oraklet anropas sekventiellt $D= O( frac{1}{ epsilon^{1-beta}})$ gånger för att utföra amplituduppskattning inom additivt fel $epsilon$. Dessa algoritmer interpolerar mellan den klassiska algoritmen $(beta=1)$ och standardkvantalgoritmen ($ beta=0$) och uppnå en avvägning $ND= O(1/epsilon^{2})$. Dessa algoritmer bringar kvanthastighetsuppgångar för Monte Carlo-metoder närmare realisering, eftersom de kan ge hastigheter med grundare kretsar.
Den första algoritmen (Power Law AE) använder kraftlagsscheman i det ramverk som introducerats av Suzuki et al [24]. Algoritmen fungerar för $beta i (0,1]$ och har bevisbara korrekthetsgarantier när log-likelihood-funktionen uppfyller regularitetsvillkor som krävs för Bernstein Von-Mises-satsen. Den andra algoritmen (QoPrime AE) använder den kinesiska restsatsen för att kombinera lägre djupuppskattningar för att uppnå högre noggrannhet. Algoritmen fungerar för diskret $beta =q/k$ där $k geq 2$ är antalet distinkta coprime-moduler som används av algoritmen och $1 leq q leq k-1$, och har en fullständigt noggrant korrekthetsbevis. Vi analyserar båda algoritmerna i närvaro av depolariserande brus och tillhandahåller numeriska jämförelser med de senaste algoritmerna för amplituduppskattning.
Populär sammanfattning
Standard AE-algoritmen kräver $O(1/epsilon)$-frågor till en orakelkrets som sekventiellt körs $O(1/epsilon)$ gånger för att få en $O(epsilon)$-noggrannhet. I det här arbetet tar vi upp frågan om snabbheterna i en närtid där kvantdatorn är begränsad i djupet för frågor som görs till oraklet. Vi tillhandahåller en bevisligen korrekt algoritm som uppnår en avvägning av formen $O(ND) = O(1/epsilon^{2})$ där $N$ är det totala antalet orakelfrågor och $D$ det maximala djupet av fråga.
Resultaten visar möjligheten av en $D$-faldig snabbhet jämfört med klassiska algoritmer när kvantdatorn kan fråga oraklet på djupet $D$. Den nya algoritmiska idén är att utnyttja den kinesiska restsatsen för att öka precisionen i AE-uppskattningarna.
► BibTeX-data
► Referenser
[1] 4 S. Aaronson och P. Rall, "Quantum approximative counting, simplified," i Symposium on Simplicity in Algorithms. SIAM, 2020, s. 24–32. [Uppkopplad]. Tillgänglig: https:///dx.doi.org/10.1137/1.9781611976014.5 0pt.
https: / / doi.org/ 10.1137 / 1.9781611976014.5
[2] DS Abrams och CP Williams, "Snabba kvantalgoritmer för numeriska integraler och stokastiska processer," arXiv:quant-ph/9908083, 1999.
arXiv: kvant-ph / 9908083
[3] 4 A. Ambainis, "Variabel tidsamplitudförstärkning och kvantalgoritmer för linjära algebraproblem", i STACS'12 (29th Symposium on Theoretical Aspects of Computer Science), vol. 14. LIPIcs, 2012, s. 636–647. [Uppkopplad]. Tillgänglig: https:///dx.doi.org/10.4230/LIPIcs.STACS.2012.636 0pt.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2012.636
[4] A. Bouland, W. van Dam, H. Joorati, I. Kerenidis och A. Prakash, "Prospects and challenges of quantum finance," arXiv preprint arXiv:2011.06492, 2020.
arXiv: 2011.06492
[5] G. Brassard, F. Dupuis, S. Gambs och A. Tapp, "En optimal kvantalgoritm för att approximera medelvärdet och dess tillämpning för att approximera medianen för en uppsättning punkter över ett godtyckligt avstånd," arXiv:1106.4267, 2011.
arXiv: 1106.4267
[6] 4 G. Brassard, P. Hoyer, M. Mosca och A. Tapp, "Quantum amplitud amplification and estimation," Contemporary Mathematics, vol. 305, s. 53–74, 2002. [Online]. Tillgänglig: https:///dx.doi.org/10.1090/conm/305/05215 0pt.
https: / / doi.org/ 10.1090 / conm / 305 / 05215
[7] 4 G. Brassard, P. Høyer och A. Tapp, "Quantum counting," i International Colloquium on Automata, Languages, and Programming. Springer, 1998, s. 820–831. [Uppkopplad]. Tillgänglig: https:///dx.doi.org/10.1007/BFb0055105 0pt.
https: / / doi.org/ 10.1007 / BFb0055105
[8] P. Burchard, "Lower bounds for parallel quantum counting," arXiv preprint arXiv:1910.04555, 2019.
arXiv: 1910.04555
[9] P. Erdös och JL Selfridge, "Complete prime subset of consecutive heltals," Proceedings of the Manitoba Conference on Numerical Mathematics, Winnipeg, sid. 13, 1971.
[10] 4 C. Ferrie, CE Granade, och GD Cory, "Hur man bäst samplar en periodisk sannolikhetsfördelning, eller om noggrannheten i hamiltoniska hittastrategier," Quantum Information Processing, vol. 12, nr. 1, s. 611–623, 2013. [Online]. Tillgänglig: https:///dx.doi.org/10.1007/s11128-012-0407-6 0pt.
https://doi.org/10.1007/s11128-012-0407-6
[11] 4 D. Grinko, J. Gacon, C. Zoufal och S. Woerner, "Iterativ kvantamplituduppskattning," arXiv preprint arXiv:1912.05559, 2019. [Online]. Tillgänglig: https:///dx.doi.org/10.1038/s41534-021-00379-1 0pt.
https://doi.org/10.1038/s41534-021-00379-1
arXiv: 1912.05559
[12] 4 LK Grover, "Ett ramverk för snabba kvantmekaniska algoritmer", i Proceedings of the trettionde årliga ACM symposium on Theory of computing, 1998, s. 53–62. [Uppkopplad]. Tillgänglig: https:///dx.doi.org/10.1145/276698.276712 0pt.
https: / / doi.org/ 10.1145 / 276698.276712
[13] Y. Hamoudi och F. Magniez, "Quantum Chebyshevs ojämlikhet och tillämpningar", i 46:e internationella kollokviet om automater, språk och programmering (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
[14] 4 AW Harrow, A. Hassidim och S. Lloyd, "Quantum algorithm for linear system of equations," Physical review letters, vol. 103, nr. 15, sid. 150502, 2009. [Online]. Tillgänglig: 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
[15] C. Hipp och R. Michel, ”On the Bernstein-v. Mises approximation of posterior distributions,” The Annals of Statistics, s. 972–980, 1976.
[16] 4 W. Hoeffding, "Sannolikhet ojämlikheter för summor av gränsade slumpvariabler," i The collected works of Wassily Hoeffding. Springer, 1994, s. 409–426. [Uppkopplad]. Tillgänglig: https:///doi.org/10.2307/2282952 0pt.
https: / / doi.org/ 10.2307 / 2282952
[17] 4 S. Jeffery, F. Magniez och R. De Wolf, "Optimala parallella kvantfrågealgoritmer," Algorithmica, vol. 79, nr. 2, s. 509–529, 2017. [Online]. Tillgänglig: https:///dx.doi.org/10.1007/s00453-016-0206-z 0pt.
https: / / doi.org/ 10.1007 / s00453-016-0206-z
[18] I. Kerenidis, J. Landman, A. Luongo och A. Prakash, "q-means: A quantum algorithm for unsupervised machine learning," Proceedings of Neural Information Processing Systems (NeurIPS), 2019.
[19] AY Kitaev, "Quantum measurements and the abelian stabilizer problem," arXiv preprint quant-ph/9511026, 1995.
arXiv: kvant-ph / 9511026
[20] DE Koh, G. Wang, PD Johnson och Y. Cao, "A framework for engineering quantum likelihood-funktioner för förväntningsuppskattning," arXiv preprint arXiv:2006.09349, 2020.
arXiv: 2006.09349
[21] 4 T. Li och X. Wu, "Quantum query complexity of entropy estimation," IEEE Transactions on Information Theory, vol. 65, nr. 5, s. 2899–2921, 2018. [Online]. Tillgänglig: https:///dx.doi.org/10.1109/TIT.2018.2883306 0pt.
https: / / doi.org/ 10.1109 / TIT.2018.2883306
[22] 4 A. Montanaro, "Quantum speedup of Monte Carlo methods," Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 471, nr. 2181, sid. 20150301, 2015. [Online]. Tillgänglig: https:///dx.doi.org/10.1098/rspa.2015.0301 0pt.
https: / / doi.org/ 10.1098 / rspa.2015.0301
[23] 4 J. Preskill, "Quantum computing in the NISQ era and beyond," Quantum, vol. 2, sid. 79, 2018. [Online]. Tillgänglig: https:///dx.doi.org/10.22331/q-2018-08-06-79 0pt.
https://doi.org/10.22331/q-2018-08-06-79
[24] 4 Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera och N. Yamamoto, "Amplitudeskattning utan fasuppskattning," Quantum Information Processing, vol. 19, nr. 2, sid. 75, 2020. [Online]. Tillgänglig: https:///dx.doi.org/10.1007/s11128-019-2565-2 0pt.
https://doi.org/10.1007/s11128-019-2565-2
[25] 4 T. Tanaka, Y. Suzuki, S. Uno, R. Raymond, T. Onodera och N. Yamamoto, "Amplituduppskattning via maximal sannolikhet på brusig kvantdator," arXiv preprint arXiv:2006.16223, 2020. [Online]. Tillgänglig: https:///dx.doi.org/10.1007/s11128-021-03215-9 0pt.
https://doi.org/10.1007/s11128-021-03215-9
arXiv: 2006.16223
[26] 4 D. Wang, O. Higgott och S. Brierley, "Accelerated variational quantum eigensolver," Physical review letters, vol. 122, nr. 14, sid. 140504, 2019. [Online]. Tillgänglig: https:///doi.org/10.1103/PhysRevLett.122.140504 0pt.
https: / / doi.org/ 10.1103 / PhysRevLett.122.140504
[27] 4 N. Wiebe, A. Kapoor och KM Svore, "Quantum algoritmer för metoder för närmaste granne för övervakat och oövervakat lärande," Quantum Information & Computation, vol. 15, nr. 3-4, s. 316–356, 2015. [Online]. Tillgänglig: https:///dx.doi.org/10.26421/QIC15.3-4-7 0pt.
https: / / doi.org/ 10.26421 / QIC15.3-4-7
[28] 4 C. Zalka, "Grovers kvantsökningsalgoritm är optimal," Physical Review A, vol. 60, nej. 4, sid. 2746, 1999. [Online]. Tillgänglig: https:///dx.doi.org/10.1103/PhysRevA.60.2746 0pt.
https: / / doi.org/ 10.1103 / PhysRevA.60.2746
Citerad av
[1] Adam Callison och Nicholas Chancellor, "Hybrida kvantklassiska algoritmer i den bullriga kvanttiden i mellanskala och därefter", Fysisk granskning A 106 1, 010101 (2022).
[2] Tudor Giurgica-Tiron, Sonika Johri, Iordanis Kerenidis, Jason Nguyen, Neal Pisenti, Anupam Prakash, Ksenia Sosnova, Ken Wright och William Zeng, "Lågdjupsamplituduppskattning på en kvantdator med fångad jon", arXiv: 2109.09685, Physical Review Research 4 3, 033034 (2022).
[3] Bo Yang, Rudy Raymond och Shumpei Uno, "Effektiv minskning av kvantavläsningsfel för glesa mätresultat av kortsiktiga kvantenheter", Fysisk granskning A 106 1, 012423 (2022).
[4] Dylan Herman, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro, Yue Sun, Marco Pistoia och Yuri Alexeev, "A Survey of Quantum Computing for Finance", arXiv: 2201.02773.
[5] Thais de Lima Silva, Márcio M. Taddei, Stefano Carrazza och Leandro Aolita, "Fragmenterad imaginär tidsevolution för kvantsignalprocessorer i tidigt skede", arXiv: 2110.13180.
[6] Prasanth Shyamsundar, "Icke-boolsk kvantamplitudförstärkning och kvantmedelsuppskattning", arXiv: 2102.04975.
[7] Koichi Miyamoto, Gonzalo Morrás, Takahiro S. Yamamoto, Sachiko Kuroyanagi och Savvas Nesseris, "Gravitationsvåganpassad filtrering genom quantum Monte Carlo integration och quantum amplitud amplification", arXiv: 2205.05966.
[8] Shouvanik Chakrabarti, Rajiv Krishnakumar, Guglielmo Mazzola, Nikitas Stamatopoulos, Stefan Woerner och William J. Zeng, "En tröskel för kvantfördel i derivatpriser", arXiv: 2012.03819.
[9] Kirill Plekhanov, Matthias Rosenkranz, Mattia Fiorentini och Michael Lubasch, "Variational quantum amplitude estimation", arXiv: 2109.03687.
[10] MC Braun, T. Decker, N. Hegemann och 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 och Yudong Cao, "Kvantalgoritm för kreditvärderingsjusteringar", New Journal of Physics 24 2, 023036 (2022).
[12] Jonas Landman, "Quantum Algorithms for Unsupervised Machine Learning and Neural Networks", arXiv: 2111.03598.
[13] Amara Katabarwa, Alex Kunitsa, Borja Peropadre och Peter Johnson, "Minska körtid och fel i VQE med djupare och bullrigare kvantkretsar", arXiv: 2110.10664.
[14] Zhicheng Zhang, Qisheng Wang och Mingsheng Ying, "Parallell Quantum Algorithm for Hamiltonian Simulation", arXiv: 2105.11889.
[15] Koichi Miyamoto, "Kvantalgoritm för att beräkna riskbidrag i en kreditportfölj", arXiv: 2201.11394.
[16] Rhea Parekh, Andrea Ricciardi, Ahmed Darwish och Stephen DiAdamo, "Quantum Algorithms and Simulation for Parallel and Distributed Quantum Computing", arXiv: 2106.06841.
[17] Koichi Miyamoto, "Bermudan optionsprissättning genom uppskattning av kvantamplitud och Chebyshev-interpolation", arXiv: 2108.09014.
[18] Tomoki Tanaka, Shumpei Uno, Tamiya Onodera, Naoki Yamamoto och Yohichi Suzuki, "Brusig kvantamplituduppskattning utan brusuppskattning", Fysisk granskning A 105 1, 012411 (2022).
[19] Alberto Manzano, Daniele Musso, Álvaro Leitao, Andrés Gómez, Carlos Vázquez, Gustavo Ordóñez och María Rodríguez-Nogueiras, "Quantum Arithmetic for Directly Embedded Arrays", arXiv: 2107.13872.
[20] Amit Saha, Turbasu Chatterjee, Anupam Chattopadhyay och Amlan Chakrabarti, "Intermediate Qutrit-based Improved Quantum Arithmetic Operations with Application on Financial Derivative Pricing", arXiv: 2205.15822.
[21] Koichi Miyamoto, "Kvantalgoritmer för numerisk differentiering av förväntade värden med avseende på parametrar", Kvantinformationsbehandling 21 3, 109 (2022).
[22] Joran van Apeldoorn och Tijn de Vos, "A Framework for Distributed Quantum Queries in the CONGEST Model", arXiv: 2202.10969.
Ovanstående citat är från Crossrefs citerade service (senast uppdaterad framgång 2022-07-19 15:37:00) och SAO / NASA ADS (senast uppdaterad framgångsrikt 2022-07-19 15:37:01). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.
Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.
