Improved Quantum Algorithms for Eigenvalues Finding and Gradient Descent

• URL: http://arxiv.org/abs/2312.14786v2
• Date: Mon, 18 Mar 2024 14:34:49 GMT
• Title: Improved Quantum Algorithms for Eigenvalues Finding and Gradient Descent
• Authors: Nhat A. Nghiem, Tzu-Chieh Wei,
• Abstract summary: Block encoding is a key ingredient in the recently developed quantum signal processing that forms a unifying framework for quantum algorithms. In this article, we utilize block encoding to substantially enhance two previously proposed quantum algorithms. We show how to extend our proposed method to different contexts, including matrix inversion and multiple eigenvalues estimation.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Block encoding is a key ingredient in the recently developed quantum signal processing that forms a unifying framework for quantum algorithms. Initially showcased for simplifying and optimizing resource utilization in several problems, such as searching, amplitude estimation, and Hamiltonian simulation, the capabilities of the quantum signal processing go beyond these and offer untapped potential for devising new quantum algorithms. In this article, we utilize block encoding to substantially enhance two previously proposed quantum algorithms: largest eigenvalue estimation and quantum gradient descent. Unlike previous works that involve sophisticated procedures, our findings, using the unitary block encoding, demonstrate that even with elementary operations, these new quantum algorithms can eliminate major scaling factors present in their original counterparts. This yields much more efficient quantum algorithms capable of tackling complex computational problems with remarkable efficiency. Furthermore, we show how to extend our proposed method to different contexts, including matrix inversion and multiple eigenvalues estimation.

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 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)
• An introduction to variational quantum algorithms for combinatorial optimization problems [0.0]
  This tutorial provides a mathematical description of the class of Variational Quantum Algorithms. We introduce precisely the key aspects of these hybrid algorithms on the quantum side and the classical side. We devote a particular attention to QAOA, detailing the quantum circuits involved in that algorithm, as well as the properties satisfied by its possible guiding functions.
  arXiv  Detail & Related papers  (2022-12-22T14:27:52Z)
• Improved maximum-likelihood quantum amplitude estimation [0.0]
  Quantum estimation is a key subroutine in a number of powerful quantum algorithms, including quantum-enhanced Monte Carlo simulation and quantum machine learning. In this article, we deepen the analysis of Maximum-likelihood quantum amplitude estimation (MLQAE) to put the algorithm in a more prescriptive form, including scenarios where quantum circuit depth is limited. We then propose and numerically validate a modification to the algorithm to overcome this problem, bringing the algorithm even closer to being useful as a practical subroutine on near- and mid-term quantum hardware.
  arXiv  Detail & Related papers  (2022-09-07T17:30:37Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Circuit Symmetry Verification Mitigates Quantum-Domain Impairments [69.33243249411113]
  We propose circuit-oriented symmetry verification that are capable of verifying the commutativity of quantum circuits without the knowledge of the quantum state. In particular, we propose the Fourier-temporal stabilizer (STS) technique, which generalizes the conventional quantum-domain formalism to circuit-oriented stabilizers.
  arXiv  Detail & Related papers  (2021-12-27T21:15:35Z)
• Parametrized Complexity of Quantum Inspired Algorithms [0.0]
  Two promising areas of quantum algorithms are quantum machine learning and quantum optimization. Motivated by recent progress in quantum technologies and in particular quantum software, research and industrial communities have been trying to discover new applications of quantum algorithms.
  arXiv  Detail & Related papers  (2021-12-22T06:19:36Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• 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)
• A Grand Unification of Quantum Algorithms [0.0]
  A number of quantum algorithms were recently tied together by a technique known as the quantum singular value transformation. This paper provides a tutorial through these developments, first illustrating how quantum signal processing may be generalized to the quantum eigenvalue transform. We then employ QSVT to construct intuitive quantum algorithms for search, phase estimation, and Hamiltonian simulation.
  arXiv  Detail & Related papers  (2021-05-06T17:46:33Z)
• Resource-efficient encoding algorithm for variational bosonic quantum simulations [0.0]
  In the Noisy Intermediate Scale Quantum (NISQ) era of quantum computing, quantum resources are limited. We present a resource-efficient quantum algorithm for bosonic ground and excited state computations.
  arXiv  Detail & Related papers  (2021-02-23T19:00:05Z)

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.