A Hybrid Quantum-Classical Approach for Solving Combinatorial Problems via Graph Decomposition

Interdisciplinary Areas: Data and Engineering Applications

Project Description

This postdoctoral project focuses on solving combinatorial problems on hybrid quantum-classical machines using separators in graphs to decompose the computation into a collection of computations on smaller graphs. The project will explore solutions for various classes of graphs with good separators, including planar graphs, graphs derived from finite element meshes, and geometric graphs such as disk overlap graphs, all of which possess small separators that decompose the graph into a collection of smaller subgraphs.

The motivation for this work is the fact that quantum computers will have only a relatively small number of sparsely connected and noisy qubits for the next several years, which severely limits the size of problems that can be solved on quantum machines. Hence to solve large problems on quantum computers, one needs to decompose the graph into a collection of small subgraphs, which can be accomplished for separable graphs.

The core idea is to decompose a graph by removing a small set of nodes or edges to obtain a collection of small subgraphs, on which the quantum algorithm can be executed. We leverage quantum machines to solve the problem instances on the small subgraphs and then combine the solutions on classical machines to obtain the solution for the larger-scale problem.

The approach can be extended to solving Quantum Unconstrained Binary Optimization (QUBO) problems by methods such as the Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing. This should also benefit from other decomposition techniques for Mixed-Integer Nonlinear Programming (MINLP) problems and potential applications to them.

The project emphasizes theoretical advancements and software development, designing efficient decomposition algorithms, and evaluating solution quality and computational efficiency. Close collaboration with the Purdue Quantum Science and Engineering Institute will ensure access to cutting-edge quantum computing resources and interdisciplinary collaborations, enriching the understanding of quantum-classical hybrid methodologies.

This research aims to advance quantum-classical computation, developing scalable algorithms by combining the power of quantum computing with classical techniques.
 
 

Start Date

Spring 2024
 
 

Postdoc Qualifications

PhD in Engineering, Mathematics, or Physics.
Previous experience in quantum computing is required.
Previous experience in optimization and graph theory is recommended.
 
 

Co-Advisors

David E. Bernal Neira. dbernaln@purdue.edu, Davidson School of Chemical Engineering, https://engineering.purdue.edu/ChE/people/ptProfile?resource_id=286478
Alex Pothen, apothen@purdue.edu, Department of Computer Science https://www.cs.purdue.edu/homes/apothen/
 
 

Short Bilbiography

- Ponce, Moises, et al. "Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms." arXiv preprint arXiv:2306.00494 (2023).
- Shaydulin, Ruslan, et al. "A hybrid approach for solving optimization problems on small quantum computers." Computer 52.6 (2019): 18-26.
- Jalving, Jordan, Sungho Shin, and Victor M. Zavala. "A graph-based modeling abstraction for optimization: Concepts and implementation in plasmo. jl." Mathematical Programming Computation 14.4 (2022): 699-747.
- Ushijima-Mwesigwa, Hayato, et al. "Multilevel combinatorial optimization across quantum architectures." ACM Transactions on Quantum Computing 2.1 (2021): 1-29.