Quantum Speedups for Approximating the John Ellipsoid

In 1948, Fritz John proposed a theorem stating that every convex body has a unique maximal volume inscribed ellipsoid, known as the John ellipsoid. The John ellipsoid has become fundamental in mathematics, with extensive applications in high-dimensional sampling, linear programming, and machine learning. Designing faster algorithms to compute the John ellipsoid is therefore an important and emerging problem. In Cohen, Cousins, Lee, Yang COLT 2019, they established an algorithm for approximating the John ellipsoid for a symmetric convex polytope defined by a matrix A R^n d with a time complexity of O (nd²). This was later improved to O (nnz (A) + d^) by Song, Yang, Yang, Zhou 2022, where nnz (A) is the number of nonzero entries of A and is the matrix multiplication exponent. Currently 2. 371 Alman, Duan, Williams, Xu, Xu, Zhou 2024. In this work, we present the first quantum algorithm that computes the John ellipsoid utilizing recent advances in quantum algorithms for spectral approximation and leverage score approximation, running in O (nd^1. 5 + d^) time. In the tall matrix regime, our algorithm achieves quadratic speedup, resulting in a sublinear running time and significantly outperforming the current best classical algorithms.