Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems

• URL: http://arxiv.org/abs/2012.03421v3
• Date: Fri, 23 Sep 2022 16:54:29 GMT
• Title: Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Authors: Asier Ozaeta, Wim van Dam, Peter L. McMahon
• Abstract summary: We report on the energy-expectation-value landscapes produced by the single-layer ($p=1$) Quantum Approximate Optimization Algorithm (QAOA) The landscapes are obtained using an analytical formula that we derive. We provide an estimate for how well the single-layer QAOA may work when run on a quantum computer with thousands of qubits.
• Score: 1.8732539895890135
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We report on the energy-expectation-value landscapes produced by the single-layer ($p=1$) Quantum Approximate Optimization Algorithm (QAOA) when being used to solve Ising problems. The landscapes are obtained using an analytical formula that we derive. The formula allows us to predict the landscape for any given Ising problem instance and consequently predict the optimal QAOA parameters for heuristically solving that instance using the single-layer QAOA. We have validated our analytical formula by showing that it accurately reproduces the landscapes published in recent experimental reports. We then applied our methods to address the question: how well is the single-layer QAOA able to solve large benchmark problem instances? We used our analytical formula to calculate the optimal energy-expectation values for benchmark MAX-CUT problems containing up to $7\,000$ vertices and $41\,459$ edges. We also calculated the optimal energy expectations for general Ising problems with up to $100\,000$ vertices and $150\,000$ edges. Our results provide an estimate for how well the single-layer QAOA may work when run on a quantum computer with thousands of qubits. In addition to providing performance estimates when optimal angles are used, we are able to use our analytical results to investigate the difficulties one may encounter when running the QAOA in practice for different classes of Ising instances. We find that depending on the parameters of the Ising Hamiltonian, the expectation-value landscapes can be rather complex, with sharp features that necessitate highly accurate rotation gates in order for the QAOA to be run optimally on quantum hardware. We also present analytical results that explain some of the qualitative landscape features that are observed numerically.

Related papers

• Parameter Setting in Quantum Approximate Optimization of Weighted Problems [10.396104620517171]
  In this work, we develop parameter settings for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth $p=1$ applied to the weighted MaxCut problem under different assumptions on the weights. Second, for $pgeq 1$ we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Third, we propose a general rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness.
  arXiv  Detail & Related papers  (2023-05-24T14:37:33Z)
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm [0.05076419064097732]
  We study the ability of QAOA to solve hard constraint satisfaction problems, as opposed to quantum computing problems. We develop analytic bounds on the average success probability of QAOA over random formulae at the satisfiability threshold. We find that for around 14 ansatz layers, QAOA matches the scaling performance of the highest-performance classical solver.
  arXiv  Detail & Related papers  (2022-08-14T20:39:48Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
  Quantifying performance bounds provides insight into when QAOA may be viable for solving real-world applications. We find QAOA exceeds the Goemans-Williamson approximation ratio bound for most graphs. The resulting data set is presented as a benchmark for establishing empirical bounds on QAOA performance.
  arXiv  Detail & Related papers  (2021-02-12T23:12:09Z)
• Exploiting Symmetry Reduces the Cost of Training QAOA [6.295931120803673]
  We propose a novel approach for accelerating the evaluation of QAOA energy by leveraging the symmetry of the problem. We show a connection between classical symmetries of the objective function and the symmetries of the terms of the cost Hamiltonian with respect to the QAOA energy. Our approach is general and applies to any known subgroup of symmetries and is not limited to graph problems.
  arXiv  Detail & Related papers  (2021-01-25T18:25:44Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Evaluation of QAOA based on the approximation ratio of individual samples [0.0]
  We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. Because of the evolving QAOA computational complexity-theoretic guidance, we utilize a framework for the search for quantum advantage.
  arXiv  Detail & Related papers  (2020-06-08T18:00:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.