publications

2024

1. 

   On the computational complexity of Schrödinger operators

   Yufan Zheng ,  Jiaqi Leng ,  Yizhou Liu , and 1 more author

   Preprint, 2024

   Abs arXiv

   We study computational problems related to the Schrödinger operator H = -∆+ V in the real space under the condition that (i) the potential function V is smooth and has its value and derivative bounded within some polynomial of n and (ii) V only consists of O(1)-body interactions. We prove that (i) simulating the dynamics generated by the Schrödinger operator implements universal quantum computation, i.e., it is BQP-hard, and (ii) estimating the ground energy of the Schrödinger operator is as hard as estimating that of local Hamiltonians with no sign problem (a.k.a. stoquastic Hamiltonians), i.e., it is StoqMA-complete. This result is particularly intriguing because the ground energy problem for general bosonic Hamiltonians is known to be QMA-hard and it is widely believed that StoqMA ⊊QMA.

2. 

   Differentiable quantum computing for large-scale linear control

   Connor Clayton ,  Jiaqi Leng ,  Gengzhi Yang , and 3 more authors

   To appear in NeurIPS, 2024

   Abs arXiv HTML

   As industrial models and designs grow increasingly complex, the demand for optimal control of large-scale dynamical systems has significantly increased. However, traditional methods for optimal control incur significant overhead as problem dimensions grow. In this paper, we introduce an end-to-end quantum algorithm for linear-quadratic control with provable speedups. Our algorithm, based on a policy gradient method, incorporates a novel quantum subroutine for solving the matrix Lyapunov equation. Specifically, we build a quantum-assisted differentiable simulator for efficient gradient estimation that is more accurate and robust than classical methods relying on stochastic approximation. Compared to the classical approaches, our method achieves a super-quadratic speedup. To the best of our knowledge, this is the first end-to-end quantum application to linear control problems with provable quantum advantage.

3. 

   QHDOPT: A software for nonlinear optimization with quantum Hamiltonian decent

   Samuel Kushnir ,  Jiaqi Leng ,  Yuxiang Peng , and 2 more authors

   To appear in INFORMS Journal on Computing, 2024

   Abs arXiv HTML

   We develop an open-source, end-to-end software (named QHDOPT), which can solve nonlinear optimization problems using the quantum Hamiltonian descent (QHD) algorithm. QHDOPT offers an accessible interface and automatically maps tasks to various supported quantum backends (i.e., quantum hardware machines). These features enable users, even those without prior knowledge or experience in quantum computing, to utilize the power of existing quantum devices for large-scale nonlinear and nonconvex optimization tasks. In its intermediate compilation layer, QHDOPT employs SimuQ, an efficient interface for Hamiltonian-oriented programming, to facilitate multiple algorithmic specifications and ensure compatible cross-hardware deployment.

4. 

   Expanding hardware-efficiently manipulable Hilbert space via Hamiltonian embedding

   Jiaqi Leng ,  Joseph Li ,  Yuxiang Peng , and 1 more author

   Preprint, 2024

   Abs arXiv

   Many promising quantum applications depend on the efficient quantum simulation of an exponentially large sparse Hamiltonian, a task known as sparse Hamiltonian simulation, which is fundamentally important in quantum computation. Although several theoretically appealing quantum algorithms have been proposed for this task, they typically require a black-box query model of the sparse Hamiltonian, rendering them impractical for near-term implementation on quantum devices. In this paper, we propose a technique named Hamiltonian embedding. This technique simulates a desired sparse Hamiltonian by embedding it into the evolution of a larger and more structured quantum system, allowing for more efficient simulation through hardware-efficient operations. We conduct a systematic study of this new technique and demonstrate significant savings in computational resources for implementing prominent quantum applications. As a result, we can now experimentally realize quantum walks on complicated graphs (e.g., binary trees, glued-tree graphs), quantum spatial search, and the simulation of real-space Schrödinger equations on current trapped-ion and neutral-atom platforms. Given the fundamental role of Hamiltonian evolution in the design of quantum algorithms, our technique markedly expands the horizon of implementable quantum advantages in the NISQ era.

2023

1. 

   A quantum central path algorithm for linear optimization

   Brandon Augustino ,  Jiaqi Leng ,  Giacomo Nannicini , and 2 more authors

   Preprint, 2023

   Abs arXiv

   We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. While interior point methods follow the central path with an iterative algorithm that works with successive linearizations of the perturbed KKT conditions, we perform a single simulation working directly with the nonlinear complementarity equations. Combining our approach with iterative refinement techniques, we obtain an exact solution to a linear optimization problem involving m constraints and n variables using at most O ((m + n) nnz(A) κL) elementary gates and O(nnz(A) L) classical arithmetic operations, where nnz(A) is the total number of non-zero elements found in the constraint matrix, L denotes binary input length of the problem data, and κis a condition number that depends only on the problem data.

2. 

   A quantum-classical performance separation in nonconvex optimization

   Jiaqi Leng ,  Yufan Zheng ,  and  Xiaodi Wu

   Preprint, 2023

   Abs arXiv

   In this paper, we identify a family of nonconvex continuous optimization instances, each d-dimensional instance with 2^d local minima, to demonstrate a quantum-classical performance separation. Specifically, we prove that the recently proposed Quantum Hamiltonian Descent (QHD) algorithm [Leng et al., arXiv:2303.01471] is able to solve any d-dimensional instance from this family using O(d^3) quantum queries to the function value and O(d^4) additional 1-qubit and 2-qubit elementary quantum gates. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical optimization algorithms/solvers (including Gurobi) would require a super-polynomial time to solve such optimization instances.

