The Quantum Approximate Optimization Algorithm (QAOA) has become one of the most widely used components in the development of modern quantum applications. It works on the paradigm of quantum variational circuits, where a quantum circuit is trained - by repeatedly adjusting circuit parameters - to adequately solve a combinatorial optimization problem. This training process, based on classical optimization algorithms, represents a significant computational bottleneck for QAOA, as it requires repeated calls to the quantum device to evaluate the cost function of the problem to solve. Therefore, there is a strong need to eliminate this computationally expensive task and identify an alternative strategy to compute good parameters for QAOA. This paper synergistically exploits the parameter concentration property of QAOA and the Fuzzy C-Means algorithm to achieve this goal. Experimental results show that the proposed approach can support QAOA to maintain high performance in solving well-known optimization problems such as MAXCUT, requiring a reduced computational effort for the parameter tuning phase.
The Quantum Approximate Optimization Algorithm (QAOA) has become one of the most widely used components in the development of modern quantum applications. It works on the paradigm of quantum variational circuits, where a quantum circuit is trained - by repeatedly adjusting circuit parameters - to adequately solve a combinatorial optimization problem. This training process, based on classical optimization algorithms, represents a significant computational bottleneck for QAOA, as it requires repeated calls to the quantum device to evaluate the cost function of the problem to solve. Therefore, there is a strong need to eliminate this computationally expensive task and identify an alternative strategy to compute good parameters for QAOA. This paper synergistically exploits the parameter concentration property of QAOA and the Fuzzy C-Means algorithm to achieve this goal. Experimental results show that the proposed approach can support QAOA to maintain high performance in solving well-known optimization problems such as MAXCUT, requiring a reduced computational effort for the parameter tuning phase.
The Quantum Approximate Optimization Algorithm (QAOA) is emerging as a key method in quantum optimization. Operating within the framework of variational quantum circuits, QAOA entails training a parameterized quantum circuit through classical optimizers to effectively address combinatorial optimization problems. In this context, evolutionary algorithms such as genetic algorithms are emerging as suitable methodologies to search the optimal parameters for QAOA circuits. However, unfortunately, the training process results in a computationally intensive task, and, as a consequence, it is crucial to explore innovative strategies to address this issue. This work introduces a novel approach based on Fuzzy C-means algorithm to opportunely initialize the population of the genetic algorithms employed as optimizers for QAOA and, as a consequence, enhance the training. Experimental results demonstrate that the proposed approach significantly improves the performance of genetic algorithms-based training for QAOA.
Optimization problems are fundamental to real-world applications, driving the need for increasingly advanced computational techniques. One promising methodology is the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical approach that maximizes the probability of obtaining sub-optimal solutions for combinatorial problems by tuning quantum gate parameters with a classical optimizer. Despite its success, QAOA still faces practical challenges, particularly in terms of training efficiency and computational cost. This paper introduces a fuzzy clustering-based approach to transfer QAOA parameters from instances of a relatively simpler problem to instances of different, more complex problems. Experimental results demonstrate both the effectiveness and efficiency of this approach in solving the Vertex Cover problem, thereby offering a viable alternative to conventional parameter tuning methods.
The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. In QAOA, a quantum circuit is trained---by repeatedly adjusting circuit parameters---to solve a problem instance. Several recent findings have reported parameter concentration effects in QAOA and their presence has become one of folklore: while empirically observed, the concentrations have not been defined and analytical approaches remain scarce, focusing on limiting system sizes while neglecting parameter scaling as system size increases. We found that optimal QAOA circuit parameters concentrate as an inverse polynomial in the problem size, providing an optimistic result for improving circuit training. Our results are analytically demonstrated for QAOA at p=1,2 (corresponding to 2 and 4 tunable parameters, respectively). The technique is also applicable for higher depths wherein the concentration effect is cross verified numerically. Parameter concentrations allow for training on a fraction w<n of qubits to assert that these parameters are nearly optimal on n qubits, thereby reducing training time.
Abstract As combinatorial optimization is one of the main quantum computing applications, many methods based on parameterized quantum circuits are being developed. In general, a set of parameters are being tweaked to optimize a cost function out of the quantum circuit output. One of these algorithms, the Quantum Approximate Optimization Algorithm stands out as a promising approach to tackling combinatorial problems. However, finding the appropriate parameters is a difficult task. Although QAOA exhibits concentration properties, they can depend on instances characteristics that may not be easy to identify, but may nonetheless offer useful information to find good parameters. In this work, we study unsupervised Machine Learning approaches for setting these parameters without optimization. We perform clustering with the angle values but also instances encodings (using instance features or the output of a variational graph autoencoder), and compare different approaches. These angle-finding strategies can be used to reduce calls to quantum circuits when leveraging QAOA as a subroutine. We showcase them within Recursive-QAOA up to depth 3 where the number of QAOA parameters used per iteration is limited to 3, achieving a median approximation ratio of 0.94 for MaxCut over 200 Erdős-Rényi graphs. We obtain similar performances to the case where we extensively optimize the angles, hence saving numerous circuit calls.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational algorithm for solving combinatorial optimization problems on near-term devices. However, as the number of layers in a QAOA circuit increases, which is correlated with the quality of the solution, the number of parameters to optimize grows linearly. This results in more iterations required by the classical optimizer, which results in an increasing computational burden as more circuit executions are needed. To mitigate this issue, we introduce QAOA-PCA, a novel reparameterization technique that employs Principal Component Analysis (PCA) to reduce the dimensionality of the QAOA parameter space. By extracting principal components from optimized parameters of smaller problem instances, QAOA-PCA facilitates efficient optimization with fewer parameters on larger instances. Our empirical evaluation on the prominent MaxCut problem demonstrates that QAOA-PCA consistently requires fewer iterations than standard QAOA, achieving substantial efficiency gains. While this comes at the cost of a slight reduction in approximation ratio compared to QAOA with the same number of layers, QAOA-PCA almost always outperforms standard QAOA when matched by parameter count. QAOA-PCA strikes a favorable balance between efficiency and performance, reducing optimization overhead without significantly compromising solution quality.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.