Session: Quantum Computing and discrete continuous optimization
Chair: David Bernal Neira
Cluster: Interplay Between Continuous and Discrete Optimization
Talk 1: Interior-point and first-order methods for quantum entanglement detection
Speaker: Javier Pena
Abstract: We describe two different algorithmic approaches to tackle the following central problem in quantum information science: given a bipartite quantum state, detect if the state is entangled by constructing a suitable "entanglement witness". The crux for both approaches is to solve a challenging convex feasibility problem based on a widely known symmetric extension criteria for entanglement detection. We show that a judicious formulation of the convex feasibility problem can be naturally tackled via both interior-point methods and Frank-Wolfe method. We will discuss the tradeoffs of these two computational approaches.
Talk 2: Prospects for quantum speedups in convex integer programming
Speaker: Brandon Augustino
Abstract: Integer programming constitutes a fundamental class of problems in computer science with countless real-world applications, and their NP-hardness makes them an attractive candidate for large quantum speedups. The most well-known quantum approaches to solve discrete optimization problems either rely on quantum speedups for unstructured search, or rely on the use of penalty functions to incorporate constraints. Unsurprisingly, these techniques do not lead to quantum algorithms that offer speedups over the state-of-the-art classical IP algorithms, which search the feasible region in a highly structured manner. In this talk we discuss the challenges and potential associated with designing faster quantum algorithms for the convex integer programming problem. From a technical standpoint, we discuss new quantum approaches to enumerating lattice points in convex bodies, which is at the core of the quantum IP algorithm we analyze.
Talk 3: Continuous optimization for unconventional continuous computing: Accelerating Continuous Variable Coherent Ising Machines with momentum updates
Speaker: David Bernal Neira
Abstract: The Coherent Ising Machine (CIM) leverages continuous dynamics and physical annealing principles for solving complex Ising problems. Our work introduces modifications to the Continuous Variable CIM (CV-CIM) by integrating momentum and Adam-based updates, targeting accelerated convergence for continuous optimization. Standard CV-CIMs operate with gradient-based updates, which, although effective, can be trapped by local minima or suffer from poor problem conditioning. By enhancing the CIM dynamics with momentum and adaptive techniques, our approach significantly improves convergence rates and solution diversity. Through numerical experiments on benchmark quadratic programming problems, we demonstrate that momentum-CV-CIM and Adam-CV-CIM variations outperform standard CV-CIM in convergence speed and robustness, especially under challenging, poorly conditioned instances. These findings suggest that incorporating classical optimization techniques like momentum and Adam into CV-CIM systems not only enhances computational efficiency but also extends the practical applicability of CIMs for a broader class of continuous optimization problems. This work underscores the potential for hybrid approaches that marry classical optimization strategies with non-conventional computing architectures, promoting more reliable and scalable solutions across diverse fields in optimization. The results are available in https://arxiv.org/abs/2401.12135
