Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

邮发代号 80-970

2019 Impact Factor: 1.275

Frontiers of Computer Science  2025, Vol. 19 Issue (7): 197907   https://doi.org/10.1007/s11704-024-40414-w
  本期目录
Shadow tomography of quantum states with prediction
Jiyu JIANG1, Zongqi WAN2,3, Tongyang LI4,5, Meiyue SHAO1,6, Jialin ZHANG2,3()
. School of Data Science, Fudan University, Shanghai 200433, China
. State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
. University of Chinese Academy of Sciences, Beijing 101408, China
. Center on Frontiers of Computing Studies, Peking University, Beijing 100871, China
. School of Computer Science, Peking University, Beijing 100871, China
. Shanghai Key Laboratory for Contemporary Applied Mathematics, Fudan University, Shanghai 200433, China
 全文: PDF(2264 KB)   HTML
Abstract

The shadow tomography problem introduced by [1] is an important problem in quantum computing. Given an unknown n-qubit quantum state ρ, the goal is to estimate t r(F1ρ ),, tr(F Mρ) using as least copies of ρ as possible, within an additive error of ε, where F1, ,FM are known 2-outcome measurements. In this paper, we consider the shadow tomography problem with a potentially inaccurate prediction ϱ of the true state ρ. This corresponds to practical cases where we possess prior knowledge of the unknown state. For example, in quantum verification or calibration, we may be aware of the quantum state that the quantum device is expected to generate. However, the actual state it generates may have deviations. We introduce an algorithm with sample complexity O~(nmax {ρ ϱ 1,ε}log2M/ε 4). In the generic case, even if the prediction can be arbitrarily bad, our algorithm has the same complexity as the best algorithm without prediction [2]. At the same time, as the prediction quality improves, the sample complexity can be reduced smoothly to O~(nlog2 M/ε3 ) when the trace distance between the prediction and the unknown state is Θ (ε). Furthermore, we conduct numerical experiments to validate our theoretical analysis. The experiments are constructed to simulate noisy quantum circuits that reflect possible real scenarios in quantum verification or calibration. Notably, our algorithm outperforms the previous work without prediction in most settings.

Key wordsshadow tomography    online learning    quantum state learning    FTRL    quantum machine learning
收稿日期: 2024-04-27      出版日期: 2024-09-11
Corresponding Author(s): Jialin ZHANG   
 引用本文:   
. [J]. Frontiers of Computer Science, 2025, 19(7): 197907.
Jiyu JIANG, Zongqi WAN, Tongyang LI, Meiyue SHAO, Jialin ZHANG. Shadow tomography of quantum states with prediction. Front. Comput. Sci., 2025, 19(7): 197907.
 链接本文:  
https://academic.hep.com.cn/fcs/CN/10.1007/s11704-024-40414-w
https://academic.hep.com.cn/fcs/CN/Y2025/V19/I7/197907
  
Fig.1  
Fig.2  
Fig.3  
  
  
  
  
  
  
  
