Extrapolation method to optimize linear-ramp quantum approximate optimization algorithm parameters: Evaluation of runtime scaling Vanessa Dehn, Martin Zaefferer, Gerhard Hellstern, Karthik Jayadevan, Florentin Reiter, Thomas Wellens Abstract The Quantum Approximate Optimization Algorithm (QAOA) has been suggested as a promising candidate for the solution of combinatorial optimization problems. Yet, whether - or under what conditions - it may offer an advantage compared to classical algorithms remains to be proven. Using the standard variational form of QAOA requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which constitutes a bottleneck for achieving a potential scaling advantage. The linear-ramp QAOA (LR-QAOA) has been proposed to address this issue, as it relies on only two parameters which have to be optimized. Based on this, we develop a method to estimate suitable values for those parameters through extrapolation, starting from smaller problem sizes (number of qubits) towards larger problem sizes. We apply this method to several use cases such as portfolio optimization, feature selection, clustering and weighted maxcut. From results obtained on a noiseless quantum emulator, we evaluate the quantum runtime scaling for finding the optimal solution and compare it with that of classical methods. In the case of portfolio optimization, we demonstrate superior scaling compared to the classical runtime for the problem sizes of up to 28 28 qubits that we consider in this work. I Introduction The quantum approximate optimization algorithm (QAOA) is a widely studied and promising algorithm for the solution of combinatorial optimization problems [ 12 , 11 , 16 , 1 ] , potentially more efficient than classical algorithms in terms of faster runtimes (time to find the optimal solution) or finding solutions of higher quality [ 33 , 38 , 13 ] . However, the standard variational QAOA ansatz, where the variational parameters of the quantum circuits are optimized in connection with a classical optimization routine, is not expected to lead to such a possible runtime advantage. This can be understood from the complexity of optimizing these parameters as follows: the quantum circuit consists of 2p circuit parameters (\vec{\gamma},\vec{\beta})=(\gamma_{1},...,\gamma_{p},\beta_{1},...,\beta_{p}) that, in standard QAOA, all need to be optimized for a sufficiently large depth p . This requires a high number of circuit evaluations. Additionally, each evaluation itself contains a substantial number of shots (typically around 1000 shots or more), to precisely determine the expectation value of the cost function, which is minimized by the variational algorithm. Furthermore, when using the variational ansatz, the classical optimizer can get stuck in local minima when optimizing \vec{\gamma} and \vec{\beta} [ 21 , 37 ] , especially without a good initial guess. Therefore, fixed schedules, i.e., structured and predefined approaches for selecting circuit parameters, are of interest to circumvent expensive optimization routines [ 38 , 37 , 4 ] . It has been observed that the optimal parameters (\vec{\gamma}^{*},\vec{\beta}^{*}) exhibit patterns, namely that \gamma_{j}^{*} increases smoothly while \beta_{j}^{*} shows a decreasing behavior (with j=1,...,p ) [ 40 ] . These patterns are consistent with QAOA being interpreted as realizing a discrete adiabatic schedule with gradually changing unitaries [ 21 ] . Based on these patterns, schedules can be formulated by which circuit parameters (\vec{\gamma},\vec{\beta}) are determined for, in principle, arbitrarily high depth p . Examples for such patterns are the Fourier heuristic strategy [ 40 ] , Trotterized quantum annealing (TQA) [ 30 ] or the linear-ramp schedule [ 21 , 20 , 32 , 34 ] , among others [ 24 , 7 ] . Sometimes (e.g., in [ 40 , 30 ] ), such schedules are used in order to provide initial parameters, which are then further optimized according to standard QAOA. Other works [ 21 , 20 , 32 , 34 ] propose to use these schedules as fixed schedules, thus saving the enormous overhead involved in further optimizing a large number of circuit parameters, as explained above. Indeed, a recent study claims that fixed linear-ramp schedules provide a runtime scaling advantage for some combinatorial optimization problems (in particular for a fully connected, randomly weighted MaxCut problem) [ 25 ] . Apart from the QAOA depth p , the linear-ramp schedule exhibits only two free parameters \Delta_{\gamma} and \Delta_{\beta} (see Sec. IV.1 below). The authors of Ref. [ 25 ] suggest that the parameter optimization needs to be performed only for one single problem instance of given size N , and then the same parameters can be used also for other instances of the same size. Nevertheless, finding the optimal parameters even for a single problem instances at large N constitutes a considerable effort. The question remains how suitable values of the parameters \Delta_{\gamma},\Delta_{\beta} and p can be found in an efficient and scalable way. In our work, we address this question by proposing an extrapolation scheme whereby circuit parameters for larger problem sizes (in our case up to N=28 ) can be determined on the basis of optimizations performed only on subproblems of smaller size ( N=4,6,8,10 ). With these parameters, we present the scaling of the quantum runtime for four combinatorial optimization problems: Portfolio Optimization, Feature Selection, Clustering and weighted MaxCut. The runtime is expressed as the median of the total depth of all quantum circuits that have to be executed to find the optimal solution. After comparing the scaling of the quantum runtime with the classical runtime, we find indication of a quantum scaling advantage in the case of Portfolio Optimization. Apart from the article [ 25 ] mentioned above, similar scaling advantages have recently been found also for Boolean satisfiability problems [ 3 ] and the low autocorrelation binary sequences (LABS) problem [ 35 ] . In both cases, fixed parameter schedules (though not as simple as linear-ramp) are considered, and the scaling of the QAOA runtime (combined with quantum minimum finding in [ 35 ] ) is analyzed at fixed QAOA depth p . In our work, we propose to adapt, both, the depth p and also the circuit parameters (\vec{\gamma},\vec{\beta}) with increasing problem size N . We therefore think it is possible that the QAOA runtime scalings obtained in the above mentioned works can be further improved when combining them with ideas presented in this article. This paper is divided into two main parts, a classical optimization and a quantum optimization part, and is organized as follows: in Sec. II , we give a brief introduction to the combinatorial optimization problems considered in this paper, which are then addressed in Sec. III by purely classical methods. This section provides the investigation as well as the discussion of the scaling behavior of different classical optimization methods (CPLEX, Gurobi, MQLib/Burer2002 Heuristic and Goemans-Williamson algorithm), which is evaluated by the time to find the optimal solution (runtime) as a function of the number of variables (bits). Sec. IV gives an introduction to the linear-ramp QAOA schedule and an explanation of our method to derive suitable QAOA parameters based on extrapolation from smaller towards larger number of qubits. The results are then discussed in Sec. V and we finally conclude in Sec. VI . II Combinatorial Optimization Problems In this section, we introduce four optimization problems that we all formulate as a QUBO [ 14 ] problem with the following structure: F(\mathbf{z})=\sum_{i,j}^{N}F_{ij}z_{i}z_{j}+\sum_{i}^{N}f_{i}z_{i} (1) with symmetric matrix F , vector f , number of bits N and binary variables z_{1},...,z_{N} . Taking into account that z_{i}z_{i}=z_{i} (for binary variables z_{i}\in\{0,1\} ) the linear term can be included in the quadratic term, leading to F(\mathbf{z})=\sum_{i,j}^{N}Q_{ij}z_{i}z_{j} (2) where Q_{ij}=F_{ij}+f_{i}\delta_{ij} is a symmetric matrix defining the problem under consideration. Before discussing different combinatorial optimization problems, we want to stress that these examples are simplified compared to real-world problems in business and industry. While it would be possible to make them more realistic, it will be seen in the following that they nevertheless obtain generic features. II.1 Formulation of the Portfolio Problem The portfolio optimization problem is one of the most famous and investigated topics in finance after Markowitz published his seminal paper [ 23 ] . It addresses the question how to build a portfolio with different financial assets in order to maximize the return and to minimize the risk when the relation between these two properties is fixed. Whereas in banks and asset management firms a lot of subtleties have to been considered (e.g. use of sophisticated risk measures as Value-at-Risk, allowing for short-selling, use of integer asset fractions, transaction costs etc.), a generic formulation is obtained within the following framework: Use the historic return as a measure of the expected return, use the covariance of the asset returns as risk measure and restrict yourself to binary portfolio fractions. Using this together with the aforementioned QUBO function, see Eq. ( 1 ), we can directly identify the cost function for the Portfolio optimization problem F_{\text{portfolio}}(\mathbf{z})=q~\sum_{i,j}^{N}z_{i}z_{j}\sigma_{ij}-(1-q)~\sum_{i}^{N}z_{i}\mu_{i} (3) with number of assets N , covariance matrix \sigma_{ij} , expected return vector \mu_{i} , binary portfolio weights z_{i}=0 or 1 of stock i , and a risk preference factor q . A budget constraint B=\sum_{i}z_{i} indicates the investment of a fixed budget, with B being the number of assets chosen for the portfolio from N total assets. A created portfolio is called feasible if the constraint is fulfilled; otherwise we call a portfolio infeasible. The constraint can be added to the cost function as a penalty term with a prefactor A : F_{\text{portfolio}}^{(A)}(\mathbf{z})=F_{\text{portfolio}}(\mathbf{z})+A\Bigl(\sum_{i=1}^{N}z_{i}-B\Bigr)^{2}. (4) A suitable candidate for the prefactor A can be computed using the routine described in Ref. [ 5 ] . In continuation of this paper, we use the annualized returns and covariance matrices for the German DAX 30 (as of 1/2/2021) between 01/01/2016 and 31/12/2020. For a given number of assets, different instances of the problem are obtained by randomly selecting N out of the 30 DAX assets. The risk preference factor q is typically set between 0 and 1 and, in contrast to our typical choice of q=1/3 , it is set here to q=1 , indicating the focus on the risk part of the problem irrespective of the return part. Concerning the budget, we choose B=N/2 (for even N ) or B=(N-1)/2 (for odd N ). II.2 Formulation of Feature Selection Problem Similarly, we can formulate the cost function for the feature selection problem in Machine Learning which can be based on two dependency measures: the first describes the dependence \rho_{i,j} between the columns i and j of the feature matrix X , and the second is the dependence \rho_{i,Y} between the feature column i and the target vector Y . Furthermore, we consider a set of binary variables z_{i}\in\{0,1\} for which z_{i}=1 indicates that the column i is selected in the model, while z_{i}=0 refers to the column not being selected in the model. An intuitive approach is to select features such that the inter-feature dependence \sum_{i,j=1}^{N}z_{i}z_{j}|\rho_{i,j}| is minimized and the dependence between feature and target \sum_{i=1}^{N}z_{i}|\rho_{i,Y}| is maximized. The cost function can now be constructed as above by combining both criteria: F_{\text{feature}}(\mathbf{z})=-\Bigl(\phi\sum_{i=1}^{N}z_{i}|\rho_{i,Y}|-(1-\phi)\sum_{\begin{subarray}{c}i,j=1\\ i\neq j\end{subarray}}^{N}z_{i}z_{j}|\rho_{i,j}|\Bigr) (5) with weighting parameter \phi\in[0,1] , that we set to \phi=0.9 . As a dependence measure between the features as well as between features and target we chose to take the linear correlation \rho^{\text{Correl}} as proposed in [ 18 ] . In accordance to this reference, the “German Credit Data” [ 19 ] is used again. It comprises a total of 20 features, encompassing 7 numerical and 13 categorical attributes along with a an imbalanced binary target variable distinguishing non-defaulted cases (700 instances) from defaulted cases (300 instances). After applying one-hot encoding to the categorical features, we end up with a maximum of 48 binary features. II.3 Formulation of Clustering and randomly weighted MaxCut Problem In unsupervised learning, the problem of clustering data is defined as follows: Given a dataset D containing N data points, where each data point is represented as a feature vector x_{i} in a feature space X : D=\{x_{1},x_{2},...,x_{N}\} , the goal of clustering is to partition the dataset into K clusters, where K is a user-specified or algorithmically determined parameter. Each cluster C_{k} is a subset of the dataset D with the following conditions: 1. Completeness: Every data point x_{i} belongs to exactly one cluster C_{k} , and the union of all clusters covers the entire dataset. 2. Homogeneity: Data points within the same cluster are similar to each other, and data points in different clusters are dissimilar. This is typically measured using a distance or similarity metric. 3. Minimization Objective: The clusters are formed in a way that minimizes an objective function. This objective function may vary depending on the specific clustering algorithm being used. Mathematically, the clustering problem can thus be defined as finding a partition of the dataset into K clusters that optimizes an objective function J , where: J=f(D,C_{1},C_{2},...,C_{K}). (6) The objective function J can be chosen based on the specific clustering algorithm’s criteria, such as minimizing intra-cluster distances or maximizing inter-cluster distances. The goal of clustering is to discover meaningful patterns or groupings within the data without any prior knowledge of the class labels. Various clustering algorithms, such as K-means [ 22 ] , hierarchical clustering [ 36 ] , and DBSCAN [ 10 ] , can be used to solve this problem of finding the optimal partition of the dataset into clusters based on different criteria and distance measures. The Euclidean distances for all data pairs x_{i},x_{j} , i.e. w_{ij}=||x_{i}-x_{j}||_{2} (7) can be interpreted as the elements of a symmetric matrix W , where all diagonal elements are zero. This matrix W can now be interpreted as an adjacency matrix of a graph G , where each vertex represents an element of W , and w_{ij} is the weight of the edge between the vertices i and j . In general, the graph is fully connected. The common assumption in clustering – distant points belonging to different clusters – translates in the case of K=2 clusters to the problem of maximizing the overall sum of all weights (distances) between nodes with different labels. Therefore, we come to a Maximum-Cut (MaxCut) problem - MaxCut(G, W) for the dense graph G of the distance matrix W [ 31 , 26 ] . A cut is a set of edges that separates all vertices V into two disjoint sets S and \bar{S} with S\cup\bar{S}=V . The cost of a cut is given by the sum of all weights of edges connecting vertices in S with vertices in \bar{S} . With the introduction of binary variables z_{i}\in\{0,1\},i=1,...,N which denote whether x_{i} belongs to S or \bar{S} , the sum of all cuts can be expressed as the cost function F_{\text{clustering}}(\mathbf{z})=\sum_{i,j=1}^{N}w_{ij}(z_{i}+z_{j}-2\cdot z_{i}z_{j}). (8) Again, we end up with a QUBO problem. Here, we decided to use the “Moons” and “Blobs” datasets of Scikit-Learn [ 27 ] with two features, i.e., x\in\mathbb{R}^{2} . Each data point then induces one binary decision variable. Using Moons and Blobs have the advantage that the clustering results can be either checked by e.g. the K-Means algorithm or visually. In addition to the MaxCut problem, that arises from the clustering problem formulation, we also consider MaxCut problems where the weights w_{ij} of the edges are randomly drawn from a uniform discrete distribution between 0 and 1000 in steps of 1. In Appendix C we show the distribution of non-diagonal and diagonal QUBO-matrix elements of the different optimization problems. III Classical optimization Figure 1: Portfolio optimization: Runtime T (seconds) obtained with CPLEX, Gurobi, Goemans-Williamson and MQLib/Burer2002, as a function of the number N of variables (bits). The dots represent the results for the ten problem instances, with blue indicating it was optimally solved, while orange indicates a non-optimal solution. The slope \alpha of a robust log2-linear model, i.e., T\propto 2^{\alpha N} (red dashed line) is denoted in the header of each figure. Figure 2: Feature Selection: Runtime T (seconds) obtained with CPLEX, Gurobi, Goemans-Williamson and MQLib/Burer2002, as a function of the number N of variables (bits). The dots represent the results for the ten problem instances, with blue indicating it was optimally solved, while orange indicates a non-optimal solution. The slope \alpha of a robust log2-linear model, i.e., T\propto 2^{\alpha N} (red dashed line) is denoted in the header of each figure. Figure 3: Clustering (Moons): Runtime T (seconds) obtained with CPLEX, Gurobi, Goemans-Williamson and MQLib/Burer2002, as a function of the number N of variables (bits). The dots represent the results for the ten problem instances, with blue indicating it was optimally solved, while orange indicates a non-optimal solution. The slope \alpha of a robust log2-linear model, i.e., T\propto 2^{\alpha N} (red dashed line) is denoted in the header of each figure. Figure 4: MaxCut: Runtime T (seconds) obtained with CPLEX, Gurobi, Goemans-Williamson and MQLib/Burer2002, as a function of the number N of variables (bits). The dots represent the results of individual algorithm runs on one instance, with blue indicating it was optimally solved, while orange indicates a non-optimal solution. The slope \alpha of a robust log2-linear model, i.e., T\propto 2^{\alpha N} (red dashed line) is denoted in the header of each figure. To solve the optimization problems introduced above, we use the following methods/software solutions: • CPLEX [ 6 ] • Gurobi [ 17 ] • MQLib/Burer2002 Heuristic [ 9 ] • Goemans-Williamson’s algorithm [ 15 ] Apart from MQLib/Burer2002, these classical optimization methods are all available in IBM’s Qiskit [ 28 ] for solving QUBOs with a uniform function call. Due to the large number of all possible solutions ( 2^{N} ), a brute-force approach is infeasible for large N . Note that Goemans-Williamson’s is an approximative algorithm, it does not guarantee to find the global optimum. In the literature, also more physics-inspired optimization methods are described, such as the parallel-tempering with isoenergetic cluster moves approach, see [ 41 ] . We refrained from implementing these approaches because our aim was primarily to use industry established and ready-to-use optimization frameworks for our work. Strictly speaking, none of the algorithms guarantees to find the global optimum, although at least CPLEX and Gurobi may provide additional information about the optimality of solutions. That is, they compute upper and lower bounds for the objective function value, which may indicate global optimality if the difference between both bounds is zero. MQLib/Burer2002, finally, does not provide information about the optimality of the solution. It continues trying to find better solutions until a user-defined maximum runtime is reached. At the end, it returns these solutions together with the times at which they have been found. To investigate the scaling behavior of the different classical optimization methods, we perform the following experiments: 1. Sample I instances with size N randomly from the respective data set/distribution, for each combinatorial optimization problem class. This accounts for variation of the runtime caused by instance characteristics. 2. For each instance, we measure R times how long each algorithm takes to find a solution. The repetition is intended to account for random variations of the runtime. 3. Repeat this for each N\in\{N_{\text{min}},N_{\text{min}}+1,\dots,N_{\text{max}}\} . This accounts for the influence of the problem size. The specific settings considered for each problem class are: • Portfolio Optimization: I=10 , R=20 , N\in\{2,3,\dots,28\} • Feature Selection: I=20 , R=10 , N\in\{2,3,\dots,48\} • Clustering (Moons): I=20 , R=10 , N\in\{2,3,\dots,100\} • Clustering (Blobs): I=20 , R=10 , N\in\{2,3,\dots,100\} • MaxCut: I=10 , R=20 , N\in\{11,12,\dots,29\} In the following, we show the runtime measured during execution as function of the number N of variables and the slope of the fit through the data. The slope is an estimator of the scaling factor which depends on the data set and on the algorithm. In Fig. 1 the results for the Portfolio Optimization problem are shown. The absolute values for the runtime differ strongly between the four classical optimization schemes. On the one hand, Gurobi shows the longest absolute runtimes as well as the highest scaling factor. On the other hand, CPLEX shows the lowest scaling factor and MQLib/Burer2002 the shortest absolute runtime. A similar behavior can be observed for the Feature Selection problem, see Fig. 2 . Again, CPLEX has the lowest scaling factor, MQLib/Burer2002 the shortest absolute runtimes, and Goemans-Williamson’s algorithm does not find the optimal solution in most cases. However, MQLib/Burer2002 now has the highest scaling factor, and GW/CPLEX the longest absolute runtimes. In Fig. 3 the Clustering results for the Moons dataset are shown. Interestingly, GW mostly finds the optimal solutions for this problem class, and Gurobi now has the lowest scaling factor, albeit also showing a strong discontinuity of runtimes at about N=45 . Similarly, but less pronounced, CPLEX also displays jumps of the runtime, e.g., around N=90 . GW has the largest scaling factor in this case. MQLib/Burer2002 has a marginally lower scaling factor than CPLEX, and is again the algorithm with lowest absolute runtimes. The results for the Blobs dataset are depicted in Fig. 13 which can be found in the Appendix A . In this case, CPLEX has the lowest \alpha , closely followed by Gurobi and MQLib/Burer2002 (with lowest absolute runtimes). Besides some instances with very small N , CPLEX does not show the discontinuities displayed on the Moons data while Gurobi has the same jump at about N=45 , in addition to jumps at lower values of N . Compared to the other problem classes, the MaxCut instances seem to exhibit the least number of discontinuities, as shown in Fig. 4 . GW only finds the optimal solution in some cases. In terms of our scaling estimates \alpha of the other three algorithms, CPLEX performs best, followed by MQLib/Burer2002, while Gurobi has the largest scaling factor. In terms of absolute values, MQLib/Burer2002 has again the lowest absolute runtimes. For each problem instance, we also performed separate runs with CPLEX (focusing on optimality), to confirm whether we find globally optimal reference solutions in each case. CPLEX provides an upper bound of the gap to the global optimum, which can become zero, in which case the corresponding reference solution that was found is provably a global optimum. Overall, this gives us only a small number of instances for which we have no proof that the best solution we found is globally optimal: • Portfolio Optimization: 1 of 270 instances • Feature Selection: 18 of 940 instances • Clustering (Moons): 2 of 1980 instances • Clustering (Blobs): 4 of 1980 instances • MaxCut: 0 of 190 instances Moreover, in all cases, the relative gap between the best-found solution and the lower bound of the objective function value is smaller than 10^{-6} . Note, that in the figures 1 - 3 , blue dots mark a run as solved even if we have no proof that the solution is a global optimum. Orange dots imply that the algorithm found a solution that is worse than the reference we determined. In summary, it can be concluded that the various classical optimization methods exhibit different scaling behaviors on the investigated combinatorial optimization problems. For the subsequent comparison with quantum algorithms, we will utilize the MQLib/Burer2002 algorithm for the following reasons: The Goemans-Williamson’s algorithm is unsuitable for the comparison because it frequently does not find the optimum. The commercial optimization algorithms CPLEX and Gurobi are problematic because their search approach may change unexpectedly depending on various criteria, as is also evidenced by the jumps and discontinuities of their runtime graphs, making it very hard to model their behavior. Moreover, the runtimes of CPLEX and Gurobi also include the efforts required for collecting additional information such as optimality bounds, which neither MQLib/Burer2002 nor the quantum algorithm discussed below do provide. Especially for small problem sizes, the runtimes of CPLEX (of the order of 10^{-1} s) exhibit a considerable overhead compared to MQLib/Burer2002 (about 10^{-5} or 10^{-4} s). For these reason, we argue that only the MQLib/Burer2002 algorithm reliably reflects the actual algorithmic complexity for finding the optimal solution and therefore appears to be the most suitable for comparison with the quantum algorithm. IV Quantum optimization IV.1 Linear-ramp QAOA When using QAOA to solve the above introduced optimization problems on a quantum computer, the following parameterized quantum state is generated: \ket{\psi_{\vec{\gamma},\vec{\beta}}}=\hat{U}_{M}(\beta_{p})\hat{U}_{F}(\gamma_{p})...\hat{U}_{M}(\beta_{1})\hat{U}_{F}(\gamma_{1})\ket{\psi_{0}}_{M} (9) with circuit parameters \vec{\gamma}=(\gamma_{1},...,\gamma_{p}) and \vec{\beta}=(\beta_{1},...,\beta_{p}) , mixer unitary \hat{U}_{M}(\beta_{j})=e^{-i\beta_{j}\hat{M}} with transverse-field mixer \hat{M}=-\sum_{i=1}^{n}\hat{X}_{i} , and cost unitary \hat{U}_{F}(\gamma_{j})=e^{-i\gamma_{j}\hat{F}} with cost Hamiltonian \hat{F} (defined by \hat{F}|\mathbf{z}\rangle=F(\mathbf{z})|\mathbf{z}\rangle for basis states |\mathbf{z}\rangle ). The initial state \ket{\psi_{0}}_{M} corresponds to the mixer Hamiltonian \hat{M} , or more precisely, it is its eigenstate associated with its smallest eigenvalue. Hence, the state is the equal superposition state \ket{\psi_{0}}=\ket{+}^{\otimes N} for this choice of \hat{M} . Finally, the probability of measuring the optimal solution \mathbf{z_{\rm opt}} is obtained as: P_{\text{opt}}=\left|\langle\mathbf{z_{\rm opt}}|\psi_{\vec{\gamma},\vec{\beta}}\rangle\right|^{2} (10) In contrast to standard QAOA, where suitable values for the circuit parameters are suggested through a classical optimization routine, we sample them directly from the ansatz \displaystyle\gamma_{j} \displaystyle= \displaystyle\Delta_{\gamma}x_{j} (11) \displaystyle\beta_{j} \displaystyle= \displaystyle\Delta_{\beta}(1-x_{j}) (12) with x_{j}=\frac{j-\frac{1}{2}}{p},\ \ j=1,2,\dots,p, (13) where the parameters \Delta_{\gamma},\Delta_{\beta} are left to be optimized. Additionally, we find optimized values for p , with the procedure outlined in more detail in Sec. IV.2.4 . Those three parameters characterize the linear-ramp schedule which is illustrated in Fig. 5 . Figure 5: Linear-Ramp protocol according to Eqs. ( 11 - 13 ) (illustrated here for p=10 ). Intuitively, the above linear-ramp schedule can be motivated by the quantum adiabatic theorem [ 2 ] , where the known ground state of \hat{M} is transformed to the desired ground state of \hat{F} . Indeed, the above QAOA circuit, Eq. ( 9 ) reproduces the continuous adiabatic evolution in the limit \Delta_{\gamma},\Delta_{\beta}\to 0 and \Delta_{\gamma}p,\Delta_{\beta}p\to\infty . As it turns out, however, the continuous limit is not necessary in order to prove convergence to the ground state (i.e. P_{\rm opt}\to 1 ) in the limit p\to\infty : according to the discrete adiabatic theorem [ 8 ] , this convergence is also guaranteed for finite \Delta_{\gamma},\Delta_{\beta}>0 – provided that \Delta_{\gamma},\Delta_{\beta} do not exceed a critical value \Delta_{\rm crit} in order to prevent the eigenvalues of the unitary QAOA operators to ”wrap around” the unit circle in the complex plane [ 20 ] . (In our case, \Delta_{\gamma,{\rm crit}}=2\pi/(F_{\rm max}-F_{\rm min}) and \Delta_{\beta,{\rm crit}}=\pi/N , with F_{\rm min} and F_{\rm max} the smallest and largest eigenvalues of \hat{F} .) From a practical point of view, however, we are rather interested in the behaviour of LR-QAOA at finite p instead of p\to\infty . Even if the limit P_{\rm opt}\to 1 is not reached in this case, the optimal solution can still be found by repeating the circuit several (approximately 1/P_{\rm opt} ) times. In the following, we will quantify the time required to find the optimal solution on a quantum computer in terms of the total depth D , defined as the depth of a single QAOA circuit (which, in turn, is proportional to p ) times the number of circuit repetitions, see Eqs. ( 16 , 17 ) below. IV.2 LR-Extrapolation We follow the idea to discard the variational optimization of the circuit parameters and finding suitable values for \Delta_{\gamma},\Delta_{\beta} and p by extrapolating from smaller to larger problem sizes, corresponding to the number of qubits N . This enables us to make a prediction of the circuit parameters for larger problem sizes, while only the optimization over small problem sizes has to be performed. The method consists of three parts: the first part includes a reduction of the original problem to smaller subproblems, the second part describes the extrapolation, and the third part focuses on the post-processing of the results. IV.2.1 Random Sampling and Grid Search For each QUBO instance of size N\in\{12,...,28\} , we first create random sub-instances of size \tilde{N}\in\{4,6,8,10\} . This is done by randomly selecting \tilde{N} out of the N binary variables and then constructing the QUBO cost functions as described in Sec. II . For Feature Selection and Clustering, this simply amounts to choosing the corresponding sub-matrices of Q_{ij} , see Eq. ( 2 ). For Portfolio Optimization, the dependence of the budget constraint B on the problem size is taken into account (whereas the penalty term A is kept constant), see Eq. ( 4 ). Thereby, 10 random sub-instances are created for each \tilde{N} . In the next step, we use the 10 sampled sub-instances of the smallest size ( \tilde{N}=4 ) and perform a grid search with an initial depth value p_{0}=6 . That is, we construct a grid of \log_{10}(\Delta_{\gamma}) , \log_{10}(\Delta_{\beta}) points, compute the probability of finding the optimal solution P_{\text{opt}} for each instance and determine the average probability \overline{P_{\text{opt}}} (averaged over the 10 sub-instances). For all subproblem sizes, we choose a 11\times 11 grid with \log_{10}(\Delta_{\gamma})_{\text{min}}\leq\log_{10}(\Delta_{\gamma})\leq\log_{10}(\Delta_{\gamma})_{\text{max}} and \log_{10}(\Delta_{\beta})_{\text{min}}\leq\log_{10}(\Delta_{\beta})\leq\log_{10}(\Delta_{\beta})_{\text{max}} . The initial size of the grid (for \tilde{N}=4 ) is chosen as \log_{10}(\Delta_{\gamma})_{\text{max}}-\log_{10}(\Delta_{\gamma})_{\text{min}}=\log_{10}(\Delta_{\beta})_{\text{max}}-\log_{10}(\Delta_{\beta})_{\text{min}}=2 , centered around [\log_{10}(\Delta_{\beta})_{\text{min}}+\log_{10}(\Delta_{\beta})_{\text{max}}]/2=0.5 in case of \log_{10}(\Delta_{\beta}) , whereas the center of the \log_{10}(\Delta_{\gamma}) -grid depends on the particular class of problem instance (due to different scalings of the corresponding QUBO matrices, see Appendix C ). In particular, we choose for [\log_{10}(\Delta_{\gamma})_{\text{min}}+\log_{10}(\Delta_{\gamma})_{\text{max}}]/2 the values 0 for portfolio optimization and clustering, +2 for feature selection, and -2.5 for MaxCut. The logarithmic scale, i.e., considering \log_{10}(\Delta_{\gamma,\beta}) instead of \Delta_{\gamma,\beta} , is used to cover a sufficiently wide range of values. IV.2.2 Multivariate Skew Gaussian Fit and Grid Reduction The above grid search provides a two-dimensional landscape consisting of 11\times 11=121 data points, see Fig. ( 6 ) as an example (for sub-problem size \tilde{N}=10 and depth p=107 ). We can clearly see a dark blue region where the average probability \overline{P_{\text{opt}}} assumes the largest values. It is the center of this region that we are interested in and which we will use for our extrapolation procedure below. In order to determine the position of the center, we fit the discrete 11\times 11 -landscape by a continuous function. Empirically, we found that the following multivariate skew Gaussian function is well suited in order to approximate the \overline{P_{\text{opt}}} -landscape (the detailed structure of which in principle depends on the random choice of sub-instances) by a simple and smooth function: \displaystyle f_{\bm{\mu},\Sigma,\bm{\alpha},A,B}(\textbf{x})=A~\text{exp}\Bigl(-\frac{1}{2}(\textbf{x}-\bm{\mu})^{T}\Sigma^{-1}(\textbf{x}-\bm{\mu})\Bigr) (14) \displaystyle\times\frac{1}{2}\left[1+\text{erf}\left(\bm{\alpha}\cdot\frac{\textbf{x}-\bm{\mu}}{\sqrt{2}}\right)\right]+B where \textbf{x}=\{\log_{10}(\Delta_{\gamma}),\log_{10}(\Delta_{\beta})\} . The fit parameters consist of a two-dimensional vector \bm{\mu} (center of the Gaussian function), a 2\times 2 (inverse) covariance matrix \Sigma^{-1}\geq 0 , a two-dimensional vector \bm{\alpha} characterizing the skewness and two parameters A,B\geq 0 . The maximum of this function is determined numerically and provides us with \{\log_{10}(\Delta_{\gamma,\text{opt}}),\log_{10}(\Delta_{\beta,\text{opt}})\}=\textbf{x}_{\text{opt}} and \left.\overline{P_{\text{opt}}}\right|_{\text{max}}=f_{\bm{\mu},\Sigma,\bm{\alpha},A,B}(\textbf{x}_{\text{opt}}) . Additionally, we extract the widths s_{\gamma}=\sqrt{\Sigma_{1,1}} and s_{\beta}=\sqrt{\Sigma_{2,2}} of the blue region from the diagonal elements of the covariance matrix \Sigma . Figure 6: (a) Portfolio Optimization: 2-dimensional grid search landscape for 10 sub-problems of size \tilde{N}=10 sampled from a problem of size N=28 at depth p=107 . The blue region shows the region with highest average ground state probability \overline{P_{\text{opt}}} . (b) Skewed Gaussian fit f , see Eq. ( 14 ), to the data shown in (a). The optimal values ( \log_{10}(\Delta_{\gamma,\text{opt}}) , \log_{10}(\Delta_{\beta,\text{opt}}) ) are represented by the yellow cross. With these parameters, we set the new coordinates for the grid search of the next-sized subproblem in the following way \displaystyle\log_{10}(\Delta_{\gamma})_{\text{min}}=\log_{10}(\Delta_{\gamma,\text{opt}})-s_{\gamma} (15) \displaystyle\log_{10}(\Delta_{\gamma})_{\text{max}}=\log_{10}(\Delta_{\gamma,\text{opt}})+s_{\gamma} \displaystyle\log_{10}(\Delta_{\beta})_{\text{min}}=\log_{10}(\Delta_{\beta,\text{opt}})-s_{\beta} \displaystyle\log_{10}(\Delta_{\beta})_{\text{min}}=\log_{10}(\Delta_{\beta,\text{opt}})+s_{\beta} which ensures that the optimum of the previous-sized problem is at the center of the following grid. This procedure is then repeated until we reach sub-problem size \tilde{N}=10 . Figure 7: Extrapolation of (a) log( \Delta_{\gamma} ), (b) log( \Delta_{\beta} ) and (c) log( P_{\text{opt}} ) for four instances of the portfolio optimization problem with N=28 assets (triangles, diamonds, circles, squares). The symbols at N=4,6,8,10 indicate the optimized values found for the respective subproblems. The dashed lines represent linear fits (on log-log scale) through these points. Finally, the markers at N=28 display the extrapolated values of these parameters. Each instance is processed at a certain depth: p=128 (triangles), p=215 (diamonds), p=304 (circles), p=608 (squares). IV.2.3 Extrapolation After having found optimized parameters \{\log_{10}(\Delta_{\gamma,\text{opt}}),\log_{10}(\Delta_{\beta,\text{opt}})\} and \left.\overline{P_{\text{opt}}}\right|_{\text{max}} for all sizes \tilde{N}=4,6,8,10 of the sub-instances, we extrapolate these values towards the size N of the original instance. For this purpose, we assume a linear behavior on a log-log scale, i.e., we fit functions y_{i}=a_{i}x+b_{i} to the above data points, where x=\log_{10}(\tilde{N}) , y_{1}=\log_{10}(\Delta_{\gamma,\text{opt}})\} , y_{2}=\log_{10}(\Delta_{\beta,\text{opt}}) and y_{3}=\log_{10}\left(\left.\overline{P_{\text{opt}}}\right|_{\text{max}}\right) . Thereby, we obtain extrapolated values \Delta_{\gamma,\text{extr}} , \Delta_{\beta,\text{extr}} of the linear-ramp circuit parameters together with an estimation P_{\text{opt,extr}} of the probability to measure the optimal solution of our problem instance with size N . In Fig. 7 , this extrapolation procedure is illustrated for four different portfolio optimization instances of size N=28 , each at a certain depth p ( 128 , 215 , 304 and 608 ). Each depth corresponds to the optimal depth for that instance, as determined in Sec. IV.2.4 below. At present, we do not have a theoretical justification for the algebraic scaling with respect to \tilde{N} assumed above (i.e. linear behaviour on log-log scale), but we empirically found that it provides better results than exponential scaling, for example. To check the quality of our extrapolation, we have determined a 20\times 20 grid search landscape for one of the four instances shown in Fig. 7 . Note that this grid search is numerically quite expensive, since it involves simulations of large quantum circuits (with N=28 qubits) – in contrast to the extrapolation procedure based on simulations of small circuits (with \tilde{N}=4,6,8,10 ). As shown in Fig. 8 , the estimated values \Delta_{\gamma,\text{extr}} , \Delta_{\beta,\text{extr}} obtained from the extrapolation agree quite well with the true maximum. This example suggests that the predictions made using the extrapolation method provide a good estimate for the linear-ramp parameters. More data supporting this conclusion (at least for most instances) will be shown in Sec. V . Figure 8: Grid search landscape for one instance (corresponding to triangles in Fig. 7 ) with N=28 qubits and QAOA depth p=128 . The optimal region is visualized by the dark blue region. The optimal (\Delta_{\gamma,\text{extr}},\Delta_{\beta,\text{extr}}) configuration predicted by the extrapolation method, represented by the yellow ‘x’ symbol, is close to the optimal configuration found through grid search. Moreover, the corresponding maximum value of P_{\text{opt}}\simeq 0.055 (see the labels of the color bar on the right-hand side) is of the same order of magnitude as the extrapolated value of P_{\text{opt,extr}}\simeq 0.103 . This indicates that the extrapolation method performs well. IV.2.4 Total depth and optimization of p As described above, the extrapolation procedure provides us with suitable estimates of the linear-ramp circuit parameters \Delta_{\beta,\gamma} and the corresponding probability P_{\text{opt}} of measuring the optimal solution. What remains is to choose an appropriate value of the QAOA depth p . In principle, we may increase P_{\text{opt}} by increasing p , which, however, leads to longer circuits. To find an optimal value of p , we want to minimize the runtime of our quantum algorithm until the optimal solution is found. For this purpose, we concentrate in the following on the depth d of the QAOA quantum circuit. The corresponding time is then given by multiplying the depth with the time of a single quantum gate. Depending on the given quantum hardware, more specific estimates could be obtained, e.g., by taking into account different times of single-qubit and two-qubit gates or times of initial state preparations and final state measurements. We expect, however, that these details will not significantly affect the scaling behavior in the limit of large problem sizes. To determine the total quantum runtime, we therefore multiply the depth d of a single QAOA circuit (which, in turn is roughly proportional to the QAOA depth p ) with the number N_{\text{shots}} of shots required to find the optimal solution: D=dN_{\text{shots}} (16) The median of the latter (defined by the condition that the probability to find the optimal solution after N_{\text{shots}} circuit executions equals 1/2 ) is given by: N_{\text{shots}}=\frac{\text{log}(\frac{1}{2})}{\text{log}(1-P_{\text{opt}})} (17) Alternatively, the expectation value given by 1/P_{\text{shots}} could also be used instead of the median. Figure 9: Scaling of quantum runtime expressed as total depth D , see Eq. ( 16 ), with increasing problem size N (number of qubits) using linear-ramp QAOA with circuit parameters determined from extrapolation individually for each instance. The red dashed lines represent exponential fits with slope \alpha (i.e. D\propto 2^{\alpha N} ) of the geometric means (blue lines) over 10 problem instances per N (transparent blue dots). (a) Portfolio Optimization. Compared to the classical runtime \alpha_{\rm cl}=0.323 , see Fig. 1 (MQLib/Burer2002), the increase of the quantum runtime is slower ( \alpha=0.219 ), thus indicating a potential quantum scaling advantage. For the remaining three cases (b) Feature Selection ( \alpha=0.378 vs. \alpha_{\rm cl}=0.197 ), (c) Clustering (Moons) ( \alpha=0.248 vs. \alpha_{\rm cl}=0.051 ), and (d) MaxCut ( \alpha=0.235 vs. \alpha_{\rm cl}=0.156 ), a scaling advantage compared to the classical runtime is not observed. The yellow diamond shapes represent the optimal values found by a minimizer, starting from the extrapolated parameters as initial point. For better visibility, the diamonds have been slightly shifted along the x-axis. The optimal QAOA depth p_{\text{opt}} can now be derived by minimizing D . More precisely, we minimize the estimated value of D based on the above extrapolation procedure, i.e., we set P_{\text{opt}}=P_{\text{opt,extr}} in Eq. ( 17 ). We consider a logarithmically spaced grid of p -values p\in\{1,2,3\}\cup\{\lfloor 2^{i/4}\rfloor,~i=9,10,11,\dots\} and, starting from an initial value p_{0} (for which we take the optimal value found for the previously calculated instance, or p_{0}=6 in case of the first instance corresponding to the smallest problem size N=12 ), we increase or decrease p on this grid until a local minimum of D is found. Figure 10: Portfolio Optimization: optimized linear-ramp parameters (a) \Delta_{\gamma} , (b) \Delta_{\beta} , and (c) QAOA depth p as a function of number of qubits N , depicted as a log-log plot, for the same instances as in Fig. 9 (a). The transparent blue dots represent values obtained from extrapolation and the blue lines show the 1/D -weighted geometric means (see main text) over all instances. The values for \Delta_{\gamma} as well as for p are increasing with increasing N while the values for \Delta_{\beta} are decreasing. The yellow diamonds represent the optimal values found by a minimizer (as in Fig. 9 (a)) and have been shifted along the x-axis for better visibility. The black dashed lines display algebraic fits f(N)=a\cdot N^{b} to the 1/D -weighted geometric means and determine the universal parameter scaling used in Fig. 11 (a). V Results and Discussion In this section, we analyze the LR-QAOA runtime scaling for the three use cases (portfolio optimization, feature selection and clustering) introduced in Sec. II . We increase the problem size from N=12 to N=28 . For each N , 10 randomly chosen problem instances are generated, and LR-QAOA circuit parameters ( \Delta_{\gamma} , \Delta_{\beta} and p ) are found using the extrapolation procedure described in Sect. IV.1 . Finally, the total depth D – which is proportional to the quantum runtime for finding the optimal solution (see Sec. IV.2.4 ) – is determined by Eqs. ( 9 , 10 , 16 ) and ( 17 ) (using a noiseless quantum emulator). Note that the last step is the only one which involves the execution of a quantum circuit with larger size ( N>10 ). Finally, we determine the runtime scaling with increasing N and compare it with the classical result (MQLib/Burer2002) of Sec. III . V.1 LR-QAOA runtime scaling For the case of Portfolio Optimization, the results for the individual 10 random instances per N are displayed by the blue circles in Fig. 9 (a). To extract the scaling behavior, we perform an exponential fit, D\propto 2^{\alpha N} (red dashed line). With this, we find a scaling exponent for the runtime of \alpha\approx 0.219 , which is smaller than the classical scaling exponent of \alpha\approx 0.323 (see Fig. 1 bottom right). This indicates a potential quantum advantage regarding the runtime scaling. In order to test our extrapolation procedure, we further optimized the circuit parameters ( \Delta_{\gamma} , \Delta_{\beta} and p ) – starting from the extrapolated parameters as initial points – by directly minimizing the actual total depth D (instead of its estimate based on extrapolation). Since this involves many executions of large quantum circuits (up to N=28 ) for each instance, we restricted ourselves to every fourth problem size N=12,16,\dots . All in all, we see that the depths D achieved with the extrapolated parameters (blue circles) are remarkably close to the actual minima (yellow diamonds) in Fig. 9 (a). This underlines the effectiveness of the extrapolation scheme. Fig. 9 (b) shows the results for the Feature Selection problem, which we evaluate on the same footing as Portfolio Optimization. Here, we find a scaling for the quantum runtime of \approx 2^{0.378N} . In comparison, the classical runtime exhibits a scaling of \approx 2^{0.197N} (see Fig. 2 , bottom right) indicating that this combinatorial optimization problem is faster to solve classically. A similar picture is observed for the Clustering problem (Moons), as shown in Fig. 9 (c) and the MaxCut problem, see Fig. 9 (d). In these case, we observe a quantum runtime scaling of \approx 2^{0.248N} for clustering and \approx 2^{0.235N} for MaxCut. In comparison, the classical heuristic MQLib/Burer2002 exhibits a scaling of \approx 2^{0.051N} for clustering (see Fig. 3 , bottom right) and \approx 2^{0.156N} for MaxCut (see Fig. 4 , bottom right) indicating that the quantum algorithm takes significantly longer to solve the problem. For Clustering, we also observe some outliers with extremely large values of D (e.g., three instances with D\approx 10^{6} at N=24 and 28 ). This suggests that, especially for the Clustering problem, the extrapolation scheme is less stable than, e.g., in the case of Portfolio Optimization and fails in providing good circuit parameters for some instances. This is also confirmed by the results of the direct optimization (yellow diamonds) in Fig. 9 (c), which do not exhibit such extreme outliers. V.2 Universal parameter scaling Figure 11: Scaling of quantum runtime expressed as total depth D , see Eq. ( 16 ), with increasing problem size N (number of qubits) using linear-ramp QAOA with universal circuit parameters (defined by the algebraic fits in Figs. 10 and 14 - 16 , black dashed lines). The blue circles refer to the same 10 problem instances per N as in Fig. 15 , whereas the orange circles in (b-d) correspond to 10 new randomly chosen problem instances per N . As in Fig. 9 , the red dashed lines represent exponential fits with slope \alpha (i.e. D\propto 2^{\alpha N} ) of the geometric means (blue lines) over all problem instances per N . (a) Portfolio Optimization. The result is almost identical to the one in Fig. 9 , exhibiting a scaling advantage compared to the classical benchmark ( \alpha=0.22 vs. \alpha_{\rm cl}=0.323 ). For the remaining three problem classes (b) Feature Selection, (c) Clustering (Moons) and (d) fully connected weighted random MaxCut, the choice of universal parameters significantly improves the LR-QAOA scaling coefficients as compared to Fig. 9 . For Feature Selection and MaxCut (b,d), equality with the classical benchmark ( \alpha_{\rm cl}=0.197 and 0.156 , respectively) is achieved. For Clustering (Moons), the classical benchmark ( \alpha_{\rm cl}=0.051 ) is not reached. Figure 12: Probability P_{\rm opt} to measure the optimal solution after a single run of the LR-QAOA circuit for the same instances and the same universal parameters as in Fig. 11 (blue and orange circles). The (geometric) averages \langle P_{\rm opt}\rangle over all problem instances are displayed by the blue lines. On average, the probabilities \langle P_{\rm opt}\rangle remain above 0.1 and appear to be constant as a function of N in case of (a) Portfolio Optimization and (d) fully connected randomly weighted MaxCut, whereas, for Feature Selection (b) and Clustering (c), a slight decrease of \langle P_{\rm opt}\rangle with increasing N is observed. In order to reduce these outliers, we additionally implemented an approach similar to the one proposed in [ 25 ] : rather than trying to find LR-QAOA circuit parameters individually for each single instance, the idea is to use the same ”universal” parameters for different instances. Fig. 10 shows the circuit parameters obtained from our extrapolation procedure (blue circles) for the case of Portfolio Optimization. To determine the universal parameter scaling, we first evaluate – for each of the three parameters y=\log_{10}(\Delta_{\gamma}),\log_{10}(\Delta_{\beta}) or \log_{10}(p) , respectively – the 1/D -weighted average (blue lines), i.e., \langle y\rangle=\left(\sum_{i}\frac{y_{i}}{D_{i}}\right)/\left(\sum_{i}\frac{1}{D_{i}}\right) , where the sum over i refers to the 10 instances per N , and the weight 1/D_{i} is employed to suppress those cases where the extrapolation fails in providing good circuit parameters (leading to a large total depth D_{i} for instance i ). Remarkably, we see that these averages closely follow algebraic fits using the function f(N)=a\cdot N^{b} (with f=\Delta_{\gamma} , \Delta_{\beta} or p , respectively), see the dashed lines in Fig. 10 . These algebraic fits are now taken to define our universal parameter scaling. In other words, we again simulate all instances shown in Fig. 9 (a) – but now using LR-QAOA circuit parameters given by the black dashed line instead of the blue points displayed in Fig. 10 (a). For Portfolio Optimization, the result shown in Fig. 11 (a) is similar to the previous one in Fig. 9 (a). In particular, the rate of the exponential increase \simeq 2^{0.215N} is almost unchanged. For the other three problem classes, however, the results in Fig. 11 (b-d) reveal clear improvements when using the universal parameter scaling (displayed by the black dashed lines in Figs. 14 - 16 , see Appendix B ). In contrast to Fig. 9 (b-d), strong outliers exhibiting extremely large depths D are no longer present. Moreover, we generated, for each problem size N , ten additional random instances (orange circles) and evaluated them using the same universal parameter scaling as for the original ten instances (blue circles), with similar results. The scaling coefficients \alpha (determined from all 20 instances per N ) are significantly smaller than in Fig. 9 before. For Feature Selection and the fully connected weighted random MaxCut problem, see Fig. 11 (b) and (d), almost equality with the classical benchmarks ( \alpha_{\rm cl}=0.197 and 0.156 , respectively) is now achieved, whereas, for Clustering (Moons), the classical scaling ( \alpha_{\rm cl}=0.051 ) is still better. All in all, we observe that, for our four problem classes, the scaling coefficients using LR-QAOA with universal parameter scaling are remarkably similar to each other (ranging between \alpha=0.16 and 0.22 ), whereas the classical benchmarks exhibit larger variations (between \alpha_{\rm cl}=0.051 and 0.323 ). Concerning the weighted MaxCut problem, a more advantageous scaling coefficient ( \alpha=0.107 ) has been observed in [ 25 ] . As we point out in Appendix D , this difference can be traced back to the selection of classically ”hard” problem instances performed in [ 25 ] . Finally, we display in Fig. 12 the probabilities P_{\rm opt} of measuring the optimal solution for the same instances and same LR-QAOA parameter scaling as in Fig. 11 . In all cases, the probabilities are, on average, above 0.1 . For Portfolio Optimization and MaxCut (a,d), the probability appears (on average) to remain constant (or even slightly increase in case of MaxCut) as a function of the problem size N . For Feature Selection and Clustering (Moons), we observe a slight decrease. We note that the behaviour of P_{\rm opt} with increasing N is relevant for the following reason: Since, according to our universal parameter scaling, the QAOA depth p(N)=a\cdot N^{b} scales algebraically and the depth d of the QAOA circuit is proportional to p\cdot N , constant median P_{\rm opt} would imply algebraic, i.e. sub-exponential, scaling of the median quantum runtime as quantified by the total depth D , see Eq. ( 16 ). VI Conclusion In this work, we present an extrapolation method to optimize linear-ramp QAOA parameters, enabling us to discard the need for variational optimization employed in standard QAOA. We start with the introduction of four different combinatorial optimization use cases: Portfolio Optimization, Feature Selection, Clustering and weighted MaxCut, which are subsequently solved using classical methods (CPLEX, Gurobi, MQLib Burer2002, Goemans-Williamson) to assess the classical runtime. The scaling of the runtime is investigated by fitting the runtime with an exponential model, which serves as a benchmark for the runtimes of our quantum algorithm. In particular, we concentrate on the runtime scaling of the MQLib Burer2002 heuristics, since it exhibits the lowest absolute values of the runtime together with a well-defined scaling behavior over a large range of problem sizes. Our quantum algorithm is based on linear-ramp QAOA, for which the circuit parameters are determined by a linear ansatz. This ansatz is characterized by three parameters ( \Delta_{\gamma} , \Delta_{\beta} and depth p ), which have to be optimized. In this paper, we expose a method to derive those optimized parameters through extrapolation from smaller to larger problem sizes. In particular, the extrapolation is based on optimizations of QAOA circuits with reduced size ( \tilde{N}=4,6,8,10 ) corresponding to randomly sampled sub-instances of the original problem instance (with size N up to 28). The quantum runtime is then expressed in terms of the total depth D=dN_{\text{shots}} , i.e., the depth d of a single linear-ramp QAOA circuit times the (median of) the number of shots required to measure the optimal solution on a noiseless quantum emulator. Comparing quantum and classical runtime scalings, we find an indication of quantum advantage for one of the three use cases mentioned above, i.e., for Portfolio Optimization. We furthermore showed that, based on the extrapolated optimized circuit parameters, a simple ansatz can be derived, according to which these parameters can be scaled algebraically with increasing problem size N , independently of the particular problem instance at hand. Employing this ”universal” parameter scaling, leaves the advantageous results in case of Portfolio Optimization unchanged, but significantly improves the scaling of quantum runtime in case of the three other problem classes (achieving equality with the classical benchmark in case of Feature Selection and MaxCut). One might argue that the cost for finding the optimized circuit parameters should also be taken into account in the evaluation of the quantum runtime scaling. Although, as mentioned above, our extrapolation scheme is based on the analysis of small sub-problems with fixed size (up to \tilde{N}=10 , independently of N ), the computational time required for this analysis nevertheless increases with increasing problem size N , due to the fact that the optimal values of the QAOA depth p tend to increase for larger N . However, the idea of the present paper is rather to analyze the general potential of LR-QAOA, assuming that suitable circuit parameters are already known or can be efficiently found. An important insight provided by our article is that methods based on extrapolation and scaling of circuit parameters with increasing problem size appear to be a promising tool for this purpose, and the results presented here may inspire further development of such methods. Probably the most important open topic concerns the question whether quantum optimization admits polynomial-time solutions of some instances of combinatorial optimization problems which, classically, can be solved only in exponential time. This possibility is suggested by our observation that, for Portfolio Optimization and MaxCut, the median probability P_{\rm opt} of finding the optimal solution after a single execution of the LR-QAOA circuit does not decrease with increasing N while, at the same time, the depth of the circuit scales algebraically. If true also for larger N , this would imply polynomial scaling of the median quantum runtime, i.e., at least half of all problem instances in the respective ensemble could be solved efficiently. To answer this question, a larger range of problem sizes (beyond N=28 as in the present paper) must be addressed in future work, which will either require extensive quantum simulations using high-performance computers and advanced simulation techniques or real, fault-tolerant quantum hardware with sufficient number of qubits (about 50 to 100 or more). Furthermore, a more elaborate statistical analysis, not concentrating on the median runtime as we did, but also considering the scaling of different percentiles [ 29 ] , would provide additional insight. Finally, a deeper understanding of the structures of combinatorial optimization problems which determine the hardness of their solution by classical or quantum methods constitutes another challenging goal for future research. Data availability The data describing the problem instances analyzed in this article are openly available [ 39 ] Appendix A Additional classical results Fig. 13 illustrates the runtime for the clustering problem using the Blobs dataset. Employing a different dataset results in slightly varying outcomes. This emphasizes the influence of both the dataset and the selected instances on runtime scaling. Notably, the Goemans-Wiliamson algorithm is able to find the optimal solution in this case, and exhibits a better scaling factor \alpha (slope of exponential fit) compared to the Moons dataset. Figure 13: Clustering (Blobs): Runtime T (seconds) obtained with CPLEX, Gurobi, Goemans-Williamson and MQLib/Burer2002, as a function of the number n of variables (bits). The dots represent the results for the ten problem instances, with blue indicating it was optimally solved, while orange indicates a non-optimal solution. The slope \alpha of a robust log2-linear model, i.e., T\propto 2^{\alpha n} (red dashed line) is denoted in the header of each figure. Appendix B LR-QAOA parameters for feature selection and clustering Fig. 14 shows the same parameters for the feature selection problem as shown in the main text (Fig. 10 ) for portfolio optimization. In this case, \Delta_{\gamma} and \Delta_{\beta} remain relatively constant as the problem size increases. Figure 14: Feature Selection: same representation as for portfolio optimization of optimized linear-ramp parameters (a): \Delta_{\gamma} , (b): \Delta_{\beta} , and (c): QAOA depth p as a function of number of qubits N on a log-log scale. In this case, the logarithmic values for \Delta_{\gamma} and for \Delta_{\beta} are relatively constant with N . For the depth p , we observe a nearly linear scaling with respect to N . The yellow diamonds again represent the optima found by a minimizer. The black dashed lines display algebraic fits f(N)=a\cdot N^{b} to the 1/D -weighted geometric means (blue lines) and determine the universal parameter scaling used in Fig. 11 (b). The parameters for the clustering problem are illustrated in Fig. 15 , again showing a different trend compared to the other problems. Here, we see \Delta_{\gamma} decreasing and \Delta_{\beta} increasing. Figure 15: Clustering (Moons): optimized linear-ramp parameters (a): \Delta_{\gamma} , (b): \Delta_{\beta} , and (c): QAOA depth p as a function of number of qubits N on a log-log scale. In this case, the values for \Delta_{\gamma} are decreasing while the values for \Delta_{\beta} are slightly increasing with N . For the depth p , we observe a scaling of \propto\sqrt{N} . The optima found by a minimizer are represented by the yellow diamonds. The black dashed lines display algebraic fits f(N)=a\cdot N^{b} to the 1/D -weighted geometric means (blue lines) and determine the universal parameter scaling used in Fig. 11 (c). Figure 16: MaxCut: optimized linear-ramp parameters (a) \Delta_{\gamma} , (b) \Delta_{\beta} , and (c) QAOA depth p as a function of number of qubits N on a log-log scale. The black dashed lines display algebraic fits f(N)=a\cdot N^{b} to the 1/D -weighted geometric means (blue lines) and determine the universal parameter scaling used in Fig. 11 (c). Appendix C Distribution of the QUBO-Data All optimization problems considered above are defined by their corresponding QUBO matrices. To compare them, we performed the following analysis: For a given problem size (here, N=20 ) and for each problem, we calculated the maximum absolute value across all instances and normalized the respective QUBO matrix by this value. Subsequently, we computed the box plots for both the diagonal and non-diagonal elements. In Fig. ( 17 ), we compare the box plots of the portfolio optimization problem with those of the other problems: The distributions of both the diagonal and non-diagonal elements of the portfolio optimization QUBO are much narrower than those of the other problems. This is due to the fact that portfolio optimization includes a penalty term to enforce the constraint, i.e., the maximum number of assets allowed in the portfolio. Figure 17: Comparison of box plots representing the distribution of QUBO matrix elements between all problem types under consideration for problem size N=20 . The distributions of the QUBO matrices’ diagonal elements are shown in the left figure; the distribution of the non-diagonal elements in the right figure. The QUBO matrices have been normalized by the following factors: 7.39\times 10^{-5} (MaxCut), 0.0102 (Clustering/Moons), 0.0112 (Clustering/Blobs), 3.45 (Feature Selection), and 0.0215 (Portfolio Optimization). Appendix D Results for hard MaxCut instances Figure 18: Scaling of quantum runtime expressed as total depth D , see Eq. ( 16 ), for the set of selected, classically hard weighted MaxCut instances ( N=20,25,30 ) considered in [ 25 ] . The blue dots (slightly shifted to the left for better visibility) show the depths obtained with the LR-QAOA circuit parameters used in [ 25 ] , whereas the orange dots (shifted to the right) display the results of our universal parameter scaling ansatz. The blue and orange crosses indicate the (geometric) mean values, respectively. The dashed lines represent exponential fits D\propto 2^{\alpha N} , with almost identical scaling coefficients ( \alpha=0.103 and 0.100 ) – similar to the one ( \alpha=0.107 ) found in [ 25 ] for problem sizes up to N=40 . Concerning the weighted random MaxCut problem, our result ( \alpha=0.163 ) for the scaling coefficient, see Fig. 11 (d), differs from the one ( \alpha=0.107 ) obtained in [ 25 ] . The latter result has been obtained for a selected set of instances ( N=20,25,30,35 and 40 ) exhibiting the longest classical runtimes. In this appendix, we present results for the same instances (up to N=30 ) using our universal parameter scaling obtained from Fig. 16 . Note, however, that the normalization of QUBO matrices (such that \max_{i\neq j}Q_{ij}=2 ) employed in [ 25 ] leads to a corresponding shift of \Delta_{\gamma} values for each instance, see the blue dots in Fig. 16 , which changes the fit parameters to a=5.945 and b=-0.800 with respect to the values displayed in Fig. 16 (a). Thereby, we obtain the following LR-QAOA parameters: \Delta_{\gamma}=0.542 , \Delta_{\beta}=0.608 , p=30 for N=20 , \Delta_{\gamma}=0.453 , \Delta_{\beta}=0.581 , p=47 for N=25 and \Delta_{\gamma}=0.392 , \Delta_{\beta}=0.560 , p=67 for N=30 . In contrast, the values \Delta_{\gamma}=0.4 , \Delta_{\beta}=0.4 , p=100 for N=20 , \Delta_{\gamma}=0.5 , \Delta_{\beta}=0.4 , p=50 for N=25 and \Delta_{\gamma}=0.4 , \Delta_{\beta}=0.5 , p=100 for N=30 are used in [ 25 ] . In Fig. 18 , we see that these two sets of parameters achieve (at least on average) almost identical results, with scaling coefficients \alpha=0.103 and 0.100 , respectively. Comparing the values of D in Figs. 11 (d) and Fig. 18 , we see that the instances, which have been selected due to their long classical runtimes, are also more difficult to solve for LR-QAOA, leading to larger D . Moreover, this increase of D appears to be more strongly pronounced for smaller problem sizes, which, in total amounts to a smaller scaling coefficient \alpha .