A competitive NISQ and qubit-efficient solver for the LABS problem
- URL: http://arxiv.org/abs/2506.17391v1
- Date: Fri, 20 Jun 2025 18:00:02 GMT
- Title: A competitive NISQ and qubit-efficient solver for the LABS problem
- Authors: Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita,
- Abstract summary: Pauli Correlation.<n>(PCE) has recently been introduced as a qubit-efficient approach to optimization problems within variational quantum algorithms.<n>We extend the PCE-based framework to solve the Low Autocorrelation Binary Sequences (LABS) problem.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Pauli Correlation Encoding (PCE) has recently been introduced as a qubit-efficient approach to combinatorial optimization problems within variational quantum algorithms (VQAs). The method offers a polynomial reduction in qubit count and a super-polynomial suppression of barren plateaus. Moreover, it has been shown to feature a competitive performance with classical state-of-the-art methods on MaxCut. Here, we extend the PCE-based framework to solve the Low Autocorrelation Binary Sequences (LABS) problem. This is a notoriously hard problem with a single instance per problem size, considered a major benchmark for classical and quantum solvers. We simulate our PCE variational quantum solver for LABS instances of up to $N=44$ binary variables using only $n=6$ qubits and a brickwork circuit Ansatz of depth $10$, with a total of $30$ two-qubit gates, i.e. well inside the NISQ regime. We observe a significant scaling advantage in the total time to (the exact) solution of our solver with respect to previous studies using QAOA, and even a modest advantage with respect to the leading classical heuristic, given by Tabu search. Our findings point at PCE-based solvers as a promising quantum-inspired classical heuristic for hard-in-practice problems as well as a tool to reduce the resource requirements for actual quantum algorithms, with both fundamental and applied potential implications.
Related papers
- Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities [23.221938246770712]
Bandits with knapsacks (BwK) constitute a model that combines integer programming with online learning.<n>We study the BwK model in the setting of quantum computing, where both reward and resource consumption can be accessed via quantum oracles.<n>Compared to previous works on quantum algorithms for multi-armed bandits, our study is the first to consider bandit models with resource constraints.
arXiv Detail & Related papers (2025-07-06T15:52:37Z) - A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
We experimentally test how existing quantum processing units (QPUs) perform as subsolvers within a multilevel strategy.
We find approximate solutions to $10$ instances of fully connected $82$-qubit Sherrington-Kirkpatrick graphs.
We observe that quantum optimization results are competitive regarding the quality of solutions compared to classicals.
arXiv Detail & Related papers (2024-08-14T20:06:32Z) - 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) - Variational quantum eigensolver with linear depth problem-inspired
ansatz for solving portfolio optimization in finance [7.501820750179541]
This paper introduces the variational quantum eigensolver (VQE) to solve portfolio optimization problems in finance.
We implement the HDC experiments on the superconducting quantum computer Wu Kong with up to 55 qubits.
The HDC scheme shows great potential for achieving quantum advantage in the NISQ era.
arXiv Detail & Related papers (2024-03-07T07:45:47Z) - 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) - Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem [8.738180371389097]
The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers.
Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem.
We observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers.
arXiv Detail & Related papers (2023-08-04T14:17:21Z) - Alleviating the quantum Big-$M$ problem [0.237499051649312]
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.
arXiv Detail & Related papers (2023-07-19T18:00:05Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry.
In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
arXiv Detail & Related papers (2023-06-14T13:44:35Z) - 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) - Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
We present an alternative method that does not require extra slack variables.
We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem.
This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
arXiv Detail & Related papers (2022-11-25T06:05:18Z) - 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)
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.