Testa identiteten för samlingar av kvanttillstånd: provkomplexitetsanalys

Testa identiteten för samlingar av kvanttillstånd: provkomplexitetsanalys

Tidsstämpel: 11 september, 2023 8:05

Marco Fanizza1, Raffaele Salvia2och Vittorio Giovannetti3

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

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Vi studerar problemet med att testa identiteten för en samling okända kvanttillstånd som ges provtillgång till denna samling, där varje tillstånd uppträder med en viss känd sannolikhet. Vi visar att för en samling $d$-dimensionella kvanttillstånd av kardinalitet $N$, är provkomplexiteten $O(sqrt{N}d/epsilon^2)$, med en matchande nedre gräns, upp till en multiplikativ konstant . Testet erhålls genom att uppskatta medelkvadratavståndet Hilbert-Schmidt mellan tillstånden, tack vare en lämplig generalisering av estimatorn för Hilbert-Schmidt-avståndet mellan två okända tillstånd av Bădescu, O'Donnell och Wright [13].

Testa identiteten för samlingar av kvanttillstånd: provkomplexitetsanalys PlatoBlockchain Data Intelligence. Vertikal sökning. Ai.

Utvald bild: Två inställningar som vår modell gäller. I a) producerar oberoende källor ett slumpmässigt antal, Poisson-distribuerat, av kopior av en stat i en tid $T$. I b) förbereder en mätprocedur märkta tillstånd, varvid varje etikett uppträder med viss sannolikhet.

► BibTeX-data

► Referenser

[1] Gerardo Adesso, Thomas R. Bromley och Marco Cianciaruso, "Mätningar och tillämpningar av kvantkorrelationer" 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 och 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 Achary och Constantinos Daskalakis "Testa Poissons binomialdistributioner" Proceedings of the Twenty-Sexth Annual ACM-SIAM Symposium on Discrete Algorithms 1829–1840 (2015).
https: / / doi.org/ 10.1137 / 1.9781611973730.122
arXiv: 1507.05952

[4] Daiki Akimoto och Masahito Hayashi "Diskriminering av förändringspunkten i en kvantmiljö" Physical Review A 83, 052328 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.052328
arXiv: 1102.2555

[5] Robert Alicki, Slawomir Rudnicki och Slawomir Sadowski, "Symmetriegenskaper hos produkttillstånd för systemet med N n-nivåatomer" 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 och 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 och Patrick White, "Testing random variables for independence and identity" 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 och Aram W. Harrow, "Effektiva kvantkretsar för Schur och Clebsch-Gordan Transforms" Physical Review Letters 97, 170502 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.170502
arXiv: 0407082

[9] Sebastien Bubeck, Sitan Chen och Jerry Li, "Entanglement 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 och 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 och R. Muñoz-Tapia, "Relativa tillstånd, kvantaxlar och kvantreferenser" Physical Review A 73, 022341 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022341
arXiv: 0508187

[12] Stéphane Boucheron, Gábor Lugosi och 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 och 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 och Robert W. Spekkens, "Optimala mätningar för relativ kvantinformation" Physical Review A 70, 032321 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.032321
arXiv: 0310009

[15] Harry Buhrman, Richard Cleve, John Watrous och 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 “En undersökning om distributionstestning: Dina data är stora. Men är den blå?" Theory of Computing 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 och Gregory Valiant, "Optimala algoritmer för att testa närhet av diskreta distributioner" Proceedings of the Twenty-Femth annual ACM-SIAM Symposium on Discrete Algorithms 1193–1203 (2014).
https: / / doi.org/ 10.1137 / 1.9781611973402.88
arXiv: 1308.3946

[18] Matthias Christandl "The Structure of Bipartite Quantum States - Insights from Group Theory and Cryptography" (2006).
arXiv: 0604183

[19] Sitan Chen, Jerry Li och 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 och Joy A. Thomas "Elements of Information Theory" (2005).
https: / / doi.org/ 10.1002 / 047174882X

[21] Ilias Diakonikolas och Daniel M. Kane "A New Approach for Testing Properties of Discrete Distributions" 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 och 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 och 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 och 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 och Vittorio Giovannetti, "Quantum Flags and New Bounds on the Quantum Capacity of the Depolarizing Channel" Physical Review Letters 125, 020503 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.020503
arXiv: 1911.01977

[26] Marco Fanizza, Farzad Kianvash och Vittorio Giovannetti, "Estimating Quantum and Private Capacities of Gaussian Channels 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 "Quantum relative states" The European Physical Journal D 39, 321–327 (2006).
https: / / doi.org/ 10.1140 / epjd / e2006-00097-y
arXiv: 0507118

