Testen van de identiteit van verzamelingen kwantumtoestanden: analyse van de complexiteit van monsters

Heruitgegeven door Plato

volgers: 0

Marco Fanizza¹, Raffaele Salvia² en Vittorio Giovannitti³

¹Física Teòrica: Informació i Fenòmens Quàntics, Departament de Física, Universitat Autònoma de Barcelona, 08193 Bellaterra, Spanje.
²Scuola Normale Superiore, I-56127 Pisa, Italië.
³NEST, Scuola Normale Superiore en Istituto Nanoscienze-CNR, I-56127 Pisa, Italië.

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

We bestuderen het probleem van het testen van de identiteit van een verzameling onbekende kwantumtoestanden, gegeven toegang tot deze verzameling, waarbij elke toestand met een bekende waarschijnlijkheid verschijnt. We laten zien dat voor een verzameling $d$-dimensionale kwantumtoestanden van kardinaliteit $N$ de steekproefcomplexiteit $O(sqrt{N}d/epsilon^2)$ is, met een bijpassende ondergrens, tot aan een multiplicatieve constante . De test wordt verkregen door het schatten van de gemiddelde kwadratische Hilbert-Schmidt-afstand tussen de toestanden, dankzij een geschikte generalisatie van de schatter van de Hilbert-Schmidt-afstand tussen twee onbekende toestanden door Bădescu, O'Donnell en Wright.13].

Testen van de identiteit van verzamelingen kwantumtoestanden: analyse van de complexiteit van monsters PlatoBlockchain Data Intelligence. Verticaal zoeken. Ai.

Uitgelichte afbeelding: twee instellingen waarop ons model van toepassing is. In a) produceren onafhankelijke bronnen een willekeurig aantal, Poisson verdeeld, kopieën van een staat in een tijd $T$. In b) bereidt een meetprocedure gelabelde toestanden voor, waarbij elk label met enige waarschijnlijkheid verschijnt.

► BibTeX-gegevens

