Test af identitet af samlinger af kvantetilstande: Prøvekompleksitetsanalyse

Genudgivet af Platon

Abonnenter: 0

Marco Fanizza¹, Raffaele Salvia²og Vittorio Giovannetti³

¹Física Teòrica: Informació i Fenòmens Quàntics, Department de Física, Universitat Autònoma de Barcelona, 08193 Bellaterra, Spanien.
²Scuola Normale Superiore, I-56127 Pisa, Italien.
³NEST, Scuola Normale Superiore og Istituto Nanoscienze-CNR, I-56127 Pisa, Italien.

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Vi studerer problemet med at teste identiteten af en samling ukendte kvantetilstande givet prøveadgang til denne samling, hvor hver tilstand optræder med en vis sandsynlighed. Vi viser, at for en samling af $d$-dimensionelle kvantetilstande af kardinalitet $N$, er prøvekompleksiteten $O(sqrt{N}d/epsilon^2)$, med en matchende nedre grænse, op til en multiplikativ konstant . Testen opnås ved at estimere den gennemsnitlige kvadrerede Hilbert-Schmidt-afstand mellem staterne, takket være en passende generalisering af estimatoren af Hilbert-Schmidt-afstanden mellem to ukendte tilstande af Bădescu, O'Donnell og Wright [13].

Test af identitet af samlinger af kvantetilstande: prøvekompleksitetsanalyse PlatoBlockchain Data Intelligence. Lodret søgning. Ai.

Udvalgt billede: To indstillinger, som vores model gælder for. I a) producerer uafhængige kilder et tilfældigt antal, Poisson-fordelt, af kopier af en tilstand i en tid $T$. I b) forbereder en måleprocedure mærkede tilstande, hvor hver etiket optræder med en vis sandsynlighed.

► BibTeX-data

