Global Technology Applied Research at JPMorganChase and CNRS, Université Paris Cité have established a definitive link between computational limits and convex optimisation; their work resolves questions posed by Chakrabarti et al. and van Apeldoorn et al. regarding the efficiency of algorithms accessing data through membership oracles. This research demonstrates that determining an exactly feasible point with specific accuracy requires a near-linear number of queries to assess whether points lie within defined boundaries. Researchers have established precise computational limits for quantum computers tackling convex optimisation; this involves finding the best solution within a complex, multidimensional shape known as an ellipsoid.

This work resolves questions surrounding how many calculations are fundamentally needed to achieve accurate results with these algorithms. By defining these boundaries, scientists can better assess and design future quantum systems intended for similar tasks involving intricate data sets accessed via membership oracles, tools verifying if points lie inside defined areas. The researchers and CNRS, Université Paris Cité have pinpointed fundamental computational limits for solving convex optimisation problems on quantum computers; these complex calculations involve finding optimal solutions within shapes called ellipsoids in multiple dimensions.

To understand this work, consider a ‘yes/no’ gatekeeper, the membership oracle, which confirms whether a proposed solution meets the required conditions of the problem. The team demonstrated that achieving accurate results requires a number of computations scaling almost linearly with the dimensionality of the data being analysed; specifically, an exactly feasible point with additive objective error Θ(n−2) requires Ω n log n log log n membership queries..

This resolves longstanding questions regarding algorithm efficiency and provides tighter bounds on query complexity, like measuring how many questions you need to ask to find something, paving the way for better quantum system design but also raising concerns about inherent limitations in tackling these intricate problems.

Decomposing Polynomial Complexity via Fourier Analytic Techniques

Fourier-rank analysis proved central to unlocking this result; it’s akin to decomposing a complex sound wave into its constituent frequencies but applied here to polynomial functions defining the optimisation problem. The technique meticulously analysed how these polynomials interact with the underlying ellipsoid, revealing inherent limitations in representing them efficiently as simpler components. By carefully constructing specific polynomial arrangements and examining their ‘decomposition complexity’, researchers established a baseline difficulty for any algorithm attempting to solve the convex optimisation task.

This approach bypassed traditional methods reliant on explicit data access, instead focusing on the fundamental structure of the mathematical function itself and quantifying its intrinsic computational cost. A near-linear quantum query lower bound concerning high-accuracy convex optimisation over explicitly defined n-dimensional ellipsoids was established through analysis of linear optimisation with a known objective function; feasible sets were accessed via a ‘membership oracle’ which confirms if a point lies within the set. Any algorithm achieving an additive error of approximately one divided by n² requires at least proportional to n/(log n · log log n) membership queries.

Quantum optimisation achieves near-linear complexity for ellipsoid convexification

A longstanding barrier in quantum optimisation has been surpassed, resulting in a near-linear quantum query complexity of Ω\.(n/(log nlog log n)). This represents an improvement on previous algorithms requiring approximately √n queries for high-accuracy convex optimisation over explicit n-dimensional ellipsoids. Crossing this threshold signifies scaling from sublinear to nearly linear with dimensionality; previously unattainable limitations existed in representing complex mathematical functions efficiently and accurately within the constraints of quantum computation.

New findings indicate that determining if a point lies within a complex, n-dimensional shape, specifically an ellipsoid, requires at least Ω\.(n/(log nlog log n)) calculations using a quantum computer. This bound extends prior knowledge by demonstrating performance scaling much closer to linear with increasing dimensionality than previous limits established when achieving high accuracy assessing membership of such shapes. Furthermore, computing the determinant of a real n × n matrix necessitates a minimum of n/2 queries involving multiplying matrices and vectors; estimating its smallest eigenvalue demands Ω(n) phase queries for acceptable precision.

Quantum limits to solving shaped convex optimisation problems

The relentless pursuit of efficient optimisation algorithms underpins progress across diverse fields like machine learning and financial modelling; however, genuinely scalable solutions remain elusive despite advances in quantum computing. This research clarifies fundamental boundaries within convex optimisation by demonstrating how efficiently problems involving complex shapes can be solved using quantum computation. Establishing firm lower bounds on computational complexity remains valuable work even though the study relies on explicitly defined problem instances which presents a significant hurdle for real world applications.

The researchers and JPMorganChase have defined these fundamental computational limits for solving convex optimisation problems on quantum computers, finding optimal solutions within multidimensional ellipsoids. Their findings establish that achieving specific accuracy requires approximately n divided by the logarithm of n times the double logarithm of n queries to assess boundaries; this provides important conwhen assessing potential advantages over classical methods. The team’s results offer crucial insight into how many calculations are fundamentally needed to achieve accurate outcomes while optimising complex shapes.

The research demonstrated a lower bound of Ω(n / (log n log log n)) membership queries are required to find feasible points with specified additive error in linear optimization over explicit n-dimensional ellipsoids using quantum computation. This clarifies the inherent computational cost for solving these optimisation problems, indicating performance scaling closer to linearity than previously known at high accuracy levels.

Additionally, the study established that computing determinants of real n × n matrices requires at least n/2 matrix-vector product queries and estimating minimum eigenvalues needs Ω(n) phase queries. These results tightly characterise query complexity alongside existing upper bounds within this field.

👉 More information
🗞 Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
✍️ Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana, Dylan Herman, Junhyung Lyle Kim, Guneykan Ozgul and Nadezhda Voronova
🧠 ArXiv: https://arxiv.org/abs/2609.09035

More like this