Polynomial Complexity of Quantum Sample Tomography

1. F. Arute, K. Arya, R. Babbush, et al. (2019). “Quantum supremacy using a programmable superconducting processor”. Nature, 574, 505–510. Arute F. Arya K. Babbush R. ( 2019 ). “ Quantum supremacy using a programmable superconducting processor ”. Nature , 574 , 505 – 510 . Search in Google Scholar

2. A.W. Harrow, A. Hassidim, and S. Lloyd (2009). “Quantum algorithm for solving linear systems of equations.” Physical Review Letters, 103, 150502. Harrow A.W. Hassidim A. Lloyd S. ( 2009 ). “ Quantum algorithm for solving linear systems of equations. ” Physical Review Letters , 103 , 150502 . Search in Google 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. Zhou L. Wang S.-T. Choi S. ( 2020 ). “ Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices . ” Physical Review X , 10 , 021067 . Search in Google 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. Smith A.W.R. Gray J. Kim M.S. ( 2021 ). “ Efficient quantum state sample tomography with basis-dependent neural networks . ” PRX Quantum , 2 , 020348 . Search in Google Scholar

5. J. Shang, Z. Zhang, and H.K. Ng (2017). “Superfast maximum-likelihood reconstruction for quantum tomography.” Physical Review A, 95, 062336 Shang J. Zhang Z. Ng H.K. ( 2017 ). “ Superfast maximum-likelihood reconstruction for quantum tomography . ” Physical Review A , 95 , 062336 . Search in Google 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. Bolduc E. Knee G.C. Gauger E.M. ( 2017 ). “ Projected gradient descent algorithms for quantum state tomography . ” npj Quantum Information , 3 , 44 . Search in Google Scholar

7. D. Gross, Y.-K. Liu, S.T. Flammia, et al. (2010). “Quantum state tomography via compressed sensing.” Physical Review Letters, 105, 150401. Gross D. Liu Y.-K. Flammia S.T. ( 2010 ). “ Quantum state tomography via compressed sensing . ” Physical Review Letters , 105 , 150401 . Search in Google 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. Qin Z. Jameson C. Gong Z. ( 2024 ). “ Quantum state tomography for matrix product density operators . ” IEEE Transactions on Information Theory , 70 , 5030 . Search in Google 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. van Apeldoorn J. Cornelissen A. Gilyén oA. ( 2023 ). “ Quantum tomography using state-preparation unitaries ”, in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 1265 – 1318 . Search in Google Scholar

10. G. Torlai, G. Mazzola, J. Carrasquilla, et al. (2018). “Neural-network quantum state tomography”. Nature Physics, 14, 447–450. Torlai G. Mazzola G. Carrasquilla J. ( 2018 ). “ Neural-network quantum state tomography ”. Nature Physics , 14 , 447 – 450 . Search in Google 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. Ahmed S. Sánchez Muñoz C. Nori F. Kockum A.F. ( 2021 ). “ Classification and reconstruction of optical quantum states with deep neural networks ”. Physical Review Research , 3 , 033278 . Search in Google Scholar

12. V. Wei, W.A. Coish, P. Ronagh, et al. (2024). “Neural-shadow quantum state tomography”. Physical Review Research, 6, 023250. Wei V. Coish W.A. Ronagh P. ( 2024 ). “ Neural-shadow quantum state tomography ”. Physical Review Research , 6 , 023250 . Search in Google Scholar

13. Y. Quek, S. Fort, and H.K. Ng (2021). “Adaptive quantum state tomography with neural networks”. npj Quantum Information., 7, 1–7. Quek Y. Fort S. Ng H.K. ( 2021 ). “ Adaptive quantum state tomography with neural networks ”. npj Quantum Information ., 7 , 1 – 7 . Search in Google Scholar

14. N. Innan, O. I. Siddiqui, S. Arora, et al. (2024). “Quantum state tomography using quantum machine learning”. Quantum Machine Intelligence, 6, 28. Innan N. Siddiqui O. I. Arora S. ( 2024 ). “ Quantum state tomography using quantum machine learning ”. Quantum Machine Intelligence , 6 , 28 . Search in Google Scholar

