Publications

Ⓐ — in alphabetical order.
Ⓒ — by contribution.

Journals

• [J22]

  On estimating the trace of quantum state powers. [C3 @SODA 2025]

  Ⓐ Yupan Liu, and Qisheng Wang.

  IEEE Transactions on Information Theory, to appear, 2026. arXiv:2410.13559.

  Presented as (part of) an invited talk (40min) at Shenzhen–Nagoya Workshop on Quantum Science 2025.

  Presented as a contributed talk at the 28th Quantum Information Processing Conference (QIP 2025).

  Presented (by Yupan Liu) as a contributed talk at the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025).

  Presented as (part of) a research talk at the NQCC-QSL December Deep Dive Agenda in the University of Edinburgh in 2024.
• [J21]

  Space-bounded quantum state testing via space-efficient quantum singular value transformation.

  Ⓐ François Le Gall, Yupan Liu, and Qisheng Wang.

  Computational Complexity, to appear, 2026. arXiv:2308.05079.

  Presented (by Yupan Liu) as a poster at the 2023 Annual Q-LEAP Quantum AI Meeting (令和5年度Q-LEAP量子AI領域研究会) in 2024.

  Presented (with Yupan Liu) as a poster at the 27th Conference on Quantum Information Processing (QIP 2024).

  Presented (by Yupan Liu) as an invited online talk at the Research Center for Quantum Software (QuSoft) in 2023.

  Appears as Monthly News for August 2023 in Property Testing Review.
• [J20]

  Quantum data structure for range minimum query.

  Ⓐ Qisheng Wang, Zhean Xu, and Zhicheng Zhang.

  Journal of Computer and System Sciences, 157: 103756, 2026. doi:10.1016/j.jcss.2026.103756. arXiv:2601.13195.
• [J19]

  Time-efficient quantum entropy estimator via samplizer. [C2 @ESA 2024]

  Ⓒ Qisheng Wang and Zhicheng Zhang.

  IEEE Transactions on Information Theory, 71(12): 9569-9599, 2025. doi:10.1109/TIT.2025.3576137. arXiv:2401.09947.

  Presented as (part of) an invited talk (40min) at Shenzhen–Nagoya Workshop on Quantum Science 2025.

  Presented as an invited talk (20min) at Shenzhen–Nagoya Workshop on Quantum Science 2024.

  Presented as a contributed talk at the 32nd Annual European Symposium on Algorithms (ESA 2024).

  Presented as an online talk invited by Patrick Rebentrost at the National University of Singapore in 2024.

  Presented as an online talk invited by Zhengfeng Ji at Tsinghua University in 2024.
• [J18]

  Double-ended palindromic trees in linear time.

  Ⓐ Qisheng Wang, Ming Yang, and Xinrui Zhu.

  Information and Computation, 307: 105379, 2025. doi:10.1016/j.ic.2025.105379. arXiv:2210.02292.

  Testable on Library Checker.
• [J17]

  Quantum lower bounds by sample-to-query lifting.

  Ⓒ Qisheng Wang and Zhicheng Zhang.

  SIAM Journal on Computing, 54(5): 1294-1334, 2025. doi:10.1137/24M1638616. arXiv:2308.01794.

  Presented as (part of) an invited talk (40min) at Shenzhen–Nagoya Workshop on Quantum Science 2025.

  Presented (with Zhicheng Zhang) as a poster at the 27th Conference on Quantum Information Processing (QIP 2024).

  Presented as an online talk invited by Zhengfeng Ji at Tsinghua University in 2023.

  Presented as an invited talk (20min) at Shenzhen–Nagoya Workshop on Quantum Science 2023.

  Appears as Monthly News for August 2023 in Property Testing Review.
• [J16]

  Quantum algorithms for matrix geometric means.

  Ⓐ Nana Liu, Qisheng Wang, Mark M. Wilde, and Zhicheng Zhang.

  npj Quantum Information, 11: 101, 2025. doi:10.1038/s41534-025-00973-7. arXiv:2405.00673.

  Presented (by Nana Liu) as (part of) an invited talk at the 8th International Conference on Quantum Techniques in Machine Learning (QTML 2024).

  Presented (by Mark M. Wilde) as a contributed talk at the 16th International Conference on Quantum Communication, Measurement and Computing (QCMC 2024). doi:10.5281/zenodo.14309036.
• [J15]

  A note on quantum divide and conquer for minimal string rotation.

  Qisheng Wang.

  Theoretical Computer Science, 1034: 115120, 2025. doi:10.1016/j.tcs.2025.115120. arXiv:2210.09149.

  Presented as a poster at the 47th Quantum Information Technology Symposium (第47回量子情報技術研究会, QIT47) in 2022.
