Efficient Internal Strategies in Quantum Relaxation based Branch-and-Bound
- URL: http://arxiv.org/abs/2405.00935v1
- Date: Thu, 2 May 2024 01:28:52 GMT
- Title: Efficient Internal Strategies in Quantum Relaxation based Branch-and-Bound
- Authors: Hiromichi Matsuyama, Wei-hao Huang, Kohji Nishimura, Yu Yamashiro,
- Abstract summary: We develop Quantum Relaxation based Branch-and-Bound ( QR-BnB)
QR-BnB is a method incorporating quantum relaxation into the Branch-and-Bound framework.
We show that our variable selection strategy via the expectation value of the Pauli operators gives better convergence than the naive random choice.
- Score: 1.3499500088995464
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A combinatorial optimization problem is to find an optimal solution under the constraints. This is one of the potential applications for quantum computers. Quantum Random Access Optimization (QRAO) is the quantum optimization algorithm that encodes multiple classical variables into a single qubit to construct a quantum Hamiltonian, thereby reducing the number of qubits required. The ground energy of the QRAO Hamiltonian provides a lower bound on the original problem's optimal value before encoding. This property allows the QRAO Hamiltonian to be used as a relaxation of the original problem, and it is thus referred to as a quantum relaxed Hamiltonian. In the Branch-and-Bound method, solving the relaxation problem plays a significant role. In this study, we developed Quantum Relaxation based Branch-and-Bound (QR-BnB), a method incorporating quantum relaxation into the Branch-and-Bound framework. We solved the MaxCut Problem and the Travelling Salesman Problem in our experiments. In all instances in this study, we obtained the optimal solution whenever we successfully computed the exact lower bound through quantum relaxation. Internal strategies, such as relaxation methods and variable selection, influence the convergence of the Branch-and-Bound. Thus, we have further developed the internal strategies for QR-BnB and examined how these strategies influence its convergence. We show that our variable selection strategy via the expectation value of the Pauli operators gives better convergence than the naive random choice. QRAO deals with only unconstrained optimization problems, but QR-BnB can handle constraints more flexibly because of the Branch-and-Bound processes on the classical computing part. We demonstrate that in our experiments with the Travelling Salesman Problem, the convergence of QR-BnB became more than three times faster by using the information in the constraints.
Related papers
- Qubit-efficient quantum combinatorial optimization solver [0.0]
We develop a qubit-efficient algorithm that overcomes the limitation by mapping a candidate bit solution to an entangled wave function of fewer qubits.
This approach could benefit near-term intermediate-scale and future fault-tolerant small-scale quantum devices.
arXiv Detail & Related papers (2024-07-22T11:02:13Z) - Bayesian Optimization Priors for Efficient Variational Quantum Algorithms [0.0]
Quantum computers currently rely on a quantum-classical approach known as Variational Quantum Algorithms (VQAs) to solve problems.
We propose a hybrid framework for basic computational optimization that reduces the number of shots per time is charged.
Using both proposed features, we show that using both proposed features statistically outperforms an implementation within VQAs for simulations.
arXiv Detail & Related papers (2024-06-20T18:00:12Z) - Quantum Relaxation for Solving Multiple Knapsack Problems [7.003282322403712]
Combinatorial problems are a common challenge in business, requiring finding optimal solutions under specified constraints.
In this study, we investigate a hybrid quantum-classical method for constrained optimization problems.
Our proposed method relies on relaxations to local quantum Hamiltonians, defined through commutative maps.
arXiv Detail & Related papers (2024-04-30T11:40:07Z) - Quantum Bayesian Optimization [64.58749619145908]
We introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm.
It is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting.
Thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm.
arXiv Detail & Related papers (2023-10-09T03:10:42Z) - 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) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
We introduce a technique that uses quantum Zeno dynamics to solve optimization problems with multiple arbitrary constraints, including inequalities.
We show that the dynamics of quantum optimization can be efficiently restricted to the in-constraint subspace on a fault-tolerant quantum computer.
arXiv Detail & Related papers (2022-09-29T18:00:40Z) - Constrained Quantum Optimization for Extractive Summarization on a
Trapped-ion Quantum Computer [13.528362112761805]
We show the largest-to-date execution of a quantum optimization algorithm that preserves constraints on quantum hardware.
We execute XY-QAOA circuits that restrict the quantum evolution to the in-constraint subspace, using up to 20 qubits and a two-qubit gate depth of up to 159.
We discuss the respective trade-offs of the algorithms and implications for their execution on near-term quantum hardware.
arXiv Detail & Related papers (2022-06-13T16:21:04Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution.
We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines.
Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
arXiv Detail & Related papers (2022-05-24T03:49:10Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z) - 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)
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.