⚛️ quantum physics

Noise-Directed Adaptive Remapping for Integer Optimization: from qubits to (encoded) qudits

This paper extends the Noise-Directed Adaptive Remapping (NDAR) heuristic from binary to integer optimization by introducing flexible gauge degrees of freedom that allow tailoring to various qubit and qudit encodings, demonstrating how noise-induced dynamics interact with different encoding strategies to provide a new criterion for selecting device-level representations in quantum optimization.

Original authors: Stuart Hadfield, Filip B. Maciejewski, Davide Venturelli

Published 2026-06-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Stuart Hadfield, Filip B. Maciejewski, Davide Venturelli

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 solve a very difficult puzzle, like finding the best way to color a map so that no two neighboring countries share the same color. You have a new, powerful tool to help you: a quantum computer. But there's a catch. This quantum computer is "noisy." It's like a radio with a lot of static; it doesn't always give you the perfect answer, and sometimes it drifts toward a specific, predictable mistake.

Usually, scientists try to fix this noise, like trying to tune a radio to clear up the static. This paper introduces a clever new strategy called NDAR (Noise-Directed Adaptive Remapping). Instead of fighting the noise, the authors say: "Let's use the noise as a helper."

Here is how the paper explains this, broken down into simple concepts:

1. The "Gravity" of Noise (The Attractor)

Think of the noise in the quantum computer like a gentle gravity. If you drop a ball, it always rolls to the bottom of the hill. Similarly, the noise in these machines tends to push the computer's answer toward a specific "default" state (like all zeros).

