6 papers · 1 filter
Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid
Tongyang Li, Weiran Ma, Ziyi Yang +1
The Knaster-Tarski fixed-point theorem states that every monotone function over a complete lattice has a fixed point. Beyond its fundamental role in order theory, the theorem and i…
Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation
Boyang Chen, Minbo Gao, Zhengfeng Ji +3
The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$ q = O\left( αT + \frac{\log(1/\varepsilon)}{\log\left(e + \log(1/\varepsilon)/(αT)…
Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition
Han Luo, Ziyi Yang, Jingquan Luo +5
The Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography, and reducing the resource requirements of quantum algorithms for solving ECDLP is an…
Scalable First-Order Interior Point Trust Region Algorithms for Linearly Constrained Optimization
Yuexin Su, Chenyi Zhang, Peiyuan Huang +2
Computing approximate Karush--Kuhn--Tucker (KKT) points for constrained nonconvex programs is a fundamental problem in mathematical programming. Interior-point trust-region (IPTR)…
Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation
Han Luo, Ziyi Yang, Ziruo Wang +2
Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimiz…
DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
Zhengfeng Ji, Tongyang Li, Changpeng Shao +2
We study the computational complexity of estimating the normalized trace for a log-local Hamiltonian acting on qubits. This problem arises natural…