Generating Target Graph Couplings for QAOA from Native Quantum Hardware Couplings

Joel Rajakumar, Jai Moondra, Swati Gupta, Creston D. HeroldarXiv 2020 · DOI · OpenReview

TL;DR

This paper introduces a new method to construct arbitrary quantum hardware coupling graphs for algorithms like QAOA, using a limited set of native operations. This approach is shown to be more robust to noise than standard compilation methods and offers efficient constructions for both unweighted and weighted graphs, paving the way for larger-scale quantum computations.

What Problem Does This Paper Address?

Quantum computers, especially those in the Noisy Intermediate-Scale Quantum (NISQ) era, have limited qubit connectivity. This means that to run algorithms on arbitrary graphs, a significant amount of "compilation" is needed to translate the desired interactions into the hardware's native operations. This compilation process can introduce errors and increase the overall execution time, hindering the performance of quantum algorithms like the Quantum Approximate Optimization Algorithm (QAOA). Specifically, QAOA for problems like Max-Cut requires implementing a cost Hamiltonian that corresponds to a target graph's couplings. When this target graph doesn't match the hardware's native connectivity, efficient construction becomes a critical challenge. This paper addresses the problem of generating arbitrary target coupling graphs from a limited set of native quantum hardware operations, aiming to minimize the number of operations and their associated noise.

Methods

The authors propose a method to construct arbitrary coupling graphs using two fundamental operations available in many quantum systems, particularly trapped ions:

  1. Global Ising Interaction ($H_{Ising}$): This is a native, hardware-controlled interaction that couples all qubits simultaneously. In trapped ions, this is often realized via the Mølmer-Sørensen (MS) interaction.
  2. Single-Qubit Bit Flips ($X_j$): These are individual rotations applied to each qubit.

The core idea is that by strategically applying bit flips before and after the global Ising interaction, the sign of individual qubit-qubit couplings can be effectively flipped. This allows for the construction of arbitrary ZZ-couplings between qubits.

The paper then formalizes this into a mathematical problem: finding a matrix $P$ (representing the bit flip sequences) and a diagonal matrix $W$ (representing the strengths of the Ising interactions) such that $A = P^T W P \odot J$, where $A$ is the target adjacency matrix, $J$ is the native hardware coupling matrix (assumed to be a complete graph $K_n$ for simplicity), and $\odot$ denotes element-wise multiplication. The goal is to minimize either the number of Ising operations ($||W||_0$, the $L_0$ norm) or the total strength of these operations ($||W||_1$, the $L_1$ norm).

They develop two main algorithmic constructions:

  • Union-of-Stars: For unweighted graphs, this method decomposes the graph into a set of "star" subgraphs (a central node connected to several peripheral nodes). Each star can be constructed efficiently, leading to an overall $O(n)$ operation sequence for an $n$-node graph.
  • Edge-by-Edge Construction: For weighted graphs, they show how to construct each edge individually in a constant number of operations, leading to an $O(m)$ operation sequence for a graph with $m$ edges.

To find truly optimal sequences (minimizing $||W||_0$ or $||W||_1$), they formulate a mixed-integer program (MIP). While this MIP is computationally expensive for larger graphs, it serves to benchmark the performance of their constructive algorithms and find optimal solutions for small systems.

Datasets

Not discussed in the paper. The paper focuses on constructing arbitrary graphs and evaluating performance on randomly generated graphs for numerical experiments.

Key Insights and Ideas

  • Bit flips as a powerful tool for sign control: The paper highlights how simple single-qubit bit flips, when combined with global entangling operations, can precisely control the sign of individual qubit-qubit interactions. This is a crucial insight for building arbitrary coupling graphs.
  • Union-of-Stars for efficient unweighted graph construction: Decomposing unweighted graphs into stars provides a provably efficient $O(n)$ construction, which is a significant improvement over naive methods.
  • Noise resilience of the proposed method: Noisy simulations demonstrate that the union-of-stars approach, due to its reduced number of operations, is less susceptible to noise compared to standard CNOT-based compilation for QAOA. This is a critical advantage for NISQ devices.
  • MIP as a benchmark for optimality: While not scalable, the MIP formulation provides a way to find the absolute minimum number of operations, allowing for a quantitative comparison of their constructive algorithms against the theoretical optimum.
  • The problem of graph coupling is related to biclique partition: The paper draws an interesting connection between the graph coupling number and the biclique partition number of a graph, suggesting potential avenues for further theoretical exploration.

Key Results

  • Algorithmic Constructions:
    • Unweighted graphs: $O(n)$ operations (union-of-stars).
  • Weighted graphs: $O(m)$ operations (edge-by-edge construction).
  • Lower Bound: Any graph with distinct edge weights requires at least $\Omega(\log n)$ Ising operations.
  • Numerical Experiments:
    • For 7-vertex graphs, the union-of-stars construction typically achieves an $L_0$ norm within a factor of two of the optimal MIP solution, and an $L_1$ norm within a factor of three.
  • Noisy simulations of Max-Cut QAOA showed that the union-of-stars method (referred to as "MS" compilation) yielded better approximation ratios than standard CNOT-based compilation ("CX") for certain graph structures and noise levels.
  • Resource Estimates: The proposed method is estimated to be feasible for constructing QAOA cost layers for hundreds of ions.

Limitations and Future Work

  • Optimality Gap: While the union-of-stars construction is efficient, it does not guarantee optimality. The MIP can find optimal solutions but is computationally intractable for larger graphs. The authors speculate that the graph coupling problem might be NP-hard.
  • Scalability of MIP: The MIP is limited to small graphs ($n \le 8$) due to its computational complexity.
  • Hardware-Specific Optimizations: The resource estimates are based on trapped-ion hardware. Further work could explore optimizations for other quantum architectures.
  • Efficient Optimal Solution Finding: A key open question is whether an efficient, scalable algorithm can be developed to find the optimal operation sequence for any arbitrary graph.
  • Complexity of Compilation: The paper raises the philosophical question of whether the complexity of compilation itself can become a bottleneck for quantum algorithms, potentially replacing one NP-hard problem with another.

Summary updated

Abstract

We present methods for constructing any target coupling graph using limited global controls in an Ising-like quantum spin system. Our approach is motivated by implementing the quantum approximate optimization algorithm (QAOA) on trapped ion quantum hardware to find approximate solutions to Max-Cut. We present a mathematical description of the problem and provide approximately optimal algorithmic constructions that generate arbitrary unweighted coupling graphs with $n$ nodes in $O(n)$ global entangling operations and weighted graphs with $m$ edges in $O(m)$ operations. These upper bounds are not tight in general, and we formulate a mixed-integer program to solve the graph coupling problem to optimality. We perform numeric experiments on small graphs with $n\le8$ and show that optimal sequences, which use fewer operations, can be found using mixed-integer programs. Noisy simulations of Max-Cut QAOA show that our implementation is less susceptible to noise than the standard gate-based compilation.
BibTeX
@misc{rajakumar2020generating,
  author = {Joel Rajakumar and Jai Moondra and Swati Gupta and Creston D. Herold},
  title = {{Generating Target Graph Couplings for QAOA from Native Quantum Hardware Couplings}},
  year = {2020},
  eprint = {2011.08165},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.08165},
}
Figure