Kvanttitilojen kokoelmien identiteetin testaus: näytteen monimutkaisuusanalyysi

Kvanttitilojen kokoelmien identiteetin testaus: näytteen monimutkaisuusanalyysi

Aikaleima: 11. syyskuuta 2023 8

Marco Fanizza1, Raffaele Salvia2ja Vittorio Giovannetti3

1Física Teòrica: Informació i Fenòmens Quantics, Departament de Física, Universitat Autònoma de Barcelona, ​​08193 Bellaterra, Espanja.
2Scuola Normale Superiore, I-56127 Pisa, Italia.
3NEST, Scuola Normale Superiore ja Istituto Nanoscienze-CNR, I-56127 Pisa, Italia.

Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.

Abstrakti

Tutkimme ongelmaa, joka liittyy tuntemattomien kvanttitilojen kokoelman identiteetin testaamiseen, jolle annetaan näytepääsy tähän kokoelmaan, ja jokainen tila esiintyy jollakin tunnetulla todennäköisyydellä. Osoitamme, että joukolle $d$-ulotteisia kardinaalisuuden $N$ kvanttitiloja näytteen kompleksisuus on $O(sqrt{N}d/epsilon^2)$, ja vastaava alaraja, aina kertovakioon asti. . Testi saadaan arvioimalla tilojen välinen keskineliö Hilbert-Schmidt -etäisyys Bădescun, O'Donnellin ja Wrightin kahden tuntemattoman tilan välisen Hilbert-Schmidtin etäisyyden estimaattorin sopivan yleistyksen ansiosta [13].

Kvanttitilojen kokoelmien identiteetin testaus: näytteen monimutkaisuusanalyysi PlatoBlockchain Data Intelligence. Pystysuuntainen haku. Ai.

Suositeltu kuva: Kaksi asetusta, joita mallimme koskee. Kohdassa a) riippumattomat lähteet tuottavat satunnaisluvun, Poisson-jakauman, tilan kopioita ajassa $T$. Kohdassa b) mittausmenettely valmistelee leimattuja tiloja, joista jokainen esiintyy jollain todennäköisyydellä.

► BibTeX-tiedot

► Viitteet

[1] Gerardo Adesso, Thomas R. Bromley ja Marco Cianciaruso, "Measures and Applications of Quantum Correlations" 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 ja Aaron B. Wagner, "Estimating Quantum Entropy" IEEE Journal on Selected Areas in Information Theory 1, 454–468 (2020).
https: / / doi.org/ 10.1109 / JSAIT.2020.3015235
https://​/​ieeexplore.ieee.org/​document/​9163139/​

[3] Jayadev Acharya ja Constantinos Daskalakis "Myrkytyksen binomiaalisten jakaumien testaus" Proceedings of Twenty-1829th Annual ACM-SIAM Symposium on Discrete Algorithms 1840–2015 (XNUMX).
https: / / doi.org/ 10.1137 / +1.9781611973730.122
arXiv: 1507.05952

[4] Daiki Akimoto ja Masahito Hayashi "Muutospisteen erottelu kvanttiympäristössä" Physical Review A 83, 052328 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.052328
arXiv: 1102.2555

[5] Robert Alicki, Slawomir Rudnicki ja Slawomir Sadowski, "Tuotetilojen symmetriaominaisuudet N n-tason atomien järjestelmälle" 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 ja Giulio Chiribella, "Quantum causal unravelling" 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 ja Patrick White, "Satunnaismuuttujien riippumattomuuden ja identiteetin testaus" Proceedings 42nd IEEE Symposium on Foundations of Computer Science 442–451 (2001).
https: / / doi.org/ 10.1109 / SFCS.2001.959920
https://​/​ieeexplore.ieee.org/​document/​959920/​

[8] Dave Bacon, Isaac L. Chuang ja Aram W. Harrow, "Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms" Physical Review Letters 97, 170502 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.170502
arXiv: 0407082

