Testen der Identität von Quantenzustandssammlungen: Analyse der Probenkomplexität

Testen der Identität von Quantenzustandssammlungen: Analyse der Probenkomplexität

Zeitstempel: 11. September 2023, 8:05 Uhr

Marco Fanizza1, Raffaele Salvia2 und Vittorio Giovannetti3

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

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Wir untersuchen das Problem des Identitätstests einer Sammlung unbekannter Quantenzustände bei Probenzugriff auf diese Sammlung, wobei jeder Zustand mit einer bekannten Wahrscheinlichkeit auftritt. Wir zeigen, dass für eine Sammlung von $d$-dimensionalen Quantenzuständen der Kardinalität $N$ die Stichprobenkomplexität $O(sqrt{N}d/epsilon^2)$ beträgt, mit einer passenden Untergrenze bis zu einer multiplikativen Konstante . Der Test wird durch Schätzung des mittleren quadratischen Hilbert-Schmidt-Abstands zwischen den Zuständen dank einer geeigneten Verallgemeinerung des Schätzers des Hilbert-Schmidt-Abstands zwischen zwei unbekannten Zuständen von Bădescu, O'Donnell und Wright erhalten [13].

Testen der Identität von Quantenzustandssammlungen: Stichprobenkomplexitätsanalyse PlatoBlockchain Data Intelligence. Vertikale Suche. Ai.

Ausgewähltes Bild: Zwei Einstellungen, auf die unser Modell anwendbar ist. In a) erzeugen unabhängige Quellen eine Poisson-verteilte Zufallszahl von Kopien eines Zustands in einer Zeit $T$. In b) bereitet ein Messverfahren markierte Zustände vor, wobei jede Markierung mit einer gewissen Wahrscheinlichkeit auftritt.

► BibTeX-Daten

► Referenzen

[1] Gerardo Adesso, Thomas R. Bromley und Marco Cianciaruso, „Maßnahmen und Anwendungen von Quantenkorrelationen“, 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 und 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 und Constantinos Daskalakis „Testing Poisson Binomial Distributions“ Vorträge des sechsundzwanzigsten jährlichen ACM-SIAM-Symposiums zu diskreten Algorithmen 1829–1840 (2015).
https: / / doi.org/ 10.1137 / 1.9781611973730.122
arXiv: 1507.05952

[4] Daiki Akimoto und Masahito Hayashi „Unterscheidung des Änderungspunkts in einer Quantenumgebung“ Physical Review A 83, 052328 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.052328
arXiv: 1102.2555

[5] Robert Alicki, Slawomir Rudnicki und Slawomir Sadowski, „Symmetrieeigenschaften von Produktzuständen für das System von N n-Niveau-Atomen“, 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 und 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 und Patrick White, „Testen von Zufallsvariablen auf Unabhängigkeit und Identität“, 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 und 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 und Jerry Li, „Entanglement is Necessary for Optimal Quantum Property Testing“ 2020 IEEE 61. 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 und Andreas Winter, „The Quantum Reverse Shannon Theorem and Resource Tradeoffs for Simulated 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 und R. Muñoz-Tapia, „Relative States, Quantenachsen und Quantenreferenzen“, Physical Review A 73, 022341 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022341
arXiv: 0508187

[12] Stéphane Boucheron, Gábor Lugosi und 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 und 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 und Robert W. Spekkens, „Optimale Messungen für relative Quanteninformation“, Physical Review A 70, 032321 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.032321
arXiv: 0310009

[15] Harry Buhrman, Richard Cleve, John Watrous und 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 „Eine Umfrage zu Verteilungstests: Ihre Daten sind groß.“ Aber ist es Blau?“ 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 und Gregory Valiant, „Optimale Algorithmen zum Testen der Nähe diskreter Verteilungen“, Tagungsband des fünfundzwanzigsten jährlichen ACM-SIAM-Symposiums zu diskreten Algorithmen 1193–1203 (2014).
https: / / doi.org/ 10.1137 / 1.9781611973402.88
arXiv: 1308.3946

[18] Matthias Christandl „Die Struktur bipartiter Quantenzustände – Erkenntnisse aus Gruppentheorie und Kryptographie“ (2006).
arXiv: 0604183

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

[21] Ilias Diakonikolas und 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 und Vladimir Nikishkin, „Testing Identity of Structured Distributions“, Tagungsband des 2015. jährlichen ACM-SIAM-Symposiums zu diskreten Algorithmen 1841 – Januar 1854–2015 (XNUMX).
https: / / doi.org/ 10.1137 / 1.9781611973730.123

[23] M. Fanizza, M. Rosati, M. Skotiniotis, J. Calsamiglia und 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 und 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 und 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 und Vittorio Giovannetti, „Schätzung der Quanten- und Privatkapazitäten von Gaußschen Kanälen über abbaubare Erweiterungen“, 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 „Einführung in die Immobilienprüfung“ Cambridge University Press (2017).
https: / / doi.org/ 10.1017 / 9781108135252

[29] Oded Goldreich und 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 und Nengkun Yu, „Probenoptimale Tomographie von Quantenzuständen“ 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 „Anwendungen der kohärenten klassischen Kommunikation und der Schur-Transformation zur Quanteninformationstheorie“ (2005).
arXiv: 0512255