• [J14]

  Optimal trace distance and fidelity estimations for pure quantum states.

  Qisheng Wang.

  IEEE Transactions on Information Theory, 70(12): 8791-8805, 2024. doi:10.1109/TIT.2024.3447915. arXiv:2408.16655.

  Presented as a talk invited by Li Zhou at the Institute of Software, Chinese Academy of Sciences in 2025.

  Presented as (part of) a contributed talk at the 25th Asian Quantum Information Science Conference (AQIS 2025).

  Presented as an invited talk at the Quantum Summer School 2025 in the University of St Andrews.

  Presented as a seminar talk at the QSL Seminar organized by Robert I. Booth in the University of Edinburgh in 2024.
• [J13]

  Quantum Büchi automata.

  Ⓒ Qisheng Wang and Mingsheng Ying.

  Theoretical Computer Science, 1012: 114740, 2024. doi:10.1016/j.tcs.2024.114740. arXiv:1804.08982.
• [J12]

  New quantum algorithms for computing quantum entropies and distances.

  Ⓒ Qisheng Wang, Ji Guan, Junyi Liu, Zhicheng Zhang, and Mingsheng Ying.

  IEEE Transactions on Information Theory, 70(8): 5653-5680, 2024. doi:10.1109/TIT.2024.3399014. arXiv:2203.13522.

  Presented as an invited talk, merged with arXiv:2103.09076, at the 35th Q-LEAP Quantum AI Seminar (第35回Q-LEAP量子AIセミナー) in 2022.
• [J11]

  Tight quantum depth lower bound for solving systems of linear equations.

  Ⓒ Qisheng Wang and Zhicheng Zhang.

  Physical Review A, 110(1): 012422, 2024. doi:10.1103/PhysRevA.110.012422. arXiv:2407.06012.
• [J10]

  Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions.

  Ⓒ Jingquan Luo, Qisheng Wang, and Lvzhou Li.

  IEEE Transactions on Information Theory, 70(7): 5092-5103, 2024. doi:10.1109/TIT.2024.3393756. arXiv:2304.12916.

  Presented (by Jingquan Luo) as a poster at the 2nd CCF Quantum Computation Conference and China Quantum Computation Industry Summit (第二届CCF量子计算大会暨中国量子计算产业峰会, CQCC 2023).
• [J9]

  Fast quantum algorithms for trace distance estimation.

  Ⓒ Qisheng Wang and Zhicheng Zhang.

  IEEE Transactions on Information Theory, 70(4): 2720-2733, 2024. doi:10.1109/TIT.2023.3321121. arXiv:2301.06783.

  Presented as an invited talk at the 2023 Annual Q-LEAP Quantum AI Meeting (令和5年度Q-LEAP量子AI領域研究会) in 2024.
• [J8]

  Quantum algorithm for lexicographically minimal string rotation.

  Ⓒ Qisheng Wang and Mingsheng Ying.

  Theory of Computing Systems, 68(1): 29-74, 2024. doi:10.1007/s00224-023-10146-8. arXiv:2012.09376.
• [J7]

  Parallel quantum algorithm for Hamiltonian simulation.

  Ⓒ Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying.

  Quantum, 8: 1228, 2024. doi:10.22331/q-2024-01-15-1228. arXiv:2105.11889.
• [J6]

  Unitarity estimation for quantum channels.

  Ⓒ Kean Chen, Qisheng Wang, Peixun Long, and Mingsheng Ying.

  IEEE Transactions on Information Theory, 69(8): 5116-5134, 2023. doi:10.1109/TIT.2023.3263645. arXiv:2212.09319.

  Presented (by Kean Chen) as a poster at the 2023 Academic Annual Conference of the Institute of Software, Chinese Academy of Sciences (2023年中国科学院软件研究所学术年会).
• [J5]

  Quantum random access stored-program machines.

  Ⓒ Qisheng Wang and Mingsheng Ying.

  Journal of Computer and System Sciences, 131: 13-63, 2023. doi:10.1016/j.jcss.2022.08.002. arXiv:2003.03514.
• [J4]

  Quantum algorithm for fidelity estimation.

  Ⓒ Qisheng Wang, Zhicheng Zhang, Kean Chen, Ji Guan, Wang Fang, Junyi Liu, and Mingsheng Ying.

  IEEE Transactions on Information Theory, 69(1): 273-282, 2023. doi:10.1109/TIT.2022.3203985. arXiv:2103.09076.

  Presented as an invited talk, merged with arXiv:2203.13522, at the 35th Q-LEAP Quantum AI Seminar (第35回Q-LEAP量子AIセミナー) in 2022.
