Layered circuit ansatze for combinatorial optimization

"Layer VQE: A Variational Approach for Combinatorial Optimization onNoisy Quantum Computers"

Published by Xiaoyuan Liu, Anthony Angone, Ruslan Shaydulin, Ilya Safro, Yuri Alexeev, Lukasz Cincio (University of Delaware, Clemson University, Argonne National Laboratory, Los Alamos National Laboratory), 21st February 2021

NISQ algorithms
Layered circuit ansatze for combinatorial optimization

Optimizing quantum algorithms on near-term noisy-intermediate scale quantum (NISQ) devices is an essential requirement to demonstrate the quantum advantage over the existing classical computing. The capabilities of these devices are constrained by high noise levels and limited error mitigation. Combinatorial optimization on quantum processors is one such promising route to solve the problem created by noise in these systems. Out of various existing approaches for optimization, the most notable ones are Quantum Approximate Optimization Algorithm (QAOA) and variational quantum algorithms, especially for eigenvalue problems with high complexity.

The authors in this work propose an iterative “Layer VQE (L-VQE)” approach, inspired by the well-known Variational Quantum Eigensolver (VQE). The work conducts numerical studies, simulating circuits with up to 40 qubits and 352 parameters (which is a hard problem to simulate) using matrix product state (MPS) representation to perform large-scale simulations of the quantum circuits. The performance of L-VQE in this work is simulated using a noisy simulator of a trapped-ion quantum computer.

It has been proven in literature that for a graph with n vertices, solving the k-communities modularity maximization problem requires kn qubits which encode the problem using the well-known Ising model Hamiltonian. The authors of this paper propose a novel formulation that requires only n log(k) qubits. They further compare the performance of L-VQE with Quantum Approximate Optimization Algorithm (QAOA), which is widely considered to be a strong candidate for quantum advantage in applications with NISQ computers. However, the many-body terms in the Hamiltonian make it harder to implement in the QAOA setting. The numerical results suggest that QAOA comparatively achieves lower approximation ratios and requires significantly deeper circuits. This gap can be compensated using the L-VQE approach for NISQ devices.

The proposed L-VQE algorithm in this work starts from a relatively simple and shallow hardware efficient ansatz with a small number of parameterized gates and then adds layers to the ansatz systematically. This differs from most VQE approaches which have an ansatz fixed upfront. The work claims that this approach can make the ansatz more expressive along with reducing the optimization overhead. Furthermore, the numerical results suggest that adding layers of the ansatz increases the probability of finding the ground state or finding the state that is sufficiently close to the ground state. Such an approach is deemed simple enough to be generalized to different quantum architectures. It is numerically shown that the standard VQE is more likely to fail in the presence of sampling noise as compared to L-VQE which is shown to be more robust under sampling noise.

Lastly, further numerical studies in this work claim that the ansatz with entanglement performs better than the ansatz without entanglement, which is intuitive because entanglement is an important resource to quantum computing; even when the target optimal state is a product state, optimization to it may be guided better with an entangling ansatz. These results provide insight into the introduction of additional entangling parameters in VQE for classical problems. It is proposed to break down the barriers in the optimization landscape, making it more convex and therefore more amenable to simple local outer-loop optimizers to find a minimum. This contrasts with the previous results where no beneficial effects of entanglement are observed. This difference in results suggests the importance of the parameterization choice and the overall VQE procedure design contributing to the success of such methods.