The Old Way: Try to stop the ball from rolling down the hill.
The NDAR Way: Accept that the ball will roll down. Instead, we change the shape of the hill so that the "bottom" (the noise's favorite spot) is actually the correct answer we are looking for.

2. The "Magic Mirror" (Adaptive Remapping)

The algorithm works in a loop. It asks the noisy computer for an answer.

The computer gives a result (which might be imperfect).
The algorithm looks at the result and says, "Okay, the noise wants to push us toward 'State A', but we found a better answer at 'State B'."
The algorithm then performs a "gauge transform." Think of this as a magic mirror. It flips the labels on the puzzle pieces. It re-maps the problem so that the "State B" we just found now looks like "State A" (the one the noise loves).
Now, when the noise pushes the computer toward its favorite state, it is actually pushing it toward the best solution we have found so far.

3. From Simple Switches to Multi-Level Dials (Qubits vs. Qudits)

Most quantum computers today use qubits, which are like simple light switches: they are either OFF (0) or ON (1).

The Problem: Many real-world problems (like scheduling or coloring maps) need more than just two options. They need 3, 4, or 10 options. To solve these on a switch-based computer, we have to group many switches together to represent one number. This is like using a whole row of light switches to represent the number "5." It's clunky and creates extra rules (constraints) to make sure the switches don't get confused.

This paper extends the NDAR method to qudits.

The Analogy: Imagine a dimmer switch or a dial that can be set to 0, 1, 2, 3, or 4. This is a qudit. It handles multi-option problems naturally, without needing a whole row of switches.
The Discovery: The authors found that when you use these multi-level dials (qudits), the "magic mirror" (the gauge transform) becomes much more flexible. With simple switches, there is only one way to flip them to get a new answer. With dials, there are many ways to rotate or shift the numbers. This gives the algorithm more freedom to choose the "cheapest" or easiest way to rearrange the puzzle for the specific hardware it is running on.

4. The "One-Hot" Trap

The paper also looked at how to represent these multi-option problems using standard switches (qubits) in different ways.

One-Hot Encoding: Imagine you have 5 colors. You use 5 switches, but you are only allowed to have one switch on at a time. If the noise accidentally turns on two switches, you have an invalid answer. The paper notes that this is risky because the "noise gravity" often pushes the system toward "all switches off," which is an invalid state in this setup.
Domain-Wall Encoding: This is a smarter way of using switches where the "all off" state is actually a valid answer. The paper suggests this is a better fit for the NDAR method when you don't have multi-level dials.

5. The Main Takeaway

The authors tested these ideas using the "Map Coloring" problem (Max-k-colorable subgraph). They found:

Native Qudits are Best: If your quantum computer has native multi-level dials (qudits), NDAR works beautifully. The noise naturally pushes toward low-energy states, which aligns perfectly with the math of these dials.
Qubits are Tricky: If you are stuck with simple switches, you have to be very careful about how you encode the problem. Some ways of encoding (like the "domain-wall" method) work well with NDAR, while others (like "one-hot") struggle because the noise pushes the system into invalid states.

Summary

This paper is a guidebook for using "broken" or noisy quantum computers more effectively. It argues that instead of trying to fix the noise, we should dance with it. By constantly re-labeling our problems to match the noise's natural tendencies, we can find better solutions faster. Furthermore, it suggests that the next generation of quantum computers, which use multi-level dials (qudits) instead of simple switches, are naturally better suited for this "noise-dancing" strategy.

Technical Summary: Noise-Directed Adaptive Remapping for Integer Optimization

Problem Statement
The paper addresses the challenge of optimizing discrete integer domains on near-term quantum hardware, specifically extending the Noise-Directed Adaptive Remapping (NDAR) meta-algorithm beyond its original scope of unconstrained binary optimization. While NDAR was previously demonstrated to improve performance on binary problems by exploiting device noise as a computational resource, its application to integer problems (domains $\mathbb{Z}_d^n$ ) and non-binary encodings (such as qudits or qubit-encoded integers) remained unexplored. The core difficulty lies in the fact that integer optimization often involves hard constraints (e.g., valid colorings in graph problems) and diverse encoding schemes (binary, one-hot, domain-wall, native qudit) that interact differently with hardware noise and gauge transformations. The authors investigate how to generalize NDAR to these settings, identifying specific requirements for feasibility, gauge selection, and circuit implementability.

Methodology
The authors generalize the NDAR framework to handle integer optimization problems over $\mathbb{Z}_d^n$ . The methodology involves four key components adapted for higher-dimensional systems:

Noise Attractor Identification: The framework assumes the existence of a known classical "attractor" state driven by hardware noise (e.g., amplitude damping). For qudits, the authors model generalized amplitude damping channels, showing that at zero or finite temperatures, the system naturally relaxes toward low-excitation states (typically $|00\dots0\rangle$ ), analogous to the all-zeros attractor in qubits.
Feasibility and Constraints: Unlike unconstrained binary optimization, integer problems often have hard constraints (e.g., valid color assignments). The authors extend NDAR to require that the attractor state encodes a feasible solution. They analyze various encodings to determine if the $|00\dots0\rangle$ state is valid and if the set of feasible states forms a transitive orbit under the chosen gauge group.
Gauge Transformation Selection: In binary optimization, a bitflip operation uniquely maps the attractor to any target string. For qudits ( $d>2$ ) or encoded qubits, this one-to-one correspondence breaks, creating an exponentially large family of compatible gauge transformations. The authors propose selecting specific gauge transformations (e.g., cyclic shifts for native qudits, prefix-flips for domain-wall encodings) that map the attractor to the best candidate solution found in the current iteration while preserving the structure of the quantum circuit (ansatz).
Adaptive Remapping Loop: The algorithm iteratively runs a quantum optimizer (e.g., QAOA), samples solutions, selects the best feasible candidate, and applies a gauge transform to the cost Hamiltonian and constraints. This aligns the noise attractor with the high-quality solution, effectively using noise to drive the system toward better solutions in subsequent iterations.

The study evaluates these criteria across several encoding schemes using the Max-k-colorable subgraph problem as a running example:

Native Qudit Encoding: Direct mapping to $d$ -level systems.
Binary Encoding: Mapping integers to $\lceil \log_2 d \rceil$ qubits.
One-Hot Encoding: Using $d$ qubits per variable (Hamming weight 1).
01-Hot Encoding: Augmented one-hot including the all-zero state.
Domain-Wall Encoding: Using $d-1$ qubits per variable with specific boundary conditions.

Key Contributions

Generalization of NDAR: The paper provides a unified framework for applying NDAR to integer domains and hard constraints, formalizing the conditions under which the algorithm remains effective (specifically regarding the feasibility of the attractor and the existence of efficient gauge transforms).
Analysis of Gauge Freedom in Qudits: The authors demonstrate that native qudit systems offer significantly more gauge freedom ( $(d-1)!^n$ ) compared to qubits. This surplus freedom is identified as a design lever, allowing the selection of gauge transformations that are most compatible with specific hardware gate sets (e.g., cyclic shifts vs. arbitrary permutations) to minimize circuit overhead.
Comparative Analysis of Encodings: Through the lens of NDAR, the paper compares native qudit encodings against binary and unary (one-hot, domain-wall) qubit encodings. Key findings include:
- Native Qudits: Offer the most favorable properties, with a naturally feasible attractor ( $|00\dots0\rangle$ ) and 2-local cost Hamiltonians.
- Binary Encodings: Space-efficient but require higher locality ( $2\lceil \log_2 d \rceil$ -local) for cost Hamiltonians and phase operators.
- Unary Encodings: While domain-wall and 01-hot encodings can support a feasible attractor, they often introduce non-trivial transformations to the cost Hamiltonian or suffer from infeasible attractors (in standard one-hot) due to noise-induced leakage.
Hardware Alignment: The work connects the theoretical requirements of NDAR to emerging superconducting cavity qudit hardware, noting that amplitude damping noise in these systems naturally aligns with the NDAR attractor model.

Results

Encoding Trade-offs: Table I in the paper summarizes that native qudit encodings provide a "best-of-category" combination of properties: 1 qudit per variable, probability of valid strings $q=1$ , no additional hard constraints, a feasible $|00\dots0\rangle$ attractor, and 2-local cost Hamiltonians. In contrast, qubit-based encodings often require additional hard constraints, have $q < 1$ (due to noise), or result in higher locality operators.
Feasibility of Attractors: The study identifies that for standard one-hot encodings, the natural noise attractor ( $|00\dots0\rangle$ ) is invalid, rendering standard NDAR inapplicable without modification. Conversely, domain-wall and 01-hot encodings can be structured to have feasible attractors, though they may alter the locality of the cost Hamiltonian.
Circuit Complexity: The authors show that while binary encodings are space-efficient, the required gauge transformations can introduce complex circuit structures if not carefully selected (e.g., requiring multi-controlled gates). Native qudit encodings allow for simpler gauge transforms (e.g., shifts) that preserve the 2-local structure of the QAOA ansatz.

Significance and Claims
The paper claims that NDAR-guided noise considerations provide a new criterion for comparing device-level encoding choices for quantum optimization. It argues that the choice of encoding is not merely a matter of resource count (qubits vs. qudits) but fundamentally impacts the algorithm's ability to leverage noise.

The authors assert that:

Native qudit implementations of NDAR present distinct advantages over comparable qubit-based encodings, particularly in how noise-induced dynamics interact with the solution landscape.
The gauge multiplicity in qudit systems is a feature, not a bug, allowing for the tailoring of transformations to specific hardware constraints.
The framework is experimentally relevant for emerging superconducting cavity qudit devices (e.g., those in the SQMS Center), where noise characteristics (amplitude damping) and gate capabilities (CSUM, ECD) align well with the NDAR requirements.

The paper concludes by outlining directions for experimental realization in superconducting qudit devices, emphasizing the need for high-fidelity two-qudit entangling gates and error suppression techniques to fully leverage the NDAR approach. It positions this work as a necessary step toward utilizing the growing class of non-qubit quantum processors for practical optimization tasks.