• [J3]

  Equivalence checking of sequential quantum circuits.

  Ⓒ Qisheng Wang, Riling Li, and Mingsheng Ying.

  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(9): 3143-3156, 2022. doi:10.1109/TCAD.2021.3117506. arXiv:1811.07722.
• [J2]

  An HHL-based algorithm for computing hitting probabilities of quantum walks.

  Ⓒ Ji Guan, Qisheng Wang, and Mingsheng Ying.

  Quantum Information and Computation, 21(5-6): 395-408, 2021. doi:10.26421/QIC21.5-6-4. arXiv:2009.03618.
• [J1]

  Equivalence checking of quantum finite-state machines.

  Ⓒ Qisheng Wang, Junyi Liu, and Mingsheng Ying.

  Journal of Computer and System Sciences, 116: 1-21, 2021. doi:10.1016/j.jcss.2020.08.004. arXiv:1901.02173.

Conferences

• [C9]

  Quantum Hamiltonian certification.

  Ⓐ Minbo Gao, Zhengfeng Ji, Qisheng Wang, Wenjun Yu, and Qi Zhao.

  In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pp. 1424-1467, 2026. doi:10.1137/1.9781611978971.53. arXiv:2505.13217.

  Appears as Monthly News for May 2025 in Property Testing Review.
• [C8]

  On estimating the quantum $\ell_\alpha$ distance.

  Ⓐ Yupan Liu and Qisheng Wang.

  In Proceedings of the 33rd Annual European Symposium on Algorithms (ESA 2025), pp. 106:1-106:19, 2025. doi:10.4230/LIPIcs.ESA.2025.106. arXiv:2505.00457.

  Presented (by Yupan Liu) as a contributed talk at the 33rd Annual European Symposium on Algorithms (ESA 2025).

  Presented as a contributed long talk at the 25th Asian Quantum Information Science Conference (AQIS 2025).

  Appears as Monthly News for May 2025 in Property Testing Review.
• [C7]

  Quantum approximate $k$-minimum finding.

  Ⓐ Minbo Gao, Zhengfeng Ji, and Qisheng Wang.

  In Proceedings of the 33rd Annual European Symposium on Algorithms (ESA 2025), pp. 51:1-51:15, 2025. doi:10.4230/LIPIcs.ESA.2025.51. arXiv:2412.16586.

  Presented as a contributed talk at the 33rd Annual European Symposium on Algorithms (ESA 2025).
• [C6]

  Optimal quantum algorithm for estimating fidelity to a pure state.

  Ⓐ Wang Fang and Qisheng Wang.

  In Proceedings of the 33rd Annual European Symposium on Algorithms (ESA 2025), pp. 4:1-4:12, 2025. doi:10.4230/LIPIcs.ESA.2025.4. arXiv:2506.23650.

  Presented as a contributed talk at the 33rd Annual European Symposium on Algorithms (ESA 2025).

  Presented as (part of) a contributed talk at the 25th Asian Quantum Information Science Conference (AQIS 2025).
• [C5]

  Space-bounded quantum interactive proof systems.

  Ⓐ François Le Gall, Yupan Liu, Harumichi Nishimura, and Qisheng Wang.

  In Proceedings of the 40th Computational Complexity Conference (CCC 2025), pp. 17:1-17:18, 2025. doi:10.4230/LIPIcs.CCC.2025.17. arXiv:2410.23958.

  Presented (by Yupan Liu) as a contributed talk at the 28th Quantum Information Processing Conference (QIP 2025).

  Presented as (part of) a research talk at the NQCC-QSL December Deep Dive Agenda in the University of Edinburgh in 2024.
• [C4]

  Improved sample upper and lower bounds for trace estimation of quantum state powers.

  Ⓐ Kean Chen and Qisheng Wang.

  In Proceedings of the 38th Conference on Learning Theory (COLT 2025), pp. 1008-1028, 2025. URL: https://proceedings.mlr.press/v291/chen25d.html. arXiv:2505.09563v1.

  Presented as a contributed talk at the 38th Annual Conference on Learning Theory (COLT 2025).

  Appears as Monthly News for May 2025 in Property Testing Review.
• [C3]

  On estimating the trace of quantum state powers. [J22 @TIT]

  Ⓐ Yupan Liu and Qisheng Wang.

  In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pp. 947-993, 2025. doi:10.1137/1.9781611978322.28. arXiv:2410.13559.
• [C2]

  Time-efficient quantum entropy estimator via samplizer. [J19 @TIT]

  Ⓒ Qisheng Wang and Zhicheng Zhang.

  In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA 2024), pp. 101:1-101:15, 2024. doi:10.4230/LIPIcs.ESA.2024.101. arXiv:2401.09947.