[32] Masahito Hayashi, Bao-Sen Shi, Akihisa Tomita, Keiji Matsumoto, Yoshiyuki Tsuda und Yun-Kun Jiang, „Hypothesetest für einen verschränkten Zustand, der durch spontane parametrische Abwärtskonvertierung erzeugt wird“ Phys. Rev. A 74, 062321 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.062321

[33] Masahito Hayashi „Ein gruppentheoretischer Ansatz zur Quanteninformation“ 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 „Quanteninformationstheorie“ Springer Berlin Heidelberg (2017).
https:/​/​doi.org/​10.1007/​978-3-662-49725-8

[36] Masahito Hayashi und Keiji Matsumoto „Quantum Universal Variable-Length Source Coding“, Physical Review A 66, 022311 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.66.022311
arXiv: 0202001

[37] Masahito Hayashi und Marco Tomamichel „Korrelationserkennung und eine operative Interpretation der gegenseitigen Rényi-Information“ Journal of Mathematical Physics 57, 102201 (2016).
https: / / doi.org/ 10.1063 / 1.4964755
arXiv: 1408.6894

[38] Masahito Hayashi, Akihisa Tomita und Keiji Matsumoto, „Statistische Analyse der Prüfung eines verschränkten Zustands basierend auf dem Poisson-Verteilungsrahmen“ New Journal of Physics 10, 043029 (2008).
https:/​/​doi.org/​10.1088/​1367-2630/​10/​4/​043029

[39] L. Henderson und V. Vedral „Klassische, Quanten- und Gesamtkorrelationen“ 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 „Quantenzustandsschätzung und große Abweichungen“ Reviews in Mathematical Physics 18, 19–60 (2006).
https: / / doi.org/ 10.1142 / S0129055X06002565

[41] Farzad Kianvash, Marco Fanizza und 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 Kliesch und Ingo Roth „Theorie der Quantensystemzertifizierung“ PRX Quantum 2, 010201 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.010201
arXiv: 2010.05925

[43] Hari Krovi „Eine effiziente hochdimensionale Quanten-Schur-Transformation“ 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 „Schätzung des Spektrums eines Dichteoperators“, Physical Review A 64, 052311 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.052311
arXiv: 0102027

[45] Lucien Le Cam „Ein Näherungssatz für die Poisson-Binomialverteilung.“ Pacific Journal of Mathematics 10, 1181–1197 (1960).

[46] Felix Leditzky, Nilanjana Datta und 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. Lehmann und Joseph P. Romano „Testen statistischer Hypothesen“ Springer Science & Business Media (2006).

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

[50] Ashley Montanaro und Ronald de Wolf „Ein Überblick über die Prüfung von Quanteneigenschaften“ 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'Donnel und John Wright „Quantum Spectrum Testing“, Tagungsband des siebenundvierzigsten jährlichen ACM-Symposiums zur Theorie des Rechnens, 14.-17. Juni, 529–538 (2015).
https: / / doi.org/ 10.1145 / 2746539.2746582
arXiv: 1501.05028

[52] Ryan O'Donnel und John Wright „Effiziente Quantentomographie“, Tagungsband des achtundvierzigsten jährlichen ACM-Symposiums zur Theorie des Rechnens, 19.-21. Juni, 899–912 (2016).
https: / / doi.org/ 10.1145 / 2897518.2897544
arXiv: 1508.01907

[53] Ryan O'Donnel und John Wright „Effiziente Quantentomographie II“, Tagungsband des 49. jährlichen ACM SIGACT-Symposiums zur Computertheorie 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 „Ein auf Zufall basierender Test auf Einheitlichkeit bei sehr spärlich abgetasteten diskreten Daten“ 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 und 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 und 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 und Ramon Muñoz-Tapia, „Online-Strategien zur genauen Identifizierung eines Quantenänderungspunkts“, Physical Review A 98, 052305 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.052305
arXiv: 1802.00280

[59] Graeme Smith, John A. Smolin und Andreas Winter, „Die Quantenkapazität mit symmetrischen Seitenkanälen“, IEEE Transactions on Information Theory 54, 4208–4217 (2008).
https: / / doi.org/ 10.1109 / TIT.2008.928269
arXiv: 0607039

[60] Igal Sason und 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 und Paul Valiant „An Automatic Inequality Prover and Instance Optimal Identity Testing“ 2014 IEEE 55. Jahressymposium zu Grundlagen der Informatik 51–60 (2014).
https: / / doi.org/ 10.1109 / FOCS.2014.14
https://​/​ieeexplore.ieee.org/​document/​6978989/​

[62] Xin Wang „Auf der Suche nach den grundlegenden Grenzen der Quantenkommunikation“ 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 „Fast enge Probenkomplexitätsanalyse von Quantenidentitätstests durch Pauli-Messungen“ IEEE Transactions on Information Theory 69, 5060–5068 (2023).
https: / / doi.org/ 10.1109 / TIT.2023.3271206
arXiv: 2009.11518

Zitiert von

[1] Li Gao und Nengkun Yu, „Sample optimale Tomography of Quantum Markov Chains“, arXiv: 2209.02240, (2022).

[2] Marco Fanizza, Michalis Skotiniotis, John Calsamiglia, Ramon Muñoz-Tapia und Gael Sentís, „Universelle Algorithmen für das Lernen von Quantendaten“, EPL (Europhysics Letters) 140 2, 28001 (2022).

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2023, 09:13:12 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2023-09-13 12:15:37).

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.

Zeitstempel:

Mehr von Quantenjournal