Quantum-enhanced Memetic Tabu Search Achieves Scaling to 10^6 for Low-autocorrelation Binary Sequence Problems

The challenge of generating long, low-autocorrelation binary sequences, crucial for applications like secure communications and radar systems, has long pushed the boundaries of computational power. Alejandro Gomez Cadavid, Pranav Chandarana, and Sebastián V. Romero, all from the University of the Basque Country EHU, alongside Jan Trautmann, Enrique Solano from the same institution, and Taylor Lee Patti from NVIDIA, now demonstrate a significant leap forward in solving this problem. Their work introduces a novel quantum-enhanced memetic tabu search algorithm that achieves state-of-the-art scaling, reducing the time needed to find optimal sequences. The team’s method, which combines classical and quantum techniques, surpasses the performance of existing classical algorithms and projects a clear advantage for even larger sequence lengths, offering compelling evidence that quantum computing can directly enhance the efficiency of practical optimisation tasks.

Quantum Advantage in Optimization Algorithms

Scientists are making significant strides in the quest for quantum advantage, the ability of quantum computers to solve problems intractable for even the most powerful classical computers. This research focuses on developing and refining quantum algorithms designed to tackle computationally hard optimization problems, including variations of adiabatic quantum computation, the quantum approximate optimization algorithm, and hybrid quantum-classical approaches. A key element of this work is the creation of challenging problem instances, such as spin glasses and problems mirroring protein folding or portfolio optimization, to rigorously test the performance of these algorithms. This research presents a multi-faceted approach, with a focus on developing a comprehensive benchmarking suite and innovative techniques for improving quantum algorithm accuracy and robustness.

The team has developed a robust set of problem instances designed to be genuinely hard for classical algorithms, crucial for reliably demonstrating quantum advantage. A key innovation is the combination of digitizing control fields and employing counterdiabatic techniques, particularly beneficial for near-term quantum devices. These techniques are specifically tailored for noisy intermediate-scale quantum devices, incorporating error mitigation and noise-aware optimization. Digitized adiabatic quantum computation, or DAQC, utilizes discrete steps instead of smoothly varying control fields, making the algorithm more resilient to noise and easier to implement on real quantum hardware.

Counterdiabatic quantum algorithms suppress unwanted transitions during quantum evolution, keeping the system in the desired state and improving solution accuracy. Warm starts, using classical solutions as initial states, help the quantum algorithm converge faster and find better solutions. Hybrid sequential quantum computing alternates between quantum and classical computations, leveraging the strengths of both. The research utilizes challenging problem instances, including spin glasses, complex disordered magnetic systems known to be NP-hard, and the MaxCut problem, a classic graph partitioning challenge.

Researchers also explore problems mirroring protein folding, with important applications in biology and medicine, and portfolio optimization, a financial problem involving optimal asset allocation. The team employs CUDA-Q, a software framework for developing and simulating quantum algorithms, and utilizes the IBM Quantum platform for experiments on real quantum hardware. The authors claim to have achieved a runtime quantum advantage for certain problem instances using their DAQC algorithm with counterdiabatic techniques, supported by experimental results on both simulated and real quantum hardware. While demonstrating definitive quantum advantage remains a challenge, this research represents a significant contribution to the field of quantum optimization. The development of DAQC with counterdiabatic techniques, combined with a robust benchmarking suite, provides a promising path towards achieving practical quantum advantage, potentially opening new possibilities for scientific discovery and technological innovation.

Hybrid Quantum and Classical Sequence Optimization

Scientists have developed a novel quantum-enhanced memetic tabu search (QE-MTS) algorithm to address the computationally demanding low-autocorrelation binary sequence (LABS) problem, a critical challenge in signal processing and radar technology. This pioneering work integrates digitized counterdiabatic quantum optimization (DCQO) with the established memetic tabu search (MTS) technique, leveraging the strengths of both quantum and classical computing. The quantum stage generates promising initial candidate sequences that then seed and guide the classical MTS local search process, exemplifying a hybrid sequential quantum computing approach. To rigorously evaluate performance, the team conducted a comprehensive scaling analysis, measuring the time-to-solution as a function of sequence length.

The quantum stage of QE-MTS employed DCQO to generate a population of low-energy candidate sequences, which were then used to initialize the MTS algorithm. This initial seeding provides statistically biased starting points, effectively guiding the subsequent local search and accelerating convergence. Experiments demonstrated that QE-MTS achieves a scaling of O(1. 24N) for sequence lengths ranging from 27 to 37, surpassing the O(1. 34N) scaling of the best-known classical MTS heuristic and improving upon the O(1.

46N) scaling of the quantum approximate optimization algorithm (QAOA). A two-stage bootstrap analysis further confirmed the scaling advantage of QE-MTS, projecting a crossover point beyond which the hybrid algorithm consistently outperforms its classical counterpart. This detailed analysis involved systematically varying the problem size and measuring the computational time required to reach optimal solutions, providing robust evidence for the improved scaling behavior. The team also demonstrated a six-fold reduction in circuit depth compared to QAOA, highlighting the potential for implementing QE-MTS on near-term quantum hardware. These results demonstrate that quantum enhancement can directly improve the scaling of classical optimization algorithms for the LABS problem, opening new avenues for tackling computationally challenging combinatorial optimization tasks.

Quantum Algorithm Accelerates Binary Sequence Optimisation

Scientists have achieved a significant breakthrough in solving the computationally demanding low-autocorrelation binary sequence (LABS) problem, a challenge at the intersection of combinatorial optimization and signal processing. Their work introduces a quantum-enhanced memetic tabu search (QE-MTS) algorithm, a non-variational hybrid approach that integrates digitized counterdiabatic optimization (DCQO) with the established memetic tabu search (MTS) method. This innovative combination leverages the strengths of both quantum and classical computing to improve optimization scaling. The team demonstrated that QE-MTS suppresses the empirical time-to-solution scaling to O(1.

24N) for sequence length N ranging from 27 to 37. This represents a substantial improvement over the best-known classical heuristic, which exhibits a scaling of O(1. 34N), and surpasses the O(1. 46N) scaling achieved by the quantum approximate optimization algorithm. Measurements confirm a six-fold reduction in circuit depth when compared to previous quantum approaches, indicating a more efficient use of quantum resources.

A rigorous two-stage bootstrap analysis projects a crossover point beyond which QE-MTS consistently outperforms its classical counterpart. This suggests that the quantum enhancement becomes increasingly beneficial as the problem size grows. The researchers meticulously analyzed the scaling behavior by benchmarking the time-to-solution as a function of system size, providing compelling evidence for the algorithm’s improved performance. The work establishes a clear path toward solving larger instances of the LABS problem, with implications for technologies reliant on low-sidelobe performance, such as radar systems.

Quantum Optimization Improves Classical Search Scaling

Researchers present a new quantum-enhanced classical optimization algorithm, termed quantum-enhanced memetic tabu search (QE-MTS), designed to address the low-autocorrelation binary sequence (LABS) problem. By initializing a classical memetic tabu search with high-quality starting points generated through digitized counterdiabatic quantum optimization, the team achieves improved scaling for this computationally challenging task.