Pure Quantum Gradient Descent Algorithm and Full Quantum Variational Eigensolver

• URL: http://arxiv.org/abs/2305.04198v2
• Date: Thu, 11 May 2023 07:55:55 GMT
• Title: Pure Quantum Gradient Descent Algorithm and Full Quantum Variational Eigensolver
• Authors: Ronghang Chen, Shi-Yao Hou, Cong Guo, and Guanru Feng
• Abstract summary: gradient-based gradient descent algorithm is a widely adopted optimization method. We propose a novel quantum-based gradient calculation method that requires only a single oracle calculation. We successfully implemented the quantum gradient descent algorithm and applied it to the Variational Quantum Eigensolver (VQE)
• Score: 0.7149735232319818
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimization problems are prevalent in various fields, and the gradient-based gradient descent algorithm is a widely adopted optimization method. However, in classical computing, computing the numerical gradient for a function with $d$ variables necessitates at least $d+1$ function evaluations, resulting in a computational complexity of $O(d)$. As the number of variables increases, the classical gradient estimation methods require substantial resources, ultimately surpassing the capabilities of classical computers. Fortunately, leveraging the principles of superposition and entanglement in quantum mechanics, quantum computers can achieve genuine parallel computing, leading to exponential acceleration over classical algorithms in some cases.In this paper, we propose a novel quantum-based gradient calculation method that requires only a single oracle calculation to obtain the numerical gradient result for a multivariate function. The complexity of this algorithm is just $O(1)$. Building upon this approach, we successfully implemented the quantum gradient descent algorithm and applied it to the Variational Quantum Eigensolver (VQE), creating a pure quantum variational optimization algorithm. Compared with classical gradient-based optimization algorithm, this quantum optimization algorithm has remarkable complexity advantages, providing an efficient solution to optimization problems.The proposed quantum-based method shows promise in enhancing the performance of optimization algorithms, highlighting the potential of quantum computing in this field.

Related papers

• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
  We develop AlphaTensor-Quantum, a method to minimize the number of T gates that are needed to implement a given circuit. Unlike existing methods for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific knowledge about quantum computation and leverage gadgets. Remarkably, it discovers an efficient algorithm akin to Karatsuba's method for multiplication in finite fields.
  arXiv  Detail & Related papers  (2024-02-22T09:20:54Z)
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms [0.0]
  We study a new class of hybrid approaches to quantum optimization, termed Iterative Maximum Quantum Algorithms. We show that for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS.
  arXiv  Detail & Related papers  (2023-09-22T18:00:03Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• 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)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• 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)
• Quantum mean value approximator for hard integer value problems [19.4417702222583]
  We show that an optimization can be improved substantially by using an approximation rather than the exact expectation. Together with efficient classical sampling algorithms, a quantum algorithm with minimal gate count can thus improve the efficiency of general integer-value problems.
  arXiv  Detail & Related papers  (2021-05-27T13:03:52Z)
• Optimization of the Variational Quantum Eigensolver for Quantum Chemistry Applications [0.0]
  The variational quantum eigensolver algorithm is designed to determine the ground state of a quantum mechanical system. We study methods of reducing the number of required qubit manipulations, prone to induce errors, for the variational quantum eigensolver.
  arXiv  Detail & Related papers  (2021-02-02T22:20:12Z)
• Quantum Gradient Algorithm for General Polynomials [5.008814514502094]
  Gradient-based algorithms, popular strategies to optimization problems, are essential for many modern machine-learning techniques. We propose a quantum gradient algorithm for optimizing numericals with the dressed amplitude. For the potential values in high-dimension optimizations, this quantum algorithm is supposed to facilitate gradient-optimizations.
  arXiv  Detail & Related papers  (2020-04-23T11:28:45Z)

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.