LABS

Low Autocorrelation Binary Sequences

Binary QUBO signal-processing dense NP-hard

Instances 99

Optimally solved 65 / 99

Variable range 2–100

Objective minimize

Overview

The Low Autocorrelation Binary Sequences (LABS) problem seeks binary sequences with minimal autocorrelation properties. This problem has applications in communications, radar systems, and cryptography, where low autocorrelation is desirable to minimize signal interference.

Problem Description

Given a sequence $\mathcal{S} = \{s_1, \ldots, s_n\}$ of spins $s_i \in \{-1,1\}$ for $i \in [n]$, we define:

Autocorrelations: $$ C_k(\mathcal{S}) \coloneqq \sum_{i = 1}^{n-k} s_i s_{i+k} $$

Energy (Objective Function): $$ E(\mathcal{S}) \coloneqq \sum_{k=1}^{n-1} C_k^2(\mathcal{S}) $$

Goal: Find the binary sequence $\mathcal{S}$ of length $n$ that minimizes $E(\mathcal{S})$.

Performance

Runtime to reach best-known objective

Sorted instances vs total runtime. A point (x, y) means x instances were solved within y seconds. Solid line + filled circle = proven exact; dashed line + open diamond = heuristic. Lower-right is better.

Classical (69 · heuristic) Quantum simulator (1 · heuristic) Quantum hardware (5 · heuristic)

Time-to-solution (TTS) to reach best-known objective

Same as the runtime cactus but uses the reported Time-to-Solution rather than total runtime. Solid = exact, dashed = heuristic.

Classical (69 · 20 exact, 49 heuristic)

Solution quality (performance profile)

Share of instances each group brings within a given optimality gap of the best-known objective. Higher is better; the value at “best” is the share solved exactly.

Classical (99) Quantum simulator (1) Quantum hardware (5)

Runtime scaling with instance size

Fastest feasible runtime (log scale) per instance versus Length N — shows how each group scales.

Classical (99) Quantum simulator (1) Quantum hardware (5)

Submissions (9)

Method	Submitter	Type	Date	Instances
dSB	Tim Bode	Classical	2026-08-20	99
Quicopt	Tim Bode	Classical	2026-08-15	99
PDBOspin	Wenbo Liu (UCAS), Akang Wang (SRIBD/CUHKSZ), Dun Ma (UCAS), Hongyi Jiang (CityUHK), Jianghua Wu (SRIBD), Wenguo Yang (UCAS)	Classical	2026-07-04	99
PDBO	Wenbo Liu (UCAS), Akang Wang (SRIBD/CUHKSZ), Dun Ma (UCAS), Hongyi Jiang (CityUHK), Jianghua Wu (SRIBD), Wenguo Yang (UCAS)	Classical	2026-07-04	99
Arvak	Daniel Hinderink	Quantum sim	2026-03-08	1
QAOA	Angelika Widl, Daniel Egger, Juris Ulmanis, Christoph Regner	Quantum HW	2025-11-17	8
Abs2	Maximilian Schicker	Classical	2025-02-21	99
BF-DCQO	Narendra N. Hegade, Alejandro Gomez Cadavid	Quantum HW	2025-01-20	1
MIP	Maximilian Schicker	Classical	20241229	99

Instances (99)

99 of 99

