Quantum Approximate Optimization Algorithm with Adaptive Bias Fields

• URL: http://arxiv.org/abs/2105.11946v3
• Date: Tue, 28 Jun 2022 06:59:42 GMT
• Title: Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Authors: Yunlong Yu, Chenfeng Cao, Carter Dewey, Xiang-Bin Wang, Nic Shannon, Robert Joynt
• Abstract summary: The quantum approximate optimization algorithm (QAOA) transforms a simple many-qubit wavefunction into one which encodes a solution to a difficult classical optimization problem. In this paper, the QAOA is modified by updating the operators themselves to include local fields, using information from the measured wavefunction at the end of one step to improve the operators at later steps.
• Score: 4.03537866744963
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantum approximate optimization algorithm (QAOA) transforms a simple many-qubit wavefunction into one which encodes a solution to a difficult classical optimization problem. It does this by optimizing the schedule according to which two unitary operators are alternately applied to the qubits. In this paper, the QAOA is modified by updating the operators themselves to include local fields, using information from the measured wavefunction at the end of one iteration step to improve the operators at later steps. It is shown by numerical simulation on MaxCut problems that, for a fixed accuracy, this procedure decreases the runtime of QAOA very substantially. This improvement appears to increase with the problem size. Our method requires essentially the same number of quantum gates per optimization step as the standard QAOA, and no additional measurements. This modified algorithm enhances the prospects for quantum advantage for certain optimization problems.

Related papers

• Quantum approximate optimization via learning-based adaptive optimization [5.399532145408153]
  Quantum approximate optimization algorithm (QAOA) is designed to solve objective optimization problems. Our results demonstrate that the algorithm greatly outperforms conventional approximations in terms of speed, accuracy, efficiency and stability. This work helps to unlock the full power of QAOA and paves the way toward achieving quantum advantage in practical classical tasks.
  arXiv  Detail & Related papers  (2023-03-27T02:14:56Z)
• A Comparative Study On Solving Optimization Problems With Exponentially Fewer Qubits [0.0]
  We evaluate and improve an algorithm based on Variational Quantum Eigensolver (VQE) We highlight the numerical instabilities generated by encoding the problem into the variational ansatz. We propose a classical optimization procedure to find the ground-state of the ansatz in less iterations with a better objective.
  arXiv  Detail & Related papers  (2022-10-21T08:54:12Z)
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
  Current quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent Ising model suitable for the quantum device. We propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits. This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Prog-QAOA.
  arXiv  Detail & Related papers  (2022-09-07T18:01:01Z)
• How Much Entanglement Do Quantum Optimization Algorithms Require? [0.0]
  We study the entanglement generated during the execution of ADAPT-QAOA. By incrementally restricting this flexibility, we find that a larger amount of entanglement entropy at earlier stages coincides with faster convergence at later stages.
  arXiv  Detail & Related papers  (2022-05-24T18:00:02Z)
• Stochastic optimization algorithms for quantum applications [0.0]
  We review the use of first-order, second-order, and quantum natural gradient optimization methods, and propose new algorithms defined in the field of complex numbers. The performance of all methods is evaluated by means of their application to variational quantum eigensolver, quantum control of quantum states, and quantum state estimation.
  arXiv  Detail & Related papers  (2022-03-11T16:17:05Z)
• 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)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• 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)
• 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.