Part 3: The primary algorithms VQA, VQE and QAOA
Variational Quantum Algorithms (VQA)
In the NISQ era, variational circuits serve as a bridge between the classical and the quantum world. The hybrid quantum-classical algorithms or Variational Quantum Algorithms (VQA) incorporate aspects from both the gate-based (i.e., logic gates) and annealing or adiabatic models (evolving after cooling to its lowest energy configuration). VQAs variationally update the parameters of a parametrized quantum circuit.
VQAs, like adiabatic models, rely on the knowledge that the end state of a quantum computation can be viewed as the ground state of a certain energy state. On the other hand, VQAs, like the gate-based technique, uses a quantum circuit. The circuit’s gates are not fixed, but rather reflect continuous parameters.
The trial state [-preparation circuit] of the optimization cost function that is utilized as a beginning point for approximations or optimizations is described by the term ansatz and refers to the first condition or first guess. How do you apply an ansatz? Within variational quantum algorithms.
VQAs might be called problem-driven because the algorithms focus on a specific job, such as preparing the ground state of a Hamiltonian. One recent VQA application is inside of the DARPA research contract awarded to POLARISqb under the IMPAQT initiative to advance quantum computing applications in drug design. You’ll see VQAs sometimes compared with Quantum Machine Learning (QML) models because they have a similar structure. See Huang et al., 2022 Near-Term Quantum Computing Techniques for details. In contrast to VQAs, QML models rely on data. Preskill et al, 2018 explains in Quantum Computing in the NISQ era and beyond that QMLs have been envisioned for almost all learning problems, including supervised and unsupervised learning, generative modeling, and so on.
The first concretization of the VQA was the Variational Quantum Eigensolver (VQE), proposed to solve quantum chemistry problems, and the Quantum Approximate Optimization Algorithm (QAOA), proposed to solve combinatorial optimization problems. Bharti et al, 2021, in Noisy intermediate-scale quantum (NISQ) algorithms writes “these two algorithms may be thought of as the parents of the whole VQA family.”
Variational Quantum Eigensolver (VQE)
Why quantum chemistry problems? The optimization cost function of variational algorithms can be obtained not just from a gate circuit but also from the actual energy of a real physical object, such as a molecule. The ground state of the electrons in this molecule with the corresponding energy will then be represented by the output state of the quantum variational optimization. The idea behind this technique led to the creation of the variational quantum eigensolver (VQE) in 2014.
The VQE algorithm is a prescription for reconstructing a corresponding eigenstate to identify the least eigenvalue of an observable like the ground-state energy of a physically realizable Hamiltonian, using a parameterized ansätze. Tilley et al., 2022’s article: Variational Quantum Eigensolver (arxiv) is a book-sized compendium and a great resource for studying VQE applications for NISQ practitioners. To see the VQE in practice, Phasecraft’s Materials Modeling Complexity Database was created with its materials’ modeling algorithms, including support for VQEs.
Quantum Approximation Optimization Algorithm (QAOA)
One can think of QAOA as a Trotterized version of quantum annealing, according to Bharti et al., 2021. Trotterization breaks down a continuous time evolution into small, discrete steps and each time evolution is simulated using a quantum circuit. The process involves alternating between two Hamiltonians that encode the problem and the mixing terms. This step-by-step approach allows for the simulation of continuous dynamics using a sequence of quantum gates. Hence, the depth of the circuit typically exhibits a polynomial relationship with both the size of the system and the duration of the simulation.
There is a trade-off between having a minimal number of parameters to facilitate the classical optimizer’s convergence to a high-quality solution and having a flexible ansatz that can represent the optimal solution. These two extremes of the trade-off are the VQEs and QAOAs.
The quantum software company, Classiq, with Hewlett Packard Labs, recently demonstrated an application of QAOA to solve large-scale combinatorial optimization problems:
Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA at the Q-Casa workshop at the IEEE IPDPS Conference on May 31 in San Francisco.
Multiple Hybrid Devices
Gate-based quantum computing devices typically run VQAs, however research is showing more variety, which you’ll see described in these QNALYSIS pages at GQI. For example, this development to combine hardware types: classical computers with gate-based and annealing quantum devices. Jattana, 2024, in Quantum annealer accelerates the variational quantum eigensolver in a triple-hybrid algorithm combines a classical computer, a gate-based quantum computer, and a quantum annealer to find the solution of a graph coloring problem, where the quantum annealer reduces the resources needed from a gate-based quantum computer to accelerate VQE.
August 27, 2024