Counting edge covers of a weighted graph on an ion trap quantum computer

ORAL

Abstract

Quantum-classical hybrid schemes, such as the Quantum Approximate Optimization Algorithm (QAOA), are promising approaches to solving combinatorial optimization problems on near-term quantum hardware. Counting edge cover, which is a set of edges that leaves no isolated vertices on a graph, is one of these problems and has important applications in network reliability. We implement a modified QAOA scheme with an adapted mixing Hamiltonian on an ion trap quantum computer to count edge covers of a weighted 3-node star graph. This modified algorithm prepares the quantum system in a superposition of ground states with pre-determined weights for efficient counting. We demonstrate how the approximate solution becomes more exact with increasing number of QAOA-layers on real hardware, despite the additional gate errors.

–

Authors

  • Yingyue Zhu

    • Joint Quantum Institute, Department of Physics, University of Maryland, College Park, MD 20742, USA

  • Bhuvanesh Sundar

    • Institute for Quantum Optics and Quantum Information of the Austrian Academy of Sciences, Innsbruck A-6020, Austria

  • Cinthia Huerta Alderete

    • Joint Quantum Institute, Department of Physics, University of Maryland, College Park, MD 20742, USA

  • Nhung H. Nguyen

    • Joint Quantum Institute, Department of Physics, University of Maryland, College Park, MD 20742, USA

  • Kaden R. A. Hazzard

    • Department of Physics and Astronomy and Rice Center for Quantum Materials, Rice University, Houston, Texas 77005, USA

  • Norbert M. Linke

    • Joint Quantum Institute, Department of Physics, University of Maryland, College Park, MD 20742, USA