⚛️ quantum physics

A competitive NISQ and qubit-efficient solver for the LABS problem

This paper demonstrates that the Pauli Correlation Encoding (PCE) framework, a qubit-efficient variational approach, effectively solves the Low Autocorrelation Binary Sequences (LABS) problem with improved scaling and noise resilience, outperforming state-of-the-art classical heuristics while requiring significantly fewer quantum resources.

Original authors: Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

Published 2026-01-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to arrange a long line of people, where each person is holding either a red flag (+1) or a blue flag (-1). Your goal is to arrange them so that if you look at the line from different angles, the patterns of red and blue flags don't accidentally line up in a confusing way. In the scientific world, this is called the Low Autocorrelation Binary Sequences (LABS) problem. It's a notoriously difficult puzzle used to test how good computers are at solving hard optimization problems.

This paper introduces a new, clever way for quantum computers (specifically the current, noisy kind known as NISQ) to solve this puzzle better than many traditional methods. Here is the breakdown of their approach:

1. The Problem: A "Golf Course" of Mistakes

Think of the search for the perfect arrangement of flags as trying to find the lowest point in a vast, foggy landscape.

The Landscape: Most of the time, you are walking on a flat plain with many small dips (local minima). These look like the bottom of the valley, but they aren't the real bottom.
The Goal: The true solution is a single, tiny, deep hole in the middle of the plain (the global minimum).
The Difficulty: Because there are so many fake "bottoms," standard computer programs often get stuck in one of them and give up, thinking they found the best answer when they haven't.

2. The Solution: A "Compressed" Map (Pauli Correlation Encoding)

Usually, to solve a problem with $N$ variables (like 45 flags), a quantum computer needs 45 quantum bits (qubits). But current quantum computers are small and fragile; they can't handle that many bits yet.

The authors use a trick called Pauli Correlation Encoding (PCE).

The Analogy: Imagine you have a huge library of books (the 45 flags), but you only have a tiny notebook (4 qubits). Instead of writing down every single book, you use a special code. You write down relationships between the books.
How it works: They map the 45 flags onto just 4 qubits. It's like compressing a high-definition movie into a tiny file size without losing the plot. This allows them to tackle huge problems (up to 45 flags in their simulation, and even 120 in a real experiment) using very few quantum resources.

3. The Strategy: Choosing the Right "Questions"

To get the most information out of those 4 qubits, the team had to decide how to ask the quantum computer questions.

