noise. 1 Adaptative Variational Quantum Algorithms (adapt-VQAs) are innovative algorithms that can dynamically adjust their circuit by adding and removing gates. While various adaptative methods have been proposed, a comprehensive comparison among them is still missing in the literature. This paper aims to fill this gap by benchmarking three adaptative algorithms against the fixed-structure QAOA. Our findings reveal that the adaptative methods generate circuits leading to solutions with approximation ratios comparable with QAOA, but use fewer gates. This leads to a decrease in computational time and an increased resilience to htp:/ceur-ws.org CEUR Workshop Proceedings (CEUR-WS.org) ISN1613-073
CEUR ceur-ws.org
Variational Quantum Algorithms (VQAs) have recently emerged as promising solutions to optimization problems on quantum computers. However, these algorithms present several limitations, mostly connected to their fixed-structure circuits, which may not be tailored to the specific problem or may require gates that do not match with the native gates of the hardware.
To address these challenges, the adaptative Variational Quantum Algorithms (adapt-VQAs) have been introduced. Diferently from their fixed-structure counterparts, the adaptative VQAs have the flexibility to modify the circuit structure by adding or removing gates during the training. These algorithms typically operate in two stages: an external loop adjusts the circuit structure based on predefined rules and an internal loop optimizes the parameters.
While several adaptative VQAs have been proposed in the literature, a comprehensive
comparison among the diferent methods applied to the same problem is still lacking. Therefore,
our study aims to fill this gap by analyzing three specific adaptative algorithms:
• Evolutionary Variational Quantum Eigensolver (EVQE)[2]: a genetic algorithm
• Variable Ansatz (VAns)[3]: this algorithm builds the circuits using heuristics and employs
simplification rules to remove redundant gates
1The results have been presented at the IEEE International Conference on Quantum Computing and Engineering
(QCE23), September 17th-22nd 2023, Bellevue (WA), USA[
Additionally, we include the Quantum Approximate Optimization Algorithm (QAOA) in our analysis to compare the adaptative algorithms with a traditional VQA.
We evaluate the algorithms on diferent QUBO problems, including MaxCut built both from Erdős-Rényi and star-topology graphs, Minimum Vertex Cover, and Number Partitioning. We consider instances with 4, 8, 12 and 15 variables, corresponding to an equivalent number of qubits. For each problem instance, we run each algorithm 10 times and then average the results. We employ COBYLA as a classical optimizer and execute the experiments in a noise-free scenario using the Qiskit statevector simulator.
To ensure fairness in the choice of the hyperparameters (e.g., population size, circuit depth), we adopt a Bayesian approach, testing 50 hyperparameter configurations for each algorithm and problem size. Furthermore, we allocate a computational budget of 10,000 cost function evaluations for each algorithm, allotting each parameter optimization subroutine 50 evaluations. An exception is made for QAOA: since this algorithm has a fixed-structure circuit, its entire evaluation budget is used for tuning the parameters of its specific circuit.
We evaluate the performance of the algorithms using diferent metrics: approximation ratio, number of gates and cnot gates in the optimal circuit, and computational time. Our results indicate that all the algorithms yield comparable high-quality solutions, with approximation ratios close to 1. However, the adaptative algorithms outperform QAOA in terms of gate count. VAns, in particular, showcases eficiency in discovering circuits with the lowest number of gates, likely due to its simplification rules. Finally, we find that computational time is strongly correlated with the gate count, with VAns emerging as the fastest algorithm.
Therefore, we conclude that an evaluation based only on the approximation ratio is insuficient, and other dimensions should be considered for a more accurate representation of how these methods perform. The adaptative VQAs, with their ability to maintain QAOA solution quality while optimizing the gate count, emerge as a promising avenue, ofering reduced computational time and enhanced noise resilience. [2] A. G. Rattew, S. Hu, M. Pistoia, R. Chen, S. Wood, A domain-agnostic, noise-resistant, hardware-eficient evolutionary variational quantum eigensolver, 2020. arXiv:1910.09694. [3] M. Bilkis, M. Cerezo, G. Verdon, P. J. Coles, L. Cincio, A semi-agnostic ansatz with variable structure for quantum machine learning, 2023. arXiv:2103.06712.