Low Autocorrelation Binary Sequences

Abstract

Binary sequences with minimal autocorrelations have applications in communication engineering, mathematics and computer science. In statistical physics they appear as groundstates of the Bernasconi model. Finding these sequences is a notoriously hard problem, that so far can be solved only by exhaustive search. We review recent algorithms and present a new algorithm that finds optimal sequences of length $N$ in time $\Theta (N1.73^N)$. We computed all optimal sequences for $N\le 66$ and all optimal skewsymmetric sequences for $N\le 119$.

17 pages, 4 figures

Cited by in corpus (14)

• Challenges and Opportunities in Quantum Optimization
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Benchmarking Discrete Optimization Heuristics with IOHprofiler
• Quantum speedup of branch-and-bound algorithms
• Low-Autocorrelation Binary Sequences: On Improved Merit Factors and Runtime Predictions to Achieve Them
• Parallel Self-Avoiding Walks for a Low-Autocorrelation Binary Sequences Problem
• Quantum Annealing with chaotic driver Hamiltonians
• Quantum Optimization Benchmarking Library - The Intractable Decathlon
• SWIFT-FMQA: Enhancing Factorization Machine with Quadratic-Optimization Annealing via Sliding Window
• Dual-Step Optimization for Binary Sequences with High Merit Factors
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Phase-coded Radar Waveform Design with Quantum Annealing
• Resource-Efficient Quantum Optimization via Higher-Order Encoding