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
- 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) - 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) - 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) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - 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) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices.
We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT)
Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
arXiv Detail & Related papers (2020-10-01T18:14:11Z) - Efficient phase-factor evaluation in quantum signal processing [1.3614427997190908]
Quantum signal processing (QSP) is a powerful quantum algorithm to exactly implement matrixs on quantum computers.
There is so far no classically stable algorithm allowing computation of the phase factors that are needed to build QSP circuits.
We present here an optimization based method that can accurately compute the phase factors using standard double precision arithmetic operations.
arXiv Detail & Related papers (2020-02-26T17:23:55Z)
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.