[28] Oded Goldreich "Introduction to Property Testing" Cambridge University Press (2017).
https: / / doi.org/ 10.1017 / 9781108135252

[29] Oded Goldreich och 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 och 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 "Tillämpningar av koherent klassisk kommunikation och Schur-transformeringen till kvantinformationsteori" (2005).
arXiv: 0512255

[32] Masahito Hayashi, Bao-Sen Shi, Akihisa Tomita, Keiji Matsumoto, Yoshiyuki Tsuda och Yun-Kun Jiang, "Hypotestestning för ett intrasslat tillstånd producerat av spontan parametrisk nedkonvertering" Phys. Rev. A 74, 062321 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.062321

[33] Masahito Hayashi "A Group Theoretic Approach to Quantum Information" 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 "Quantum Information Theory" Springer Berlin Heidelberg (2017).
https:/​/​doi.org/​10.1007/​978-3-662-49725-8

[36] Masahito Hayashi och Keiji Matsumoto "Quantum universal variabel-längd källkodning" Physical Review A 66, 022311 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.66.022311
arXiv: 0202001

[37] Masahito Hayashi och Marco Tomamichel "Korrelationsdetektion och en operativ tolkning av Rényi ömsesidig information" Journal of Mathematical Physics 57, 102201 (2016).
https: / / doi.org/ 10.1063 / 1.4964755
arXiv: 1408.6894

[38] Masahito Hayashi, Akihisa Tomita och Keiji Matsumoto, "Statistisk analys av testning av ett intrasslat tillstånd baserat på Poissons distributionsramverk" New Journal of Physics 10, 043029 (2008).
https:/​/​doi.org/​10.1088/​1367-2630/​10/​4/​043029

[39] L. Hendersonand V. Vedral "Klassiska, kvant- och totala korrelationer" 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 "Quantum state estimation and large deviations" Reviews in Mathematical Physics 18, 19–60 (2006).
https: / ⠀ </ ⠀ <doi.org/†<10.1142 / ⠀ <S0129055X06002565

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

[42] Martin Klieschand Ingo Roth "Theory of Quantum System Certification" PRX Quantum 2, 010201 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.010201
arXiv: 2010.05925

[43] Hari Krovi "En effektiv högdimensionell kvantomvandling av Schur" 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 "Estimating the spectrum of a density operator" Physical Review A 64, 052311 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.052311
arXiv: 0102027

[45] Lucien Le Cam "En approximationssats för Poissons binomialfördelning." Pacific Journal of Mathematics 10, 1181–1197 (1960).

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

[47] Erich L Lehmann och Joseph P Romano "Testa statistiska hypoteser" Springer Science & Business Media (2006).

[48] Reut Levi, Dana Ron och 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 och Dagmar Bruß, "Quantum estimering of relativ information" International Journal of Quantum Information 4, 131–149 (2006).
https: / / doi.org/ 10.1142 / S0219749906001657
arXiv: 0506223

[50] Ashley Montanaro och 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 "Quantum Spectrum Testing" Proceedings av det fyrtiosjunde årliga ACM-symposiet om 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 "Efficient quantum tomography" Proceedings av det fyrtioåttonde årliga ACM-symposiet om 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 "Efficient quantum tomography 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 "Quantum Discord: A Measure of the Quantumness of Correlations" Physical Review Letters 88, 017901 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.88.017901
arXiv: 0105072

[55] Liam Paninski "Ett tillfällighetsbaserat test för enhetlighet givet mycket sparsamt samplade diskreta data" 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 och Ramon Munoz-Tapia, "Exact Identification of a Quantum Change Point" 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 och 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 och Ramon Muñoz-Tapia, "Onlinestrategier för att exakt identifiera en kvantförändringspunkt" Physical Review A 98, 052305 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.052305
arXiv: 1802.00280

[59] Graeme Smith, John A. Smolin och Andreas Winter, "Kvantumkapaciteten med symmetriska sidokanaler" IEEE Transactions on Information Theory 54, 4208–4217 (2008).
https: / / doi.org/ 10.1109 / TIT.2008.928269
arXiv: 0607039

[60] Igal Sason och 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 och 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 "Pursuing the fundamental limits for quantum communication" 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" 12th 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

Citerad av

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

[2] Marco Fanizza, Michalis Skotiniotis, John Calsamiglia, Ramon Muñoz-Tapia och Gael Sentís, "Universella algoritmer för kvantdatainlärning", EPL (Europhysics Letters) 140 2, 28001 (2022).

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2023-09-13 12:15:38). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2023-09-13 12:15:37).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal