Combinatorial optimization through variational quantum power method
- URL: http://arxiv.org/abs/2007.01004v3
- Date: Tue, 29 Jun 2021 15:31:49 GMT
- Title: Combinatorial optimization through variational quantum power method
- Authors: Ammar Daskin
- Abstract summary: We present a variational quantum circuit method for the power iteration.
It can be used to find the eigenpairs of unitary matrices and so their associated Hamiltonians.
The circuit can be simulated on the near term quantum computers with ease.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The power method (or iteration) is a well-known classical technique that can
be used to find the dominant eigenpair of a matrix. Here, we present a
variational quantum circuit method for the power iteration, which can be used
to find the eigenpairs of unitary matrices and so their associated
Hamiltonians. We discuss how to apply the circuit to combinatorial optimization
problems formulated as a quadratic unconstrained binary optimization and
discuss its complexity. In addition, we run numerical simulations for random
problem instances with up to 21 parameters and observe that the method can
generate solutions to the optimization problems with only a few number of
iterations and the growth in the number of iterations is polynomial in the
number of parameters. Therefore, the circuit can be simulated on the near term
quantum computers with ease.
Related papers
- High order schemes for solving partial differential equations on a quantum computer [0.0]
We show that higher-order methods can reduce the number of qubits necessary for discretization, similar to the classical case.
This result has important consequences for the practical application of quantum algorithms based on Hamiltonian evolution.
arXiv Detail & Related papers (2024-12-26T14:21:59Z) - Tensor networks based quantum optimization algorithm [0.0]
In optimization, one of the well-known classical algorithms is power iterations.
We propose a quantum realiziation to circumvent this pitfall.
Our methodology becomes instance agnostic and thus allows one to address black-box optimization within the framework of quantum computing.
arXiv Detail & Related papers (2024-04-23T13:49:11Z) - Quantum Iterative Methods for Solving Differential Equations with Application to Computational Fluid Dynamics [14.379311972506791]
We propose quantum methods for solving differential equations based on a gradual improvement of the solution via an iterative process.
We benchmark the approach on paradigmatic fluid dynamics problems.
arXiv Detail & Related papers (2024-04-12T17:08:27Z) - Polynomial-time Solver of Tridiagonal QUBO and QUDO problems with Tensor Networks [41.94295877935867]
We present an algorithm for solving tridiagonal Quadratic Unconstrained Binary Optimization (QUBO) problems and Quadratic Unconstrained Discrete Optimization (QUDO) problems with one-neighbor interactions.
Our method is based on the simulation of a quantum state to which we will apply an imaginary time evolution and perform a series of partial traces to obtain the state of maximum amplitude.
arXiv Detail & Related papers (2023-09-19T10:45:15Z) - Sub-universal variational circuits for combinatorial optimization
problems [0.0]
This work introduces a novel class of classical probabilistic circuits designed for generating quantum approximate solutions to optimization problems constructed using two-bit matrices.
Through a numerical study, we investigate the performance of our proposed variational circuits in solving the Max-Cut problem on various graphs of increasing sizes.
Our findings suggest that evaluating the performance of quantum variational circuits against variational circuits with sub-universal gate sets is a valuable benchmark for identifying areas where quantum variational circuits can excel.
arXiv Detail & Related papers (2023-08-29T02:16:48Z) - Efficient estimation of trainability for variational quantum circuits [43.028111013960206]
We find an efficient method to compute the cost function and its variance for a wide class of variational quantum circuits.
This method can be used to certify trainability for variational quantum circuits and explore design strategies that can overcome the barren plateau problem.
arXiv Detail & Related papers (2023-02-09T14:05:18Z) - Depth analysis of variational quantum algorithms for heat equation [0.0]
We consider three approaches to solve the heat equation on a quantum computer.
An exponential number of Pauli products in the Hamiltonian decomposition does not allow for the quantum speed up to be achieved.
The ansatz tree approach exploits an explicit form of the matrix what makes it possible to achieve an advantage over classical algorithms.
arXiv Detail & Related papers (2022-12-23T14:46:33Z) - 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) - 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) - 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) - 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)
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.