Non-Asymptotic Running-Time Analysis of Quantum Convex Optimization Algorithms

Explore a comprehensive analysis of quantum convex optimization algorithms in this hour-long conference talk that examines the practical viability of quantum computing for real-world problems. Delve into non-asymptotic running-time analyses that move beyond theoretical asymptotic statements to provide concrete insights into quantum algorithm performance. Focus on the Brandão, França, and Kueng proposal for SDP relaxations of QUBO problems, examining why semidefinite programs appear naturally suited for quantum methods and how the algorithm's rounding step addresses precision limitations in quantum SDP solvers. Learn about optimization efforts for realistic problem instances and discover findings about the minimum problem size required for proven asymptotic advantages to emerge in practice. Gain insights into the challenging question of which practical problems would benefit from scaled-up quantum computers, supported by rigorous analysis and recent research findings from arXiv:2502.15426.