@article{Fanizza2023testingidentityof, doi = {10.22331/q-2023-09-11-1105}, url = {https://doi.org/10.22331/q-2023-09-11-1105}, title = {Identiteit testen van verzamelingen kwantumtoestanden: analyse van de complexiteit van monsters}, auteur = {Fanizza, Marco en Salvia, Raffaele en Giovannetti, Vittorio}, tijdschrift = {{Quantum}}, issn = {2521-327X}, uitgever = {{Verein zur F {“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pagina's = {1105}, maand = sep, jaar = {2023} }

► Referenties

[1] Gerardo Adesso, Thomas R. Bromley en Marco Cianciaruso, "Maatregelen en toepassingen van kwantumcorrelaties" Journal of Physics A: Mathematical and Theoretical 49, 473001 (2016).
https://doi.org/10.1088/1751-8113/49/47/473001
arXiv: 1605.00806

[2] Jayadev Acharya, Ibrahim Issa, Nirmal V. Shende en Aaron B. Wagner, “Estimating Quantum Entropy” IEEE Journal over geselecteerde gebieden in de informatietheorie 1, 454–468 (2020).
https: / / doi.org/ 10.1109 / JSAIT.2020.3015235
https:///ieeexplore.ieee.org/document/9163139/

[3] Jayadev Acharya en Constantinos Daskalakis "Testing Poisson Binomial Distributions" Proceedings van het zesentwintigste jaarlijkse ACM-SIAM-symposium over discrete algoritmen 1829–1840 (2015).
https: / / doi.org/ 10.1137 / 1.9781611973730.122
arXiv: 1507.05952

[4] Daiki Akimoto en Masahito Hayashi "Discriminatie van het veranderingspunt in een kwantumomgeving" Physical Review A 83, 052328 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.052328
arXiv: 1102.2555

[5] Robert Alicki, Slawomir Rudnicki en Slawomir Sadowski, "Symmetrie-eigenschappen van producttoestanden voor het systeem van atomen op N-niveau" Journal of Mathematical Physics 29, 1158–1162 (1988).
https: / / doi.org/ 10.1063 / 1.527958

[6] Ge Bai, Ya-Dong Wu, Yan Zhu, Masahito Hayashi en Giulio Chiribella, “Quantum causale ontrafeling” npj Quantum Information 8, 69 (2022).
https://doi.org/10.1038/s41534-022-00578-4
arXiv: 2109.13166

[7] Tuğkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld en Patrick White, "Het testen van willekeurige variabelen op onafhankelijkheid en identiteit" Proceedings 42e IEEE-symposium over de grondslagen van computerwetenschappen 442–451 (2001).
https: / / doi.org/ 10.1109 / SFCS.2001.959920
https:///ieeexplore.ieee.org/document/959920/

[8] Dave Bacon, Isaac L. Chuang en Aram W. Harrow, "Efficiënte kwantumcircuits voor Schur- en Clebsch-Gordan-transformaties" Physical Review Letters 97, 170502 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.170502
arXiv: 0407082

[9] Sebastien Bubeck, Sitan Chen en Jerry Li, "Verstrengeling is noodzakelijk voor het optimaal testen van kwantumeigenschappen" 2020 IEEE 61e jaarlijkse symposium over de fundamenten van de computerwetenschappen (FOCS) 692–703 (2020).
https://doi.org/10.1109/FOCS46700.2020.00070
arXiv: 2004.07869

[10] Charles H. Bennett, Igor Devetak, Aram W. Harrow, Peter W. Shor en Andreas Winter, "The Quantum Reverse Shannon Theorem en Resource Tradeoffs voor het simuleren van Quantum Channels" IEEE Transactions on Information Theory 60, 2926–2959 (2014).
https: / / doi.org/ 10.1109 / TIT.2014.2309968
http:///ieeexplore.ieee.org/document/6757002/

[11] E. Bagan, S. Iblisdir en R. Muñoz-Tapia, "Relatieve toestanden, kwantumassen en kwantumreferenties" Physical Review A 73, 022341 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022341
arXiv: 0508187

[12] Stéphane Boucheron, Gábor Lugosi en Pascal Massart, “Concentratie-ongelijkheid” Oxford University Press (2013).
https: / / doi.org/ 10.1093 / acprof: oso / 9780199535255.001.0001

[13] Costin Bădescu, Ryan O'Donnell en John Wright, "Quantum State Certification" Proceedings of the 51e Annual ACM SIGACT Symposium on Theory of Computing 503–514 (2019).
https: / / doi.org/ 10.1145 / 3313276.3316344
arXiv: 1708.06002

[14] Stephen D. Bartlett, Terry Rudolph en Robert W. Spekkens, “Optimale metingen voor relatieve kwantuminformatie” Physical Review A 70, 032321 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.032321
arXiv: 0310009

[15] Harry Buhrman, Richard Cleve, John Watrous en Ronald de Wolf, “Quantum Fingerprinting” Physical Review Letters 87, 167902 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.87.167902
arXiv: 0102001

[16] Clement L. Canonne “Een onderzoek naar distributietests: uw gegevens zijn groot. Maar is het blauw?” Computertheorie 1, 1–100 (2020).
https: / / doi.org/ 10.4086 / toc.gs.2020.009
http:///www.theoryofcomputing.org/articles/gs009

[17] Siu-On Chan, Ilias Diakonikolas, Paul Valiant en Gregory Valiant, "Optimale algoritmen voor het testen van de nabijheid van discrete distributies" Proceedings van het vijfentwintigste jaarlijkse ACM-SIAM-symposium over discrete algoritmen 1193–1203 (2014).
https: / / doi.org/ 10.1137 / 1.9781611973402.88
arXiv: 1308.3946

[18] Matthias Christandl “De structuur van bipartiete kwantumstaten – inzichten uit groepstheorie en cryptografie” (2006).
arXiv: 0604183

[19] Sitan Chen, Jerry Li en Ryan O'Donnell, ‘Toward Instance-Optimal State Certification With Incoherent Measurements’ Proceedings of Thirty Fifth Conference on Learning Theory 178, 2541–2596 (2022) https://proceedings.mlr.press /v178/chen22b.html.
arXiv: 2102.13098

[20] Thomas M. Cover en Joy A. Thomas “Elementen van informatietheorie” (2005).
https: / / doi.org/ 10.1002 / 047174882X

[21] Ilias Diakonikolas en Daniel M. Kane "Een nieuwe aanpak voor het testen van eigenschappen van discrete distributies" 2016 IEEE 57e jaarlijkse symposium over de grondslagen van computerwetenschappen (FOCS) 685–694 (2016).
https: / / doi.org/ 10.1109 / FOCS.2016.78
arXiv: 1601.05557
http:///ieeexplore.ieee.org/document/7782983/

[22] Ilias Diakonikolas, Daniel M. Kane en Vladimir Nikishkin, "Testing Identity of Structured Distributions" Proceedings van het zesentwintigste jaarlijkse ACM-SIAM-symposium over discrete algoritmen 2015-janua, 1841–1854 (2015).
https: / / doi.org/ 10.1137 / 1.9781611973730.123

[23] M. Fanizza, M. Rosati, M. Skotiniotis, J. Calsamiglia en V. Giovannetti, “Beyond the Swap Test: Optimal Estimation of Quantum State Overlap” Physical Review Letters 124, 060503 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.124.060503
arXiv: 1906.10639

[24] Marco Fanizza, Christoph Hirche en John Calsamiglia, “Ultieme grenzen voor de snelste detectie van kwantumveranderingspunten” Phys. Ds. Lett. 131, 020602 (2023).
https: / / doi.org/ 10.1103 / PhysRevLett.131.020602
arXiv: 2208.03265

[25] Marco Fanizza, Farzad Kianvash en Vittorio Giovannetti, “Kwantumvlaggen en nieuwe grenzen aan de kwantumcapaciteit van het depolariserende kanaal” Physical Review Letters 125, 020503 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.020503
arXiv: 1911.01977

[26] Marco Fanizza, Farzad Kianvash en Vittorio Giovannetti, "Het schatten van de kwantum- en privécapaciteiten van Gaussiaanse kanalen via afbreekbare extensies" Phys. Ds. Lett. 127, 210501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.210501
arXiv: 2103.09569

[27] N. Gisinand S. Iblisdir “Quantum relatieve staten” The European Physical Journal D 39, 321–327 (2006).
https: / / doi.org/ 10.1140 / epjd / e2006-00097-y
arXiv: 0507118

[28] Oded Goldreich “Inleiding tot het testen van eigendommen” Cambridge University Press (2017).
https: / / doi.org/ 10.1017 / 9781108135252

[29] Oded Goldreichand Dana Ron “Over het testen van uitbreidingen in grafieken met beperkte graden” (2011).
https://doi.org/10.1007/978-3-642-22670-0_9

[30] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu en Nengkun Yu, "Voorbeeld-optimale tomografie van kwantumstaten" IEEE Transactions on Information Theory 63, 1–1 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2719044
arXiv: 1508.01797
http:///ieeexplore.ieee.org/document/7956181/

[31] Aram W. Harrow “Toepassingen van coherente klassieke communicatie en de Schur-transformatie naar de kwantuminformatietheorie” (2005).
arXiv: 0512255

[32] Masahito Hayashi, Bao-Sen Shi, Akihisa Tomita, Keiji Matsumoto, Yoshiyuki Tsuda en Yun-Kun Jiang, "Hypothesetest voor een verstrikte toestand geproduceerd door spontane parametrische neerwaartse conversie" Phys. Rev.A 74, 062321 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.062321

[33] Masahito Hayashi “Een groepstheoretische benadering van kwantuminformatie” Springer International Publishing (2017).
https://doi.org/10.1007/978-3-319-45241-8

[34] Masahito Hayashi “Groepsvertegenwoordiging voor kwantumtheorie” Springer International Publishing (2017).
https://doi.org/10.1007/978-3-319-44906-7

[35] Masahito Hayashi “Quantum Information Theory” Springer Berlin Heidelberg (2017).
https://doi.org/10.1007/978-3-662-49725-8

[36] Masahito Hayashi en Keiji Matsumoto "Quantum universele broncodering met variabele lengte" Physical Review A 66, 022311 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.66.022311
arXiv: 0202001

[37] Masahito Hayashi en Marco Tomamichel "Correlatiedetectie en een operationele interpretatie van de wederzijdse informatie van Rényi" Journal of Mathematical Physics 57, 102201 (2016).
https: / / doi.org/ 10.1063 / 1.4964755
arXiv: 1408.6894

[38] Masahito Hayashi, Akihisa Tomita en Keiji Matsumoto, "Statistische analyse van het testen van een verstrikte toestand gebaseerd op het Poisson-distributieraamwerk" New Journal of Physics 10, 043029 (2008).
https://doi.org/10.1088/1367-2630/10/4/043029

[39] L. Hendersonand V. Vedral "Klassieke, kwantum- en totale correlaties" Journal of Physics A: Mathematical and General 34, 6899–6905 (2001).
https://doi.org/10.1088/0305-4470/34/35/315
arXiv: 0105028

[40] M. Keyl “Kwantumtoestandschatting en grote afwijkingen” Recensies in Mathematical Physics 18, 19–60 (2006).
https: / / doi.org/ 10.1142 / S0129055X06002565

[41] Farzad Kianvash, Marco Fanizza en Vittorio Giovannetti, “De kwantumcapaciteit begrenzen met gemarkeerde uitbreidingen” Quantum 6, 647 (2022).
https://doi.org/10.22331/q-2022-02-09-647
arXiv: 2008.02461

[42] Martin Klieschand Ingo Roth “Theorie van kwantumsysteemcertificering” PRX Quantum 2, 010201 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.010201
arXiv: 2010.05925

[43] Hari Krovi “Een efficiënte hoogdimensionale kwantum Schur-transformatie” Quantum 3, 122 (2019).
https://doi.org/10.22331/q-2019-02-14-122
arXiv: 1804.00055
https: / / quantum-journal.org/ papers / q-2019-02-14-122 /

[44] M. Keyland RF Werner “Het schatten van het spectrum van een dichtheidsoperator” Physical Review A 64, 052311 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.052311
arXiv: 0102027

[45] Lucien Le Cam "Een benaderingsstelling voor de binominale verdeling van Poisson." Pacific Journal of Mathematics 10, 1181–1197 (1960).

[46] Felix Leditzky, Nilanjana Datta en Graeme Smith, "Nuttige staten en verstrengelingsdistillatie" IEEE-transacties over informatietheorie 64, 4689–4708 (2018).
https: / / doi.org/ 10.1109 / TIT.2017.2776907
arXiv: 1701.03081

[47] Erich L Lehmannand Joseph P Romano “Statistische hypothesen testen” Springer Science & Business Media (2006).

[48] Reut Levi, Dana Ron en Ronitt Rubinfeld, "Eigenschappen van verzamelingen van verdelingen testen" Theory of Computing 9, 295–347 (2013).
https: / / doi.org/ 10.4086 / toc.2013.v009a008
https:///theoryofcomputing.org/articles/v009a008

[49] Netanel H. Lindner, Petra F. Scudo en Dagmar Bruß, “Kwantumschatting van relatieve informatie” International Journal of Quantum Information 4, 131–149 (2006).
https: / / doi.org/ 10.1142 / S0219749906001657
arXiv: 0506223

[50] Ashley Montanaro en Ronald de Wolf “Een overzicht van het testen van kwantumeigenschappen” Theory of Computing 1, 1–81 (2016).
https: / / doi.org/ 10.4086 / toc.gs.2016.007
arXiv: 1310.2035
http:///www.theoryofcomputing.org/articles/gs007

[51] Ryan O'Donnelland John Wright "Quantum Spectrum Testing" Proceedings van het zevenenveertigste jaarlijkse ACM-symposium over Theory of Computing 14-17 juni, 529-538 (2015).
https: / / doi.org/ 10.1145 / 2746539.2746582
arXiv: 1501.05028

[52] Ryan O'Donnelland John Wright "Efficiënte kwantumtomografie" Proceedings van het achtenveertigste jaarlijkse ACM-symposium over Theory of Computing 19-21 juni, 899–912 (2016).
https: / / doi.org/ 10.1145 / 2897518.2897544
arXiv: 1508.01907

[53] Ryan O'Donnelland John Wright "Efficiënte kwantumtomografie II" Proceeding of the 49th Annual ACM SIGACT Symposium on Theory of Computing 962–974 (2017).
https: / / doi.org/ 10.1145 / 3055399.3055454
arXiv: 1612.00034

[54] Harold Ollivierand Wojciech H Zurek “Quantum Discord: een maatstaf voor de kwantumheid van correlaties” Physical Review Letters 88, 017901 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.88.017901
arXiv: 0105072

[55] Liam Paninski "Een op toeval gebaseerde test voor uniformiteit gegeven zeer schaars bemonsterde discrete gegevens" IEEE Transactions on Information Theory 54, 4750–4755 (2008).
https: / / doi.org/ 10.1109 / TIT.2008.928987
http:///ieeexplore.ieee.org/document/4626074/

[56] Gael Sentís, John Calsamiglia en Ramon Munoz-Tapia, “Exacte identificatie van een kwantumveranderingspunt” Physical Review Letters 119 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.140506
arXiv: 1707.07769

[57] Gael Sentís, Emilio Bagan, John Calsamiglia, Giulio Chiribella en Ramon Munoz-Tapia, “Quantum change point” Physical Review Letters 117 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.150502
arXiv: 1605.01916

[58] Gael Sentís, Esteban Martínez-Vargas en Ramon Muñoz-Tapia, "Onlinestrategieën voor het exact identificeren van een kwantumveranderingspunt" Physical Review A 98, 052305 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.052305
arXiv: 1802.00280

[59] Graeme Smith, John A. Smolin en Andreas Winter, "De kwantumcapaciteit met symmetrische zijkanalen" IEEE Transactions on Information Theory 54, 4208–4217 (2008).
https: / / doi.org/ 10.1109 / TIT.2008.928269
arXiv: 0607039

[60] Igal Sasonand Sergio Verdu "$f$ -Divergentie-ongelijkheid" IEEE-transacties over informatietheorie 62, 5973–6006 (2016).
https: / / doi.org/ 10.1109 / TIT.2016.2603151
arXiv: 1508.00335
https:///ieeexplore.ieee.org/document/7552457/

[61] Gregory Valiant en Paul Valiant "Een automatische ongelijkheidsbewijzer en optimale identiteitstests" 2014 IEEE 55e jaarlijkse symposium over de fundamenten van de computerwetenschappen 51–60 (2014).
https: / / doi.org/ 10.1109 / FOCS.2014.14
https:///ieeexplore.ieee.org/document/6978989/

[62] Xin Wang “De fundamentele grenzen voor kwantumcommunicatie nastreven” IEEE Transactions on Information Theory 67, 4524–4532 (2021).
https: / / doi.org/ 10.1109 / TIT.2021.3068818
arXiv: 1912.00931
https:///ieeexplore.ieee.org/document/9386074/

[63] Nengkun Yu "Voorbeeld van efficiënte identiteitstests en onafhankelijkheidstests van kwantumstaten" 12e Innovations in Theoretical Computer Science Conference (ITCS 2021) 185, 11: 1–11: 20 (2021).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2021.11
arXiv: 1904.03218
https:///drops.dagstuhl.de/opus/volltexte/2021/13550

[64] Nengkun Yu "Bijna strakke steekproefcomplexiteitsanalyse van kwantumidentiteitstests door Pauli-metingen" IEEE-transacties over informatietheorie 69, 5060–5068 (2023).
https: / / doi.org/ 10.1109 / TIT.2023.3271206
arXiv: 2009.11518

Geciteerd door

[1] Li Gao en Nengkun Yu, "Voorbeeld van optimale tomografie van kwantum-Markov-ketens", arXiv: 2209.02240, (2022).

[2] Marco Fanizza, Michalis Skotiniotis, John Calsamiglia, Ramon Muñoz-Tapia en Gael Sentís, "Universele algoritmen voor het leren van kwantumdata", EPL (Eurofysica Letters) 140 2, 28001 (2022).

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2023-09-13 12:15:38). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2023-09-13 12:15:37).

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.

