Quantum Optimization - Solving QUBO with Gurobi

#quantum #algorithms #ai #complexity

Quantum advantage doesn’t begin with quantum hardware. It begins with understanding what the best classical algorithms can already do.

In this video, we explore how Gurobi, a state-of-the-art classical optimizer solves Quadratic Unconstrained Binary Optimization (QUBO) problems. Gurobi is widely used as a classical baseline when evaluating quantum algorithms for combinatorial optimization.

Starting with a simple Max-Cut problem, we formulate the problem as a QUBO and solve it in Python using gurobipy. We then benchmark larger problem instances and investigate why Gurobi’s runtime does not always increase predictably with problem size.

You’ll learn about:

Solving QUBO problems with Gurobi and Python
Using Gurobi as a classical baseline for quantum optimization
Branch-and-bound and mathematical bounds
Why some problem instances are harder than others
Dense versus sparse QUBO problems
How MIPGap affects runtime and optimality guarantees
The role of primal heuristics in finding high-quality solutions
Why proving optimality can take longer than finding a good solution
Gurobi’s deterministic behavior
Accessing a free Gurobi academic license

This video is designed for software engineers and Python developers who want to explore quantum algorithms and their practical applications. You don’t need previous experience with quantum computing, being comfortable with Python is enough to follow along.

To build useful applications with quantum computers, we first need to understand the capabilities and limitations of classical computers. Only then can we meaningfully evaluate where quantum algorithms might provide real value.

Sources mentioned in the video:
💻 GitHub Repo

https://github.com/supreethmv/Quantum-Algorithms-and-Applications.git

🎓 Gurobi Academic License

https://www.gurobi.com/academics

This is a continuation of:
▶️ Quantum Optimization - Introduction to QUBO

https://youtu.be/P9sM2M-ahvs

▶️ Navigating into Quantum Computing for Software Engineers

https://youtu.be/W-i2Iy_KWTg

Subscribe to Practical Quantum with Supreeth for practical, code-focused explanations of quantum algorithms, optimization, and real-world applications.