Quantum-Inspired Optimization over Permutation Groups
- URL: http://arxiv.org/abs/2212.02669v1
- Date: Tue, 6 Dec 2022 00:02:39 GMT
- Title: Quantum-Inspired Optimization over Permutation Groups
- Authors: Rathi Munukur, Bhaskar Roy Bardhan, Devesh Upadhyay, Joydip Ghosh
- Abstract summary: Quantum-inspired optimization (QIO) algorithms are computational techniques that emulate certain quantum mechanical effects on a classical hardware.
We develop an algorithmic framework, called Perm-QIO, to tailor QIO tools to solve an arbitrary optimization problem.
- Score: 0.2294014185517203
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Quantum-inspired optimization (QIO) algorithms are computational techniques
that emulate certain quantum mechanical effects on a classical hardware to
tackle a class of optimization tasks. QIO methods have so far been employed to
solve various binary optimization problems and a significant (polynomial)
computational speedup over traditional techniques has also been reported. In
this work, we develop an algorithmic framework, called Perm-QIO, to tailor QIO
tools to directly solve an arbitrary optimization problem, where the domain of
the underlying cost function is defined over a permutation group. Such problems
are not naturally recastable to a binary optimization and, therefore, are not
necessarily within the scope of direct implementation of traditional QIO tools.
We demonstrate the efficacy of Perm-QIO in leveraging the structure of
cost-landscape to find high-quality solutions for a class of vehicle routing
problems that belong to the category of non-trivial combinatorial optimization
over the space of permutations.
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) - Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks.
A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form.
This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method.
A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
arXiv Detail & Related papers (2023-12-28T23:15:18Z) - Quantum-Informed Recursive Optimization Algorithms [0.0]
We propose and implement a family of quantum-informed recursive optimization (QIRO) algorithms for optimization problems.
Our approach leverages quantum resources to obtain information that is used in problem-specific classical reduction steps.
We use backtracking techniques to further improve the performance of the algorithm without increasing the requirements on the quantum hardware.
arXiv Detail & Related papers (2023-08-25T18:02:06Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms.
Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability.
We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
arXiv Detail & Related papers (2023-07-17T20:11:56Z) - Quantum approximate optimization via learning-based adaptive
optimization [5.399532145408153]
Quantum approximate optimization algorithm (QAOA) is designed to solve objective optimization problems.
Our results demonstrate that the algorithm greatly outperforms conventional approximations in terms of speed, accuracy, efficiency and stability.
This work helps to unlock the full power of QAOA and paves the way toward achieving quantum advantage in practical classical tasks.
arXiv Detail & Related papers (2023-03-27T02:14:56Z) - Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
Current quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent Ising model suitable for the quantum device.
We propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits.
This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Prog-QAOA.
arXiv Detail & Related papers (2022-09-07T18:01:01Z) - Quantum variational optimization: The role of entanglement and problem
hardness [0.0]
We study the role of entanglement, the structure of the variational quantum circuit, and the structure of the optimization problem.
Our numerical results indicate an advantage in adapting the distribution of entangling gates to the problem's topology.
We find evidence that applying conditional value at risk type cost functions improves the optimization, increasing the probability of overlap with the optimal solutions.
arXiv Detail & Related papers (2021-03-26T14:06:54Z) - 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) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z) - 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)
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.