Door SEO aangedreven content en PR-distributie. Word vandaag nog versterkt.
PlatoData.Network Verticale generatieve AI. Versterk jezelf. Toegang hier.
PlatoAiStream. Web3-intelligentie. Kennis versterkt. Toegang hier.
PlatoESG. Automotive / EV's, carbon, CleanTech, Energie, Milieu, Zonne, Afvalbeheer. Toegang hier.
Plato Gezondheid. Intelligentie op het gebied van biotech en klinische proeven. Toegang hier.
ChartPrime. Verhoog uw handelsspel met ChartPrime. Toegang hier.
BlockOffsets. Eigendom voor milieucompensatie moderniseren. Toegang hier.
Bron: https://quantum-journal.org/papers/q-2023-09-11-1105/

Tijdstempel: 11 september 2023

Tijdstempel: September 7, 2023

Testen van de identiteit van verzamelingen kwantumtoestanden: analyse van de complexiteit van monsters

Heruitgegeven door Plato

Abstract

► BibTeX-gegevens

► Referenties

Geciteerd door

Meer van Quantum Journaal

Het bereiken van de limiet van de kwantumveldentheorie in kwantumlinkmodellen die ver van het evenwicht zijn

Qubits verdelen in hypergraph-productcodes om logische poorten te implementeren

Gelijktijdige schatting van meerdere eigenwaarden met een kwantumcircuit met korte diepte op vroege fouttolerante kwantumcomputers

Incompatibiliteit van kwantuminstrumenten

Adaptieve variatiesimulatie voor open kwantumsystemen

Verbeterde kwantumalgoritmen voor lineaire en niet-lineaire differentiaalvergelijkingen

Over Ons

Verticaal zoeken & Ai

Platform

Blijf verbonden

Account