1AWS Center for Quantum Computing, VS
2IQIM, California Institute of Technology, VS
3Afdeling Computerwetenschappen, Carnegie Mellon University, VS
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
Gemotiveerd door schatting van kwantumruismodellen, bestuderen we het probleem van het leren van een Pauli-kanaal, of meer in het algemeen de Pauli-foutpercentages van een willekeurig kanaal. Door een nieuwe reductie van het "Population Recovery"-probleem toe te passen, geven we een uiterst eenvoudig algoritme dat de Pauli-foutpercentages van een $n$-qubit-kanaal leert tot precisie $epsilon$ in $ell_infty$ met slechts $O(1/epsilon ^2) log(n/epsilon)$ toepassingen van het kanaal. Dit is optimaal tot aan de logaritmische factoren. Ons algoritme gebruikt alleen niet-verstrengelde toestandsvoorbereiding en metingen, en de klassieke runtime na meting is slechts een $O(1/epsilon)$-factor groter dan de grootte van de meetgegevens. Het is ook ongevoelig voor een beperkt model van meetruis waarbij aangekondigde meetfouten onafhankelijk optreden met een waarschijnlijkheid van $ le 1/4 $.
We beschouwen dan het geval waarin het ruiskanaal dicht bij de identiteit ligt, wat betekent dat de uitkomst zonder fouten optreedt met waarschijnlijkheid $1-eta$. In het regime van kleine $eta$ breiden we ons algoritme uit om multiplicatieve precisie $1 pm epsilon$ (dwz additieve precisie $epsilon eta$) te bereiken met slechts $Obigl(frac{1}{epsilon^2 eta}bigr) log(n /epsilon)$ toepassingen van het kanaal.
Populaire samenvatting
In dit werk beschouwen we het probleem van het leren van een kansverdeling over Pauli-operatoren; dat wil zeggen, we willen een Pauli-kanaal leren. Verder willen we dit doen met alleen zeer eenvoudige (productstaat) preparaten en basismetingen. Het leren van Pauli-kanalen met minimale middelen is belangrijk om de fouten in een lawaaierige kwantumcomputer te leren en betere manieren te vinden om die fouten op te lossen of anderszins te verminderen.
Ons werk laat zien dat dit probleem gereduceerd wordt tot het klassieke probleem van populatieherstel met een bepaald type asymmetrische ruis. Vervolgens laten we zien dat de in de literatuur bekende standaardalgoritmen voor populatieherstel onveranderd van toepassing zijn op dit type ruis. Dit geeft ons zeer steekproefefficiënte algoritmen voor het leren van Pauli-kanalen die zeer eenvoudige toestandsvoorbereidingen en metingen gebruiken.
We laten ook een paar andere interessante weetjes zien. Ten eerste is het algoritme van nature robuust tegen bepaalde soorten extra meetruis. We kunnen het algoritme ook uitbreiden om het geval te behandelen waarin meestal slechts één enkele Pauli voorkomt (bijvoorbeeld de identiteit Pauli), en we willen de resterende populatie herstellen met een precisie die relatief is ten opzichte van de frequentie van de resterende populatie ( een zwaardere taak). We laten een interessant verband zien met Fourier-analyse op booleaanse variabelen. Ten slotte geven we een open source implementatie in Julia van een van de algoritmen.
► BibTeX-gegevens
► Referenties
[1] F. Ban, X. Chen, A. Freilich, R. Servedio en S. Sinha. Beyond trace-reconstructie: populatieherstel van het verwijderingskanaal. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science, pagina's 745-768, 2019, arXiv:1904.05532.
https: / / doi.org/ 10.1109 / FOCS.2019.00050
arXiv: 1904.05532
[2] F. Ban, X. Chen, RA Servedio en S. Sinha. Efficiënt herstel van de populatie van gemiddelde gevallen in aanwezigheid van inserties en deleties. In D. Achlioptas en LA Végh, redacteuren, Approximation, Randomization en Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 44:1–44:18, Dagstuhl, Duitsland, 2019. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, arXiv:1907.05964 .
https: / / doi.org/ 10.4230 / LIPIcs.APPROX-RANDOM.2019.44
arXiv: 1907.05964
[3] L. Batman, R. Impagliazzo, C. Murray en R. Paturi. Het vinden van zware hitters van data met verlies of ruis. In Proceedings of the 16th Annual International Conference on Approximation Algorithms for Combinatorial Optimization Problems, pagina's 347-362, 2013.
https://doi.org/10.1007/978-3-642-40328-6_25
[4] CH Bennett en SJ Wiesner. Communicatie via operatoren met één en twee deeltjes op Einstein-Podolsky-Rosen-toestanden. Fys. Rev. Lett., 69:2881-2884, november 1992.
https: / / doi.org/ 10.1103 / PhysRevLett.69.2881
[5] CL Kanon. Een korte opmerking over het leren van discrete distributies, 2020, arXiv:2002.11457.
arXiv: 2002.11457
[6] C. Dankert. Efficiënte simulatie van willekeurige kwantumtoestanden en operators. Proefschrift, Universiteit van Waterloo, 2015, arXiv:quant-ph/0512217.
arXiv: quant-ph / 0512217
[7] A. De, R. O'Donnell en R. Servedio. Scherpe grenzen voor bevolkingsherstel. Theory of Computing, 16 (6): 1-20, 2020, arXiv: 1703.01474.
https: / / doi.org/ 10.4086 / toc.2020.v016a006
arXiv: 1703.01474
[8] A. De, M. Saks en S. Tang. Luidruchtig populatieherstel in polynomiale tijd. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, pagina's 675-684, 2016, arXiv:1602.07616.
https: / / doi.org/ 10.1109 / FOCS.2016.77
arXiv: 1602.07616
[9] Z. Dvir, A. Rao, A. Wigderson en A. Yehudayoff. Beperking toegang. In Proceedings of the 3nd Annual Innovations in Theoretical Computer Science, pagina's 19-33, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090239
[10] S. Flammia en J. Wallman. Efficiënte schatting van Pauli-kanalen. ACM-transacties op Quantum Computing, 1(1):1–32, 2020, arXiv:1907.12976.
https: / / doi.org/ 10.1145 / 3408039
arXiv: 1907.12976
[11] ST Flammia. PauliPopRec, Github-repository, 2021.
https:///doi.org/10.5281/ZENODO.5327656
[12] A. Fujiwara en H. Imai. Schatting van kwantumparameters van een gegeneraliseerd Pauli-kanaal. Journal of Physics A: Mathematisch en algemeen, 36(29):8093-8103, juli 2003.
https://doi.org/10.1088/0305-4470/36/29/314
[13] O. Goldreich en L. Levin. Een hard-core predikaat voor alle eenrichtingsfuncties. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pagina's 25-32, 1989.
https: / / doi.org/ 10.1145 / 73007.73010
[14] R. Harper, ST Flammia en JJ Wallman. Efficiënt leren van kwantumruis. Natuurfysica, 16 (12): 1184-1188, augustus 2020, arXiv: 1907.13022.
https://doi.org/10.1038/s41567-020-0992-8
arXiv: 1907.13022
[15] R. Harper, W. Yu en ST Flammia. Snelle schatting van schaarse kwantumruis. PRX Quantum, 2(1):010322, februari 2021, arXiv:2007.07901.
https: / / doi.org/ 10.1103 / PRXQuantum.2.010322
arXiv: 2007.07901
[16] M. Hayashi. Quantum Informatie Theorie. Springer Berlin Heidelberg, 2e editie, 2017.
https://doi.org/10.1007/978-3-662-49725-8
[17] J. Helsen, X. Xue, LMK Vandersypen en S. Wehner. Een nieuwe klasse van efficiënte gerandomiseerde benchmarkingprotocollen. npj Quantum Information, 5(1):71, aug. 2019, arXiv:1806.02048.
https://doi.org/10.1038/s41534-019-0182-7
arXiv: 1806.02048
[18] E. Knill. Quantum computing met apparaten met realistische ruis. Nature, 434(7029):39–44, maart 2005, arXiv:quant-ph/0410199.
https: / / doi.org/ 10.1038 / nature03350
arXiv: quant-ph / 0410199
[19] S. Lovett en J. Zhang. Verbeterd herstel van luidruchtige populatie en omgekeerde Bonami-Beckner-ongelijkheid voor schaarse functies. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pagina's 137-142, 2015.
https: / / doi.org/ 10.1145 / 2746539.2746540
[20] S. Lovett en J. Zhang. Herstel van lawaaierige bevolking van onbekend geluid. In Conference on Learning Theory, pagina's 1417-1431, 2017.
[21] A. Moitra en M. Saks. Een polynomiaal tijdalgoritme voor populatieherstel met verlies. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pagina's 110-116, 2013, arXiv:1302.1515.
https: / / doi.org/ 10.1109 / FOCS.2013.20
arXiv: 1302.1515
[22] A. Montanaro en TJ Osborne. Quantum Booleaanse functies. Chicago Journal of Theoretical Computer Science, 2010(1):1–45, januari 2010, arXiv:0810.2435.
https: / / doi.org/ 10.4086 / cjtcs.2010.001
arXiv: 0810.2435
[23] S. Narayanan. Verbeterde algoritmen voor populatieherstel van het verwijderingskanaal. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pagina's 1259-1278. Vereniging voor Industriële en Toegepaste Wiskunde, januari 2021, arXiv:2004.06828.
https: / / doi.org/ 10.1137 / 1.9781611976465.77
arXiv: 2004.06828
[24] R. O'Donnell. Analyse van Booleaanse functies. Cambridge University Press, 2014, arXiv:2105.10386.
https: / / doi.org/ 10.1017 / CBO9781139814782
arXiv: 2105.10386
[25] Y. Polyanskiy, AT Suresh en Y. Wu. Voorbeeldcomplexiteit van populatieherstel. In S. Kale en O. Shamir, redacteuren, Proceedings of the 2017 Conference on Learning Theory, volume 65 van Proceedings of Machine Learning Research, pagina's 1589-1618, Amsterdam, Nederland, 07-10 juli 2017. PMLR, arXiv:1702.05574.
arXiv: 1702.05574
[26] B. Terhal. Kwantumfoutcorrectie voor kwantumgeheugens. Recensies van moderne fysica, 87(2):307, 2015, arXiv:1302.3428.
https: / / doi.org/ 10.1103 / RevModPhys.87.307
arXiv: 1302.3428
[27] J. ur Rehman en H. Shin. Verstrengelingsvrije parameterschatting van gegeneraliseerde Pauli-kanalen. Quantum, 5:490, juli 2021, arXiv:2102.00740.
https://doi.org/10.22331/q-2021-07-01-490
arXiv: 2102.00740
[28] M. Wainwright. Hoogdimensionale statistiek: een niet-asymptotisch gezichtspunt. Cambridge University Press, 2019.
https: / / doi.org/ 10.1017 / 9781108627771
[29] J. Wallman en J. Emerson. Ruisaanpassing voor schaalbare kwantumberekening via gerandomiseerde compilatie. Fysieke beoordeling A, 94(5):052325, 2016, arXiv:1512.01098.
https: / / doi.org/ 10.1103 / PhysRevA.94.052325
arXiv: 1512.01098
[30] A. Wigderson en A. Yehudayoff. Herstel van de bevolking en gedeeltelijke identificatie. Machinaal leren, 102(1):29-56, 2016.
https://doi.org/10.1007/s10994-015-5489-9
Geciteerd door
[1] Yunchao Liu, Matthew Otten, Roozbeh Bassirianjahromi, Liang Jiang en Bill Fefferman, "Benchmarking van kwantumcomputers op korte termijn via willekeurige circuitbemonstering", arXiv: 2105.05232.
[2] Thomas Wagner, Hermann Kampermann, Dagmar Bruß en Martin Kliesch, "Pauli-kanalen kunnen worden geschat op basis van syndroommetingen bij kwantumfoutcorrectie", arXiv: 2107.14252.
[3] Senrui Chen, Sisi Zhou, Alireza Seif en Liang Jiang, "Kwantumvoordelen voor Pauli-kanaalschatting", arXiv: 2108.08488.
[4] Steven T. Flammia, "Sampling eigenwaarde van gemiddeld circuit", arXiv: 2108.05803.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2021-09-23 14:17:36). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
Kon niet ophalen Door Crossref geciteerde gegevens tijdens laatste poging 2021-09-23 14:17:34: kon niet geciteerde gegevens voor 10.22331 / q-2021-09-23-549 niet ophalen van Crossref. Dit is normaal als de DOI recent is geregistreerd.
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
PlatoAi. Web3 opnieuw uitgevonden. Gegevensintelligentie versterkt.
Klik hier om toegang te krijgen.
