Performant near-term quantum combinatorial optimization
- URL: http://arxiv.org/abs/2404.16135v1
- Date: Wed, 24 Apr 2024 18:49:07 GMT
- Title: Performant near-term quantum combinatorial optimization
- Authors: Titus D. Morris, Phillip C. Lotshaw,
- Abstract summary: We present a variational quantum algorithm for solving optimization problems with linear-depth circuits.
Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target function.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum, while resources are minimized by pruning optimized gates that are close to the identity. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. This performant and resource-minimal approach is a promising candidate for potential quantum computational advantages on near-term quantum computing hardware.
Related papers
- Ising formulation of integer optimization problems for utilizing quantum
annealing in iterative improvement strategy [1.14219428942199]
We propose an Ising formulation of integer optimization problems to utilize quantum annealing in the iterative improvement strategy.
We analytically show that a first-order phase transition is successfully avoided for a fully connected ferro Potts model if the overlap between a ground state and a candidate solution exceeds a threshold.
arXiv Detail & Related papers (2022-11-08T02:12:49Z) - Monte Carlo Tree Search based Hybrid Optimization of Variational Quantum
Circuits [7.08228773002332]
We propose a new variational quantum algorithm called MCTS-QAOA.
It combines a Monte Carlo tree search method with an improved natural policy gradient solver to optimize the discrete and continuous variables in the quantum circuit.
We find that MCTS-QAOA has excellent noise-resilience properties and outperforms prior algorithms in challenging instances of the generalized QAOA.
arXiv Detail & Related papers (2022-03-30T23:15:21Z) - A Gauss-Newton based Quantum Algorithm for Combinatorial Optimization [0.0]
We present a Gauss-Newton based quantum algorithm (GNQA) for optimization problems that, under optimal conditions, rapidly converge towards one of the optimal solutions without being trapped in local minima or plateaus.
Our approach mitigates those by employing a tensor product state that accurately represents the optimal solution, and an appropriate function for the Hamiltonian, containing all the combinations of binary variables.
Numerical experiments presented here demonstrate the effectiveness of our approach, and they show that GNQA outperforms other optimization methods in both convergence properties and accuracy for all problems considered here.
arXiv Detail & Related papers (2022-03-25T23:49:31Z) - 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) - Markov Chain Monte-Carlo Enhanced Variational Quantum Algorithms [0.0]
We introduce a variational quantum algorithm that uses Monte Carlo techniques to place analytic bounds on its time-complexity.
We demonstrate both the effectiveness of our technique and the validity of our analysis through quantum circuit simulations for MaxCut instances.
arXiv Detail & Related papers (2021-12-03T23:03:44Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation.
We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
arXiv Detail & Related papers (2021-08-18T09:26:17Z) - 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) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications.
Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem.
In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
arXiv Detail & Related papers (2020-03-11T13:52:41Z) - Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical
and Quantum Computers [3.04585143845864]
We present a decomposition-based approach to extend the applicability of current approaches to "quadratic plus convex" mixed binary optimization problems.
We show that the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms)
The validity of the approach is then showcased by numerical results obtained on several optimization problems via simulations with VQE and QAOA on the quantum circuits implemented in Qiskit.
arXiv Detail & Related papers (2020-01-07T14:43:13Z)
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.