Technical Summary: Clifford Circuit Synthesis for Distributed Quantum Architectures with Arbitrary Network Topology

Problem Statement

The paper addresses the challenge of compiling quantum circuits for distributed quantum architectures, where qubits are partitioned into distinct blocks (e.g., separate quantum processors linked by entanglement or logical qubits encoded in block codes). In these systems, non-local operations (gates acting between partitions) are significantly more expensive in terms of time and error rates compared to local operations. For instance, in the proposed "bicycle architecture," non-local operations have error rates two orders of magnitude higher than local ones.

The core problem is to synthesize equivalent circuits for CNOT, Clifford, and Clifford+RZ (including Clifford+T) circuits that minimize the number of non-local gates while respecting arbitrary connectivity constraints between partitions. Existing approaches primarily focus on scheduling and placing qubits (e.g., via teleportation) to minimize the cost of existing non-local gates, rather than fundamentally reducing the number of non-local gates required through circuit resynthesis.

Methodology

1. Circuit Representation

The author introduces a novel circuit representation that abstracts away all local Clifford operations. Any Clifford+RZ circuit is decomposed into:

• Local Clifford Circuit ($C_L$): Contains only operations within partitions.
• Non-Local/Non-Clifford DAG ($D(C_N)$): A Directed Acyclic Graph representing the remaining operations, consisting of two gate types:
  • Pauli Exponentials ($P(A, \theta)$): $e^{-i\theta/2 A}$, encoding non-Clifford operations (e.g., T-gates).
  • Generalized CNOT Gates ($C(A, B)$): Defined as $e^{i\frac{\pi}{4}(A \otimes I + I \otimes B - A \otimes B - I \otimes I)}$, where $A$ and $B$ are Pauli strings on different partitions. Crucially, any generalized CNOT can be implemented using exactly one non-local CNOT gate (plus local Cliffords), making the minimization of these gates equivalent to minimizing non-local resources.

2. Synthesis Algorithms

The paper adapts existing resynthesis techniques to operate on block matrices and block tableaux, treating partitions as atomic units.

• BlockRowCol (for CNOT Circuits):

  • Based on the RowCol algorithm, which uses Gaussian elimination on parity matrices.
  • Key Insight: The parity matrix of a distributed circuit is viewed as a block matrix. The goal is to eliminate off-diagonal blocks (inter-partition interactions) using block row operations.
  • Mechanism: A block row addition corresponds to applying a set of generalized CNOT gates. The number of gates required is determined by the rank of the coefficient matrix used for the block addition.
  • Connectivity: Uses Steiner trees to respect arbitrary partition connectivity when performing block operations.
  • Optimality: For $k=2$ partitions, the algorithm is proven to be within a factor of 2 of the optimal number of non-local gates for ZX-type generalized CNOTs. Asymptotically, it is optimal when $k = o(n / \log n)$.

• DistRowCol (for Clifford Circuits):

  • Extends the synthesis to full Clifford circuits using stabilizer tableaux.
  • Mechanism: Disentangles partitions one by one by reducing the stabilizer tableau to a block-diagonal form. It utilizes lemmas to find Pauli strings that commute with existing stabilizers/destabilizers to ensure structural integrity during elimination.
  • Complexity: Uses at most $2n(k-1)$ non-local gates, matching the asymptotic bounds of BlockRowCol.

• Clifford+RZ Optimization:

  • Distribution: Adapts phase polynomial synthesis methods to distribute Pauli exponentials across partitions, using heuristics to select pivot partitions that minimize future gate counts.
  • Folding: Introduces Generalized CNOT Folding, a technique analogous to phase-folding. It combines adjacent generalized CNOT gates sharing a Pauli string argument ($C(A, B_1) \cdot C(A, B_2)$) to reduce the count, potentially introducing local Clifford corrections.
  • Subcircuit Detection: Proposes a method to detect CNOT or Clifford subcircuits within the DAG representation (using convex acyclic partitions and beam search) to apply the specialized BlockRowCol or DistRowCol routines.

Key Results and Benchmarks

The author implemented these algorithms and benchmarked them against pytket-dqc (a state-of-the-art tool for distributed circuit optimization based on qubit placement and teleportation) and standard resynthesis methods.

• CNOT Circuits:

  • For deep circuits and larger qubit counts, BlockRowCol generally outperforms or matches pytket-dqc combined with resynthesis.
  • BlockRowCol is particularly effective in linear nearest-neighbor architectures, where it significantly reduces non-local gate counts compared to other methods.
  • For shallow circuits, pytket-dqc (without resynthesis) often performs better, likely due to the overhead of resynthesis and the benefits of qubit reordering (which the current implementation does not support).

• Clifford Circuits:

  • DistRowCol shows a consistent advantage over pytket-dqc with resynthesis for deeper circuits and is notably insensitive to the specific connectivity topology (2D grid vs. linear).

• Clifford+T Circuits:

  • The results are mixed. For architectures with many partitions ($k=9$), resynthesis methods (including the author's) often perform worse than pytket-dqc alone. The author suggests this is due to the general inefficiency of resynthesis for Clifford+T in distributed settings, rather than a flaw in their specific method.
  • For $k=2$, performance is comparable to other methods.

• Scalability:

  • The algorithms are highly efficient in runtime. The author successfully ran BlockRowCol on instances with 512 qubits and 128 partitions (circuits with $>2 \cdot 10^5$ gates) in seconds, whereas pytket-dqc (based on hypergraph partitioning) is significantly slower.

Significance and Claims

The paper claims the following contributions:

1. Asymptotic Optimality: The BlockRowCol algorithm is proven to be asymptotically optimal for CNOT circuit synthesis in distributed settings when the number of partitions $k$ is small relative to the number of qubits ($k = o(n / \log n)$).
2. Approximate Optimality for $k=2$: For two partitions, the method is shown to be within a constant factor (specifically, at most 2x) of the optimal solution for circuits using ZX-type generalized CNOTs.
3. General Framework: The work demonstrates that existing synthesis techniques based on parity matrices, stabilizer tableaux, and phase polynomials can be naturally generalized to distributed settings by operating on block structures.
4. Practical Applications:
   • CSS Codes: The method enables the synthesis of logical CNOT circuits in CSS codes using $O(nk)$ intra-block Pauli measurements and $O(k^2)$ inter-block transversal CNOTs, independent of inter-block connectivity.
   • Phantom Codes: Provides a bound of $6k(k-1)$ CNOT operations for logical circuits, scaling quadratically with the number of blocks rather than the number of logical qubits.
   • Tree Tensor Networks: The method can be used to minimize high-level gates in tree tensor network simulations, offering an asymptotic improvement over standard synthesis methods for classical simulation costs.

The author maintains a modest tone, acknowledging that their methods are preliminary and that practical details (such as qubit reordering and heuristic tuning) could be further optimized. They emphasize that their approach complements, rather than replaces, existing placement and scheduling strategies.