Abstract We present a framework to split quantum circuits of variational quantum algorithms (VQAs) to allow for parallel training and execution to solve problems larger than the number of available qubits in a quantum device. We apply this method to combinatorial optimization problems, where inherent structures can be identified, and show how to implement these parallelized quantum circuits. We show how to formulate an objective function for the classical optimizer to guide the optimization towards meaningful solutions. We test our framework by creating a parallelized version of the Quantum Approximate Optimization Algorithm and a variational version of quantum annealing and explain how our framework applies to other quantum optimization algorithms. We provide results obtained both from simulation and experiments on real hardware. Our results show that the information lost by splitting the quantum circuits can be partially recovered by optimizing a global objective function evaluated with the separate circuit samples.
Abstract We present a framework to split quantum circuits of variational quantum algorithms (VQAs) to allow for parallel training and execution to solve problems larger than the number of available qubits in a quantum device. We apply this method to combinatorial optimization problems, where inherent structures can be identified, and show how to implement these parallelized quantum circuits. We show how to formulate an objective function for the classical optimizer to guide the optimization towards meaningful solutions. We test our framework by creating a parallelized version of the Quantum Approximate Optimization Algorithm and a variational version of quantum annealing and explain how our framework applies to other quantum optimization algorithms. We provide results obtained both from simulation and experiments on real hardware. Our results show that the information lost by splitting the quantum circuits can be partially recovered by optimizing a global objective function evaluated with the separate circuit samples.
Variational quantum algorithms have promising applications in noisy intermediate-scale quantum (NISQ) devices. These algorithms rely on a classical optimization outer loop that minimizes a parameterized quantum circuit function. The optimization in variational quantum eigensolver (VQE) is NP-hard, meaning that finding the optimal solution is infeasible in the worst-case scenario. One way to address this challenge is through parallel optimization of parameters using multiple-parameterized quantum circuits. However, this approach is unsuitable for cloud-based quantum processing unit utilization due to the increased number of quantum circuit executions. Although NISQ devices have limitations in terms of gate depth, their size has been growing in recent years. Therefore, implementing multiple-parameterized quantum circuits in NISQ devices can suppress the increase in the number of executions. In this study, we propose a parallel-VQE, which leverages the parallel execution of parameterized quantum circuits to perform parallel parameter optimization in VQE, achieving convergence to solutions closer to the ground state. We validate the effectiveness of parallel-VQE in solving the random weighted max-cut problem using numerical simulations and a real quantum device. We present the results of running up to six circuits in parallel (120 qubits) and demonstrate the advantages of using multiple units to improve computational accuracy. This study provides a potential method for solving eigenvalue problems and combinatorial optimization problems for future quantum devices.
Noisy intermediate-scale quantum computers (NISQ computers) are now readily available, motivating many researchers to experiment with Variational Quantum Algorithms (VQAs). Among them, the Quantum Approximate Optimization Algorithm (QAOA) is one of the most popular one studied by the combinatorial optimization community. In this tutorial, we provide a mathematical description of the class of Variational Quantum Algorithms, assuming no previous knowledge of quantum physics from the readers. We introduce precisely the key aspects of these hybrid algorithms on the quantum side (parametrized quantum circuit) and the classical side (guiding function, optimizer). We devote a particular attention to QAOA, detailing the quantum circuits involved in that algorithm, as well as the properties satisfied by its possible guiding functions. Finally, we discuss the recent literature on QAOA, highlighting several research trends.
While variational quantum algorithms (VQAs) have demonstrated considerable success in unconstrained optimization, their application to constrained combinatorial problems face a trade-off. Penalty-based methods, despite their circuit simplicity, suffer from a fundamental limitation: inefficient sampling in vast infeasible regions. This often results in suboptimal solutions that violate constraints and impede convergence to high-quality results. In contrast, ansatz-based approaches enforce solution feasibility by design but require complex, problem-specific circuits that are challenging to implement on current noisy intermediate-scale quantum devices. To overcome these limitations, we introduce an alternative VQA whose core innovation lies in a strategically designed loss function. This function offers a dual advantage. First, it is provably guaranteed that its global minimum corresponds uniquely to the optimal feasible solution, as this is achieved by ensuring universally higher loss values for all infeasible solutions. Second, it furnishes distinct computational pathways for feasible versus infeasible regions, thus creating clear and non competing guidance for the optimizer. As a result of these combined features, the algorithm's overall performance is significantly enhanced. Regarding hardware overhead, our design requires adding only an efficient validation oracle module to the penalty-based circuit, resulting in a circuit complexity significantly lower than that of ansatz-based approaches with their custom mixers. To validate the practical efficiency of our method, we empirically demonstrate its effectiveness by solving minimum vertex cover and maximum independent set problems on random graphs of varying small-scale sizes.
Variational quantum algorithms (VQAs) provide a promising approach to achieve quantum advantage in the noisy intermediate-scale quantum era. In this era, quantum computers experience high error rates and quantum error detection and correction is not feasible. VQAs can utilize noisy qubits in tandem with classical optimization algorithms to solve hard problems. However, VQAs are still slow relative to their classical counterparts. Hence, improving the performance of VQAs will be necessary to make them competitive. While VQAs are expected perform better as the problem sizes increase, increasing their performance will make them a viable option sooner. In this work we show that circuit-level concurrency provides a means to increase the performance of variational quantum algorithms on noisy quantum computers. This involves mapping multiple instances of the same circuit (program) onto the quantum computer at the same time, which allows multiple samples in a variational quantum algorithm to be gathered in parallel for each training iteration. We demonstrate that this technique provides a linear increase in training speed when increasing the number of concurrently running quantum circuits. Furthermore, even with pessimistic error rates concurrent quantum circuit sampling can speed up the quantum approximate optimization algorithm by up to 20x with low mapping and run time overhead.
There has been much recent interest in near-term applications of quantum computers, i.e., using quantum circuits that have short decoherence times due to hardware limitations. Variational quantum algorithms (VQA), wherein an optimization algorithm implemented on a classical computer evaluates a parametrized quantum circuit as an objective function, are a leading framework in this space. An enormous breadth of algorithms in this framework have been proposed for solving a range of problems in machine learning, forecasting, applied physics, and combinatorial optimization, among others.In this paper, we analyze the iteration complexity of VQA, that is, the number of steps that VQA requires until its iterates satisfy a surrogate measure of optimality. We argue that although VQA procedures incorporate algorithms that can, in the idealized case, be modeled as classic procedures in the optimization literature, the particular nature of noise in near-term devices invalidates the claim of applicability of off-the-shelf analyses of these algorithms. Specifically, noise makes the evaluations of the objective function via quantum circuits biased . Commonly used optimization procedures, such as SPSA and the parameter shift rule, can thus be seen as derivative-free optimization algorithms with biased function evaluations, for which there are currently no iteration complexity guarantees in the literature. We derive the missing guarantees and find that the rate of convergence is unaffected. However, the level of bias contributes unfavorably to both the constant therein, and the asymptotic distance to stationarity, i.e., the more bias, the farther one is guaranteed, at best, to reach a stationary point of the VQA objective.
In the absence of error correction, noisy intermediate-scale quantum devices are operated by training parametrized quantum circuits (PQCs) so as to minimize a suitable loss function. Finding the optimal parameters of those circuits is a hard optimization problem, where global guarantees are known only for highly structured cases of limited practical relevance, and first-order methods can fail to find even local minima due to the presence of barren plateaus. In this work, we study the training of practical classes of PQCs, namely polynomial-depth circuits with a constant number of trainable parameters. This captures widely used PQC families, including fixed-depth QAOA, hardware-efficient ansätze, and Fixed Parameter Count QAOA. Our main technical result is a fully polynomial randomized approximation scheme (FPRAS), which, for every ε>0, returns an ε-approximate solution to the problem's global optimum with high probability, and has runtime and query complexity polynomial in 1/ε and the number of qubits. Unlike the standard hybrid quantum-classical training loop in variational algorithms, where the quantum device is queried repeatedly throughout the training, our approach separates the computation into two distinct stages: (1) an initial quantum data-acquisition phase, followed by (2) a classical global-optimization phase based on the trigonometric moment/sum-of-squares hierarchies. Under a standard flat-extension condition, which can be checked numerically, the method also supports the extraction of optimal circuit parameters. The existence of an FPRAS implies that the promise problem associated with the optimization of poly-depth constant-parameter PQC is in BQP. This imposes a limitation on the expressive power of the class, namely, it cannot encode combinatorial optimization problems whose objective values are separated by an inverse-polynomial gap.