Polynomial unconstrained binary optimisation inspired by optical
simulation
- URL: http://arxiv.org/abs/2106.13167v2
- Date: Sun, 11 Sep 2022 21:36:19 GMT
- Title: Polynomial unconstrained binary optimisation inspired by optical
simulation
- Authors: Dmitry A. Chermoshentsev, Aleksei O. Malyshev, Mert Esencan, Egor S.
Tiunov, Douglas Mendoza, Al\'an Aspuru-Guzik, Aleksey K. Fedorov and
Alexander I. Lvovsky
- Abstract summary: We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization.
We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance.
The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
- Score: 52.11703556419582
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose an algorithm inspired by optical coherent Ising machines to solve
the problem of polynomial unconstrained binary optimization (PUBO). We
benchmark the proposed algorithm against existing PUBO algorithms on the
extended Sherrington-Kirkpatrick model and random third-degree polynomial
pseudo-Boolean functions, and observe its superior performance. We also address
instances of practically relevant computational problems such as protein
folding and electronic structure calculations with problem sizes not accessible
to existing quantum annealing devices. The application of our algorithm to
protein folding and quantum chemistry problems sheds light on the shortcomings
of approximating the electronic structure problem by a PUBO problem, which, in
turn, puts into question the applicability of the unconstrained binary
optimization formulation, such as that of quantum annealers and coherent Ising
machines, in this context.
Related papers
- Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems.
In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems.
We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
arXiv Detail & Related papers (2024-04-17T11:00:12Z) - Compressed sensing enhanced by quantum approximate optimization algorithm [0.0]
We present a framework to deal with a range of large scale compressive sensing problems using a quantum subroutine.
Our results explore a promising path of applying quantum computers in the compressive sensing field.
arXiv Detail & Related papers (2024-03-26T05:26:51Z) - 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) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - Fermionic Quantum Approximate Optimization Algorithm [11.00442581946026]
We propose fermionic quantum approximate optimization algorithm (FQAOA) for solving optimization problems with constraints.
FQAOA tackle the constrains issue by using fermion particle number preservation to intrinsically impose them throughout QAOA.
We provide a systematic guideline for designing the driver Hamiltonian for a given problem Hamiltonian with constraints.
arXiv Detail & Related papers (2023-01-25T18:36:58Z) - A quantum-inspired tensor network method for constrained combinatorial
optimization problems [5.904219009974901]
We propose a quantum-inspired tensor-network-based algorithm for general locally constrained optimization problems.
Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem.
Our results show the effectiveness of this construction and potential applications.
arXiv Detail & Related papers (2022-03-29T05:44:07Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory.
We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
arXiv Detail & Related papers (2021-11-30T12:21:41Z) - 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) - 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.