Name	Length N	Best objective	Source	Status	Download
labs002	2	1	Reference solution	Optimal	↓ raw
labs003	3	1	Reference solution	Optimal	↓ raw
labs004	4	2	Reference solution	Optimal	↓ raw
labs005	5	2	Reference solution	Optimal	↓ raw
labs006	6	7	Reference solution	Optimal	↓ raw
labs007	7	3	Reference solution	Optimal	↓ raw
labs008	8	8	Reference solution	Optimal	↓ raw
labs009	9	12	Reference solution	Optimal	↓ raw
labs010	10	13	Reference solution	Optimal	↓ raw
labs011	11	5	Reference solution	Optimal	↓ raw
labs012	12	10	Reference solution	Optimal	↓ raw
labs013	13	6	Reference solution	Optimal	↓ raw
labs014	14	19	Reference solution	Optimal	↓ raw
labs015	15	15	Reference solution	Optimal	↓ raw
labs016	16	24	Reference solution	Optimal	↓ raw
labs017	17	32	Reference solution	Optimal	↓ raw
labs018	18	25	Reference solution	Optimal	↓ raw
labs019	19	29	Reference solution	Optimal	↓ raw
labs020	20	26	Reference solution	Optimal	↓ raw
labs021	21	26	Reference solution	Optimal	↓ raw
labs022	22	39	Reference solution	Optimal	↓ raw
labs023	23	47	Reference solution	Optimal	↓ raw
labs024	24	36	Reference solution	Optimal	↓ raw
labs025	25	36	Reference solution	Optimal	↓ raw
labs026	26	45	Reference solution	Optimal	↓ raw
labs027	27	37	Reference solution	Optimal	↓ raw
labs028	28	50	Reference solution	Optimal	↓ raw
labs029	29	62	Reference solution	Optimal	↓ raw
labs030	30	59	Reference solution	Optimal	↓ raw
labs031	31	67	Reference solution	Optimal	↓ raw
labs032	32	64	Reference solution	Optimal	↓ raw
labs033	33	64	Reference solution	Optimal	↓ raw
labs034	34	65	Reference solution	Optimal	↓ raw
labs035	35	73	Reference solution	Optimal	↓ raw
labs036	36	82	Reference solution	Optimal	↓ raw
labs037	37	86	Reference solution	Optimal	↓ raw
labs038	38	87	Reference solution	Optimal	↓ raw
labs039	39	99	Reference solution	Optimal	↓ raw
labs040	40	108	Reference solution	Optimal	↓ raw
labs041	41	108	Reference solution	Optimal	↓ raw
labs042	42	101	Reference solution	Optimal	↓ raw
labs043	43	109	Reference solution	Optimal	↓ raw
labs044	44	122	Reference solution	Optimal	↓ raw
labs045	45	118	Reference solution	Optimal	↓ raw
labs046	46	131	Reference solution	Optimal	↓ raw
labs047	47	135	Reference solution	Optimal	↓ raw
labs048	48	140	Reference solution	Optimal	↓ raw
labs049	49	136	Reference solution	Optimal	↓ raw
labs050	50	153	Reference solution	Optimal	↓ raw
labs051	51	153	Reference solution	Optimal	↓ raw
labs052	52	166	Reference solution	Optimal	↓ raw
labs053	53	170	Reference solution	Optimal	↓ raw
labs054	54	175	Reference solution	Optimal	↓ raw
labs055	55	171	Reference solution	Optimal	↓ raw
labs056	56	192	Reference solution	Optimal	↓ raw
labs057	57	188	Reference solution	Optimal	↓ raw
labs058	58	197	Reference solution	Optimal	↓ raw
labs059	59	205	Reference solution	Optimal	↓ raw
labs060	60	218	Reference solution	Optimal	↓ raw
labs061	61	226	Reference solution	Optimal	↓ raw
labs062	62	235	Reference solution	Optimal	↓ raw
labs063	63	207	Reference solution	Optimal	↓ raw
labs064	64	208	Reference solution	Optimal	↓ raw
labs065	65	240	Reference solution	Optimal	↓ raw
labs066	66	257	Reference solution	Optimal	↓ raw
labs067	67	241	Reference solution	Best known	↓ raw
labs068	68	250	Reference solution	Best known	↓ raw
labs069	69	274	Reference solution	Best known	↓ raw
labs070	70	295	Reference solution	Best known	↓ raw
labs071	71	275	Reference solution	Best known	↓ raw
labs072	72	300	Reference solution	Best known	↓ raw
labs073	73	308	Reference solution	Best known	↓ raw
labs074	74	341	Reference solution	Best known	↓ raw
labs075	75	329	Reference solution	Best known	↓ raw
labs076	76	334	Reference solution	Best known	↓ raw
labs077	77	358	Reference solution	Best known	↓ raw
labs078	78	347	Reference solution	Best known	↓ raw
labs079	79	339	Reference solution	Best known	↓ raw
labs080	80	352	Reference solution	Best known	↓ raw
labs081	81	372	Reference solution	Best known	↓ raw
labs082	82	377	Reference solution	Best known	↓ raw
labs083	83	377	Reference solution	Best known	↓ raw
labs084	84	430	Reference solution	Best known	↓ raw
labs085	85	414	Reference solution	Best known	↓ raw
labs086	86	439	Reference solution	Best known	↓ raw
labs087	87	431	Reference solution	Best known	↓ raw
labs088	88	448	Reference solution	Best known	↓ raw
labs089	89	432	Reference solution	Best known	↓ raw
labs090	90	453	Reference solution	Best known	↓ raw
labs091	91	477	Reference solution	Best known	↓ raw
labs092	92	498	Reference solution	Best known	↓ raw
labs093	93	486	Reference solution	Best known	↓ raw
labs094	94	499	Reference solution	Best known	↓ raw
labs095	95	479	Reference solution	Best known	↓ raw
labs096	96	520	Reference solution	Best known	↓ raw
labs097	97	536	Reference solution	Best known	↓ raw
labs098	98	545	Reference solution	Best known	↓ raw
labs099	99	577	Reference solution	Best known	↓ raw
labs100	100	578	Reference solution	Best known	↓ raw

View on GitHub ↗ View Leaderboard Browse All Instances