Testiranje identitete zbirk kvantnih stanj: analiza kompleksnosti vzorcev

Testiranje identitete zbirk kvantnih stanj: analiza kompleksnosti vzorcev

Časovni žig: 11. september 2023 8

Marco Fanizza1, Raffaele Salvia2in Vittorio Giovannetti3

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

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Preučujemo problem testiranja identitete zbirke neznanih kvantnih stanj z vzorčnim dostopom do te zbirke, pri čemer se vsako stanje pojavi z neko znano verjetnostjo. Pokažemo, da je za zbirko $d$-dimenzionalnih kvantnih stanj kardinalnosti $N$ kompleksnost vzorca $O(sqrt{N}d/epsilon^2)$ z ujemajočo se spodnjo mejo, do multiplikativne konstante . Test dobimo z oceno srednjega kvadrata Hilbert-Schmidtove razdalje med stanji, zahvaljujoč ustrezni posplošitvi ocenjevalca Hilbert-Schmidtove razdalje med dvema neznanima stanjema Bădescuja, O'Donnella in Wrighta [13].

Testiranje identitete zbirk kvantnih stanj: analiza kompleksnosti vzorcev PlatoBlockchain Data Intelligence. Navpično iskanje. Ai.

Predstavljena slika: dve nastavitvi, za katere velja naš model. V a) neodvisni viri ustvarijo naključno število, Poissonovo porazdeljeno, kopij stanja v času $T$. V b) merilni postopek pripravi označena stanja, pri čemer se vsaka oznaka pojavi z določeno verjetnostjo.

► BibTeX podatki

► Reference

[1] Gerardo Adesso, Thomas R. Bromley in Marco Cianciaruso, »Meritve in aplikacije kvantnih korelacij«, 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 in 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 in Constantinos Daskalakis »Testiranje Poissonovih binomskih porazdelitev« Zbornik šestindvajsetega letnega simpozija ACM-SIAM o diskretnih algoritmih 1829–1840 (2015).
https: / / doi.org/ 10.1137 / 1.9781611973730.122
arXiv: 1507.05952

[4] Daiki Akimoto in Masahito Hayashi »Razlikovanje točke spremembe v kvantni nastavitvi« Physical Review A 83, 052328 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.052328
arXiv: 1102.2555

[5] Robert Alicki, Slawomir Rudnicki in Slawomir Sadowski, “Simetrične lastnosti produktnih stanj za sistem atomov na ravni N n” 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 in Giulio Chiribella, »Kvantno vzročno razpletanje« npj Kvantne informacije 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 in Patrick White, “Testiranje naključnih spremenljivk za neodvisnost in identiteto” Zbornik 42. simpozija IEEE o temeljih računalništva 442–451 (2001).
https: / / doi.org/ 10.1109 / SFCS.2001.959920
https://​/​ieeexplore.ieee.org/​document/​959920/​

[8] Dave Bacon, Isaac L. Chuang in Aram W. Harrow, »Učinkovita kvantna vezja za Schur in Clebsch-Gordanove transformacije« Physical Review Letters 97, 170502 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.170502
arXiv: 0407082

