Abstract A key open question in quantum computing is whether quantum algorithms can potentially offer a significant advantage over classical algorithms for tasks of practical interest. Understanding the limits of classical computing in simulating quantum systems is an important component of addressing this question. We introduce a method to simulate layered quantum circuits consisting of parametrized gates, an architecture behind many variational quantum algorithms suitable for near-term quantum computers. A neural-network parametrization of the many-qubit wavefunction is used, focusing on states relevant for the Quantum Approximate Optimization Algorithm (QAOA). For the largest circuits simulated, we reach 54 qubits at 4 QAOA layers, approximately implementing 324 RZZ gates and 216 RX gates without requiring large-scale computational resources. For larger systems, our approach can be used to provide accurate QAOA simulations at previously unexplored parameter values and to benchmark the next generation of experiments in the Noisy Intermediate-Scale Quantum (NISQ) era.
Abstract A key open question in quantum computing is whether quantum algorithms can potentially offer a significant advantage over classical algorithms for tasks of practical interest. Understanding the limits of classical computing in simulating quantum systems is an important component of addressing this question. We introduce a method to simulate layered quantum circuits consisting of parametrized gates, an architecture behind many variational quantum algorithms suitable for near-term quantum computers. A neural-network parametrization of the many-qubit wavefunction is used, focusing on states relevant for the Quantum Approximate Optimization Algorithm (QAOA). For the largest circuits simulated, we reach 54 qubits at 4 QAOA layers, approximately implementing 324 RZZ gates and 216 RX gates without requiring large-scale computational resources. For larger systems, our approach can be used to provide accurate QAOA simulations at previously unexplored parameter values and to benchmark the next generation of experiments in the Noisy Intermediate-Scale Quantum (NISQ) era.
Quantum computer systems require robust software integration to support quantum algorithm development towards addressing practical challenges in many important problem areas including logistics, chemistry, and AI/ML. Researchers predict quantum algorithms will achieve computational advantage over classical algorithms for these specific problem areas in the Noisy Intermediate Scale Quantum (NISQ) era [1]. We consider one such algorithm, the Quantum Approximate Optimization Algorithm (QAOA), a variational quantum algorithm for solving combinatorial optimization problems [2]. QAOA promises to be a practical alternative to inefficient classical algorithms for large problem sizes, but quantum hardware capabilities lag behind the requirements for practical application. We show that the Superstaq quantum compiler can support performance improvements for QAOA by exploiting optimization opportunities only revealed at levels lower than logic gates, i.e., at the level of pulses, quantum hardware instructions.
Quantum computers are increasing in size and quality but are still very noisy. Error mitigation extends the size of the quantum circuits that noisy devices can meaningfully execute. However, state-of-the-art error mitigation methods are hard to implement and the limited qubit connectivity in superconducting qubit devices restricts most applications to the hardware's native topology. Here we show a quantum approximate optimization algorithm (QAOA) on nonplanar random regular graphs with up to 40 nodes enabled by a machine learning-based error mitigation. We use a swap network with careful decision-variable-to-qubit mapping and a feed-forward neural network to optimize a depth-two QAOA on up to 40 qubits. We observe a meaningful parameter optimization for the largest graph which requires running quantum circuits with 958 two-qubit gates. Our paper emphasizes the need to mitigate samples, and not only expectation values, in quantum approximate optimization. These results are a step towards executing quantum approximate optimization at a scale that is not classically simulable. Reaching such system sizes is key to properly understanding the true potential of heuristic algorithms like QAOA. Published by the American Physical Society 2024
In this thesis, I explore the domain of hybrid quantum-classical computation, the foremost approach for utilizing Noisy Intermediate-Scale Quantum (NISQ) devices. The opening chapter presents an overview of Variational Quantum Algorithms (VQAs), highlighting the primary algorithmic challenges. It offers an in-depth review of the Quantum Approximate Optimization Algorithm (QAOA), discussing its variants for ground state preparation. In the second chapter, we apply QAOA for the supervised learning of a simple Binary Neural Network. This model represents an idealized yet prototypical example of classical combinatorial optimization problems involving multi-spin interactions. In the following chapters, the discussion shifts toward quantum many-body ground state preparation, focusing on the one-dimensional Heisenberg XYZ model and the longitudinal-transverse-field Ising model (LTFIM). We have developed a novel technique that, at any point in the phase diagram, leverages the transferability of a specific class of optimal schedules from systems with small to those with larger numbers of qubits. This approach mitigates trainability issues, specifically vanishing gradients (Barren Plateaus). Next, we tailor a QAOA scheme to characterize a topological quantum phase transition within a lattice gauge theory model. This investigation is particularly significant due to its implications for high-energy physics and relevance to quantum error correction and surface codes. In the concluding chapter, I propose new stimulating research directions and help to identify core challenges and unresolved questions in variational quantum computing that transcend any particular application domain.
Variational quantum algorithms are believed to be promising for solving computationally hard problems and are often comprised of repeated layers of quantum gates. An example thereof is the quantum approximate optimization algorithm (QAOA), an approach to solve combinatorial optimization problems on noisy intermediate-scale quantum (NISQ) systems. Gaining computational power from QAOA critically relies on the mitigation of errors during the execution of the algorithm, which for coherence-limited operations is achievable by reducing the gate count. Here, we demonstrate an improvement of up to a factor of 3 in algorithmic performance as measured by the success probability, by implementing a continuous hardware-efficient gate set using superconducting quantum circuits. This gate set allows us to perform the phase separation step in QAOA with a single physical gate for each pair of qubits instead of decomposing it into two CZ-gates and single-qubit gates. With this reduced number of physical gates, which scales with the number of layers employed in the algorithm, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances mapped onto three and seven qubits, using up to a total of 399 operations and up to 9 layers. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
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.
Quantum computing is an emerging field on the multidisciplinary interface between physics, engineering, and computer science with the potential to make a large impact on computational intelligence (CI). The aim of this paper is to introduce quantum approximate optimization methods to the CI community because of direct relevance to solving combinatorial problems. We introduce quantum computing and variational quantum algorithms (VQAs). VQAs are an effective method for the near-term implementation of quantum solutions on noisy intermediate-scale quantum (NISQ) devices with less reliable qubits and early-stage error correction. Then, we explain Farhi et al.'s quantum approximate optimization algorithm (Farhi's QAOA, to prevent confusion). This VQA is generalized by Hadfield et al. to the quantum alternating operator ansatz (QAOA), which is a nature-inspired (particularly, adiabatic) quantum metaheuristic for approximately solving combinatorial optimization problems on gate-based quantum computers. We discuss connections of QAOA to relevant domains, such as computational learning theory and genetic algorithms, discussing current techniques and known results regarding hybrid quantum-classical intelligence systems. We present a schematic of how QAOA is constructed, and also discuss how CI techniques can be used to improve QAOA. We conclude with QAOA implementations for the well-known maximum cut, maximum bisection, and traveling salesperson problems, which can serve as templates for CI practitioners interested in using QAOA.