Publications

Ⓐ — in alphabetical order.
Ⓒ — by contribution.

1. On estimating the trace of quantum state powers.
   Ⓐ Yupan Liu and Qisheng Wang.
   In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), to appear, 2025. arXiv:2410.13559.
2. 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 seminar talk at the QSL Seminar organized by Robert I. Booth in the University of Edinburgh in 2024.
3. 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.
4. Time-efficient quantum entropy estimator via samplizer.
   Ⓒ 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.
   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.
5. 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.
6. 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.
7. 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).
8. 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.
9. 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).
10. 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.
11. 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.
12. 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年中国科学院软件研究所学术年会).
13. 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.
14. 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.
15. 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.
16. 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.
17. 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.

Preprints

1. Quantum algorithm for sparse online learning with truncated gradient descent.
   Ⓐ Debbie Lim, Yixian Qiu, Patrick Rebentrost, Qisheng Wang.
   arXiv:2411.03925, 2024.
2. Space-bounded quantum interactive proof systems.
   Ⓐ François Le Gall, Yupan Liu, Harumichi Nishimura, and Qisheng Wang.
   arXiv:2410.23958, 2024.
3. Sample-optimal quantum estimators for pure-state trace distance and fidelity via samplizer.
   Ⓒ Qisheng Wang and Zhicheng Zhang.
   arXiv:2410.21201, 2024.
4. Quantum algorithms for matrix geometric means.
   Ⓐ Nana Liu, Qisheng Wang, Mark M. Wilde, and Zhicheng Zhang.
   arXiv:2405.00673, 2024.
   Presented (by Mark M. Wilde) as a talk at the 16th International Conference on Quantum Communication, Measurement and Computing (QCMC 2024).
5. Local test for unitarily invariant properties of bipartite quantum states.
   Ⓐ Kean Chen, Qisheng Wang, and Zhicheng Zhang.
   arXiv:2404.04599, 2024.
   Appears as Monthly News for April 2024 in Property Testing Review.
6. Space-bounded quantum state testing via space-efficient quantum singular value transformation.
   Ⓐ François Le Gall, Yupan Liu, and Qisheng Wang.
   arXiv:2308.05079, 2023.
   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.
7. Quantum lower bounds by sample-to-query lifting.
   Ⓒ Qisheng Wang and Zhicheng Zhang.
   arXiv:2308.01794, 2023.
   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.
8. A note on quantum divide and conquer for minimal string rotation.
   Qisheng Wang.
   arXiv:2210.09149, 2022.
   Presented as a poster at the 47th Quantum Information Technology Symposium (第47回量子情報技術研究会, QIT47) in 2022.
9. Double-ended palindromic trees: a linear-time data structure and its applications.
   Ⓒ Qisheng Wang, Ming Yang, and Xinrui Zhu.
   arXiv:2210.02292, 2022.
   Implemented on Library Checker.
10. 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.
11. 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.