{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T13:02:53Z","timestamp":1771678973119,"version":"3.50.1"},"reference-count":29,"publisher":"Walter de Gruyter GmbH","issue":"2","license":[{"start":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T00:00:00Z","timestamp":1746057600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,5,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>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.<\/jats:p>","DOI":"10.2478\/qic-2025-0008","type":"journal-article","created":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T02:39:34Z","timestamp":1750905574000},"page":"156-174","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial Complexity of Quantum Sample Tomography"],"prefix":"10.2478","volume":"25","author":[{"given":"Kun","family":"Tang","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Zhejiang University , Hangzhou , Zhejiang , China"}]},{"given":"Jun","family":"Lai","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Zhejiang University , Hangzhou , Zhejiang , China"}]}],"member":"374","published-online":{"date-parts":[[2025,5,26]]},"reference":[{"key":"2026022112210173042_j_qic-2025-0008_ref_001","doi-asserted-by":"crossref","unstructured":"F. Arute, K. Arya, R. Babbush, et al. (2019). \u201cQuantum supremacy using a programmable superconducting processor\u201d. Nature, 574, 505\u2013510.","DOI":"10.1038\/s41586-019-1666-5"},{"key":"2026022112210173042_j_qic-2025-0008_ref_002","doi-asserted-by":"crossref","unstructured":"A.W. Harrow, A. Hassidim, and S. Lloyd (2009). \u201cQuantum algorithm for solving linear systems of equations.\u201d Physical Review Letters, 103, 150502.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"2026022112210173042_j_qic-2025-0008_ref_003","doi-asserted-by":"crossref","unstructured":"L. Zhou, S.-T. Wang, S. Choi, et al. (2020). \u201cQuantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices.\u201d Physical Review X, 10, 021067.","DOI":"10.1103\/PhysRevX.10.021067"},{"key":"2026022112210173042_j_qic-2025-0008_ref_004","doi-asserted-by":"crossref","unstructured":"A.W.R. Smith, J. Gray, and M.S. Kim (2021). \u201cEfficient quantum state sample tomography with basis-dependent neural networks.\u201d PRX Quantum, 2, 020348.","DOI":"10.1103\/PRXQuantum.2.020348"},{"key":"2026022112210173042_j_qic-2025-0008_ref_005","doi-asserted-by":"crossref","unstructured":"J. Shang, Z. Zhang, and H.K. Ng (2017). \u201cSuperfast maximum-likelihood reconstruction for quantum tomography.\u201d Physical Review A, 95, 062336","DOI":"10.1103\/PhysRevA.95.062336"},{"key":"2026022112210173042_j_qic-2025-0008_ref_006","doi-asserted-by":"crossref","unstructured":"E. Bolduc, G.C. Knee, E.M. Gauger, et al. (2017). \u201cProjected gradient descent algorithms for quantum state tomography.\u201d npj Quantum Information, 3, 44.","DOI":"10.1038\/s41534-017-0043-1"},{"key":"2026022112210173042_j_qic-2025-0008_ref_007","doi-asserted-by":"crossref","unstructured":"D. Gross, Y.-K. Liu, S.T. Flammia, et al. (2010). \u201cQuantum state tomography via compressed sensing.\u201d Physical Review Letters, 105, 150401.","DOI":"10.1103\/PhysRevLett.105.150401"},{"key":"2026022112210173042_j_qic-2025-0008_ref_008","doi-asserted-by":"crossref","unstructured":"Z. Qin, C. Jameson, Z. Gong, et al. (2024). \u201cQuantum state tomography for matrix product density operators.\u201d IEEE Transactions on Information Theory, 70, 5030.","DOI":"10.1109\/TIT.2024.3360951"},{"key":"2026022112210173042_j_qic-2025-0008_ref_009","doi-asserted-by":"crossref","unstructured":"J. van Apeldoorn, A. Cornelissen, A. Gily\u00e9n, et al. (2023). \u201cQuantum tomography using state-preparation unitaries\u201d, in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1265\u20131318.","DOI":"10.1137\/1.9781611977554.ch47"},{"key":"2026022112210173042_j_qic-2025-0008_ref_010","doi-asserted-by":"crossref","unstructured":"G. Torlai, G. Mazzola, J. Carrasquilla, et al. (2018). \u201cNeural-network quantum state tomography\u201d. Nature Physics, 14, 447\u2013450.","DOI":"10.1038\/s41567-018-0048-5"},{"key":"2026022112210173042_j_qic-2025-0008_ref_011","doi-asserted-by":"crossref","unstructured":"S. Ahmed, C. S\u00e1nchez Mu\u00f1oz, F. Nori, and A.F. Kockum (2021). \u201cClassification and reconstruction of optical quantum states with deep neural networks\u201d. Physical Review Research, 3, 033278.","DOI":"10.1103\/PhysRevResearch.3.033278"},{"key":"2026022112210173042_j_qic-2025-0008_ref_012","doi-asserted-by":"crossref","unstructured":"V. Wei, W.A. Coish, P. Ronagh, et al. (2024). \u201cNeural-shadow quantum state tomography\u201d. Physical Review Research, 6, 023250.","DOI":"10.1103\/PhysRevResearch.6.023250"},{"key":"2026022112210173042_j_qic-2025-0008_ref_013","doi-asserted-by":"crossref","unstructured":"Y. Quek, S. Fort, and H.K. Ng (2021). \u201cAdaptive quantum state tomography with neural networks\u201d. npj Quantum Information., 7, 1\u20137.","DOI":"10.1038\/s41534-021-00436-9"},{"key":"2026022112210173042_j_qic-2025-0008_ref_014","doi-asserted-by":"crossref","unstructured":"N. Innan, O. I. Siddiqui, S. Arora, et al. (2024). \u201cQuantum state tomography using quantum machine learning\u201d. Quantum Machine Intelligence, 6, 28.","DOI":"10.1007\/s42484-024-00162-3"},{"key":"2026022112210173042_j_qic-2025-0008_ref_015","doi-asserted-by":"crossref","unstructured":"S. Aaronson (2007). \u201cThe learnability of quantum states\u201d. Proceedings of the Royal Society A, 463, 3089\u20133114.","DOI":"10.1098\/rspa.2007.0113"},{"key":"2026022112210173042_j_qic-2025-0008_ref_016","doi-asserted-by":"crossref","unstructured":"H.-Y. Hu, S. Choi, and Y.-Z. You (2023). \u201cClassical shadow tomography with locally scrambled quantum dynamics\u201d. Physical Review Research, 5, 023027.","DOI":"10.1103\/PhysRevResearch.5.023027"},{"key":"2026022112210173042_j_qic-2025-0008_ref_017","doi-asserted-by":"crossref","unstructured":"H.-Y. Huang (2022). \u201cLearning quantum states from their classical shadows\u201d. Nature Review Physics, 4, 81.","DOI":"10.1038\/s42254-021-00411-5"},{"key":"2026022112210173042_j_qic-2025-0008_ref_018","doi-asserted-by":"crossref","unstructured":"P.L. Bartlett, O. Bousquet, and S. Mendelson (2005). \u201cLocal Rademacher complexities\u201d. Annals of Statistics, 33.","DOI":"10.1214\/009053605000000282"},{"key":"2026022112210173042_j_qic-2025-0008_ref_019","doi-asserted-by":"crossref","unstructured":"A. Kitaev, A. Shen, and M. Vyalyi (2002). Classical and Quantum Computation. American Mathematical Society.","DOI":"10.1090\/gsm\/047"},{"key":"2026022112210173042_j_qic-2025-0008_ref_020","doi-asserted-by":"crossref","unstructured":"J. Cotler and F. Wilczek (2020). \u201cQuantum overlapping tomography\u201d. Physical Review Letters, 124, 100401.","DOI":"10.1103\/PhysRevLett.124.100401"},{"key":"2026022112210173042_j_qic-2025-0008_ref_021","doi-asserted-by":"crossref","unstructured":"S. Aaronson (2020). \u201cShadow tomography of quantum states\u201d. SIAM Journal on Computing, 49, STOC18-368- STOC18-394.","DOI":"10.1137\/18M120275X"},{"key":"2026022112210173042_j_qic-2025-0008_ref_022","doi-asserted-by":"crossref","unstructured":"A. Maurer (2016). \u201cA vector-contraction inequality for rademacher complexities\u201d, in R. Ortner, H.U. Simon, and S. Zilles (eds), Algorithmic Learning Theory. Cham: Springer International Publishing, 3\u201317.","DOI":"10.1007\/978-3-319-46379-7_1"},{"key":"2026022112210173042_j_qic-2025-0008_ref_023","unstructured":"C. Cortes, M. Kloft, and M. Mohri (2013). \u201cLearning kernels using local Rademacher complexity\u201d. Advances in Neural Information Processing Systems (NIPS), 26, 2760\u20132768."},{"key":"2026022112210173042_j_qic-2025-0008_ref_024","doi-asserted-by":"crossref","unstructured":"S. Dasgupta and A. Gupta (2003). \u201cAn elementary proof of a theorem of Johnson and Lindenstrauss\u201d. Random Structures & Algorithms, 22, 60.","DOI":"10.1002\/rsa.10073"},{"key":"2026022112210173042_j_qic-2025-0008_ref_025","doi-asserted-by":"crossref","unstructured":"P. Cha, P. Ginsparg, F. Wu, J. Carrasquilla, et al. (2022). \u201cAttention-based quantum tomography\u201d. Machine Learning: Science and Technology, 3, 01LT01","DOI":"10.1088\/2632-2153\/ac362b"},{"key":"2026022112210173042_j_qic-2025-0008_ref_026","doi-asserted-by":"crossref","unstructured":"J.R. Johansson, P.D. Nation, and F. Nori (2012). \u201cQuTiP: An open-source python framework for the dynamics of open quantum systems\u201d. Computer Physics Communications, 183, 1760\u20131772.","DOI":"10.1016\/j.cpc.2012.02.021"},{"key":"2026022112210173042_j_qic-2025-0008_ref_027","doi-asserted-by":"crossref","unstructured":"J.R. Johansson, P.D. Nation, and F. Nori (2013). \u201cQuTiP 2: A python framework for the dynamics of open quantum systems\u201d. Computer Physics Communications, 184, 1234\u20131240.","DOI":"10.1016\/j.cpc.2012.11.019"},{"key":"2026022112210173042_j_qic-2025-0008_ref_028","doi-asserted-by":"crossref","unstructured":"B.I. Bantysh, A.Y. Chernyavskiy, and Y.I. Bogdanov (2021). \u201cQuantum tomography benchmarking\u201d. Quantum Information Processing, 20, 339.","DOI":"10.1007\/s11128-021-03285-9"},{"key":"2026022112210173042_j_qic-2025-0008_ref_029","doi-asserted-by":"crossref","unstructured":"J. Carrasquilla, G. Torlai, R.G. Melko, et al. (2019). \u201cReconstructing quantum states with generative models\u201d. Nature Machine Intelligence, 1, 155\u2013161.","DOI":"10.1038\/s42256-019-0028-1"}],"container-title":["Quantum Information &amp; Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/qic-2025-0008","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T12:21:13Z","timestamp":1771676473000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.sciendo.com\/article\/10.2478\/qic-2025-0008"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,1]]},"references-count":29,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,5,26]]},"published-print":{"date-parts":[[2025,5,1]]}},"alternative-id":["10.2478\/qic-2025-0008"],"URL":"https:\/\/doi.org\/10.2478\/qic-2025-0008","relation":{},"ISSN":["1533-7146"],"issn-type":[{"value":"1533-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,1]]}}}