Quantum circuit partition as a maze: emerging percolation transition via path finding

This paper proposes a novel framework that formalizes quantum circuit partitioning as a maze-cutting problem, demonstrating that a percolation phase transition determines whether a circuit can be optimally split into two CNOT clusters without removing gates, particularly when the number of CNOTs is comparable to the number of qubits.

The Gist

Imagine you have a giant, tangled ball of yarn representing a complex quantum computer program. Your goal is to cut this ball in half so that two different computers can work on each half simultaneously, speeding up the process. However, there's a catch: the "yarn" is made of special knots called CNOT gates. If you cut through a knot, the program breaks and stops working. You need to find a way to slice the ball so that you don't cut any knots at all.

This paper treats that problem like solving a maze.

The Maze Analogy

The authors turn the quantum circuit into a grid, like a video game level:

• The Walls: The CNOT gates are the walls of the maze. They are solid barriers you cannot pass through.
• The Path: You need to draw a line (a "cut") from the left side of the maze to the right side.
• The Goal: If you can draw a line that goes from left to right without hitting a wall, you have successfully split the circuit into two independent parts. If you hit a wall, the circuit is too tangled to split without breaking it.

The Problem: The "Crowded Center"

When they first built these mazes, they noticed a pattern. The walls (knots) tended to pile up right in the middle of the maze, like a traffic jam in the center of a city. Because the center was so crowded, it was almost impossible to draw a straight line through it without hitting a wall.

The Solution: Rearranging the Furniture (Simulated Annealing)

To fix this, the authors used a clever trick called Simulated Annealing. Think of this as a very smart, patient robot that can rearrange the rows of the maze.

1. The Shuffle: The robot shuffles the order of the "wires" (the lines where the quantum bits travel). It's like taking a deck of cards, shuffling them, and seeing if the walls move to the top or bottom of the deck.
2. The Goal: The robot tries to push all the walls away from the center and toward the top and bottom edges of the maze.
3. The Result: If the robot is successful, it creates a "Central Corridor"—a clear, empty hallway running straight through the middle of the maze. Now, you can easily draw your cutting line through this empty space without hitting a single wall.

The "Phase Transition": The Tipping Point

The most exciting discovery in the paper is what happens when you change the number of walls (CNOT gates) compared to the number of wires (qubits).

They found a tipping point, similar to how water suddenly turns to ice:

• The "Easy" Zone: If the number of walls is roughly equal to (or less than) the number of wires, the robot can almost always rearrange the maze to create that clear central corridor. The circuit is partitionable.
• The "Impossible" Zone: If there are too many walls (too many CNOT gates), the maze becomes so crowded that no matter how the robot shuffles the rows, the walls block every possible path. The circuit is non-partitionable.

This sudden shift from "we can split it" to "we can't split it" is called a percolation transition. It's like a flood: at a certain water level, the water suddenly connects the whole lake. Here, at a certain density of gates, the walls suddenly connect the whole maze, blocking any path.

Why This Matters

The paper doesn't just say "it's hard to split circuits." It gives a practical rule: If you have roughly one CNOT gate for every qubit, you can likely split the circuit. If you have many more gates than qubits, you probably can't.

By turning a complex math problem into a "maze-solving" game, the authors provided a clear, visual way to know if a quantum circuit can be optimized by splitting it up, without needing to break the circuit apart. They used a "maze agent" (a simple computer program) to find the best path, confirming that this "corridor" strategy works for many types of quantum circuits.

Technical Summary

Technical Summary: Quantum Circuit Partition as a Maze: Emerging Percolation Transition via Path Finding

Problem Statement
In quantum circuit optimization, particularly for Noisy Intermediate-Scale Quantum (NISQ) devices, reducing the number of two-qubit gates (typically CNOTs) is a primary goal due to their significant noise impact. While circuit partitioning allows for parallel optimization across multiple devices, existing approaches often rely on splitting CNOT gates via mid-circuit measurements and qubit resets. A critical gap exists in determining whether a circuit can be optimally partitioned into two subcircuits without cutting any CNOT gates. The challenge is to identify a criterion that distinguishes between circuits that are partitionable (allowing independent resynthesis of subcircuits) and those that are not, without resorting to gate cutting.

Methodology
The authors formalize the circuit partitioning problem as a path-finding task within a "maze." The methodology proceeds through several key stages:

