Link-middle-cut lower bounds for Clifford circuit synthesis

• URL: http://arxiv.org/abs/2609.16208v1
• Date: Mon, 14 Sep 2026 18:42:19 GMT
• Title: Link-middle-cut lower bounds for Clifford circuit synthesis
• Abstract summary: Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization.<n>We extend the link--middle-cut (LMC) framework for linear circuits to Clifford operators represented by binary symplectic tableaux.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization. We extend the link--middle--cut (LMC) framework for linear reversible circuits to Clifford operators represented by binary symplectic tableaux. By introducing block-support connectivity graphs and determinantal invariants, we obtain efficiently computable lower bounds on ancilla-free CNOT complexity. We prove that these bounds are tight for qubit permutations: a permutation of $n$ qubits with $k$ cycles requires exactly $3(n-k)$ CNOT gates, even when arbitrary one-qubit Clifford gates are available. We also derive efficiently computable bounds for synthesis up to a permutation of the output qubits, corresponding to free qubit relabeling. Finally, we further demonstrate the utility of the bound by using it as an admissible heuristic for $A^*$-based Clifford synthesis and show that, on benchmark instances, the resulting search can prove optimality beyond what was possible with earlier SAT-based methods, and that it may be used in combination with earlier $A^*$ heuristics to improve the CNOT counts obtained through heuristic search.

Related papers

• AlphaClifford: Efficient Clifford Synthesis and Transpilation with Model-based RL [2.018550249418405]
  We introduce AlphaClifford, a model-based Reinforcement Learning framework powered by Monte Carlo Tree Search.<n>By modeling the state space through the algebraic properties of the symplectic group, AlphaClifford effectively explores this space to minimize overall circuit cost.<n>We demonstrate the broad applicability of our framework on two additional tasks: hardware-constrained Clifford transpilation, and as a post-synthesis optimization component within a full Clifford+T logical pipeline.
  arXiv  Detail & Related papers  (2026-08-19T14:13:26Z)
• Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings [1.0171167503994478]
  We show that random circuits on two-qubit Clifford gates provide encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth.<n>We show that the same tradeoff is attained in optimal $O(log n)$ depth under a gate distribution with a more restricted support.<n>These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings.
  arXiv  Detail & Related papers  (2026-08-19T04:39:23Z)
• Reducing entanglement with a Hamiltonian derived Clifford transformation [37.803764941926374]
  Recently, an algorithm was introduced that deterministically generates a Clifford transformation from the Qubit Coupled Cluster (QCC) algorithm.<n>Here, we show that Q-Cliff can be utilized to generate efficient classical and quantum approximations to the ground states of chemical systems.
  arXiv  Detail & Related papers  (2026-07-20T18:00:40Z)
• Chutes and Ladders: Dynamical Automorphisms via the ZX-Calculus [37.09090127609627]
  We use the ZX-calculus language to handle dynamical stabilizer codes.<n>We combine gauge-fixing steps to implement a closed loop in the space of stabilizer codes.<n>This yields a machine-interpretable method for constructing dynamical automorphisms.
  arXiv  Detail & Related papers  (2026-06-01T17:46:09Z)
• Improved quantum circuits for division [42.76841620787673]
  We develop new fault-tolerant quantum circuits for various integer division algorithms.<n> circuits achieve an up to 76.08% and 68.35% reduction in T-count and CNOT-count.
  arXiv  Detail & Related papers  (2026-03-18T13:41:43Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [41.99844472131922]
  We use global interactions, such as the Global Molmer-Sorensen gate present in ion trap hardware, to optimize and synthesize quantum circuits.<n>The algorithm is based on the ZX-calculus and uses a specialized circuit extraction routine that groups entangling gates into Global MolmerSorensen gates.<n>We benchmark the algorithm in a variety of circuits, and show how it improves their performance under state-of-the-art hardware considerations.
  arXiv  Detail & Related papers  (2025-07-28T10:25:31Z)
• Heuristic and Optimal Synthesis of CNOT and Clifford Circuits [3.1952340441132474]
  Linear reversible circuits, equivalent to circuits composed of CNOT gates, have important applications in classical computing.<n>We present methods for CNOT and general Clifford circuit synthesis which can be used to minimise either the entangling two-qubit gate count or the circuit depth.<n>The algorithms have been implemented in a GitHub repository for use by the classical and quantum computing community.
  arXiv  Detail & Related papers  (2025-03-18T19:09:58Z)
• Minimum Synthesis Cost of CNOT Circuits [0.0]
  We use a novel method of categorizing CNOT gates in a synthesis to obtain a strict lower bound computable in $O(nomega)$ time. Applying our framework, we prove that $3(n-1)$ gate syntheses of the $n$-cycle circuit are optimal and provide insight into their structure.
  arXiv  Detail & Related papers  (2024-08-15T03:09:53Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• Low-depth Clifford circuits approximately solve MaxCut [44.99833362998488]
  We introduce a quantum-inspired approximation algorithm for MaxCut based on low-depth Clifford circuits. Our algorithm finds an approximate solution of MaxCut on an $N$-vertex graph by building a depth $O(N)$ Clifford circuit.
  arXiv  Detail & Related papers  (2023-10-23T15:20:03Z)
• Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
  An ideal state preparation protocol can be characterized by being easily generated classically. We propose a method that meets these requirements by introducing a variant of the iterative qubit coupled cluster (iQCC) We demonstrate the algorithm's correctness in ground-state simulations and extend our study to complex systems like the titanium-based compound Ti(C5H5)(CH3)3 with a (20, 20) active space.
  arXiv  Detail & Related papers  (2022-11-18T20:31:10Z)
• Hadamard-free circuits expose the structure of the Clifford group [9.480212602202517]
  The Clifford group plays a central role in quantum randomized benchmarking, quantum tomography, and error correction protocols. We show that any Clifford operator can be uniquely written in the canonical form $F_HSF$. A surprising connection is highlighted between random uniform Clifford operators and the Mallows distribution on the symmetric group.
  arXiv  Detail & Related papers  (2020-03-20T17:51:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.