Hybrid quantum-classical and quantum-inspired classical algorithms for
solving banded circulant linear systems
- URL: http://arxiv.org/abs/2309.11451v1
- Date: Wed, 20 Sep 2023 16:27:16 GMT
- Title: Hybrid quantum-classical and quantum-inspired classical algorithms for
solving banded circulant linear systems
- Authors: Po-Wei Huang, Xiufan Li, Kelvin Koor, Patrick Rebentrost
- Abstract summary: We present an efficient algorithm based on convex optimization of combinations of quantum states to solve for banded circulant linear systems.
By decomposing banded circulant matrices into cyclic permutations, our approach produces approximate solutions to such systems with a combination of quantum states linear to $K$.
We validate our methods with classical simulations and actual IBM quantum computer implementation, showcasing their applicability for solving physical problems such as heat transfer.
- Score: 0.8192907805418583
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Solving linear systems is of great importance in numerous fields. In
particular, circulant systems are especially valuable for efficiently finding
numerical solutions to physics-related differential equations. Current quantum
algorithms like HHL or variational methods are either resource-intensive or may
fail to find a solution. We present an efficient algorithm based on convex
optimization of combinations of quantum states to solve for banded circulant
linear systems whose non-zero terms are within distance $K$ of the main
diagonal. By decomposing banded circulant matrices into cyclic permutations,
our approach produces approximate solutions to such systems with a combination
of quantum states linear to $K$, significantly improving over previous
convergence guarantees, which require quantum states exponential to $K$. We
propose a hybrid quantum-classical algorithm using the Hadamard test and the
quantum Fourier transform as subroutines and show its PromiseBQP-hardness.
Additionally, we introduce a quantum-inspired algorithm with similar
performance given sample and query access. We validate our methods with
classical simulations and actual IBM quantum computer implementation,
showcasing their applicability for solving physical problems such as heat
transfer.
Related papers
- Benchmarking Variational Quantum Eigensolvers for Entanglement Detection in Many-Body Hamiltonian Ground States [37.69303106863453]
Variational quantum algorithms (VQAs) have emerged in recent years as a promise to obtain quantum advantage.
We use a specific class of VQA named variational quantum eigensolvers (VQEs) to benchmark them at entanglement witnessing and entangled ground state detection.
Quantum circuits whose structure is inspired by the Hamiltonian interactions presented better results on cost function estimation than problem-agnostic circuits.
arXiv Detail & Related papers (2024-07-05T12:06:40Z) - Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO)
Our purely quantum approach eliminates the dependency on classical variational quantum algorithms.
It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
arXiv Detail & Related papers (2024-05-22T18:11:42Z) - Nonlinear dynamics as a ground-state solution on quantum computers [39.58317527488534]
We present variational quantum algorithms (VQAs) that encode both space and time in qubit registers.
The spacetime encoding enables us to obtain the entire time evolution from a single ground-state computation.
arXiv Detail & Related papers (2024-03-25T14:06:18Z) - Preconditioning for a Variational Quantum Linear Solver [0.0]
We numerically demonstrate a notable reduction in the required ansatz depth, demonstrating that preconditioning is useful for quantum algorithms.
Our findings suggest that combining classical computing techniques, such as preconditioning, with quantum algorithms can significantly enhance the performance of NISQ algorithms.
arXiv Detail & Related papers (2023-12-25T08:50:22Z) - A Universal Quantum Algorithm for Weighted Maximum Cut and Ising
Problems [0.0]
We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems.
We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian.
Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
arXiv Detail & Related papers (2023-06-10T23:28:13Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
We propose a hybrid quantum-classical algorithm for robust fitting.
Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs.
We present results obtained using an actual quantum computer.
arXiv Detail & Related papers (2022-01-25T05:59:24Z) - 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 Linear Solver with Dynamic Ansatz [0.0]
Variational quantum algorithms have found success in the NISQ era owing to their hybrid quantum-classical approach.
We introduce the dynamic ansatz in the Variational Quantum Linear Solver for a system of linear algebraic equations.
We demonstrate the algorithm advantage in comparison to the standard, static ansatz by utilizing fewer quantum resources.
arXiv Detail & Related papers (2021-07-19T03:42:25Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard.
We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware.
The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z) - Quantum Algorithms for Solving Ordinary Differential Equations via
Classical Integration Methods [1.802439717192088]
We explore utilizing quantum computers for the purpose of solving differential equations.
We devise and simulate corresponding digital quantum circuits, and implement and run a 6$mathrmth$ order Gauss-Legendre collocation method.
As promising future scenario, the digital arithmetic method could be employed as an "oracle" within quantum search algorithms for inverse problems.
arXiv Detail & Related papers (2020-12-17T09:49:35Z) - Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular
Simulations on Quantum Computing Devices [0.0]
We introduce a quantum solver of contracted eigenvalue equations, the quantum analogue of classical methods for the energies.
We demonstrate the algorithm though computations on both a quantum simulator and two IBM quantum processing units.
arXiv Detail & Related papers (2020-04-23T18:35:26Z)
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.