15. S. Aaronson (2007). “The learnability of quantum states”. Proceedings of the Royal Society A, 463, 3089–3114. Aaronson S. ( 2007 ). “ The learnability of quantum states ”. Proceedings of the Royal Society A , 463 , 3089 – 3114 . Search in Google 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. Hu H.-Y. Choi S. You Y.-Z. ( 2023 ). “ Classical shadow tomography with locally scrambled quantum dynamics ”. Physical Review Research , 5 , 023027 . Search in Google Scholar

17. H.-Y. Huang (2022). “Learning quantum states from their classical shadows”. Nature Review Physics, 4, 81. Huang H.-Y. ( 2022 ). “ Learning quantum states from their classical shadows ”. Nature Review Physics , 4 , 81 . Search in Google Scholar

18. P.L. Bartlett, O. Bousquet, and S. Mendelson (2005). “Local Rademacher complexities”. Annals of Statistics, 33. Bartlett P.L. Bousquet O. Mendelson S. ( 2005 ). “ Local Rademacher complexities ”. Annals of Statistics , 33 . Search in Google Scholar

19. A. Kitaev, A. Shen, and M. Vyalyi (2002). Classical and Quantum Computation. American Mathematical Society. Kitaev A. Shen A. Vyalyi M. ( 2002 ). Classical and Quantum Computation . American Mathematical Society . Search in Google Scholar

20. J. Cotler and F. Wilczek (2020). “Quantum overlapping tomography”. Physical Review Letters, 124, 100401. Cotler J. Wilczek F. ( 2020 ). “ Quantum overlapping tomography ”. Physical Review Letters , 124 , 100401 . Search in Google Scholar

21. S. Aaronson (2020). “Shadow tomography of quantum states”. SIAM Journal on Computing, 49, STOC18-368- STOC18-394. Aaronson S. ( 2020 ). “ Shadow tomography of quantum states ”. SIAM Journal on Computing , 49 , STOC18-368 STOC18-394 . Search in Google 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. Maurer A. ( 2016 ). “ A vector-contraction inequality for rademacher complexities ”, in Ortner R. Simon H.U. Zilles S. (eds), Algorithmic Learning Theory . Cham : Springer International Publishing , 3 – 17 . Search in Google 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. Cortes C. Kloft M. Mohri M. ( 2013 ). “ Learning kernels using local Rademacher complexity ”. Advances in Neural Information Processing Systems (NIPS) , 26 , 2760 – 2768 . Search in Google Scholar

24. S. Dasgupta and A. Gupta (2003). “An elementary proof of a theorem of Johnson and Lindenstrauss”. Random Structures & Algorithms, 22, 60. Dasgupta S. Gupta A. ( 2003 ). “ An elementary proof of a theorem of Johnson and Lindenstrauss ”. Random Structures & Algorithms , 22 , 60 . Search in Google Scholar

25. P. Cha, P. Ginsparg, F. Wu, J. Carrasquilla, et al. (2022). “Attention-based quantum tomography”. Machine Learning: Science and Technology, 3, 01LT01 Cha P. Ginsparg P. Wu F. Carrasquilla J. ( 2022 ). “ Attention-based quantum tomography ”. Machine Learning: Science and Technology , 3 , 01LT01. Search in Google 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. Johansson J.R. Nation P.D. Nori F. ( 2012 ). “ QuTiP: An open-source python framework for the dynamics of open quantum systems ”. Computer Physics Communications , 183 , 1760 – 1772 . Search in Google 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. Johansson J.R. Nation P.D. Nori F. ( 2013 ). “ QuTiP 2: A python framework for the dynamics of open quantum systems ”. Computer Physics Communications , 184 , 1234 – 1240 . Search in Google Scholar

28. B.I. Bantysh, A.Y. Chernyavskiy, and Y.I. Bogdanov (2021). “Quantum tomography benchmarking”. Quantum Information Processing, 20, 339. Bantysh B.I. Chernyavskiy A.Y. Bogdanov Y.I. ( 2021 ). “ Quantum tomography benchmarking ”. Quantum Information Processing , 20 , 339 . Search in Google Scholar

29. J. Carrasquilla, G. Torlai, R.G. Melko, et al. (2019). “Reconstructing quantum states with generative models”. Nature Machine Intelligence, 1, 155–161. Carrasquilla J. Torlai G. Melko R.G. ( 2019 ). “ Reconstructing quantum states with generative models ”. Nature Machine Intelligence , 1 , 155 – 161 . Search in Google Scholar