{
  "id": "1905.12134",
  "version": "v1",
  "published": "2019-05-28T23:29:38.000Z",
  "updated": "2019-05-28T23:29:38.000Z",
  "title": "Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth",
  "authors": [
    "Murphy Yuezhen Niu",
    "Sirui Lu",
    "Isaac L. Chuang"
  ],
  "categories": [
    "quant-ph"
  ],
  "abstract": "The quantum approximate optimization algorithm~(QAOA) first proposed by Farhi et al. promises near-term applications based on its simplicity, universality, and provable optimality. A depth-p QAOA consists of p interleaved unitary transformations induced by two mutually non-commuting Hamiltonians. A long-standing question concerning the performance of QAOA is the dependence of its success probability as a function of circuit depth p. We make initial progress by analyzing the success probability of QAOA for realizing state transfer in a one-dimensional qubit chain using two-qubit XY Hamiltonians and single-qubit Hamiltonians. We provide analytic state transfer success probability dependencies on p in both low and large p limits by leveraging the unique spectral property of the XY Hamiltonian. We support our proof under a given QAOA ansatz with numerical optimizations of QAOA for up to \\(N\\)=20 qubits. We show that the optimized QAOA can achieve the well-known quadratic speedup, Grover speedup, over the classical alternatives. Treating QAOA optimization as a quantum control problem, we also provide numerical evidence of how the circuit depth determines the controllability of the QAOA ansatz.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-28T23:29:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "circuit depth",
      "runtime dependence",
      "optimizing qaoa",
      "state transfer success probability dependencies",
      "analytic state transfer success probability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}