Which practical problems would a scaled-up quantum computer be useful for? This is a challenging question, because hardware capable of running real-world benchmarks is unavailable, and theoretical works typically make only asymptotic statements. In this talk, I'll report on non-asymptotic analyses of quantum convex optimization algorithms. The focus will be on a proposal by Brandão, França, and Kueng for SDP relaxations of QUBO problems. It felt particularly attractive: SDPs seem like a natural match for quantum methods; the algorithm, targeting combinatorial problems, includes a rounding step that mitigates the unfavorable precision of quantum SDP solvers; and the proposal came with a rigorous asymptotic running time estimate. After having optimized their proposal for performance on realistic instances, we proceeded to estimate the smallest problem size for which the proven asymptotic advantage manifests. To learn the results, come to the talk! (Or have a sneak peek at arXiv:2502.15426).

*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*