2 citations · 4 across the 8 of their papers we have counts for
8 papers
(Sub)Exponential Quantum Speedup for Optimization
Jiaqi Leng, Kewen Wu, Xiaodi Wu +1
We demonstrate provable (sub)exponential quantum speedups in both discrete and continuous optimization, achieved through simple and natural quantum optimization algorithms, namely…
Quantum Hamiltonian Descent for Non-smooth Optimization
Jiaqi Leng, Yufan Zheng, Zhiyuan Jia +4
Non-smooth optimization models play a fundamental role in various disciplines, including engineering, science, management, and finance. However, classical algorithms for solving su…
On the Computational Complexity of Schrödinger Operators
Yufan Zheng, Jiaqi Leng, Yizhou Liu +1
We study computational problems related to the Schrödinger operator in the real space under the condition that (i) the potential function is smooth and has its valu…
A quantum-classical performance separation in nonconvex optimization
Jiaqi Leng, Yufan Zheng, Xiaodi Wu
In this paper, we identify a family of nonconvex continuous optimization instances, each -dimensional instance with local minima, to demonstrate a quantum-classical perfor…
Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful
Xiaoming Sun, Yufan Zheng
In this paper, we introduce the hybrid query complexity, denoted as , which is the minimal query number needed to compute , when a classical decision tree is al…
On the Degree of Boolean Functions as Polynomials over
Xiaoming Sun, Yuan Sun, Jiaheng Wang +3
Polynomial representations of Boolean functions over various rings such as and have been studied since Minsky and Papert (1969). From then on, they have…
The Complexity of Coloring inCongested Clique, Massively Parallel Computation,and Centralized Local Computation
Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari +2
We present new randomized algorithms that improve the complexity of the classic -coloring problem, and its generalization -list-coloring, in three well-studied models…
A Rudimentary Model for Low-Latency Anonymous Communication Systems
Yufan Zheng
In this paper we present a rudimentary model for low-latency anonymous communication systems. Specifically, we study distributed OR algorithm as an abstract of the system. Based on…