Succinct QUBO formulations for permutation problems by sorting networks

This paper introduces a novel, succinct QUBO formulation for permutation problems using sorting networks that reduces variable complexity to $O(n \log^2 n)$ while enabling unbiased sampling and supporting complex operations like multiplication, inversion, and order checking.

The Gist

Imagine you have a deck of $n$ playing cards, and your goal is to shuffle them into a specific order, or perhaps find a shuffle that meets a very specific rule (like "the Ace of Spades must be in the middle" or "the shuffle must be its own reverse").

In the world of quantum computing and optimization, finding these specific shuffles is a huge headache. The standard way to describe a shuffle is like trying to map out a massive grid where every card has to be assigned to every single seat. If you have 100 cards, that's a grid of 10,000 squares. It's messy, heavy, and slow for computers to process.

This paper introduces a much smarter, lighter way to describe these shuffles using a concept called Sorting Networks.

Here is the breakdown of their idea using simple analogies:

1. The Old Way: The "Permutation Matrix" (The Giant Grid)

Think of the old method as trying to describe a shuffle by drawing a giant spreadsheet. For every card, you have to write down which seat it goes to.

• The Problem: As you add more cards, the spreadsheet explodes in size. It's like trying to organize a library by writing a unique label for every single book on every single shelf, even though the books are just moving around. It's too much paperwork (variables) for the computer to handle efficiently.

2. The New Way: The "Sorting Network" (The Assembly Line)

The authors suggest we stop thinking about the final destination of every card and start thinking about the process of sorting them.

Imagine a factory assembly line with $n$ conveyor belts.

• The Machine: The machine has a series of "gates." Each gate looks at two belts, compares the items on them, and if they are in the wrong order, it swaps them. If they are already in order, it leaves them alone.
• The Magic: If you design this assembly line correctly (a "Sorting Network"), no matter what order you put the cards in at the start, they will always come out sorted at the end.

3. How They Turn This Into a Puzzle (QUBO)

The paper's big breakthrough is realizing that we can turn this assembly line into a math puzzle (a QUBO) that a quantum computer can solve.

Instead of asking, "Where is every card?" they ask, "Did every gate in the assembly line do its job correctly?"

• The Variables: Instead of tracking $n^2$ positions, they only track the actions of the gates. Did Gate #1 swap? Did Gate #2 swap?
• The Efficiency: Because the assembly line is a fixed sequence of steps, the number of variables needed grows much slower. If the old method was like a brick wall ($n^2$), this new method is like a spiral staircase ($n \log n$). It's much smaller and lighter.

4. Why "Uniformity" Matters

The authors emphasize that their method is unbiased.

• The Analogy: Imagine you want to pick a random shuffle for a magic trick. If your method is biased, you might accidentally pick "shuffles where the Ace is always on top" more often than others.
• The Result: Their method ensures that every possible valid shuffle has an equal chance of being found. It's like a perfectly fair lottery where every ticket has the exact same odds.

5. What Can You Do With This?

Because this method is so efficient and fair, it opens the door to solving complex problems that were previously too hard for quantum computers:

• Cryptography: Creating secret codes (S-boxes) that are mathematically perfect.
• Scheduling: Organizing sports tournaments so that every team plays fairly without conflicts.
• Pattern Matching: Checking if a specific pattern exists inside a larger sequence of events (like finding a specific melody hidden inside a long song).
• Special Rules: You can easily add rules like "The shuffle must be its own reverse" or "The shuffle must have a specific number of swaps."

The Bottom Line

The authors took a complex, heavy way of describing shuffles (the giant grid) and replaced it with a sleek, efficient assembly line (the sorting network).

By focusing on the steps rather than the destinations, they created a "succinct" (short and sweet) recipe for permutations. This makes it possible for future quantum computers to explore vast oceans of possibilities quickly, fairly, and without getting bogged down by too much math. It's the difference between trying to carry a library in your backpack versus using a magical conveyor belt that sorts the books for you as you walk.

Technical Summary

Here is a detailed technical summary of the paper "Succinct QUBO formulations for permutation problems by sorting networks" by Friedl et al.

1. Problem Statement

The paper addresses the challenge of encoding permutations into Quadratic Unconstrained Binary Optimization (QUBO) models. QUBO is a standard NP-hard problem format used in quantum annealing and classical optimization.

• Current State: The standard method for encoding permutations is the permutation matrix encoding (one-hot encoding). This approach requires $n^2$ binary variables for a permutation of size $n$. Furthermore, it results in a dense interaction graph where each variable interacts with $O(n)$ other variables, making it inefficient for quantum hardware with limited connectivity.
• Goal: The authors aim to develop a more efficient QUBO formulation that:
  1. Reduces the number of variables from $O(n^2)$ to $O(n \log^2 n)$.
  2. Reduces the interaction density (sparsity) to $O(\log n)$ per variable.
  3. Ensures uniformity, meaning every valid permutation corresponds to exactly one unique assignment of variables (crucial for unbiased sampling).
  4. Supports complex constraints (e.g., fixed points, parity, order, conjugacy) without significantly increasing complexity.

2. Methodology