[9] Sebastien Bubeck, Sitan Chen in Jerry Li, »Prepletenost je potrebna za optimalno testiranje kvantnih lastnosti«, 2020, 61. letni simpozij IEEE o temeljih računalništva (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 in Andreas Winter, »Kvantni obratni Shannonov izrek in kompromisi virov za simulacijo kvantnih kanalov« 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 in R. Muñoz-Tapia, »Relativna stanja, kvantne osi in kvantne reference« Physical Review A 73, 022341 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022341
arXiv: 0508187

[12] Stéphane Boucheron, Gábor Lugosi in 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 in John Wright, »Quantum state certification« Zbornik 51. letnega simpozija ACM SIGACT o teoriji računalništva 503–514 (2019).
https: / / doi.org/ 10.1145 / 3313276.3316344
arXiv: 1708.06002

[14] Stephen D. Bartlett, Terry Rudolph in Robert W. Spekkens, »Optimalne meritve za relativne kvantne informacije« Physical Review A 70, 032321 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.032321
arXiv: 0310009

[15] Harry Buhrman, Richard Cleve, John Watrous in 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 »Anketa o testiranju distribucije: Vaši podatki so veliki. Toda ali je modra? Teorija računalništva 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 in Gregory Valiant, »Optimalni algoritmi za testiranje bližine diskretnih porazdelitev« Zbornik petindvajsetega letnega simpozija ACM-SIAM o diskretnih algoritmih 1193–1203 (2014).
https: / / doi.org/ 10.1137 / 1.9781611973402.88
arXiv: 1308.3946

[18] Matthias Christandl »Struktura bipartitnih kvantnih stanj – vpogled v teorijo skupin in kriptografijo« (2006).
arXiv: 0604183

[19] Sitan Chen, Jerry Li in 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 in Joy A. Thomas »Elementi teorije informacij« (2005).
https: / / doi.org/ 10.1002 / 047174882X

[21] Ilias Diakonikolas in Daniel M. Kane »Nov pristop za testiranje lastnosti diskretnih porazdelitev« 2016 57. letni simpozij IEEE o temeljih računalništva (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 in Vladimir Nikishkin, »Testing Identity of Structured Distributions« Zbornik šestindvajsetega letnega simpozija ACM-SIAM o diskretnih algoritmih 2015-Janua, 1841–1854 (2015).
https: / / doi.org/ 10.1137 / 1.9781611973730.123

[23] M. Fanizza, M. Rosati, M. Skotiniotis, J. Calsamiglia in V. Giovannetti, »Onkraj preizkusa zamenjave: optimalna ocena prekrivanja kvantnega stanja« Physical Review Letters 124, 060503 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.124.060503
arXiv: 1906.10639

[24] Marco Fanizza, Christoph Hirche in 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 in Vittorio Giovannetti, »Kvantne zastavice in nove meje kvantne zmogljivosti depolarizirajočega kanala« Physical Review Letters 125, 020503 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.020503
arXiv: 1911.01977

[26] Marco Fanizza, Farzad Kianvash in Vittorio Giovannetti, »Ocenjevanje kvantnih in zasebnih zmogljivosti Gaussovih kanalov prek razgradljivih razširitev« Phys. Rev. Lett. 127, 210501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.210501
arXiv: 2103.09569

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

[28] Oded Goldreich »Uvod v testiranje lastnosti« Cambridge University Press (2017).
https: / / doi.org/ 10.1017 / 9781108135252

[29] Oded Goldreichand Dana Ron »O testiranju razširitve v grafih z omejenimi stopinjami« (2011).
https:/​/​doi.org/​10.1007/​978-3-642-22670-0_9

[30] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu in Nengkun Yu, »Vzorčna optimalna tomografija kvantnih stanj« 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 »Uporaba koherentne klasične komunikacije in Schurjeve transformacije v kvantni informacijski teoriji« (2005).
arXiv: 0512255

[32] Masahito Hayashi, Bao-Sen Shi, Akihisa Tomita, Keiji Matsumoto, Yoshiyuki Tsuda in Yun-Kun Jiang, »Preizkušanje hipotez za zapleteno stanje, ki ga povzroči spontana parametrična pretvorba navzdol« Phys. Rev. A 74, 062321 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.062321

[33] Masahito Hayashi »Grupinski teoretični pristop k kvantnim informacijam« 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 “Kvantna teorija informacij” Springer Berlin Heidelberg (2017).
https:/​/​doi.org/​10.1007/​978-3-662-49725-8

[36] Masahito Hayashiand Keiji Matsumoto “Kvantno univerzalno izvorno kodiranje s spremenljivo dolžino” Physical Review A 66, 022311 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.66.022311
arXiv: 0202001

[37] Masahito Hayashi in Marco Tomamichel »Odkrivanje korelacije in operativna interpretacija vzajemnih informacij Rényi« Journal of Mathematical Physics 57, 102201 (2016).
https: / / doi.org/ 10.1063 / 1.4964755
arXiv: 1408.6894

[38] Masahito Hayashi, Akihisa Tomita in Keiji Matsumoto, »Statistična analiza testiranja prepletenega stanja na podlagi okvira Poissonove porazdelitve« New Journal of Physics 10, 043029 (2008).
https:/​/​doi.org/​10.1088/​1367-2630/​10/​4/​043029

[39] L. Henderson in V. Vedral “Klasične, kvantne in popolne korelacije” 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 “Ocena kvantnega stanja in velika odstopanja” Reviews in Mathematical Physics 18, 19–60 (2006).
https: / / doi.org/ 10.1142 / S0129055X06002565

[41] Farzad Kianvash, Marco Fanizza in Vittorio Giovannetti, »Omejevanje kvantne zmogljivosti z označenimi razširitvami« Quantum 6, 647 (2022).
https:/​/​doi.org/​10.22331/​q-2022-02-09-647
arXiv: 2008.02461

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

[43] Hari Krovi »Učinkovita visokodimenzionalna kvantna Schurjeva transformacija« 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 “Ocenjevanje spektra operatorja gostote” Physical Review A 64, 052311 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.052311
arXiv: 0102027

[45] Lucien Le Cam "Aproksimacijski izrek za Poissonovo binomsko porazdelitev." Pacific Journal of Mathematics 10, 1181–1197 (1960).

[46] Felix Leditzky, Nilanjana Datta in Graeme Smith, »Uporabna stanja in destilacija zapletenosti« 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 »Preizkušanje statističnih hipotez« Springer Science & Business Media (2006).

[48] Reut Levi, Dana Ron in Ronitt Rubinfeld, »Testiranje lastnosti zbirk distribucij« Teorija računalništva 9, 295–347 (2013).
https: / / doi.org/ 10.4086 / toc.2013.v009a008
https://​/​theoryofcomputing.org/​articles/​v009a008

[49] Netanel H. Lindner, Petra F. Scudo in Dagmar Bruß, »Kvantna ocena relativne informacije« Mednarodni časopis za kvantne informacije 4, 131–149 (2006).
https: / / doi.org/ 10.1142 / S0219749906001657
arXiv: 0506223

[50] Ashley Montanaro in Ronald de Wolf "Raziskava o testiranju kvantnih lastnosti" 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 »Testiranje kvantnega spektra« Zbornik sedeminštiridesetega letnega simpozija ACM o teoriji računalništva 14.–17. junija, 529–538 (2015).
https: / / doi.org/ 10.1145 / 2746539.2746582
arXiv: 1501.05028

[52] Ryan O'Donnelland John Wright »Učinkovita kvantna tomografija« Zbornik oseminštiridesetega letnega simpozija ACM o teoriji računalništva 19.–21. junija, 899–912 (2016).
https: / / doi.org/ 10.1145 / 2897518.2897544
arXiv: 1508.01907

[53] Ryan O'Donnelland John Wright »Učinkovita kvantna tomografija II« Zbornik 49. letnega simpozija ACM SIGACT o teoriji računalništva 962–974 (2017).
https: / / doi.org/ 10.1145 / 3055399.3055454
arXiv: 1612.00034

[54] Harold Ollivier in Wojciech H Zurek “Kvantno neskladje: merilo kvantnosti korelacije” Physical Review Letters 88, 017901 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.88.017901
arXiv: 0105072

[55] Liam Paninski »Na naključju temelječ test enotnosti glede na zelo redko vzorčene diskretne podatke« 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 in Ramon Munoz-Tapia, »Natančna identifikacija točke kvantne spremembe« 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 in 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 in Ramon Muñoz-Tapia, »Spletne strategije za natančno identifikacijo točke kvantne spremembe« Physical Review A 98, 052305 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.052305
arXiv: 1802.00280

[59] Graeme Smith, John A. Smolin in Andreas Winter, »Kvantna zmogljivost s simetričnimi stranskimi kanali« IEEE Transactions on Information Theory 54, 4208–4217 (2008).
https: / / doi.org/ 10.1109 / TIT.2008.928269
arXiv: 0607039

[60] Igal Sason in Sergio Verdu “$f$ -Divergence Inequalities” 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 Valiant in Paul Valiant »An Automatic Inequality Prover and Instance Optimal Identity Testing« 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 »Prizadevanje za temeljne omejitve kvantne komunikacije« 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 »Vzorčno učinkovito testiranje identitete in testiranje neodvisnosti kvantnih stanj« 12. konferenca o inovacijah v teoretični računalniški znanosti (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 »Analiza kompleksnosti skoraj tesnega vzorca testiranja kvantne identitete s Paulijevimi meritvami« IEEE Transactions on Information Theory 69, 5060–5068 (2023).
https: / / doi.org/ 10.1109 / TIT.2023.3271206
arXiv: 2009.11518

Navedel

[1] Li Gao in Nengkun Yu, "Vzorec optimalne tomografije kvantnih markovskih verig", arXiv: 2209.02240, (2022).

[2] Marco Fanizza, Michalis Skotiniotis, John Calsamiglia, Ramon Muñoz-Tapia in Gael Sentís, "Univerzalni algoritmi za kvantno učenje podatkov", EPL (Europhysics Letters) 140 2, 28001 (2022).

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2023-09-13 12:15:38). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2023-09-13 12:15:37).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal