Combining Digital-Counterdiabatic Quantum Optimization with GPU-accelerated Memetic Tabu Search to solve the Low Autocorrelation Binary Sequences problem at unprecedented scale.
View on GitHubThe Low Autocorrelation Binary Sequences (LABS) problem seeks binary sequences with minimal autocorrelation sidelobes. It's a classic combinatorial optimization problem with deep connections to physics and signal processing.
Given a binary sequence s = (s₁, s₂, ..., sₙ) where each sᵢ ∈ {-1, +1}, we want to minimize the energy function based on autocorrelation values.
Classical approaches exhibit exponential O(1.34ᴺ) scaling. For N=66, the search space contains 2⁶⁶ possible sequences. Finding optimal solutions requires either exhaustive search or sophisticated heuristics.
We implement a modified DCQO approach with a hybrid impulse-to-adiabatic transition and variable λ schedule. The quantum circuit first explores the solution space rapidly, then transitions to careful convergence.
Rapid exploration of the solution space early in optimization, escaping local minima more effectively than pure adiabatic methods.
Slower, controlled evolution at the end to ensure convergence to high-quality solutions while maintaining quantum coherence.
Quantum-seeded Memetic Tabu Search running on 8x A100 GPUs with custom CUDA kernels for parallel energy evaluation.
Tensor network contraction via NVIDIA's cuTensorNet library avoids explicit 2ᴺ state vector storage for larger problem sizes.