The core innovation is mapping oblivious compare-exchange networks (sorting networks) to QUBO formulations. Unlike standard algorithms where operation sequences depend on data, sorting networks follow a fixed sequence of gates regardless of the input.

A. Sorting Network as a QUBO

The authors model a sorting network as a sequence of Compare-Exchange (CE) gates.

• Gate Logic: A CE gate takes two numbers, compares them, and swaps them if they are out of order.
• Polynomial Representation: The behavior of each gate is described by a quadratic polynomial. The total energy of the system is the sum of these gate polynomials. The global minimum (energy = 0) is achieved if and only if every gate behaves correctly according to the network's logic.
• Components:
  1. Controlled Swap (SWAP): A polynomial ensuring that if a control bit $c=1$, inputs $(x_1, x_2)$ become outputs $(x_2, x_1)$; otherwise, they remain unchanged.
  2. Greater Than (GT): A polynomial determining the comparison bit $c$ based on inputs $x$ and $y$.
  3. CE Gate: The combination of GT and SWAP.

B. From Sorting to Permutations

To represent a permutation $\pi$, the authors utilize the property that a sorting network transforms an input sequence into a sorted sequence.

• Formulation: They define a QUBO where the input variables $x$ represent the permutation, and the output variables are constrained to be the identity sequence $id = (1, 2, \dots, n)$.
• Stable Sorting: To ensure the mapping is bijective (one-to-one) and uniform, they employ stable sorting networks. This is achieved by appending the original index (line number) to each input value. If two values are equal, the network preserves their original relative order based on these indices. This guarantees that for any valid permutation input, there is a unique path of control bits (swaps) leading to the sorted output.

C. Quadratization

Since sorting networks involve higher-order logic (comparing multi-bit numbers), the authors use quadratization techniques. They introduce auxiliary variables to reduce higher-degree monomials to quadratic terms while preserving the uniformity of the solution space.

3. Key Contributions

1. Variable Efficiency:

   • The proposed method uses $O(n \log^2 n)$ binary variables.
   • This is a substantial improvement over the standard $O(n^2)$ permutation matrix encoding.
   • The number of interactions per variable is reduced to $O(\log n)$, creating a sparse interaction graph suitable for quantum hardware.

2. Uniformity:

   • The formulation is uniform: every valid permutation corresponds to a unique assignment of the auxiliary control bits. This allows for unbiased sampling of permutations, a critical feature for randomized algorithms and cryptographic applications.

3. Constraint Flexibility:

   • The framework easily incorporates additional constraints by adding penalty terms. The authors demonstrate how to enforce:
     • Fixed points and Derangements (no fixed points).
     • Parity (even/odd permutations).
     • Order of a permutation ($\pi^r = I$).
     • Commutativity ($\pi \sigma = \sigma \pi$).
     • Conjugacy and Involutions ($\pi^2 = I$).
     • Permutation Pattern Matching (finding if a subsequence matches a pattern).

4. Theoretical Link:

   • This is the first work to explicitly link oblivious compare-exchange networks with QUBO encodings, providing a general framework for translating oblivious algorithms into mathematical programming formulations.

4. Results and Complexity Analysis

• Complexity:
  • Variables: $O(n \log^2 n)$ (assuming $k \approx \log n$ bits per number).
  • Auxiliary Variables: $O(n \log^2 n)$.
  • Interactions: $O(\log n)$ per variable.
• Comparison:
  • Permutation Matrix: $O(n^2)$ variables, $O(n)$ interactions.
  • Domain-Wall Encoding: $O(n^2)$ variables (halved interactions), but still quadratic.
  • HOBO (Higher-Order): Can achieve $O(n \log n)$ variables but requires higher-order terms, which are harder to implement on current quantum annealers.
• Performance: The resulting QUBO is significantly smaller and sparser, making it more practical for near-term quantum devices.

5. Significance and Applications

• Quantum Computing: The reduction in variable count and interaction density makes permutation problems feasible for current and near-future quantum annealers, which are limited by qubit count and connectivity.
• Cryptography: The ability to uniformly sample permutations with specific constraints (e.g., fixed points, specific orders, or commutativity) is vital for designing S-boxes and analyzing cryptographic primitives.
• Combinatorial Design: The method supports problems like Latin Square Completion and tournament scheduling, where specific permutation constraints are required.
• Generalizability: The approach of mapping oblivious algorithms to QUBO offers a new paradigm for solving other combinatorial problems beyond permutations, provided the algorithm's operation sequence is input-independent.

6. Limitations

The authors note a limitation in modeling graph-theoretic problems like the Traveling Salesperson Problem (TSP). In TSP, representing vertices as binary strings makes edge verification (checking if two cities are connected) non-trivial within this specific sorting-network framework, unlike the direct adjacency matrix approach used in permutation matrix encodings.

Conclusion

Friedl et al. present a breakthrough in QUBO formulation for permutations. By leveraging sorting networks, they achieve a succinct, sparse, and uniform encoding that outperforms traditional matrix-based methods. This advancement opens new avenues for solving constrained permutation problems on quantum hardware, with immediate relevance to cryptography and combinatorial optimization.