1. Circuit Representation:

   • Wire Representation ($W$): A grid where rows correspond to qubit wires and columns to CNOT gates. A cell is marked if a CNOT involves that qubit.
   • Maze Representation ($M$): A transformed grid where rows represent the spaces between qubit wires (plus padding), and columns alternate between empty space and CNOT gates. In this representation, CNOT gates act as "walls." A valid partition corresponds to a continuous path from the left to the right edge of the maze that does not intersect these walls.

2. Qubit Ordering Optimization (Simulated Annealing):

   • Randomly generated circuits initially exhibit a wall distribution peaked at the center of the maze, making horizontal traversal difficult.
   • The authors employ Simulated Annealing (SA) to permute the order of qubit wires in the wire representation. This permutation is mapped back to the maze representation.
   • A cost function is minimized during SA, which penalizes CNOT interactions that span the central region of the grid. The goal is to push interactions toward the top and bottom boundaries, creating a "central corridor" free of walls.

3. Path Finding Heuristic:

   • Once the maze is optimized, a heuristic agent traverses the maze. Two deterministic agents (one moving upward upon hitting a wall, one downward) are launched from each cell in the first column.
   • The agents are constrained to move monotonically (never backward in time or vertically reversing direction) to ensure the resulting subcircuits are chronologically consistent.
   • A weighted cost function ($L_{tot}$) evaluates candidate paths based on three metrics: CNOT imbalance between partitions, cell (area) imbalance, and path length deviation from the ideal horizontal trajectory.

4. Network Science Analysis:

   • The authors analyze the circuit as a directed graph where nodes represent CNOT events and edges represent causal or entangling relationships.
   • They utilize centrality measures (degree and betweenness) and consensus dynamics (DeGroot model) to quantify the separation of qubit regions and the mixing of information flow before and after SA optimization.

Key Results

• Percolation Phase Transition: The study identifies a phase transition in the space of quantum circuits. There exists a distinct regime where a valid, balanced partition path exists (partitionable) and a regime where no such path exists without cutting CNOTs (non-partitionable).
• Scaling Criterion: The transition is governed by the ratio of the number of CNOT gates ($N_c$) to the number of qubits ($N_q$). The authors observe that partitioning into two balanced CNOT clusters is feasible when $N_c$ is approximately equal to $N_q$. As the density of CNOTs increases relative to qubits, the "central corridor" closes, and the circuit becomes non-partitionable.
• Effect of Simulated Annealing: SA successfully restructures the circuit layout, moving CNOT interactions to the periphery and creating a low-density central corridor. This transformation shifts the wall distribution from a single-peaked (Beta distribution) profile to a bimodal profile, facilitating the existence of a horizontal cut.
• Network Dynamics: Centrality analysis shows that in the partitionable regime, SA concentrates interactions on qubits at the edges of the register, leaving the center weakly coupled. Consensus dynamics confirm that in sparse regimes, the circuit separates into two weakly coupled clusters, whereas in dense regimes, information mixes globally, preventing separation.
• Three Regimes: The analysis reveals three distinct phases based on the path-finding score:
  1. First Phase (Partitionable): A strictly horizontal cut exists, balancing CNOTs and cells.
  2. Transient Regime: The path must alternate between vertical and horizontal steps to navigate walls, resulting in less balanced partitions.
  3. Second Phase (Non-partitionable): No valid cut exists that separates the circuit; the agent is forced to the boundaries, leaving one partition negligible and the other containing almost the entire circuit.

Significance and Claims
The paper claims to provide a theoretical and numerical framework for understanding circuit partitioning as a percolation phenomenon. By mapping the problem to a maze, the authors establish a scalable and practical criterion for identifying whether a quantum circuit can be partitioned without cutting CNOT gates.

The work positions the ability to partition a circuit without cutting entangling gates as the first phase of a percolation transition, linking quantum circuit optimization to broader critical phenomena such as measurement-induced phase transitions and topological transitions. The authors assert that their framework forms a basis for algorithmic development in quantum circuit optimization, offering a method to determine the feasibility of parallelizing optimization tasks across multiple devices without the overhead of mid-circuit measurements. The results suggest that for circuits where the number of entangling gates scales linearly with the number of qubits, such partitioning is theoretically possible and can be identified via the proposed percolation criterion.