The QAOA with Few Measurements

• URL: http://arxiv.org/abs/2205.06845v6
• Date: Wed, 28 Feb 2024 18:42:47 GMT
• Title: The QAOA with Few Measurements
• Authors: Anthony M. Polloreno and Graeme Smith
• Abstract summary: The Approximate Quantum Optimization Algorithm (QAOA) was originally developed to solve optimization problems. Fully descriptive benchmarking techniques are often expensive for large numbers of qubits. Some experimental quantum computing platforms such as neutral atom quantum computers have slow repetition rates.
• Score: 4.713817702376467
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) was originally developed to solve combinatorial optimization problems, but has become a standard for assessing the performance of quantum computers. Fully descriptive benchmarking techniques are often prohibitively expensive for large numbers of qubits ($n \gtrsim 10$), so the QAOA often serves in practice as a computational benchmark. The QAOA involves a classical optimization subroutine that attempts to find optimal parameters for a quantum subroutine. Unfortunately, many optimizers used for the QAOA require many shots ($N \gtrsim 1000$) per point in parameter space to get a reliable estimate of the energy being minimized. However, some experimental quantum computing platforms such as neutral atom quantum computers have slow repetition rates, placing unique requirements on the classical optimization subroutine used in the QAOA in these systems. In this paper we investigate the performance of two choices of gradient-free classical optimizer for the QAOA - dual annealing and natural evolution strategies - and demonstrate that optimization is possible even with $N=1$ and $n=16$.

Related papers

• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era [3.734751161717204]
  Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum optimizations. Recent advances in parameter setting in QAOA make EFTQC experiments with QAOA practically viable.
  arXiv  Detail & Related papers  (2024-08-18T16:48:14Z)
• Optimization by Decoded Quantum Interferometry [43.55132675053983]
  We introduce a quantum algorithm for reducing classical optimization problems to classical decoding problems. We show that DQI achieves a better approximation ratio than any quantum-time classical algorithm known to us.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Bayesian Optimization Priors for Efficient Variational Quantum Algorithms [0.0]
  Quantum computers currently rely on a quantum-classical approach known as Variational Quantum Algorithms (VQAs) to solve problems. We propose a hybrid framework for basic computational optimization that reduces the number of shots per time is charged. Using both proposed features, we show that using both proposed features statistically outperforms an implementation within VQAs for simulations.
  arXiv  Detail & Related papers  (2024-06-20T18:00:12Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Randomized Benchmarking of Local Zeroth-Order Optimizers for Variational Quantum Systems [65.268245109828]
  We compare the performance of classicals across a series of partially-randomized tasks. We focus on local zeroth-orders due to their generally favorable performance and query-efficiency on quantum systems.
  arXiv  Detail & Related papers  (2023-10-14T02:13:26Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Unsupervised strategies for identifying optimal parameters in Quantum Approximate Optimization Algorithm [3.508346077709686]
  We study unsupervised Machine Learning approaches for setting parameters without optimization. We showcase them within Recursive-QAOA up to depth $3$ where the number of QAOA parameters used per iteration is limited to $3$. We obtain similar performances to the case where we extensively optimize the angles, hence saving numerous circuit calls.
  arXiv  Detail & Related papers  (2022-02-18T19:55:42Z)
• An Empirical Review of Optimization Techniques for Quantum Variational Circuits [0.0]
  Quantum Variational Circuits (QVCs) are often claimed as one of the most potent uses of both near term and long term quantum hardware. Standard approaches to optimizing these circuits rely on a classical system to compute the new parameters at every optimization step. We empirically evaluate the potential of many common gradient and frees on a variety of optimization tasks.
  arXiv  Detail & Related papers  (2022-02-03T03:20:54Z)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  Variational quantum algorithms (VQAs) have the potential of utilizing near-term quantum machines to gain certain computational advantages. Modern VQAs suffer from cumbersome computational overhead, hampered by the tradition of employing a solitary quantum processor to handle large data. Here we devise an efficient distributed optimization scheme, called QUDIO, to address this issue.
  arXiv  Detail & Related papers  (2021-06-24T08:18:42Z)
• 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)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.