Testing identity of collections of quantum states: sample complexity analysis

Marco Fanizza1, Raffaele Salvia2, and Vittorio Giovannetti3

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

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We study the problem of testing identity of a collection of unknown quantum states given sample access to this collection, each state appearing with some known probability. We show that for a collection of $d$-dimensional quantum states of cardinality $N$, the sample complexity is $O(\sqrt{N}d/\epsilon^2)$, with a matching lower bound, up to a multiplicative constant. The test is obtained by estimating the mean squared Hilbert-Schmidt distance between the states, thanks to a suitable generalization of the estimator of the Hilbert-Schmidt distance between two unknown states by Bădescu, O'Donnell, and Wright [13].

► BibTeX data

► References

[1] Gerardo Adesso, Thomas R. Bromley, and Marco Cianciaruso, ``Measures and applications of quantum correlations'' 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, and 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 Acharyaand 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 Akimotoand Masahito Hayashi ``Discrimination of the change point in a quantum setting'' Physical Review A 83, 052328 (2011).
https:/​/​doi.org/​10.1103/​PhysRevA.83.052328
arXiv:1102.2555

[5] Robert Alicki, Slawomir Rudnicki, and Slawomir Sadowski, ``Symmetry properties of product states for the system of N n-level atoms'' 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, and 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, and 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, and 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, and 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, and 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, and R. Muñoz-Tapia, ``Relative states, quantum axes, and quantum references'' Physical Review A 73, 022341 (2006).
https:/​/​doi.org/​10.1103/​PhysRevA.73.022341
arXiv:0508187

[12] Stéphane Boucheron, Gábor Lugosi, and 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, and 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, and Robert W. Spekkens, ``Optimal measurements for relative quantum information'' Physical Review A 70, 032321 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.70.032321
arXiv:0310009

[15] Harry Buhrman, Richard Cleve, John Watrous, and 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 ``A Survey on Distribution Testing: Your Data is Big. But is it Blue?'' 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, and Gregory Valiant, ``Optimal Algorithms for Testing Closeness of Discrete Distributions'' 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 ``The Structure of Bipartite Quantum States - Insights from Group Theory and Cryptography'' (2006).
arXiv:0604183

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

[21] Ilias Diakonikolasand 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, and 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, and 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, and 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, and 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, and 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 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, and 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 ``Applications of coherent classical communication and the Schur transform to quantum information theory'' (2005).
arXiv:0512255

[32] Masahito Hayashi, Bao-Sen Shi, Akihisa Tomita, Keiji Matsumoto, Yoshiyuki Tsuda, and Yun-Kun Jiang, ``Hypothesis testing for an entangled state produced by spontaneous parametric down-conversion'' 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 Hayashiand 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 Hayashiand Marco Tomamichel ``Correlation detection and an operational interpretation of the Rényi mutual information'' Journal of Mathematical Physics 57, 102201 (2016).
https:/​/​doi.org/​10.1063/​1.4964755
arXiv:1408.6894

[38] Masahito Hayashi, Akihisa Tomita, and Keiji Matsumoto, ``Statistical analysis of testing of an entangled state based on the Poisson distribution framework'' New Journal of Physics 10, 043029 (2008).
https:/​/​doi.org/​10.1088/​1367-2630/​10/​4/​043029

[39] L. Hendersonand V. Vedral ``Classical, quantum and total correlations'' 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, and 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 ``Theory of Quantum System Certification'' PRX Quantum 2, 010201 (2021).
https:/​/​doi.org/​10.1103/​PRXQuantum.2.010201
arXiv:2010.05925

[43] Hari Krovi ``An efficient high dimensional quantum Schur transform'' 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 R. F. 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 ``An approximation theorem for the Poisson binomial distribution.'' Pacific Journal of Mathematics 10, 1181–1197 (1960).

[46] Felix Leditzky, Nilanjana Datta, and 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 ``Testing statistical hypotheses'' Springer Science & Business Media (2006).

[48] Reut Levi, Dana Ron, and 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, and 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 Montanaroand 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 of the forty-seventh annual ACM symposium on Theory of Computing 14-17-June, 529–538 (2015).
https:/​/​doi.org/​10.1145/​2746539.2746582
arXiv:1501.05028

[52] Ryan O'Donnelland John Wright ``Efficient quantum tomography'' Proceedings of the forty-eighth annual ACM symposium on Theory of Computing 19-21-June, 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 ``A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete 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, and 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, and 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, and Ramon Muñoz-Tapia, ``Online strategies for exactly identifying a quantum change point'' Physical Review A 98, 052305 (2018).
https:/​/​doi.org/​10.1103/​PhysRevA.98.052305
arXiv:1802.00280

[59] Graeme Smith, John A. Smolin, and 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 Sasonand 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 Valiantand 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

Cited by

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

[2] Marco Fanizza, Michalis Skotiniotis, John Calsamiglia, Ramon Muñoz-Tapia, and Gael Sentís, "Universal algorithms for quantum data learning", EPL (Europhysics Letters) 140 2, 28001 (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2024-03-02 16:47:57). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2024-03-02 16:47:55).