Alleviating the quantum Big-$M$ problem
- URL: http://arxiv.org/abs/2307.10379v3
- Date: Thu, 8 Feb 2024 10:17:30 GMT
- Title: Alleviating the quantum Big-$M$ problem
- Authors: Edoardo Alessandroni, Sergi Ramos-Calderer, Ingo Roth, Emiliano
Traversi, Leandro Aolita
- Abstract summary: Classically known as the "Big-$M$" problem, it affects the physical energy scale.
We take a systematic, encompassing look at the quantum big-$M$ problem, revealing NP-hardness in finding the optimal $M$.
We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks.
- Score: 0.237499051649312
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A major obstacle for quantum optimizers is the reformulation of constraints
as a quadratic unconstrained binary optimization (QUBO). Current QUBO
translators exaggerate the weight $M$ of the penalty terms. Classically known
as the "Big-$M$" problem, the issue becomes even more daunting for quantum
solvers, since it affects the physical energy scale. We take a systematic,
encompassing look at the quantum big-$M$ problem, revealing NP-hardness in
finding the optimal $M$ and establishing bounds on the Hamiltonian spectral gap
$\Delta$, inversely related to the expected run-time of quantum solvers. We
propose a practical translation algorithm, based on SDP relaxation, that
outperforms previous methods in numerical benchmarks. Our algorithm gives
values of $\Delta$ orders of magnitude greater, e.g. for portfolio optimization
instances. Solving such instances with an adiabatic algorithm on 6-qubits of an
IonQ device, we observe significant advantages in time to solution and average
solution quality. Our findings are relevant to quantum and quantum-inspired
solvers alike.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
We introduce an approach to compute the minimum distance of quantum stabilizer codes by reformulating the problem as a Quadratic Unconstrained Binary Optimization problem.
We demonstrate practical viability of our method by comparing the performance of purely classical algorithms with the D-Wave Advantage 4.1 quantum annealer.
arXiv Detail & Related papers (2024-04-26T21:29:42Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin
Models [8.463477025989542]
We take advantage of a digitized-counterdiabatic quantum optimization (DCQO) algorithm to find an optimal solution of the $p$-spin model up to 4-local interactions.
By further optimizing parameters using variational methods, we solve with unit accuracy 2-spin, 3-spin, and 4-spin problems for $100%$, $93%$, and $83%$ of instances, respectively.
arXiv Detail & Related papers (2023-11-11T22:49:16Z) - 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 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) - Sampling Frequency Thresholds for Quantum Advantage of Quantum
Approximate Optimization Algorithm [0.7046417074932257]
We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers.
We find that classical solvers are capable of producing high-quality approximate solutions in linear time complexity.
Other problems, such as different graphs, weighted MaxCut, maximum independent set, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.
arXiv Detail & Related papers (2022-06-07T20:59:19Z) - 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) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
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.