Scaling advantage with quantum-enhanced memetic tabu search for LABS

• URL: http://arxiv.org/abs/2511.04553v1
• Date: Thu, 06 Nov 2025 17:07:10 GMT
• Title: Scaling advantage with quantum-enhanced memetic tabu search for LABS
• Authors: Alejandro Gomez Cadavid, Pranav Chandarana, Sebastián V. Romero, Jan Trautmann, Enrique Solano, Taylor Lee Patti, Narendra N. Hegade,
• Abstract summary: We introduce quantum-enhanced memetic tabu search (QE-MTS) for the low-autocorrelation binary sequence (LABS) problem.<n>By seeding the classical MTS with high-quality initial states from digitized counterdiabatic quantum optimization (DCQO), our method suppresses the empirical time-to-solution scaling.<n>This scaling surpasses the best-known classical $mathcalO (1.34N)$ and improves upon the $mathcalO (1.46N)$ of the quantum approximate optimization algorithm.
• Score: 32.505127447635864
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce quantum-enhanced memetic tabu search (QE-MTS), a non-variational hybrid algorithm that achieves state-of-the-art scaling for the low-autocorrelation binary sequence (LABS) problem. By seeding the classical MTS with high-quality initial states from digitized counterdiabatic quantum optimization (DCQO), our method suppresses the empirical time-to-solution scaling to $\mathcal{O}(1.24^N)$ for sequence length $N \in [27,37]$. This scaling surpasses the best-known classical heuristic $\mathcal{O}(1.34^N)$ and improves upon the $\mathcal{O}(1.46^N)$ of the quantum approximate optimization algorithm, achieving superior performance with a $6\times$ reduction in circuit depth. A two-stage bootstrap analysis confirms the scaling advantage and projects a crossover point at $N \gtrsim 47$, beyond which QE-MTS outperforms its classical counterpart. These results provide evidence that quantum enhancement can directly improve the scaling of classical optimization algorithms for the paradigmatic LABS problem.

Related papers

• Quantum-Enhanced Neural Contextual Bandit Algorithms [50.880384999888044]
  This paper introduces the Quantum Neural Tangent Kernel-Upper Confidence Bound (QNTK-UCB) algorithm.<n>QNTK-UCB is a novel algorithm that leverages the Quantum Neural Tangent Kernel (QNTK) to address these limitations.
  arXiv  Detail & Related papers  (2026-01-06T09:58:14Z)
• Verifiable Quantum Advantage via Optimized DQI Circuits [2.149968465453488]
  Decoded Quantum Interferometry (DQI) provides a framework for superpolynomial quantum speedups.<n>We apply DQI to the Optimal Polynomial Intersection (OPI) problem, whose code is Reed-Solomon (RS)<n>We establish that DQI for OPI is the first known candidate for verifiable quantum advantage with optimal speedup.
  arXiv  Detail & Related papers  (2025-10-13T03:19:28Z)
• A competitive NISQ and qubit-efficient solver for the LABS problem [0.0]
  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.
  arXiv  Detail & Related papers  (2025-06-20T18:00:02Z)
• Quantum Non-Linear Bandit Optimization [2.7718037613443127]
  We study non-linear bandit optimization where the learner maximizes a black-box function with zeroth order function oracle.<n>We propose the new Q-NLB-UCB algorithm which uses the novel parametric function approximation technique.<n>We prove that the regret bound of Q-NLB-UCB is not only $O(mathrmpolylog T)$ but also input dimension-free.
  arXiv  Detail & Related papers  (2025-03-04T21:53:33Z)
• Enhancing Quantum State Reconstruction with Structured Classical Shadows [22.432806329828782]
  We introduce a projected classical shadow (PCS) method with guaranteed performance for QST based on Haar-random projective measurements.<n>PCS extends the standard CS method by incorporating a projection step onto the target subspace.<n>For matrix product operator states, we demonstrate that the PCS method can recover the ground-truth state with $O(n2)$ total state copies.
  arXiv  Detail & Related papers  (2025-01-06T17:09:38Z)
• 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)
• 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)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria.<n>This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)

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.