@article{Fanizza2023testingidentityof, doi = {10.22331/q-2023-09-11-1105}, url = {https://doi.org/10.22331/q-2023-09-11-1105}, title = {Testing identitet af samlinger af kvantetilstande: prøvekompleksitetsanalyse}, forfatter = {Fanizza, Marco og Salvia, Raffaele og Giovannetti, Vittorio}, tidsskrift = {{Quantum}}, issn = {2521-327X}, udgiver = {{Verein zur F {“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, bind = {7}, sider = {1105}, måned = sep, år = {2023} }

► Referencer

[1] Gerardo Adesso, Thomas R. Bromley og Marco Cianciaruso, "Mål og anvendelser af kvantekorrelationer" 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 og 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 og Constantinos Daskalakis "Testing Poisson Binomial Distributions" Proceedings of the 1829. årlige ACM-SIAM Symposium on Discrete Algorithms 1840-2015 (XNUMX).
https:///doi.org/10.1137/1.9781611973730.122
arXiv: 1507.05952

[4] Daiki Akimoto og Masahito Hayashi "Diskriminering af ændringspunktet i en kvante indstilling" Physical Review A 83, 052328 (2011).
https:///doi.org/10.1103/PhysRevA.83.052328
arXiv: 1102.2555

[5] Robert Alicki, Slawomir Rudnicki og Slawomir Sadowski, "Symmetriegenskaber af produkttilstande for systemet af N n-niveau 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 og 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 og Patrick White, "Testing random variables for uafhængighed og identitet" 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 og 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 og Jerry Li, "Entanglement er nødvendig 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 og 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 og R. Muñoz-Tapia, "Relative tilstande, kvanteakser og kvantereferencer" Fysisk gennemgang A 73, 022341 (2006).
https:///doi.org/10.1103/PhysRevA.73.022341
arXiv: 0508187

[12] Stéphane Boucheron, Gábor Lugosi og 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 og 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 og Robert W. Spekkens, "Optimale målinger for relativ kvanteinformation" Physical Review A 70, 032321 (2004).
https:///doi.org/10.1103/PhysRevA.70.032321
arXiv: 0310009

[15] Harry Buhrman, Richard Cleve, John Watrous og 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øgelse om distributionstestning: Dine data er store. Men er 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 og Gregory Valiant, "Optimale algoritmer til testning af nærhed af diskrete distributioner" Proceedings of the 1193. årlige ACM-SIAM Symposium on Discrete Algorithms 1203-2014 (XNUMX).
https:///doi.org/10.1137/1.9781611973402.88
arXiv: 1308.3946

[18] Matthias Christandl "Strukturen af bipartite kvantestater - Indsigt fra gruppeteori og kryptografi" (2006).
arXiv: 0604183

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

[21] Ilias Diakonikolas og 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 og 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 og 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 og 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 og 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 og Vittorio Giovannetti, "Estimering af kvante- og private kapaciteter af Gaussiske kanaler via nedbrydelige udvidelser" Fysisk. 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 og 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 og 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 "Anvendelser af sammenhængende klassisk kommunikation og Schur-transformationen til kvanteinformationsteori" (2005).
arXiv: 0512255

[32] Masahito Hayashi, Bao-Sen Shi, Akihisa Tomita, Keiji Matsumoto, Yoshiyuki Tsuda og Yun-Kun Jiang, "Hypotesetestning for en sammenfiltret tilstand frembragt af spontan parametrisk nedkonvertering" Fysisk. 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 og Keiji Matsumoto "Quantum universal variabel-længde kildekodning" Physical Review A 66, 022311 (2002).
https:///doi.org/10.1103/PhysRevA.66.022311
arXiv: 0202001

[37] Masahito Hayashi og Marco Tomamichel "Korrelationsdetektion og en operationel fortolkning af Rényi gensidige information" Journal of Mathematical Physics 57, 102201 (2016).
https:///doi.org/10.1063/1.4964755
arXiv: 1408.6894

[38] Masahito Hayashi, Akihisa Tomita og Keiji Matsumoto, "Statistisk analyse af test af en sammenfiltret tilstand baseret på Poisson-fordelingsrammen" New Journal of Physics 10, 043029 (2008).
https://doi.org/10.1088/1367-2630/10/4/043029

[39] L. Hendersonand V. Vedral "Klassiske, kvante- og totale 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 og Vittorio Giovannetti, "Bounding the quantum kapacitet med flagede udvidelser" 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øjdimensionel kvante-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 "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 tilnærmelsessætning for Poissons binomiale fordeling." Pacific Journal of Mathematics 10, 1181-1197 (1960).

[46] Felix Leditzky, Nilanjana Datta og 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 og Joseph P Romano "Testing statistical hypotheses" Springer Science & Business Media (2006).

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

[50] Ashley Montanaro og 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 af det syvogfyrre-syvende årlige ACM-symposium 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 af det otteogfyrre årlige ACM-symposium 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 "En tilfældighedsbaseret test for ensartethed givet meget sparsomt udvalgte diskrete 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 og 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 og 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 og Ramon Muñoz-Tapia, "Online strategier til nøjagtigt at identificere et kvanteændringspunkt" Fysisk gennemgang A 98, 052305 (2018).
https:///doi.org/10.1103/PhysRevA.98.052305
arXiv: 1802.00280

[59] Graeme Smith, John A. Smolin og Andreas Winter, "Kvantekapaciteten med symmetriske sidekanaler" IEEE Transactions on Information Theory 54, 4208-4217 (2008).
https:///doi.org/10.1109/TIT.2008.928269
arXiv: 0607039

[60] Igal Sason og 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 og 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 "Forfølger de grundlæggende grænser for kvantekommunikation" 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 "Næsten stram prøvekompleksitetsanalyse af kvanteidentitetstestning af Pauli-målinger" IEEE Transactions on Information Theory 69, 5060–5068 (2023).
https:///doi.org/10.1109/TIT.2023.3271206
arXiv: 2009.11518

Citeret af

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

[2] Marco Fanizza, Michalis Skotiniotis, John Calsamiglia, Ramon Muñoz-Tapia og Gael Sentís, "Universelle algoritmer til kvantedataindlæring", EPL (Europhysics Letters) 140 2, 28001 (2022).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2023-09-13 12:15:38). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2023-09-13 12:15:37).

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

SEO Powered Content & PR Distribution. Bliv forstærket i dag.
PlatoData.Network Vertical Generative Ai. Styrk dig selv. Adgang her.
PlatoAiStream. Web3 intelligens. Viden forstærket. Adgang her.
PlatoESG. Automotive/elbiler, Kulstof, CleanTech, Energi, Miljø, Solenergi, Affaldshåndtering. Adgang her.
PlatoHealth. Bioteknologiske og kliniske forsøgs intelligens. Adgang her.
ChartPrime. Løft dit handelsspil med ChartPrime. Adgang her.
BlockOffsets. Modernisering af miljømæssig offset-ejerskab. Adgang her.
Kilde: https://quantum-journal.org/papers/q-2023-09-11-1105/

Tidsstempel: September 11, 2023

Tidsstempel: September 7, 2023

Test af identitet af samlinger af kvantetilstande: prøvekompleksitetsanalyse

Genudgivet af Platon

Abstrakt

► BibTeX-data

► Referencer

Citeret af

Mere fra Quantum Journal

Opnåelse af kvantefeltteoriens grænse i langt fra ligevægt kvantelinkmodeller

Opdeling af qubits i hypergraf-produktkoder for at implementere logiske porte

Samtidig estimering af flere egenværdier med kort dybde kvantekredsløb på tidlige fejltolerante kvantecomputere

Inkompatibilitet af kvanteinstrumenter

Adaptiv variationssimulering for åbne kvantesystemer

Forbedrede kvantealgoritmer til lineære og ikke-lineære differentialligninger

Om os

Vertikal søgning & Ai

perron

Stay Connected

Konto