3. 

   Quantum Hamiltonian Descent

   Jiaqi Leng ,  Ethan Hickman ,  Joseph Li , and 1 more author

   Preprint, 2023

   Abs arXiv HTML

   Gradient descent is a fundamental algorithm in both theory and practice for continuous optimization. Identifying its quantum counterpart would be appealing to both theoretical and practical quantum applications. A conventional approach to quantum speedups in optimization relies on the quantum acceleration of intermediate steps of classical algorithms, while keeping the overall algorithmic trajectory and solution quality unchanged. We propose Quantum Hamiltonian Descent (QHD), which is derived from the path integral of dynamical systems referring to the continuous-time limit of classical gradient descent algorithms, as a truly quantum counterpart of classical gradient methods where the contribution from classically-prohibited trajectories can significantly boost QHD’s performance for non-convex optimization. Moreover, QHD is described as a Hamiltonian evolution efficiently simulatable on both digital and analog quantum computers. By embedding the dynamics of QHD into the evolution of the so-called Quantum Ising Machine (including D-Wave and others), we empirically observe that the D-Wave-implemented QHD outperforms a selection of state-of-the-art gradient-based classical solvers and the standard quantum adiabatic algorithm, based on the time-to-solution metric, on non-convex constrained quadratic programming instances up to 75 dimensions. Finally, we propose a "three-phase picture" to explain the behavior of QHD, especially its difference from the quantum adiabatic algorithm.

2022

1. 

   Differentiable analog quantum computing for optimization and control

   Jiaqi Leng ,  Yuxiang Peng ,  Yi-Ling Qiao , and 2 more authors

   Advances in Neural Information Processing Systems, 2022

   Abs Bib PDF

   We formulate the first differentiable analog quantum computing framework with specific parameterization design at the analog signal (pulse) level to better exploit near-term quantum devices via variational methods. We further propose a scalable approach to estimate the gradients of quantum dynamics using a forward pass with Monte Carlo sampling, which leads to a quantum stochastic gradient descent algorithm for scalable gradient-based training in our framework. Applying our framework to quantum optimization and control, we observe a significant advantage of differentiable analog quantum computing against SOTAs based on parameterized digital quantum circuits by orders of magnitude.

   @article{leng2022differentiable,
     title = {Differentiable analog quantum computing for optimization and control},
     author = {Leng, Jiaqi and Peng, Yuxiang and Qiao, Yi-Ling and Lin, Ming and Wu, Xiaodi},
     journal = {Advances in Neural Information Processing Systems},
     volume = {35},
     pages = {4707--4721},
     year = {2022},
   }

2. Quantum

   Quantum simulation of real-space dynamics

   Andrew M Childs ,  Jiaqi Leng ,  Tongyang Li , and 2 more authors

   Quantum, 2022

   Abs Bib PDF

   Quantum simulation is a prominent application of quantum computers. While there is extensive previous work on simulating finite-dimensional systems, less is known about quantum algorithms for real-space dynamics. We conduct a systematic study of such algorithms. In particular, we propose quantum algorithms to simulate the dynamics of a d-dimensional Schrödinger equation with ηparticles. Compared to the best previous results, our quantum algorithms achieve exponential improvements in several problem parameters. We give applications to several computational problems, including faster real-space simulation of quantum chemistry, rigorous analysis of discretization error for simulation of a uniform electron gas, and a quadratic improvement to a quantum algorithm for escaping saddle points in nonconvex optimization.

   @article{childs2022quantum,
     title = {Quantum simulation of real-space dynamics},
     author = {Childs, Andrew M and Leng, Jiaqi and Li, Tongyang and Liu, Jin-Peng and Zhang, Chenyi},
     journal = {Quantum},
     volume = {6},
     pages = {860},
     year = {2022},
     publisher = {Verein zur F{\"o}rderung des Open Access Publizierens in den Quantenwissenschaften},
   }

2021

1. 

   Quantum algorithms for escaping from saddle points

   Chenyi Zhang ,  Jiaqi Leng ,  and  Tongyang Li

   Quantum, 2021

   Abs Bib PDF

   We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Compared to classical algorithms by Jin et al., our quantum algorithm is polynomially better in terms of log(n) (n is the problem dimension) and matches its complexity in terms of 1/ε. Technically, our main contribution is the idea of replacing the classical perturbations in gradient descent methods by simulating quantum wave equations, which constitutes the improvement in the quantum query complexity with log(n) factors for escaping from saddle points. We also show how to use a quantum gradient computation algorithm due to Jordan to replace the classical gradient queries by quantum evaluation queries with the same complexity. Finally, we also perform numerical experiments that support our theoretical findings.

   @article{zhang2021quantum,
     title = {Quantum algorithms for escaping from saddle points},
     author = {Zhang, Chenyi and Leng, Jiaqi and Li, Tongyang},
     journal = {Quantum},
     volume = {5},
     pages = {529},
     year = {2021},
     publisher = {Verein zur F{\"o}rderung des Open Access Publizierens in den Quantenwissenschaften},
   }