# Quantum Speedups for Approximating the John Ellipsoid

arXiv: https://arxiv.org/abs/2408.14018 · HTML: https://mlsanity.com/paper/2408.14018/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Aug 2024.

## Built on by (most cited first, 6 of 6)

- [High-Order Matching for One-Step Shortcut Diffusion Models](https://mlsanity.com/paper/2502.00688/) (2025)
- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers](https://mlsanity.com/paper/2501.10688/) (2025)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)
- [On Quantum Perceptron Learning via Quantum Search](https://mlsanity.com/paper/2503.17308/) (2025)
- [Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model](https://mlsanity.com/paper/2606.20082/) (2026)

## Abstract (arXiv)

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 ∈ ℝn × d with a time complexity of O(nd2). 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(√nd1.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.