1 S Aaronson . Shadow tomography of quantum states. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018, 325−338
2 C, Bădescu R O’Donnell . Improved quantum data analysis. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021, 1398−1411
3 X W, Huang J Q, Luo L Li . Quantum speedup and limitations on matroid property problems. Frontiers of Computer Science, 2024, 18( 4): 184905
4 M, Paris J Řeháček . Quantum State Estimation. Berlin: Springer, 2004
5 N, Innan O I, Siddiqui S, Arora T, Ghosh Y P, Koçak D, Paragas A A O, Galib M A Z, Khan M Bennai . Quantum state tomography using quantum machine learning. Quantum Machine Intelligence, 2024, 6( 1): 28
6 M, Cramer M B, Plenio S T, Flammia R, Somma D, Gross S D, Bartlett O, Landon-Cardinal D, Poulin Y K Liu . Efficient quantum state tomography. Nature Communications, 2010, 1: 149
7 R, O’Donnell J Wright . Efficient quantum tomography. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing. 2016, 899−912
8 J Wright . How to learn a quantum state. Carnegie Mellon University, Dissertation, 2016
9 J, Haah A W, Harrow Z, Ji X, Wu N Yu . Sample-optimal tomography of quantum states. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing. 2016, 913−925
10 S, Chen B, Huang J, Li A, Liu M Sellke . When does adaptivity help for quantum state learning? In: Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 2023, 391−404
11 B P, Lanyon C, Maier M, Holzäpfel T, Baumgratz C, Hempel P, Jurcevic I, Dhand A S, Buyskikh A J, Daley M, Cramer M B, Plenio R, Blatt C F Roos . Efficient tomography of a quantum many-body system. Nature Physics, 2017, 13( 12): 1158–1162
12 J, Carrasquilla G, Torlai R G, Melko L Aolita . Reconstructing quantum states with generative models. Nature Machine Intelligence, 2019, 1( 3): 155–161
13 G, Torlai G, Mazzola J, Carrasquilla M, Troyer R, Melko G Carleo . Neural-network quantum state tomography. Nature Physics, 2018, 14( 5): 447–450
14 S, Aaronson X, Chen E, Hazan S Kale . Online learning of quantum states. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018, 8976−8986
15 E Hazan . Introduction to online convex optimization. Foundations and Trends® in Optimization, 2016, 2(3−4): 157−325
16 S H, Sack R A, Medina A A, Michailidis R, Kueng M Serbyn . Avoiding barren plateaus using classical shadows. PRX Quantum, 2022, 3( 2): 020365
17 J R, McClean S, Boixo V N, Smelyanskiy R, Babbush H Neven . Barren plateaus in quantum neural network training landscapes. Nature Communications, 2018, 9( 1): 4812
18 M, Cerezo A, Arrasmith R, Babbush S C, Benjamin S, Endo K, Fujii J R, McClean K, Mitarai X, Yuan L, Cincio P J Coles . Variational quantum algorithms. Nature Reviews Physics, 2021, 3( 9): 625–644
19 H Y, Huang R, Kueng J Preskill . Predicting many properties of a quantum system from very few measurements. Nature Physics, 2020, 16( 10): 1050–1057
20 H Y, Huang R, Kueng G, Torlai V V, Albert J Preskill . Provably efficient machine learning for quantum many-body problems. Science, 2022, 377( 6613): eabk3333
21 Y, Chen X Wang . More practical and adaptive algorithms for online quantum state learning. 2020, arXiv preprint arXiv: 2006.01013
22 F, Yang J, Jiang J, Zhang X Sun . Revisiting online quantum state learning. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence. 2020, 6607−6614
23 X, Chen E, Hazan T, Li Z, Lu X, Wang R Yang . Adaptive online learning of quantum states. 2022, arXiv preprint arXiv: 2206.00220
24 W, Gong S Aaronson . Learning distributions over quantum measurement outcomes. In: Proceedings of the 40th International Conference on Machine Learning. 2023, 11598−11613
25 X F, Yin Y, Du Y Y, Fei R, Zhang L Z, Liu Y, Mao T, Liu M H, Hsieh L, Li N L, Liu D, Tao Y A, Chen J W Pan . Efficient bipartite entanglement detection scheme with a quantum adversarial solver. Physical Review Letters, 2022, 128( 11): 110501
26 S, Aaronson G N Rothblum . Gentle measurement of quantum states and differential privacy. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019, 322−333
27 S, Chen J, Cotler H Y, Huang J Li . Exponential separations between learning with and without quantum memory. In: Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS). 2022, 574−585
28 M A, Nielsen I L Chuang . Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2010
29 H Osamu . Application of quantum Pinsker inequality to quantum communications. 2020, arXiv preprint arXiv: 2005.04553
30 D M, Greenberger M A, Horne A Zeilinger . Going beyond Bell’s theorem. In: Kafatos M, ed. Bell’s Theorem, Quantum Theory and Conceptions of the Universe. Dordrecht: Springer, 1989, 69−72
31 A, Rocchetto S, Aaronson S, Severini G, Carvacho D, Poderini I, Agresti M, Bentivegna F Sciarrino . Experimental learning of quantum states. Science Advances, 2019, 5( 3): eaau1946
32 M, Möttönen J J, Vartiainen V, Bergholm M M Salomaa . Transformation of quantum states using uniformly controlled rotations. Quantum Information & Computation, 2005, 5( 6): 467–473
33 M, Plesch Č Brukner . Quantum-state preparation with universal gate decompositions. Physical Review A, 2011, 83( 3): 032302
34 S, Chen W, Yu P, Zeng S T Flammia . Robust shadow estimation. PRX Quantum, 2021, 2( 3): 030348
35 N, Metropolis S Ulam . The Monte Carlo method. Journal of the American Statistical Association, 1949, 44( 247): 335–341
36 M M Wilde . Quantum Information Theory. 2nd ed. Cambridge: Cambridge University Press, 2017
37 J Preskill . Quantum computing in the NISQ era and beyond. Quantum, 2018, 2: 79
38 S, Chen J, Cotler H Y, Huang J Li . The complexity of NISQ. Nature Communications, 2023, 14( 1): 6001
[1] Highlights Download
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed