北京雁栖湖应用数学研究院

程嵩 , 刘锦鹏 , 刘正伟 , 刘子文

李彤阳

2026年05月29日 14:00 至 15:00

Shuangqing-B626

Zoom 230 432 7880 (BIMSA)

Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimizing the number of logical qubits required to execute this algorithm is a key object. In implementations of Shor's algorithm, the space complexity is largely dictated by the modular inversion operation during point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing method of Proos and Zalka and propose a space-efficient reversible modular inversion algorithm. We use length registers together with location-controlled arithmetic to store the intermediate variables in a compact form throughout the computation. We then optimize the stepwise update rules and give concrete circuit constructions for the resulting controlled arithmetic components. This leads to a modular inversion circuit that uses $3n + 4\lfloor \log_2 n \rfloor + O(1)$ logical qubits and $204n^2\log_2 n + O(n^2)$ Toffoli gates. By inserting this modular inversion component into the controlled affine point-addition circuit, we obtain a space-efficient algorithm for the ECDLP with $5n + 4\lfloor \log_2 n \rfloor + O(1)$ qubits and $O(n^3)$ Toffoli gates. In particular, for a 256-bit prime-field curve, our estimate reduces the logical-qubit count to 1333, compared with 2124 in the previous low-width implementation of Häner et al.

Dr. Tongyang Li joined Peking University in July 2021 and is currently an assistant professor at Center on Frontiers of Computing Studies, Peking University. Previously he was a postdoctoral associate at the Center for Theoretical Physics, Massachusetts Institute of Technology. He received Master and Ph.D. degrees from the Department of Computer Science, University of Maryland in 2018 and 2020, respectively. He received Bachelor of Engineering from Institute for Interdisciplinary Information Sciences, Tsinghua University and Bachelor of Science from Department of Mathematical Sciences, Tsinghua University, both in 2015. Dr. Tongyang Li’s research focuses on designing quantum algorithms for machine learning and optimization, as well as performing quantum algorithms on current noisy, intermediate-scale quantum devices (NISQ). He has published more than 40 papers at Nature Physics, Nature Communications, Journal of the ACM, Physical Review Letters, IEEE Transactions on Information Theory, STOC, ICML, NeurIPS, ICLR, AAAI, and other top venues. He has 9 contributed talks at QIP.