Reachability Deficits in Quantum Approximate Optimization of Graph Problems

Summary:

Use absolute error or fidelity as performance metrics

Details:

• the variational approach is as powerful as a general quantum computer.

• However only restricted forms—which require significant classical resources in the optimization step—can currently be realized in practice.

• High depth variational circuits of fixed structure have been proven to represent universal resources for quantum computation [14,15]. However, higher depth circuits demand a significant optimization task to be performed on a classical computer.

• we propose graph density (ratio of graph edges to graph nodes) as an order parameter which correlates with the performance of QAOA.

• density dependent performance (even in deeper circuits)

• deeper –> better performance

• density < 0.5 –> num of edges < 0.5 * num of nodes (sparse graph)

• below densities of 0.5, QAOA shows the best performance independent of the number of nodes.

• Beyond density 0.5, we find the performance to strongly depend on density for fixed number of nodes.

• sharp fall-off behaviour in performance beyond density 1.5.

• google, depth-3 QAOA circuit worked, higher had too much noise. till depth 5 tested

• from google’s experiemntal paper, 3 classes of graphs considered:
  • hardware defined graph (edges fixed by chip connectivity)
  • k-regular graph: each node has degree k.
  • fully connected graph (SK model)
• performance metrics:
  • error in energy relative error (energy obtanied/min energy expected)
  • success prob: fidelity
  • relative error (energy obtanied/min energy expected)
• better to use other metrics than relative error to study performance when density changes (graph or qubit size) are involved

refs: QAOA proposed in: 11, 12 QAOA for discrete ptimization: 2, 9, 10 universality QAOA: 13, 14, 15