10 papers
Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
Tongyang Li, Weiran Ma, Ziyi Yang +1
The Tarski fixed-point problem asks for a fixed point of a monotone map on a -dimensional grid lattice of width and has applications in game theory, economics, and verificat…
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…
Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
Yuexin Su, Ziyi Yang, Peiyuan Huang +2
Bandits with knapsacks (BwK) constitute a fundamental model that combines aspects of stochastic integer programming with online learning. Classical algorithms for BwK with a time h…
Classification and structure of generalized Legendrian racks
Luc Ta
This paper develops the structure theory of generalized Legendrian racks, which are algebraic structures used to study Legendrian knots. First, we give a group-theoretic characteri…
Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs
Tongyang Li, Yuexin Su, Ziyi Yang +1
Maximum cut (MaxCut) on graphs is a classic NP-hard problem. In quantum computing, Farhi, Gutmann, and Goldstone proposed the Quantum Approximate Optimization Algorithm (QAOA) for…