[9] Sebastien Bubeck, Sitan Chen ja Jerry Li, "Setanglement is Necessary for Optimal Quantum Property Testing" 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (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 ja Andreas Winter, "The Quantum Reverse Shannon Theorem and Resource Tradeoffs for Simulating 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 ja R. Muñoz-Tapia, "Suhteelliset tilat, kvanttiakselit ja kvanttiviittaukset" Physical Review A 73, 022341 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022341
arXiv: 0508187

[12] Stéphane Boucheron, Gábor Lugosi ja Pascal Massart, "Concentration Inequalities" Oxford University Press (2013).
https: / / doi.org/ 10.1093 / acprof: OSO / 9780199535255.001.0001

[13] Costin Bădescu, Ryan O'Donnell ja John Wright, "Quantum state certification" Proceedings of 51st 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 ja Robert W. Spekkens, "Suhteellisen kvanttitiedon optimaaliset mittaukset" Physical Review A 70, 032321 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.032321
arXiv: 0310009

[15] Harry Buhrman, Richard Cleve, John Watrous ja 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 ”Tutkimus jakelutestauksesta: tietosi ovat suuria. Mutta onko se sininen?" Laskennan teoria 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 ja Gregory Valiant, "Optimal Algorithms for Testing Closeness of Discrete Distributions" Proceedings of Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms 1193–1203 (2014).
https: / / doi.org/ 10.1137 / +1.9781611973402.88
arXiv: 1308.3946

[18] Matthias Christandl "Kaksipuolisten kvanttitilojen rakenne – Insights from Group Theory and Cryptography" (2006).
arXiv: 0604183

[19] Sitan Chen, Jerry Li ja 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. /​v178/​chen22b.html.
arXiv: 2102.13098

[20] Thomas M. Coverand Joy A. Thomas "Informaatioteorian elementit" (2005).
https: / / doi.org/ 10.1002 / 047174882X

[21] Ilias Diakonikolas ja Daniel M. Kane "Uusi lähestymistapa diskreettien jakaumien ominaisuuksien testaamiseen" 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (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 ja Vladimir Nikishkin, "Testing Identity of Structured Distributions" Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms 2015-tammikuu, 1841-1854 (2015).
https: / / doi.org/ 10.1137 / +1.9781611973730.123

[23] M. Fanizza, M. Rosati, M. Skotiniotis, J. Calsamiglia ja 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 ja John Calsamiglia, "Ultimate Limits for Quickest Quantum Change-Point Detection" Phys. Rev. Lett. 131, 020602 (2023).
https: / / doi.org/ 10.1103 / PhysRevLett.131.020602
arXiv: 2208.03265

[25] Marco Fanizza, Farzad Kianvash ja Vittorio Giovannetti, "Kvanttiliput ja uudet rajat depolarisoivan kanavan kvanttikapasiteetille" Physical Review Letters 125, 020503 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.020503
arXiv: 1911.01977

[26] Marco Fanizza, Farzad Kianvash ja Vittorio Giovannetti, "Gaussian Channels Quantum and Private Capacitys via Degradable Extensions" Phys. Rev. Lett. 127, 210501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.210501
arXiv: 2103.09569

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

[28] Oded Goldreich "Johdatus omaisuustestaukseen" Cambridge University Press (2017).
https: / / doi.org/ 10.1017 / +9781108135252

[29] Oded Goldreichand Dana Ron "On Testing Expansion in Bounded-Degree Graphs" (2011).
https:/​/​doi.org/​10.1007/​978-3-642-22670-0_9

[30] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu ja Nengkun Yu, "Sample-optimal tomography of quantum states" 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 "Koherentin klassisen viestinnän sovellukset ja Schur-muunnos kvanttitietoteoriaksi" (2005).
arXiv: 0512255

[32] Masahito Hayashi, Bao-Sen Shi, Akihisa Tomita, Keiji Matsumoto, Yoshiyuki Tsuda ja Yun-Kun Jiang, "Hypoteesin testaus spontaanin parametrisen alasmuunnoksen tuottaman sotkeutuneen tilan suhteen" Phys. Rev. A 74, 062321 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.062321

[33] Masahito Hayashi "Kvanttiinformaation ryhmäteoreettinen lähestymistapa" Springer International Publishing (2017).
https:/​/​doi.org/​10.1007/​978-3-319-45241-8

[34] Masahito Hayashi "Group Representation for Quantum Theory" Springer International Publishing (2017).
https:/​/​doi.org/​10.1007/​978-3-319-44906-7

[35] Masahito Hayashi "Kvanttiinformaatioteoria" Springer Berlin Heidelberg (2017).
https:/​/​doi.org/​10.1007/​978-3-662-49725-8

[36] Masahito Hayashi ja Keiji Matsumoto "Kvanttiuniversaali muuttuvapituinen lähdekoodaus" Physical Review A 66, 022311 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.66.022311
arXiv: 0202001

[37] Masahito Hayashi ja Marco Tomamichel "Korrelaation havaitseminen ja Rényi-keskisten tietojen operatiivinen tulkinta" Journal of Mathematical Physics 57, 102201 (2016).
https: / / doi.org/ 10.1063 / +1.4964755
arXiv: 1408.6894

[38] Masahito Hayashi, Akihisa Tomita ja Keiji Matsumoto, "Tilastollinen analyysi takertuneen tilan testaamisesta Poisson-jakaumakehyksen perusteella" New Journal of Physics 10, 043029 (2008).
https:/​/​doi.org/​10.1088/​1367-2630/​10/​4/​043029

[39] L. Hendersonand V. Vedral "Klassiset, kvantti- ja kokonaiskorrelaatiot" 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 "Kvanttitilaestimointi ja suuret poikkeamat" Reviews in Mathematical Physics 18, 19–60 (2006).
https: / / doi.org/ 10.1142 / S0129055X06002565

[41] Farzad Kianvash, Marco Fanizza ja Vittorio Giovannetti, "Kvanttikapasiteetin rajoittaminen merkittyjen laajennusten kanssa" Quantum 6, 647 (2022).
https:/​/​doi.org/​10.22331/​q-2022-02-09-647
arXiv: 2008.02461

[42] Martin Klieschand Ingo Roth "Kvanttijärjestelmän sertifioinnin teoria" PRX Quantum 2, 010201 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.010201
arXiv: 2010.05925

[43] Hari Krovi "Tehokas korkeaulotteinen kvantti-Schur-muunnos" 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 "Tiheysoperaattorin spektrin arviointi" Physical Review A 64, 052311 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.052311
arXiv: 0102027

[45] Lucien Le Cam "Approksimaatiolause Poissonin binomijakaumaa varten." Pacific Journal of Mathematics 10, 1181–1197 (1960).

[46] Felix Leditzky, Nilanjana Datta ja Graeme Smith, "Useful States and Entanglement Distillation" IEEE Transactions on Information Theory 64, 4689–4708 (2018).
https: / / doi.org/ 10.1109 / TIT.2017.2776907
arXiv: 1701.03081

[47] Erich L Lehmannand Joseph P Romano "Tilastollisten hypoteesien testaus" Springer Science & Business Media (2006).

[48] Reut Levi, Dana Ron ja Ronitt Rubinfeld, "Testing Properties of Collections of Distributions" 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 ja Dagmar Bruß, "Suhteellisen tiedon kvanttiestimointi" International Journal of Quantum Information 4, 131–149 (2006).
https: / / doi.org/ 10.1142 / S0219749906001657
arXiv: 0506223

[50] Ashley Montanaro ja Ronald de Wolf "Kvanttiominaisuustestauksen kysely" 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 of the 14. vuotuinen ACM symposium on Theory of Computing 17.-529., 538-2015 (XNUMX).
https: / / doi.org/ 10.1145 / +2746539.2746582
arXiv: 1501.05028

[52] Ryan O'Donnelland John Wright "Tehokas kvanttitomografia" Proceedings of the 19th vuotuinen ACM symposium on Theory of Computing 21.-899., 912-2016 (XNUMX).
https: / / doi.org/ 10.1145 / +2897518.2897544
arXiv: 1508.01907

[53] Ryan O'Donnelland John Wright "Tehokas kvanttitomografia II" Proceedings of 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 "Kvanttiriita: korrelaatioiden kvantiteetin mitta" Physical Review Letters 88, 017901 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.88.017901
arXiv: 0105072

[55] Liam Paninski "Sattuma-pohjainen testi yhtenäisyydestä, kun on annettu erittäin harvoin otettuja diskreettejä tietoja" 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 ja Ramon Munoz-Tapia, "Kvanttimuutospisteen tarkka tunnistus" 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 ja 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 ja Ramon Muñoz-Tapia, "Online-strategioita kvanttimuutospisteen täsmälliseen tunnistamiseen" Physical Review A 98, 052305 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.052305
arXiv: 1802.00280

[59] Graeme Smith, John A. Smolin ja Andreas Winter, "Kvanttikapasiteetti symmetrisillä sivukanavilla" 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$ - Divergenssin epätasa-arvot" IEEE Transactions on Information Theory 62, 5973–6006 (2016).
https: / / doi.org/ 10.1109 / TIT.2016.2603151
arXiv: 1508.00335
https://​/​ieeexplore.ieee.org/​document/​7552457/​

[61] Gregory Valiantand Paul Valiant "Automaattinen epätasa-arvon todistaja ja optimaalinen identiteettitestaus" 2014 IEEE 55th Annual Symposium on Foundations of Computer Science 51–60 (2014).
https: / / doi.org/ 10.1109 / FOCS.2014.14
https://​/​ieeexplore.ieee.org/​document/​6978989/​

[62] Xin Wang "Kvanttiviestinnän perusrajojen tavoittelu" 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 “Sample Efficient Identity Testing and Independence Testing of Quantum States” 12. 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 "Almost Tight Sample Complexity Analysis of Quantum Identity Testing by Pauli Measurements" IEEE Transactions on Information Theory 69, 5060–5068 (2023).
https: / / doi.org/ 10.1109 / TIT.2023.3271206
arXiv: 2009.11518

Viitattu

[1] Li Gao ja Nengkun Yu, "Sample optimal tomography of Quantum Markov chains", arXiv: 2209.02240, (2022).

[2] Marco Fanizza, Michalis Skotiniotis, John Calsamiglia, Ramon Muñoz-Tapia ja Gael Sentís, "Universaalit algoritmit kvanttidatan oppimiseen", EPL (Europhysics Letters) 140 2, 28001 (2022).

Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2023-09-13 12:15:38). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.

On Crossrefin siteerattu palvelu tietoja teosten viittaamisesta ei löytynyt (viimeinen yritys 2023-09-13 12:15:37).

Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.

Aikaleima:

Lisää aiheesta Quantum Journal