The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the density of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.
The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the density of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.
The quantum approximate optimisation algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the density of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. We performed a detailed reanalysis of the data reproduced from Google's Sycamore superconducting qubit quantum processor executing QAOA applied to minimization problems on graphs. We found that Sycamore approaches a rapid fall-off in approximation quality experienced beyond intermediate-density instances. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.
The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithm's ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio-this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such reachability deficits persist even in the absence of barren plateaus and are outside of the recently reported level-1 QAOA limitations. These findings are among the first to determine strong limitations on variational quantum approximate optimization.
The main object of study of this work is the Quantum Approximate Optimization Algorithm (QAOA) —the best-known heuristic quantum algorithm for addressing combinatorial optimization problems. Despite its popularity, QAOA poses major challenges. Namely, its performance remains poorly understood, especially in the low depth regime most relevant to near-term quantum computing. Besides, the algorithm is of variational nature, relying on several hyperparameters to be classically trained. In this work, we contribute to addressing these issues by developing techniques to understand the performance of QAOA at low depth, and deducing from these pretrained hyperparameters, thereby eliminating or considerably reducing the need for a classical optimization loop. We first consider applying QAOA to constraint satisfaction problems with the goal of maximizing the algorithm’s approximation ratio (fraction of satisfied constraints). As a particular example, we consider QAOA applied to MAXCUT on non-regular graphs, showing how analytic techniques provide good guess hyperparameters in this setting. Next, we analyze the performance of QAOA on a well-studied constraint satisfaction problem: random k-SAT. In this case, the performance is measured by the probability of finding an assignment satisfying all constraints (“success probability”). To estimate this quantity, we develop new techniques, mapping quantum expectation values of the QAOA circuits to classical spin models. We further show how these techniques can be generalized to a larger family of random constraint satisfaction problems. We conclude the work by two feasibility studies inspired by real-world use cases encountered in collaborations with industrial partners: peptide sampling, and solving flow problems. These problems are naturally phrased by encoding combinatorial variables in qudits, a relatively unexplored setting in the existing literature. We present partial analytic and numerical results for optimal QAOA hyperparameters and the scaling of its success probability in this framework, underlining potential specific difficulties when using QAOA with qudits.
Abstract The quantum approximate optimization algorithm (QAOA) is a hybrid quantum–classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors it is a promising candidate likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. In particular for three-regular random graphs, QAOA performance shows improvement by up to two orders of magnitude compared to previous estimates, strongly reducing the performance gap with classical alternatives. This was possible by reducing the number of function evaluations per iteration and optimizing the variational parameters on small graph instances and transferring to large via training. Because QAOA’s performance guarantees are only known for limited applications and contexts, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.
Quantum Computing promises to solve complex combinatorial optimization problems more efficiently than classical methods, with the Quantum Approximate Optimization Algorithm (QAOA) being a leading candidate. Recent fixed-parameter variations of QAOA eliminate costly run-time optimization, but determining their optimal initialization as well as the number of required layers (p) for a target solution remains a critical, unsolved challenge. In this work, we propose a novel approach using a Graph Neural Network (GNN) to predict QAOA performance: Based on a graph representation of the problem, the GNN forecasts the probability of the optimal solution in the resulting distribution across different parameter initializations and layer depths for a wide variety of combinatorial optimization problems. We demonstrate that the GNN accurately predicts QAOA performance within a 10% margin of the true values. Furthermore, the model exhibits strong generalization capabilities across unseen problem classes, larger problem sizes, and higher layer counts. Our approach allows to identify viable problem instances for QAOA and to select an adequate parameter initialization strategy with minimal layer depth, without the need of costly parameter optimization.
Abstract Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.