Li and Colleagues Develop Quantum Algorithm for Ε-Stationary Point Finding

Researchers at Peking University and Stanford University, led by Helin Wang, have developed a new method for identifying stationary points of non-convex functions utilising only comparison-based feedback. The method addresses a fundamental challenge in optimisation, where traditional gradient-based approaches are often impractical due to restricted access to objective function values. The algorithm achieves an approximate query complexity of widetilde O(n²/ε^1.5) to locate an $ε$-stationary point for twice differentiable functions possessing a Lipschitz gradient and Hessian. Furthermore, the team presents the first quantum algorithm designed for this specific task, demonstrating a speedup with widetilde O(n/ε^1.5) queries and opening avenues for efficient optimisation within a quantum computing framework.

Quantum optimisation algorithm achieves exponential speedup in function evaluation complexity

A substantial advancement in optimisation algorithms has been realised, significantly reducing the number of function evaluations needed to identify a suitable stationary point. The new quantum approach lowers the query requirement from approximately widetilde O(n²/ε^1.5) to widetilde O(n/ε^1.5). Previous methods constrained the use of comparison-based feedback, preventing the direct utilisation of gradient information, but this novel quantum algorithm unlocks efficiency gains with implications for areas such as tensor decomposition and matrix completion. This breakthrough represents a threshold where quantum computation offers a demonstrable practical advantage over classical methods for specific optimisation tasks, potentially enabling solutions to previously intractable problems. The core of the algorithm relies on a subroutine designed to accurately estimate the normalised Hessian, a matrix comprising second-order partial derivatives that describe the local curvature of the function. The algorithm achieves this estimation using approximately widetilde O(n²log(1/δ)) queries, where δ represents the desired accuracy of the Hessian approximation. Consequently, the overall query complexity of widetilde O(n/ε^1.5) is achieved, representing a substantial improvement over classical approaches and highlighting potential benefits for applications in tensor decomposition, a technique used to break down complex data into simpler components, and matrix completion, a process used to estimate missing entries in a matrix. The logarithmic factor in the Hessian estimation, $log(1/δ)$, indicates that increasing the desired accuracy of the Hessian estimate incurs a logarithmic cost in the number of queries. This is typical in estimation problems where higher precision requires more samples or evaluations.

Establishing quantum optimisation baselines with limited function knowledge

A central challenge within the field of optimisation, namely finding acceptable solutions when only limited information about the function is available, is now being actively addressed. Instead of demanding detailed knowledge of a function’s gradients or curvature, the algorithms presented rely on a ‘comparison oracle’. This oracle functions by determining which of two input points yields a higher function value, providing a relative assessment without revealing the absolute value. This approach is particularly valuable in scenarios where direct function evaluation is costly or impossible. This work establishes a crucial baseline for optimisation in challenging scenarios where only limited function information is accessible, although current algorithms restrict their operation to functions exhibiting both a Lipschitz gradient and a Lipschitz Hessian. A Lipschitz gradient implies that the rate of change of the function is bounded, preventing excessively steep gradients, while a Lipschitz Hessian implies a similar bound on the rate of change of the gradient, ensuring a degree of smoothness in the function’s curvature.

Many real-world optimisation problems do not satisfy the stringent conditions of possessing both a Lipschitz gradient and a Lipschitz Hessian, representing a significant limitation of the current methodology. Functions lacking these properties can exhibit unbounded gradients or abrupt changes in curvature, rendering the algorithms less effective. However, a novel technique has been devised for pinpointing stationary points within complex functions, relying solely on comparisons of their values instead of direct gradient measurements. This approach estimates a function’s curvature, representing its steepness and shape, to locate $ε$-stationary points, which are points where the gradient is sufficiently small, indicating a local minimum, maximum, or saddle point, and are key to solving optimisation problems. The development of this technique broadens the scope of applicable algorithms by enabling the exploration of optimisation problems where direct gradient information is unavailable. The concept of an $ε$-stationary point allows for a degree of tolerance, recognising that finding a true stationary point with perfect precision is often computationally prohibitive. Future research will concentrate on extending the method to functions that do not adhere to the Lipschitz gradient and Hessian constraints, potentially through adaptive techniques that dynamically adjust the algorithm’s parameters based on the observed function behaviour, or alternative curvature estimation methods that do not rely on these assumptions. Investigating the robustness of the algorithm to noise and imperfections in the comparison oracle is also an important area for future work, as real-world oracles are rarely perfect. Furthermore, exploring the potential for parallelisation and distributed computation could further enhance the algorithm’s scalability and performance on large-scale optimisation problems.

The researchers developed an algorithm to find approximate stationary points within functions using only comparisons of values, requiring a number of queries scaling with n²/ε^1.5 for classical computation. This matters because it allows optimisation of more complex functions where direct gradient measurements are unavailable or impractical. Furthermore, a quantum algorithm was also created which achieves the same result with significantly fewer queries, scaling with n/ε^1.5. The authors intend to extend this method to functions without strict smoothness constraints and improve its resilience to imperfect data.