The Commuting Set: Asking questions that don't interfere with each other (like asking about the weather and the time of day).
The Non-Commuting Set: Asking questions that do interfere with each other (like trying to measure a spinning coin's position and speed at the exact same time).
The Result: They found that the "interfering" questions (non-commuting) were much better. It's like shaking a jar of marbles to see the whole picture rather than just looking at one side. This method gave them the best results.

4. The Performance: Faster and Smarter

They tested their new method against the best classical (regular) computer programs and other quantum methods.

The Race: They measured "Time-to-Solution" (how long it takes to find the perfect answer).
The Outcome: Their quantum method was faster than the best classical "heuristic" (a smart guessing algorithm called Tabu Search) for the sizes they tested.
The Scale: While other quantum methods needed massive, perfect computers that don't exist yet, this method works on small, current devices. It scales better, meaning as the problem gets bigger, their method stays competitive longer than the others.

5. The Real-World Test: The "Noisy" Playground

The authors didn't just run simulations; they actually ran their algorithm on a real quantum computer made by IonQ (called the Forte processor).

The Challenge: Real quantum computers are "noisy." It's like trying to hear a whisper in a hurricane. The hardware makes mistakes.
The Result: They successfully solved a problem with 120 flags (the largest ever shown on quantum hardware for this specific problem).
Resilience: Even with the "hurricane" of noise, the final answer was still good. They found that they didn't need millions of tries (shots) to get a decent answer; a few thousand were enough. However, the noise did make the final answer slightly less perfect than a perfect simulation would be.

Summary

The paper claims that by using a clever "compression" technique (PCE) and asking the right types of questions (non-commuting operators), they can solve a very hard math puzzle (LABS) on small, imperfect quantum computers. Their method is faster than the best current classical guessing methods for the sizes they tested and is robust enough to work on real, noisy hardware today. They suggest this could be a powerful tool for solving hard problems right now, even before we have perfect, error-free quantum computers.

Technical Summary: A Competitive NISQ and Qubit-Efficient Solver for the LABS Problem

Problem Definition
The Low Autocorrelation Binary Sequences (LABS) problem is a well-known NP-hard combinatorial optimization challenge with applications in engineering, communications, and statistical physics. Given an integer $N$ , the objective is to find a binary sequence $x \in \{-1, +1\}^N$ that minimizes the sidelobe energy $E(x)$ , defined as the sum of squared autocorrelations $C_\ell(x)$ for $\ell > 0$ . Equivalently, the goal is to maximize the merit factor $F(x) = N^2 / 2E(x)$ . The problem is characterized by a "golf course" optimization landscape with numerous local minima and isolated global minima. While exact solutions are known for $N \le 66$ , finding optimal or high-quality approximate solutions for larger $N$ becomes intractable for classical brute-force methods, and even state-of-the-art heuristics like Memetic Tabu Search face significant scaling challenges.

Methodology: Pauli Correlation Encoding (PCE)
The authors propose a qubit-efficient variational quantum solver based on the Pauli Correlation Encoding (PCE) framework. Unlike standard encodings that require one qubit per binary variable, PCE compresses $N$ binary variables into $n$ qubits where $N = \text{poly}(n)$ , specifically $n \ll N$ .

Encoding: Binary variables $x_i$ are encoded as the signs of expectation values of a set of $n$ -qubit Pauli strings $\Pi = \{\Pi_i\}_{i \in [N]}$ :
$x_i := \text{sgn}(\langle \Pi_i \rangle)$
where $\langle \Pi_i \rangle = \langle \Psi | \Pi_i | \Psi \rangle$ .
Optimization: The quantum state $|\Psi\rangle$ is generated by a parameterized brickwork circuit. The parameters are optimized classically to minimize a non-linear loss function $L$ . To facilitate gradient-based optimization, the binary variables are relaxed using a hyperbolic tangent function: $\tilde{x}_i = \tanh(\alpha \langle \Pi_i \rangle)$ . The loss function includes a regularization term to prevent correlators from vanishing.
Pauli Set Selection: The study evaluates two distinct sets for $\Pi$ $Π$ :
1. $\Pi(C)$ : A set of randomly selected, mutually commuting Pauli operators.
2. $\Pi(NC)$ : A set designed to maximize the number of mutually non-commuting Pauli operators. The authors hypothesize that non-commutativity leads to mutually unbiased measurements, thereby increasing the expressivity and independence of the encoded variables.

Key Contributions and Results

Numerical Simulations ( $N \le 45$ ):
- The authors simulated the PCE solver using $n=4$ qubits and a circuit depth of 15 layers (30 two-qubit gates, 150 parameters).
- The $\Pi(NC)$ variant consistently outperformed the commuting variant.
- Scaling Analysis: The Time-to-Solution (TTS), defined as the number of cost function evaluations required to find the exact solution, was benchmarked against QAOA and Memetic Tabu Search.
  - PCE Scaling: $O(1.330^N)$ for even instances and $O(1.326^N)$ for odd instances.
  - Comparison: This scaling improves upon the QAOA scaling of $O(1.46^N)$ and is marginally better than the state-of-the-art Tabu Search scaling of $O(1.34^N)$ (for even instances) and $O(1.409^N)$ (for odd instances).
- The results indicate a power-law advantage for PCE over classical baselines within the tested range.
Experimental Demonstration (IonQ Forte):
- The authors performed a proof-of-principle demonstration on IonQ's Forte quantum processor for an instance size of $N=120$ , the largest demonstrated to date on quantum hardware.
- For the experiment, a specific hardware-friendly set of $k$ -body correlators ( $k=2$ ) was used, requiring only three measurement setups.
- Noise Resilience: The study found that while shot noise had a minor impact (requiring only a few thousand shots), hardware noise significantly degraded the final solution quality. However, the training process itself remained robust, suggesting that error mitigation or higher compression rates are critical for near-term deployment.

Significance and Claims
The paper claims that PCE-based solvers represent a promising approach for two distinct avenues:

Quantum-Inspired Classical Heuristics: Even when simulated classically, the PCE framework offers competitive or superior scaling compared to leading classical heuristics for hard problems like LABS, acting as a powerful quantum-inspired algorithm.
NISQ Resource Reduction: By encoding $N$ variables into a polynomially smaller number of qubits ( $n$ ), PCE drastically reduces the qubit requirements for near-term devices. The authors note that $n=8$ qubits could theoretically tackle instances up to $N=66$ (where exact solutions are known), and $n \le 20$ could challenge the largest instances solvable by classical heuristics.

The authors maintain a modest stance regarding "quantum advantage." They acknowledge that the overhead of simulating full quantum state vectors in classical benchmarks delays the crossover point where a true quantum runtime advantage becomes evident. Furthermore, they note that while the method shows strong performance, it currently lacks performance guarantees. Nevertheless, the ability to solve $N=120$ instances on current hardware with modest shot budgets and the observation of noise resilience highlight the potential of PCE as a tool for reducing resource requirements in actual quantum algorithms.