• [C1]

  Logarithmic-regret quantum learning algorithms for zero-sum games.

  Ⓐ Minbo Gao, Zhengfeng Ji, Tongyang Li, and Qisheng Wang.

  In Advances in Neural Information Processing Systems 36 (NeurIPS 2023), pp. 31177-31203, 2024. URL: https://papers.nips.cc/paper_files/paper/2023/hash/637df18481a6aa74238bd2cafff94cb9-Abstract-Conference.html. arXiv:2304.14197.

  Presented as a seminar talk at the QML/ALGO Group Meeting organized by Mina Doosti in the University of Edinburgh in 2024.

  Presented as a poster at the 27th Conference on Quantum Information Processing (QIP 2024).

  Presented (online by Minbo Gao and in-person by me) as a poster at the 37th Annual Conference on Neural Information Processing Systems (NeurIPS 2023).

Preprints

• [P13]

  Trace estimation of quantum state powers: Sample complexity and computational hardness.

  Ⓐ Kean Chen, Yupan Liu, and Qisheng Wang.

  arXiv:2505.09563v2, 2026.
• [P12]

  A slightly improved upper bound for quantum statistical zero-knowledge.

  Ⓐ François Le Gall, Yupan Liu, and Qisheng Wang.

  arXiv:2512.11597, 2025.
• [P11]

  A list of complexity bounds for property testing by quantum sample-to-query lifting.

  Ⓐ Kean Chen, Qisheng Wang, and Zhicheng Zhang.

  arXiv:2512.01971, 2025.
• [P10]

  On estimating the quantum Tsallis relative entropy.

  Ⓐ Jinge Bao, Minbo Gao, and Qisheng Wang.

  arXiv:2510.00752, 2025.
• [P9]

  Quantum algorithms for Uhlmann transformation.

  Ⓒ Takeru Utsumi, Yoshifumi Nakata, Qisheng Wang, and Ryuji Takagi.

  arXiv:2509.03619, 2025.
• [P8]

  Information-theoretic lower bounds for approximating monomials via optimal quantum Tsallis entropy estimation.

  Qisheng Wang.

  arXiv:2509.03496, 2025.
• [P7]

  Simultaneous estimation of nonlinear functionals of a quantum state.

  Ⓐ Kean Chen, Qisheng Wang, Zhan Yu, and Zhicheng Zhang.

  arXiv:2505.16715, 2025.

  Presented (by Zhan Yu) as a contributed talk at the the 25th Asian Quantum Information Science Conference (AQIS 2025).
• [P6]

  Does there exist a quantum fingerprinting protocol without coherent measurements?.

  Ⓐ Atsuya Hasegawa, Srijita Kundu, François Le Gall, Harumichi Nishimura, and Qisheng Wang.

  arXiv:2502.13427, 2025.
• [P5]

  Quantum algorithm for sparse online learning with truncated gradient descent.

  Ⓐ Debbie Lim, Yixian Qiu, Patrick Rebentrost, Qisheng Wang.

  arXiv:2411.03925, 2024.

  Presented as (part of) a research talk at the NQCC-QSL December Deep Dive Agenda in the University of Edinburgh in 2024.
• [P4]

  Sample-optimal quantum estimators for pure-state trace distance and fidelity via samplizer.

  Ⓒ Qisheng Wang and Zhicheng Zhang.

  arXiv:2410.21201, 2024.

  Presented as (part of) an invited talk (40min) at Shenzhen–Nagoya Workshop on Quantum Science 2025.

  Presented as (part of) a contributed talk at the 25th Asian Quantum Information Science Conference (AQIS 2025).

  Presented as (part of) a research talk at the NQCC-QSL December Deep Dive Agenda in the University of Edinburgh in 2024.
• [P3]

  Local test for unitarily invariant properties of bipartite quantum states.

  Ⓐ Kean Chen, Qisheng Wang, and Zhicheng Zhang.

  arXiv:2404.04599, 2024.

  Presented as (part of) an invited talk (40min) at Shenzhen–Nagoya Workshop on Quantum Science 2025.

  Appears as Monthly News for April 2024 in Property Testing Review.
• [P2]

  VeriQBench: a benchmark for multiple types of quantum circuits.

  Ⓐ Kean Chen, Wang Fang, Ji Guan, Xin Hong, Mingyu Huang, Junyi Liu, Qisheng Wang, and Mingsheng Ying.

  arXiv:2206.10880, 2022.
• [P1]

  Improving positive unlabeled learning: practical AUL estimation and new training method for extremely imbalanced data sets.

  Ⓒ Liwei Jiang, Dan Li, Qisheng Wang, Shuai Wang, and Songtao Wang.

  arXiv:2004.09820, 2020.