Quantum Information & Computation
Volume 25, Issue 2
RESEARCH ARTICLE Open access

Polynomial Complexity of Quantum Sample Tomography

Kun Tang, Jun Lai

Author affiliations
  • Kun Tang1
  • Jun Lai1
  1. School of Mathematical Sciences, Zhejiang University, Hangzhou, Zhejiang, China

pp. 156-174 · 10.2478/qic-2025-0008

Read PDF View on Reference Global
On this page

Abstract

Efficient quantum tomography is crucial for advancing quantum computing technologies. Traditional quantum state tomography requires an exponential number of measurements for complete reconstruction. Therefore, developing methods that reduce measurement complexity to polynomial scale is essential for practical applications. In this paper, we show that quantum sample tomography can be accomplished with polynomial scale measurements while maintaining accuracy with a high probability. We present a novel approach using conditional recurrent neural networks (RNNs) with solid theoretical foundations from Rademacher complexity and random projection theory. The effectiveness of our method is validated through several quantum models.
Open accessCC BY-NC-ND 4.0

Keywords

  • quantum sample tomography
  • Rademacher complexity
  • random projection
  • neural network

Suggested citation

Kun Tang, Jun Lai (2025). Polynomial Complexity of Quantum Sample Tomography. Quantum Information & Computation, 25(2), 156-174. https://doi.org/10.2478/qic-2025-0008

Download BibTeX

References (29)

  1. F. Arute, K. Arya, R. Babbush, et al. (2019). “Quantum supremacy using a programmable superconducting processor”. Nature, 574, 505–510.DOI: 10.1038/s41586-019-1666-5Google Scholar
  2. A.W. Harrow, A. Hassidim, and S. Lloyd (2009). “Quantum algorithm for solving linear systems of equations.” Physical Review Letters, 103, 150502.DOI: 10.1103/PhysRevLett.103.150502Google Scholar
  3. L. Zhou, S.-T. Wang, S. Choi, et al. (2020). “Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices.” Physical Review X, 10, 021067.DOI: 10.1103/PhysRevX.10.021067Google Scholar
  4. A.W.R. Smith, J. Gray, and M.S. Kim (2021). “Efficient quantum state sample tomography with basis-dependent neural networks.” PRX Quantum, 2, 020348.DOI: 10.1103/PRXQuantum.2.020348Google Scholar
  5. J. Shang, Z. Zhang, and H.K. Ng (2017). “Superfast maximum-likelihood reconstruction for quantum tomography.” Physical Review A, 95, 062336DOI: 10.1103/PhysRevA.95.062336Google Scholar
  6. E. Bolduc, G.C. Knee, E.M. Gauger, et al. (2017). “Projected gradient descent algorithms for quantum state tomography.” npj Quantum Information, 3, 44.DOI: 10.1038/s41534-017-0043-1Google Scholar
  7. D. Gross, Y.-K. Liu, S.T. Flammia, et al. (2010). “Quantum state tomography via compressed sensing.” Physical Review Letters, 105, 150401.DOI: 10.1103/PhysRevLett.105.150401Google Scholar
  8. Z. Qin, C. Jameson, Z. Gong, et al. (2024). “Quantum state tomography for matrix product density operators.” IEEE Transactions on Information Theory, 70, 5030.DOI: 10.1109/TIT.2024.3360951Google Scholar
  9. J. van Apeldoorn, A. Cornelissen, A. Gilyén, et al. (2023). “Quantum tomography using state-preparation unitaries”, in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1265–1318.DOI: 10.1137/1.9781611977554.ch47Google Scholar
  10. G. Torlai, G. Mazzola, J. Carrasquilla, et al. (2018). “Neural-network quantum state tomography”. Nature Physics, 14, 447–450.DOI: 10.1038/s41567-018-0048-5Google Scholar
  11. S. Ahmed, C. Sánchez Muñoz, F. Nori, and A.F. Kockum (2021). “Classification and reconstruction of optical quantum states with deep neural networks”. Physical Review Research, 3, 033278.DOI: 10.1103/PhysRevResearch.3.033278Google Scholar
  12. V. Wei, W.A. Coish, P. Ronagh, et al. (2024). “Neural-shadow quantum state tomography”. Physical Review Research, 6, 023250.DOI: 10.1103/PhysRevResearch.6.023250Google Scholar
  13. Y. Quek, S. Fort, and H.K. Ng (2021). “Adaptive quantum state tomography with neural networks”. npj Quantum Information., 7, 1–7.DOI: 10.1038/s41534-021-00436-9Google Scholar
  14. N. Innan, O. I. Siddiqui, S. Arora, et al. (2024). “Quantum state tomography using quantum machine learning”. Quantum Machine Intelligence, 6, 28.DOI: 10.1007/s42484-024-00162-3Google Scholar
  15. S. Aaronson (2007). “The learnability of quantum states”. Proceedings of the Royal Society A, 463, 3089–3114.DOI: 10.1098/rspa.2007.0113Google Scholar
  16. H.-Y. Hu, S. Choi, and Y.-Z. You (2023). “Classical shadow tomography with locally scrambled quantum dynamics”. Physical Review Research, 5, 023027.DOI: 10.1103/PhysRevResearch.5.023027Google Scholar
  17. H.-Y. Huang (2022). “Learning quantum states from their classical shadows”. Nature Review Physics, 4, 81.DOI: 10.1038/s42254-021-00411-5Google Scholar
  18. P.L. Bartlett, O. Bousquet, and S. Mendelson (2005). “Local Rademacher complexities”. Annals of Statistics, 33.DOI: 10.1214/009053605000000282Google Scholar
  19. A. Kitaev, A. Shen, and M. Vyalyi (2002). Classical and Quantum Computation. American Mathematical Society.DOI: 10.1090/gsm/047Google Scholar
  20. J. Cotler and F. Wilczek (2020). “Quantum overlapping tomography”. Physical Review Letters, 124, 100401.DOI: 10.1103/PhysRevLett.124.100401Google Scholar
  21. S. Aaronson (2020). “Shadow tomography of quantum states”. SIAM Journal on Computing, 49, STOC18-368- STOC18-394.DOI: 10.1137/18M120275XGoogle Scholar
  22. A. Maurer (2016). “A vector-contraction inequality for rademacher complexities”, in R. Ortner, H.U. Simon, and S. Zilles (eds), Algorithmic Learning Theory. Cham: Springer International Publishing, 3–17.DOI: 10.1007/978-3-319-46379-7_1Google Scholar
  23. C. Cortes, M. Kloft, and M. Mohri (2013). “Learning kernels using local Rademacher complexity”. Advances in Neural Information Processing Systems (NIPS), 26, 2760–2768.Google Scholar
  24. S. Dasgupta and A. Gupta (2003). “An elementary proof of a theorem of Johnson and Lindenstrauss”. Random Structures & Algorithms, 22, 60.DOI: 10.1002/rsa.10073Google Scholar
  25. P. Cha, P. Ginsparg, F. Wu, J. Carrasquilla, et al. (2022). “Attention-based quantum tomography”. Machine Learning: Science and Technology, 3, 01LT01DOI: 10.1088/2632-2153/ac362bGoogle Scholar
  26. J.R. Johansson, P.D. Nation, and F. Nori (2012). “QuTiP: An open-source python framework for the dynamics of open quantum systems”. Computer Physics Communications, 183, 1760–1772.DOI: 10.1016/j.cpc.2012.02.021Google Scholar
  27. J.R. Johansson, P.D. Nation, and F. Nori (2013). “QuTiP 2: A python framework for the dynamics of open quantum systems”. Computer Physics Communications, 184, 1234–1240.DOI: 10.1016/j.cpc.2012.11.019Google Scholar
  28. B.I. Bantysh, A.Y. Chernyavskiy, and Y.I. Bogdanov (2021). “Quantum tomography benchmarking”. Quantum Information Processing, 20, 339.DOI: 10.1007/s11128-021-03285-9Google Scholar
  29. J. Carrasquilla, G. Torlai, R.G. Melko, et al. (2019). “Reconstructing quantum states with generative models”. Nature Machine Intelligence, 1, 155–161.DOI: 10.1038/s42256-019-0028-1Google Scholar