Testarea identității colecțiilor de stări cuantice: analiza complexității eșantionului

Testarea identității colecțiilor de stări cuantice: analiza complexității eșantionului

Marca temporală: 11 septembrie 2023, ora 8:05

Marco Fanizza1, Raffaele Salvia2, și Vittorio Giovannetti3

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

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

Studiem problema testării identității unei colecții de stări cuantice necunoscute având acces la eșantion la această colecție, fiecare stare apărând cu o anumită probabilitate cunoscută. Arătăm că pentru o colecție de stări cuantice de cardinalitate $d$-dimensionale $N$, complexitatea eșantionului este $O(sqrt{N}d/epsilon^2)$, cu o limită inferioară de potrivire, până la o constantă multiplicativă . Testul se obține prin estimarea mediei pătrate a distanței Hilbert-Schmidt dintre stări, grație unei generalizări adecvate a estimatorului distanței Hilbert-Schmidt între două stări necunoscute de către Bădescu, O'Donnell și Wright.13].

Testarea identității colecțiilor de stări cuantice: analiza complexității eșantionului PlatoBlockchain Data Intelligence. Căutare verticală. Ai.

Imagine prezentată: două setări la care se aplică modelul nostru. În a) sursele independente produc un număr aleatoriu, distribuit de Poisson, de copii ale unei stări într-un timp $T$. În b), o procedură de măsurare pregătește stări etichetate, fiecare etichetă apărând cu o anumită probabilitate.

► Date BibTeX

► Referințe

[1] Gerardo Adesso, Thomas R. Bromley și Marco Cianciaruso, „Măsuri și aplicații ale corelațiilor cuantice” 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 și 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 și Constantinos Daskalakis „Testing Poisson Binomial Distributions” Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms 1829–1840 (2015).
https: / / doi.org/ 10.1137 / 1.9781611973730.122
arXiv: 1507.05952

[4] Daiki Akimoto și Masahito Hayashi „Discriminarea punctului de schimbare într-un cadru cuantic” Physical Review A 83, 052328 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.052328
arXiv: 1102.2555

[5] Robert Alicki, Slawomir Rudnicki și Slawomir Sadowski, „Proprietățile de simetrie ale stărilor de produs pentru sistemul de N atomi de nivel 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 și 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 și Patrick White, „Testarea variabilelor aleatoare pentru independență și identitate” Proceedings 42th 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 și 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 și Jerry Li, „Entanglement is Necessary for Optimal Quantum Property Testing” 2020 IEEE 61th 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 și 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 și R. Muñoz-Tapia, „Stări relative, axe cuantice și referințe cuantice” Physical Review A 73, 022341 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022341
arXiv: 0508187

[12] Stéphane Boucheron, Gábor Lugosi și 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 și John Wright, „Quantum state certification” Proceedings of the 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 și Robert W. Spekkens, „Măsurări optime pentru informații cuantice relative” Physical Review A 70, 032321 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.032321
arXiv: 0310009

[15] Harry Buhrman, Richard Cleve, John Watrous și 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 „Un sondaj privind testarea distribuției: datele tale sunt mari. Dar este albastru?” Teoria calculului 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 și Gregory Valiant, „Algoritmi optimi pentru testarea apropierii distribuțiilor discrete” Proceedings of the 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 „Structura statelor cuantice bipartite – Perspective din teoria grupurilor și criptografia” (2006).
arXiv: 0604183

[19] Sitan Chen, Jerry Li și Ryan O'Donnell, „Toward Instance-Optimal State Certification With Incoerent 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 și Joy A. Thomas „Elemente de teoria informației” (2005).
https: / / doi.org/ 10.1002 / 047174882X

[21] Ilias Diakonikolas și Daniel M. Kane „A New Approach for Testing Properties of Discrete Distributions” 2016 Simpozionul anual al 57-a IEEE privind fundamentele informaticii (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 și Vladimir Nikishkin, „Testing Identity of Structured Distributions” Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms 2015-Janua, 1841–1854 (2015).
https: / / doi.org/ 10.1137 / 1.9781611973730.123

[23] M. Fanizza, M. Rosati, M. Skotiniotis, J. Calsamiglia și 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 și 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 și Vittorio Giovannetti, „Drapele cuantice și noi limite privind capacitatea cuantică a canalului de depolarizare” Physical Review Letters 125, 020503 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.020503
arXiv: 1911.01977

[26] Marco Fanizza, Farzad Kianvash și Vittorio Giovannetti, „Estimarea capacităților cuantice și private ale canalelor gaussiene prin extensii degradabile” Phys. Rev. Lett. 127, 210501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.210501
arXiv: 2103.09569

[27] N. Gisinand S. Iblisdir „Stări relative cuantice” The European Physical Journal D 39, 321–327 (2006).
https: / / doi.org/ 10.1140 / epjd / e2006-00097-y
arXiv: 0507118

[28] Oded Goldreich „Introducere în testarea proprietății” 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 și 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 „Aplicații ale comunicării clasice coerente și transformarea Schur în teoria informației cuantice” (2005).
arXiv: 0512255

[32] Masahito Hayashi, Bao-Sen Shi, Akihisa Tomita, Keiji Matsumoto, Yoshiyuki Tsuda și Yun-Kun Jiang, „Testarea ipotezei pentru o stare încurcată produsă de o conversie în jos parametrică spontană” Fizica. Rev. A 74, 062321 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.062321

[33] Masahito Hayashi „O abordare teoretică de grup a informațiilor cuantice” Springer International Publishing (2017).
https:/​/​doi.org/​10.1007/​978-3-319-45241-8

[34] Masahito Hayashi „Reprezentarea grupului pentru teoria cuantică” Springer International Publishing (2017).
https:/​/​doi.org/​10.1007/​978-3-319-44906-7

[35] Masahito Hayashi „Teoria informațiilor cuantice” Springer Berlin Heidelberg (2017).
https:/​/​doi.org/​10.1007/​978-3-662-49725-8

[36] Masahito Hayashi și Keiji Matsumoto „Codare sursă cu lungime variabilă universală cuantică” Physical Review A 66, 022311 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.66.022311
arXiv: 0202001

[37] Masahito Hayashi și Marco Tomamichel „Detecția corelației și o interpretare operațională a informațiilor reciproce Rényi” Journal of Mathematical Physics 57, 102201 (2016).
https: / / doi.org/ 10.1063 / 1.4964755
arXiv: 1408.6894

[38] Masahito Hayashi, Akihisa Tomita și Keiji Matsumoto, „Analiza statistică a testării unei stări încurcate pe baza cadrului de distribuție Poisson” New Journal of Physics 10, 043029 (2008).
https:/​/​doi.org/​10.1088/​1367-2630/​10/​4/​043029

[39] L. Henderson și V. Vedral „Corelări clasice, cuantice și totale” 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 „Estimarea stării cuantice și abaterile mari” Reviews in Mathematical Physics 18, 19–60 (2006).
https: / / doi.org/ 10.1142 / S0129055X06002565

[41] Farzad Kianvash, Marco Fanizza și Vittorio Giovannetti, „Bounding the quantum capacity with flagged extensions” Quantum 6, 647 (2022).
https:/​/​doi.org/​10.22331/​q-2022-02-09-647
arXiv: 2008.02461

[42] Martin Klieschand Ingo Roth „Teoria certificării sistemelor cuantice” PRX Quantum 2, 010201 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.010201
arXiv: 2010.05925

[43] Hari Krovi „O transformare Schur cuantică de înaltă dimensiune eficientă” 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 „Estimarea spectrului unui operator de densitate” Physical Review A 64, 052311 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.052311
arXiv: 0102027

[45] Lucien Le Cam „O teoremă de aproximare pentru distribuția binomială Poisson”. Pacific Journal of Mathematics 10, 1181–1197 (1960).

[46] Felix Leditzky, Nilanjana Datta și 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 „Testarea ipotezelor statistice” Springer Science & Business Media (2006).

[48] Reut Levi, Dana Ron și 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 și Dagmar Bruß, „Estimarea cuantică a informațiilor relative” International Journal of Quantum Information 4, 131–149 (2006).
https: / / doi.org/ 10.1142 / S0219749906001657
arXiv: 0506223

[50] Ashley Montanaro și Ronald de Wolf „A survey of quantum property testing” 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 „Testarea cuantică a spectrului” Actele celui de-al patruzeci și șaptelea simpozion anual ACM privind teoria calculului 14-17-iunie, 529-538 (2015).
https: / / doi.org/ 10.1145 / 2746539.2746582
arXiv: 1501.05028

[52] Ryan O'Donnelland John Wright „Tomografie cuantică eficientă” Proceedings of the fourty-19th annual ACM symposium on Theory of Computing 21-899-iunie, 912–2016 (XNUMX).
https: / / doi.org/ 10.1145 / 2897518.2897544
arXiv: 1508.01907

[53] Ryan O'Donnelland John Wright „Tomografie cuantică eficientă II” Proceedings 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 „Discord cuantic: o măsură a cuanticității corelațiilor” Physical Review Letters 88, 017901 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.88.017901
arXiv: 0105072

[55] Liam Paninski „Un test bazat pe coincidențe pentru uniformitate dată de date discrete eșantionate foarte puțin” 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 și Ramon Munoz-Tapia, „Identificarea exactă a unui punct de schimbare cuantică” 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 și Ramon Munoz-Tapia, „Punctul de schimbare cuantică” Physical Review Letters 117 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.150502
arXiv: 1605.01916

[58] Gael Sentís, Esteban Martínez-Vargas și Ramon Muñoz-Tapia, „Strategii online pentru identificarea exactă a unui punct de schimbare cuantică” Physical Review A 98, 052305 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.052305
arXiv: 1802.00280

[59] Graeme Smith, John A. Smolin și Andreas Winter, „The quantum capacity with symmetric side channels” IEEE Transactions on Information Theory 54, 4208–4217 (2008).
https: / / doi.org/ 10.1109 / TIT.2008.928269
arXiv: 0607039

[60] Igal Sason și 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 și Paul Valiant „An Automatic Inequality Prover and Instance Optimal Identity Testing” 2014 Simpozionul anual al 55-lea IEEE privind fundamentele informaticii 51–60 (2014).
https: / / doi.org/ 10.1109 / FOCS.2014.14
https://​/​ieeexplore.ieee.org/​document/​6978989/​

[62] Xin Wang „Urmărirea limitelor fundamentale pentru comunicarea cuantică” 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 „Eșantion de testare eficientă a identității și testare a independenței statelor cuantice” A 12-a Conferință de inovații în informatică teoretică (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

Citat de

[1] Li Gao și Nengkun Yu, „Eșantion de tomografie optimă a lanțurilor cuantice Markov”, arXiv: 2209.02240, (2022).

[2] Marco Fanizza, Michalis Skotiniotis, John Calsamiglia, Ramon Muñoz-Tapia și Gael Sentís, „Algoritmi universali pentru învățarea datelor cuantice”, EPL (Europhysics Letters) 140 2, 28001 (2022).

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2023-09-13 12:15:38). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

On Serviciul citat de Crossref nu s-au găsit date despre citarea lucrărilor (ultima încercare 2023-09-13 12:15:37).

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Timestamp-ul:

Mai mult de la Jurnalul cuantic