Tackling Complementarity Problem at Scale via Continuous-Variable Quantum Computing

Project begins 2024.

Physics-based high-fidelity simulation is crucial for autonomous vehicles navigating off-road terrains, treating terrain as granular particles tracked individually through methods like the discrete element method (DEM). A class of DEM methods called the DEM-C methods enforce contacts using complementarity constraints, which allows for the use of larger time-steps since contacts are enforced geometrically. Despite advancements in algorithms and distributed computing hardware, simulating grain-to-vehicle level remains computationally expensive, preventing real-time execution. This capability, however, is extremely important as current physics-based mobility simulations, which coarse-grain the soil particles, often result in inaccurate predictions, necessitating high factor-of-safety.

The primary goal of this proposal is to develop novel continuous-variable quantum algorithms for directly attacking the inequality-constrained optimization problem arising in DEM-C methods along with a software implementation that can be executed on a recently released photonic quantum computer. Our team will create software demonstration within this project period that directly plugs into the GVSC physics-based mobility simulation frameworks. Given that the number of qumodes, which are the fundamental computing units similar to qubits, is expected to scale to millions in the next five years, a quantum advantage demonstration may be feasible within that timeframe.

The proposed research involves three key objectives and associated challenges. First, the use of quantum slack variable to handle inequality constraints posed by the complementarity problem involves the introduction of m additional qumodes, such that the total Hilbert space describing the joint quantum state over the search variables and the Lagrange multipliers is given by L^2(R^(n+2m)). This should be compared to our previous work on equality constraints which only required m additional qumodes leading to the Hilbert space L^2(R^(n+m)), which in turn, builds on the original proposal of for unconstrained optimization using L^2(R^n). The demand for increasing number of qumodes will be met by leveraging associated advancements in hardware including the Borealis device.

The second objective is to overcome challenges involving considerations of computational complexity. In our previous work we considered the warmup problem of quadratic programming with affine equality constraints. This problem is considered a warmup because there exist classical algorithms which solve it in polynomial time and moreover we were able to show that the quantum CV-QAOA algorithm can be expressed in terms of elementary Gaussian gate operations which are efficiently simulable by classical computers. Inequality constraints, however, are significantly more challenging because even in the case of quadratic programming with affine inequality constraints, the resulting optimization problem is NP-hard. This NP-hardness has an avatar in the CV-QAOA, where it is possible to show that our quantum slack variables algorithm is not classically simulable. The above considerations lead to a considerably more challenging problem and likewise improves the plausibility of quantum speedup. Therefore, unlike our previous work, the use of quantum devices is pivotal even in the prototyping phase, because the overhead for classical simulation quickly becomes prohibitive due to the increased qumode requirement.

The final challenge is to overcome theoretical challenges posed by the nature of quantum gradient descent-ascient GDA, whose theory of convergence involves significant subtleties compared to classical GD. For example, previous work by us has emphasized the importance of convergence notions based on the last iterate versus the average iterate, and an enormous body of research establishing last-iterate convergence has emerged in machine learning literature motivated by application to optimization of generative adversarial networks. Establishing convergence results for QGDA by transplanting related results for the classical ML literature will be a considerable undertaking, which can have a correspondingly large payoff in terms of improving the trainability and practicality of the developed quantum algorithms.

Publications from Prior Work closely related to the proposed project:

1. Zhang, Yabin, David Gorsich, Paramsothy Jayakumar, and Shravan Veerapaneni. “Continuous-variable optimization with neural network quantum states.” Quantum Machine Intelligence 4, no. 1 (2022): 9.
2. Stokes, J., De, S., Veerapaneni, S., & Carleo, G. (2023). Continuous-variable neural network quantum states and the quantum rotor model. Quantum Machine Intelligence, 5(1), 12.
3. De, Saibal, Eduardo Corona, Paramsothy Jayakumar, and Shravan Veerapaneni. “Tensor-train compression of discrete element method simulation data.” arXiv preprint arXiv:2210.08399 (2022).
4. Corona, E., Gorsich, D., Jayakumar, P., & Veerapaneni, S. (2019). Tensor train accelerated solvers for nonsmooth rigid body dynamics. Applied Mechanics Reviews, 71(5), 050804.
5. Zhang, Yabin, James Stokes, David Gorisch, Paramsothy Jayakumar, and Shravan Veerapaneni. “A note on equality-constrained continuous optimization within the quantum approximate optimization framework.” (2023).

Previous projects include 1.22, 1.A73 and 1.32.

#3.27