A Hybrid Quantum-Classical Approach for Solving Combinatorial Problems via Graph Decomposition
|Interdisciplinary Areas:||Data and Engineering Applications
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 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.
Previous experience in quantum computing is required.
Previous experience in optimization and graph theory is recommended.
Alex Pothen, email@example.com, Department of Computer Science https://www.cs.purdue.edu/homes/apothen/
- 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.