Quantum Advantage in Testing (Local) Convexity and Monotonicity of Function
Nhat A. Nghiem · 2025
Read Quantum Advantage in Testing (Local) Convexity and Monotonicity of Function by Nhat A. Nghiem (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-18696.txt.
Introduction
Nghiem shows that a quantum computer can test whether a function is convex, or monotonic, exponentially faster than any classical machine. The work appeared in twenty twenty-five. Such shape tests sit inside optimization routines everywhere, so a speedup there is more than a curiosity. One more proven quantum edge joins the list of function problems where quantum methods pull far ahead.
Catalog record
| CREATOR | Nhat A. Nghiem |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-18696
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum Advantage in Testing (Local) Convexity and Monotonicity of Function Nhat A. Nghiem Abstract It is shown that a quantum computer can test the convexity and monotonicity of a given function exponentially more efficiently than a classical computer. This establishes another prominent example that showcases the potential of quantum computers in function-related problems, which can be practical in functional optimization. I Introduction Quantum computers hold great promise for solving problems that lie beyond the reach of classical computers. The intrinsic properties of quantum physics, such as entanglement and superposition, allow information to be stored and processed in a different manner, enabling advantage in solving certain computational problems. Numerous examples have been found, including quantum search algorithm [ 1 ] , factorization algorithm [ 2 , 3 ] , computing black-box [ 4 , 5 ] , simulation algorithm [ 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 ] , linear equation solver [ 23 , 24 , 25 , 26 , 27 ] , topological data analysis [ 28 , 29 , 30 , 31 ] , quantum machine learning algorithms [ 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 ] , etc. Despite significant progress and there are certainly many more algorithms to be discovered, there is a major roadblock to the practical realization of quantum advantage. Many algorithms above, for example, quantum linear solver [ 23 , 24 ] , quantum supervised learning [ 32 ] , quantum principal component analysis [ 33 ] , quantum data fitting [ 34 ] , assume a black-box/oracle in which a quantum computer can access classical data coherently. Quantum random access memory (QRAM) was proposed to realize this oracle [ 41 , 42 ] , however, large-scale QRAM is still far away, thus deferring near-term realization of many quantum algorithms. More severely, in a series of seminal works [ 43 , 44 , 45 ] , it was even shown that quantum advantage primarily comes from the black-box/oracle assumption. With an analogous assumption, a classical computer can tackle corresponding problems with at most polynomial slowdown, thus resisting many claimed exponential quantum speedups. Thereby, these results have raised an important question concerning whether a quantum computer can be advantageous without resorting to strong input assumptions. A few examples have been found with provable theoretical advantage. Bravyi et al. [ 46 ] proved that the constant depth circuit can solve the problem involving binary quadratic form, whereas the classical circuit requires logarithmical depth. This advantage is maintained even in the presence of noise [ 47 ] . Maslov et al. [ 48 ] showed that quantum scratch space is stronger than its classical counterpart. In [ 49 ] , the authors introduced a quantum generative model and rigorously proved that it is stronger than the classical model. Liu et al. [ 50 ] constructed a supervised learning problem where the quantum classifier is provably more efficient than the classical classifier. Recently, it has been shown in [ 51 ] that it is possible to execute quantum gradient descent, which was first proposed in [ 52 ] , without oracle/black-box access. The idea and technique outlined in [ 51 ] have been carried out further in [ 53 , 54 ] , where the author showed that a wide range of problems, such as solving linear systems, nonlinear systems, constructing support vector machines and performing data fitting can also be efficiently handled by quantum algorithms without the need of oracle / black-box access. x y Key motivation: How does the function look like in shaded region? Quantum computer can test sign of first, second derivative, at chose points in parallel and dissect the local shape, achieving exponential enhancement compared to classical counterpart Figure 1 : A plot of y=2x^{5}-6x^{3}+4x and y=x^{3}-2x+1 . These two functions exhibit complicated landscape across the whole x-y domain. However, one may be interested in its local behavior, for example, its “shape” inside the shaded region as indicated above. Apparently from the plot, one can see that the function y=x^{3}-2x+1 (with red color) is convex inside this region, and the blue colored function is monotonically decreasing. In this work, motivated by the aforementioned line of research, we explore how quantum computers perform in function-related problems. Specifically, we focus on two key aspects: convexity and monotonicity, which characterize the “shape” of the given function within a certain domain (see Figure 1 for illustration). To examine convexity, we develop three quantum algorithms based on the first derivative test, the second derivative test, and Jensen’s inequality. Broadly speaking, the first derivative test leverages the fact that the first-order derivative (if it exists) of a (locally) convex function is nondecreasing within corresponding domain. The second derivative test relies on the sign of the second-order derivative (if it exists), which should hold positive for a convex function. Both approaches, however, apply only to univariate polynomials. For multivariate polynomials, a more general method involves Jensen’s inequality, which assesses the function’s values at multiple points to determine whether they satisfy a specific inequality. We demonstrate that the ability of quantum computers to store and process classical information (data points) using logarithmic resources, combined with recent advances in quantum computation [ 55 , 56 , 57 ] , enables us to analyze the behavior of first- and second-order derivatives in (poly)logarithmic time. As a result, we reveal convexity efficiently, achieving an exponential speedup compared to classical algorithms. Similarly, the third approach, based on Jensen’s inequality, examines the function’s behavior across multiple points. The ability of quantum computers to process these points simultaneously facilitates testing whether Jensen’s inequality holds, thereby confirming convexity. Furthermore, the techniques we develop for convexity testing can be naturally extended to monotonicity testing with only minor modifications, leading to an exponential speedup in this setting as well. We point out that a quantum algorithm for convexity testing has recently appeared in [ 58 ] . However, their method requires an oracle/black-box assumption and is only applicable to some specific types of polynomial. As we pointed out before, this assumption is not completely justified and, as we will see subsequently, our method can work for a broader range of polynomials. Before outlining our proposal in detail, we remark that many of the important recipes that appear in our subsequent discussion are provided in the Appendix A . Thus, we strongly encourage the readers to take a look at these preliminaries and then return to the main text. II Testing convexity of univariate polynomial Consider a univariate polynomial f(x):\mathbb{R}\longrightarrow\mathbb{R} and examine the shape of such a function in some domain \mathcal{D} . We note that by trivially redefining the function, it is always possible to choose \mathscr{D}=[-\frac{1}{2},\frac{1}{2}] , therefore, through the remaining, we work with this domain for simplicity. Without loss of generalization, assume that |f(\textbf{x})|\leq\frac{1}{2} for all x\in\mathscr{D} , and also |\frac{\partial f(x)}{\partial x}|\leq\mathcal{P} , |\frac{\partial^{2}f(x)}{\partial^{2}x}|\leq\mathcal{Q} . For the purpose of testing, we choose n points x_{1},x_{2},...,x_{n}\in\mathscr{D} . Define n -dimensional vector \textbf{x}=(x_{1},x_{2},...,x_{n})^{T} . For a purpose that would be clear later,