QUBO formulations for numerical quantum computing
- URL: http://arxiv.org/abs/2106.10819v4
- Date: Sun, 23 Jan 2022 18:26:04 GMT
- Title: QUBO formulations for numerical quantum computing
- Authors: Kyungtaek Jun
- Abstract summary: Harrow-Hassidim-Lloyd algorithm is a monumental quantum algorithm for solving linear systems on gate model quantum computers.
We will find unconstrained binary optimization (QUBO) models for a vector x that satisfies Ax=b.
We validate those QUBO models on the D-Wave system and discuss the results.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: With the advent of quantum computers, many quantum computing algorithms are
being developed. Solving linear systems is one of the most fundamental problems
in almost all science and engineering. The Harrow-Hassidim-Lloyd algorithm, a
monumental quantum algorithm for solving linear systems on gate model quantum
computers, was invented and several advanced variations have been developed.
For a given n by n matrix A and a vector b, we will find unconstrained binary
optimization (QUBO) models for a vector x that satisfies Ax=b. To formulate
QUBO models for a linear system solving problem, we make use of a linear
least-square problem with binary representation of the solution. We validate
those QUBO models on the D-Wave system and discuss the results. For a simple
system, we provide a Python code to calculate the matrix characterizing the
relationship between the variables and to print the test code that can be used
directly in the D-Wave system.
Related papers
- Shadow Quantum Linear Solver: A Resource Efficient Quantum Algorithm for Linear Systems of Equations [0.8437187555622164]
We present an original algorithmic procedure to solve the Quantum Linear System Problem (QLSP) on a digital quantum device.
The result is a quantum algorithm avoiding the need for large controlled unitaries, requiring a number of qubits that is logarithmic in the system size.
We apply this to a physical problem of practical relevance, by leveraging decomposition theorems from linear algebra to solve the discretized Laplace Equation in a 2D grid.
arXiv Detail & Related papers (2024-09-13T15:46:32Z) - Hybrid quantum-classical and quantum-inspired classical algorithms for
solving banded circulant linear systems [0.8192907805418583]
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.
arXiv Detail & Related papers (2023-09-20T16:27:16Z) - Carleman linearization based efficient quantum algorithm for higher
order polynomial differential equations [2.707154152696381]
We present an efficient quantum algorithm to simulate nonlinear differential equations with vector fields of arbitrary degree on quantum platforms.
Models of physical systems governed by ordinary differential equations (ODEs) or partial differential equation (PDEs) can be challenging to solve on classical computers.
arXiv Detail & Related papers (2022-12-21T05:21:52Z) - Accelerating the training of single-layer binary neural networks using
the HHL quantum algorithm [58.720142291102135]
We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL)
This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
arXiv Detail & Related papers (2022-10-23T11:58:05Z) - A near-term quantum algorithm for solving linear systems of equations based on the Woodbury identity [0.602276990341246]
We describe a quantum algorithm for solving linear systems of equations that avoids problems such as barren plateaus and local optima.
Our algorithm is based on the Woodbury identity, which analytically describes the inverse of a matrix that is a low-rank modification of another (easily-invertible) matrix.
We estimate the inner product involving the solution of a system of more than 16 million equations with 2% error using IBM's Auckland quantum computer.
arXiv Detail & Related papers (2022-05-02T04:32:01Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
We propose quantum algorithms for matrix operations using the "Sender-Receiver" model.
These quantum protocols can be used as subroutines in other quantum schemes.
arXiv Detail & Related papers (2022-02-10T08:12:20Z) - Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations [0.22940141855172036]
The complexity of our algorithm is $O(rm polylog(n/epsilon))$, which provides an exponential improvement over the optimal classical algorithm in dimension $n$.
Our algorithm exponentially accelerates the solution of QNSE and has wide applications in all kinds of nonlinear problems.
arXiv Detail & Related papers (2021-12-03T00:27:16Z) - 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) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth.
We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model.
In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06:00Z) - Joint Deep Reinforcement Learning and Unfolding: Beam Selection and
Precoding for mmWave Multiuser MIMO with Lens Arrays [54.43962058166702]
millimeter wave (mmWave) multiuser multiple-input multiple-output (MU-MIMO) systems with discrete lens arrays have received great attention.
In this work, we investigate the joint design of a beam precoding matrix for mmWave MU-MIMO systems with DLA.
arXiv Detail & Related papers (2021-01-05T03:55:04Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression.
We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
arXiv Detail & Related papers (2020-11-09T01:13:07Z)
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.