Document Open Access Logo

Sample Efficient Identity Testing and Independence Testing of Quantum States

Author Nengkun Yu

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.11.pdf
  • Filesize: 0.61 MB
  • 20 pages

Document Identifiers

Author Details

Nengkun Yu
  • Centre for Quantum Software and Information, Faculty of Engineering and Information Technology, University of Technology, Sydney, Australia

Funding

  • Yu, Nengkun: N. Y. is supported by ARC Discovery Early Career Researcher Award DE180100156 and ARC Discovery Program DP210102449.

Acknowledgements

We thank Youming Qiao for his helpful comments on the previous version of this manuscript. We thank Tongyang Li for pointing out relevant reference [Andr{á}s Gilyén and Tongyang Li, 2020]. We thank Ryan O'Donnell and John Wright for telling us the Sanov’s theorem and its relation to [J. Haah et al., 2016]. We are grateful for the reviewer to point out that using random independent measurement can provide a tight bound for quantum state certification.

Cite AsGet BibTex

Nengkun Yu. Sample Efficient Identity Testing and Independence Testing of Quantum States. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.11

Abstract

In this paper, we study the quantum identity testing problem, i.e., testing whether two given quantum states are identical, and quantum independence testing problem, i.e., testing whether a given multipartite quantum state is in tensor product form. For the quantum identity testing problem of 𝒟(ℂ^d) system, we provide a deterministic measurement scheme that uses 𝒪(d²/ε²) copies via independent measurements with d being the dimension of the state and ε being the additive error. For the independence testing problem 𝒟(ℂ^d₁⊗ℂ^{d₂}⊗⋯⊗ℂ^{d_m}) system, we show that the sample complexity is Θ̃((Π_{i = 1}^m d_i)/ε²) via collective measurements, and 𝒪((Π_{i = 1}^m d_i²)/ε²) via independent measurements. If randomized choice of independent measurements are allowed, the sample complexity is Θ(d^{3/2}/ε²) for the quantum identity testing problem, and Θ̃((Π_{i = 1}^m d_i^{3/2})/ε²) for the quantum independence testing problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Mathematics of computing → Probability and statistics
Keywords
  • Quantum property testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. S. Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 325-338, 2018. Google Scholar
  2. S. Aaronson, X. Chen, E. Hazan, S. Kale, and A. Nayak. Online learning of quantum states. In Advances in Neural Information Processing Systems 31, pages 8962-8972, 2018. Google Scholar
  3. S. Aaronson and G. Rothblum. Gentle measurement of quantum states and differential privacy. In Proceedings of the 51th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, 2019. Google Scholar
  4. Scott Aaronson. The learnability of quantum states. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463(2088):3089–3114, September 2007. Google Scholar
  5. J. Acharya, H. Das, A. Jafarpour, A. Orlitsky, and S. Pan. Competitive closeness testing. In Proceedings of the 24th Annual Conference on Learning Theory, volume 19, pages 47-68, 2011. Google Scholar
  6. J. Acharya, C. Daskalakis, and G. Kamath. Optimal testing for properties of distributions. In Advances in Neural Information Processing Systems 28, pages 3591-3599, 2015. Google Scholar
  7. J. Acharya, I. Diakonikolas, J. Li, and L. Schmidt. Sample-optimal density estimation in nearly-linear time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 1278-1289, 2017. Google Scholar
  8. J. Acharya, I. Issa, N. Shende, and A. B. Wagner. Measuring quantum entropy. 1711.00814, 2017. Google Scholar
  9. Anurag Anshu, Dave Touchette, Penghui Yao, and Nengkun Yu. Exponential separation of quantum communication and classical information. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 277-288, New York, NY, USA, 2017. ACM. URL: https://doi.org/10.1145/3055399.3055401.
  10. Leandro Aolita, Christian Gogolin, Martin Kliesch, and Jens Eisert. Reliable quantum certification of photonic state preparations. Nature Communications, 6, 2015. Google Scholar
  11. Bandyopadhyay, Boykin, Roychowdhury, and Vatan. A new proof for the existence of mutually unbiased bases. Algorithmica, 34(4):512-528, 2002. Google Scholar
  12. T. Batu, S. Dasgupta, R. Kumar, and R. Rubinfeld. The complexity of approximating entropy. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC '02, pages 678-687, 2002. Google Scholar
  13. T. Batu, L. Fortnow, E. Fischer, R. Kumar, R. Rubinfeld, and P. White. Testing random variables for independence and identity. In Proceedings of the 42Nd IEEE Symposium on Foundations of Computer Science, FOCS '01, pages 442-451, 2001. Google Scholar
  14. T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing that distributions are close. In Proceedings 41st Annual Symposium on Foundations of Computer Science, FOCS'00, pages 259-269, 2000. Google Scholar
  15. T. Batu, R. Kumar, and R. Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC '04, pages 381-390, 2004. Google Scholar
  16. S. Bravyi, A. W. Harrow, and A. Hassidim. Quantum algorithms for testing properties of distributions. IEEE Transactions on Information Theory, 57(6):3971-3981, 2011. Google Scholar
  17. C. Bădescu and R. O'Donnell. Lower bounds for testing complete positivity and quantum separability. In 14th Latin American Theoretical Informatics Symposium, 2020. Google Scholar
  18. C. Bădescu, R. O'Donnell, and J. Wright. Quantum state certification. In Proceedings of the Forty-Nineth Annual ACM on Symposium on Theory of Computing, STOC '19, 2019. Google Scholar
  19. Sébastien Bubeck, Sitan Chen, and Jerry Li. Entanglement is necessary for optimal quantum property testing. In FOCS 2020, April 2020. Google Scholar
  20. C. L. Canonne. A survey on distribution testing: Your data is big. but is it blue? Electronic Colloquium on Computational Complexity (ECCC), 22:63, 2015. Google Scholar
  21. C. L. Canonne, I. Diakonikolas, T. Gouleakis, and R. Rubinfeld. Testing shape restrictions of discrete distributions. Theory of Computing Systems, 62(1):4-62, 2018. Google Scholar
  22. C. L. Canonne, I. Diakonikolas, D. M. Kane, and A. Stewart. Testing conditional independence of discrete distributions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 735-748, 2018. Google Scholar
  23. S. Chan, I. Diakonikolas, G. Valiant, and P. Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pages 1193-1203, 2014. Google Scholar
  24. Y. Cheng, I. Diakonikolas, and R. Ge. High-dimensional robust mean estimation in nearly-linear time. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019. Google Scholar
  25. Marcus P. da Silva, Olivier Landon-Cardinal, and David Poulin. Practical characterization of quantum devices without tomography. Phys. Rev. Lett., 107:210404, 2011. Google Scholar
  26. C. Daskalakis, I. Diakonikolas, R. A. Servedio, G. Valiant, and P. Valiant. Testing k-modal distributions: Optimal algorithms via reductions. In Proceedings of the Twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '13, pages 1833-1852, 2013. Google Scholar
  27. C. Daskalakis, N. Dikkala, and G. Kamath. Testing ising models. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 1989-2007, 2018. Google Scholar
  28. C. Daskalakis and Q. Pan. Square hellinger subadditivity for bayesian networks and its applications to identity testing. In Proceedings of the 2017 Conference on Learning Theory, volume 65, pages 697-703, 2017. Google Scholar
  29. L. Devroye and G. Lugosi. Combinatorial Methods in Density Estimation. Springer, 2001. Google Scholar
  30. I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Robust estimators in high dimensions without the computational intractability. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 655-664, 2016. Google Scholar
  31. I. Diakonikolas and D. Kane. A new approach for testing properties of discrete distributions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 685-694, 2016. Google Scholar
  32. I. Diakonikolas, D. M. Kane, and V. Nikishkin. Optimal algorithms and lower bounds for testing closeness of structured distributions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1183-1202, 2015. Google Scholar
  33. I. Diakonikolas, D. M. Kane, and V. Nikishkin. Near-Optimal Closeness Testing of Discrete Histogram Distributions. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80, pages 8:1-8:15, 2017. Google Scholar
  34. I. Diakonikolas, D. M. Kane, and A. Stewart. Sharp bounds for generalized uniformity testing. In Advances in Neural Information Processing Systems 31, pages 6201-6210, 2018. Google Scholar
  35. T. Durt, B. Englert, I. Bengtsson, and Zyczkowski K. On mutually unbiased bases. International Journal of Quantum Information, pages 535-640, 2010. Google Scholar
  36. S. T. Flammia, D. Gross, Y. Liu, and J. Eisert. Quantum tomography via compressed sensing: Error bounds, sample complexity, and efficient estimators. New J. Phys., 14:095022, 2012. Google Scholar
  37. Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few pauli measurements. Phys. Rev. Lett., 106:230501, 2011. Google Scholar
  38. András Gilyén and Tongyang Li. Distributional Property Testing in a Quantum World. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151, pages 25:1-25:19, 2020. Google Scholar
  39. O. Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  40. O. Goldreich and D. Ron. On Testing Expansion in Bounded-Degree Graphs, volume 6650 of Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, Lecture Notes in Computer Science. Springer, 2000. Google Scholar
  41. Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, July 1998. Google Scholar
  42. D. Gross, Y. Liu, S. T. Flammia, S. Becker, and J. Eisert. Quantum state tomography via compressed sensing. Phys. Rev. Lett., 105(150401), 2010. Google Scholar
  43. D. Gross, S. Nezami, and M. Walter. Schur-weyl duality for the clifford group with applications: Property testing, a robust hudson theorem, and de finetti representations. arXiv, 2017. URL: http://arxiv.org/abs/1712.08628.
  44. J. Haah, A. W. Harrow, Z. Ji, X. Wu, , and N. Yu. Sample-optimal tomography of quantum states. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '16, pages 913-925, 2016. Google Scholar
  45. Aram W. Harrow and Ashley Montanaro. Testing product states, quantum merlin-arthur games and tensor optimization. J. ACM, 60(1):3:1-3:43, 2013. Google Scholar
  46. P. Indyk, R. Levi, and R. Rubinfeld. Approximating and testing k-histogram distributions in sub-linear time. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS '12, pages 15-22, 2012. Google Scholar
  47. R. Jain, J. Radhakrishnan, and Sen P. A lower bound for the bounded round quantum communication complexity of set disjointness. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 220-229, October 2003. URL: https://doi.org/10.1109/SFCS.2003.1238196.
  48. J. Jiao, K. Venkat, Y. Han, and T. Weissman. Minimax estimation of functionals of discrete distributions. IEEE Transactions on Information Theory, 61(5):2835-2885, 2015. Google Scholar
  49. R. Kueng, H. Rauhut, and U. Terstiege. Low rank matrix recovery from rank one measurements. Applied and Computational Harmonic Analysis, 42:88-116, 2017. Google Scholar
  50. E. L. Lehmann and Joseph P. Romano. Testing statistical hypotheses. Springer Texts in Statistics. Springer, New York, 2005. Google Scholar
  51. R. Levi, D. Ron, and R. Rubinfeld. Testing properties of collections of distributions. In proceedings of the Second Symposium on Innovations in Computer Science, ICS '11, pages 179-194, 2011. Google Scholar
  52. Florian Mintert, Marek Kuś, and Andreas Buchleitner. Concurrence of mixed multipartite quantum states. Phys. Rev. Lett., 95:260502, 2005. Google Scholar
  53. A. Montanaro and R. de Wolf. A survey of quantum property testing. Theory of Computing Graduate Surveys, 7, 2016. Google Scholar
  54. M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 10th edition, 2011. Google Scholar
  55. R. O'Donnell and J. Wright. Quantum spectrum testing. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '15, pages 529-538, 2015. Google Scholar
  56. R. O'Donnell and J. Wright. Efficient quantum tomography. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '16, pages 899-912, 2016. Google Scholar
  57. R. O'Donnell and J. Wright. Efficient quantum tomography ii. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '17, pages 962-974, 2017. Google Scholar
  58. L. Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Trans. Inf. Theor., 54(10):4750-4755, 2008. Google Scholar
  59. R. Rubinfeld. Taming big probability distributions. XRDS, 19(1):24-28, 2012. Google Scholar
  60. R. Rubinfeld and M. Sudan. Self-testing polynomial functions efficiently and over rational domains. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '92, pages 23-32, 1992. Google Scholar
  61. R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996. Google Scholar
  62. I. N. Sanov. On the probability of large deviations of random variables. Mat. Sbornik, 42:11-44, 1957. Google Scholar
  63. G. Valiant and P. Valiant. Estimating the unseen: An n/log(n)-sample estimator for entropy and support size, shown optimal via new clts. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 685-694, 2011. Google Scholar
  64. G. Valiant and P. Valiant. The power of linear estimators. In Proceedings of the 2011 IEEE 52Nd Annual Symposium on Foundations of Computer Science, FOCS '11, pages 403-412, 2011. Google Scholar
  65. G. Valiant and P. Valiant. An automatic inequality prover and instance optimal identity testing. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS '14, pages 51-60, 2014. Google Scholar
  66. G. Valiant and P. Valiant. Instance optimal learning of discrete distributions. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 142-155, 2016. Google Scholar
  67. G. Valiant and P. Valiant. Estimating the unseen: Improved estimators for entropy and other properties. Journal of the ACM, 64(6), 2017. Google Scholar
  68. P. Valiant. Testing symmetric properties of distributions. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, pages 383-392, 2008. Google Scholar
  69. V. Voroninski. Quantum tomography from few full-rank observables, 2013. URL: http://arxiv.org/abs/1309.7669.
  70. Y. Wu and P. Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory, 62(6):3702-3720, 2016. Google Scholar
  71. Nengkun Yu. Quantum closeness testing: A streaming algorithm and applications, 2020. URL: http://arxiv.org/abs/1904.03218.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact