Link-middle-cut lower bounds for Clifford circuit synthesis

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.

(A Variant of) Clifford Circuit Synthesis is NP-Complete
Luna Lima Keller, Richard Kueng
arXiv1 Oct 2026PreprintCC BY-SA 4.0Full textQuantum physics & quantum informationarXiv
Strictly positive lower bound on the thermodynamic cost of running a Boolean circuit
Abhishek Yadav, Mahran Yousef, David Wolpert
Physical Review X7 Oct 2026Peer-reviewedCC BY 4.0Statistical & nonlinear physicsCrossref
Improved bounds on stabilizer extent and Clifford rank
Pulkit Sinha, Benjamin Lovitz
arXiv5 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Clifford synthesis is NP-complete
Søren Fuglede Jørgensen
arXiv29 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Complexity separations for optimal matchgate-Clifford synthesis
Berta Casas, Diego García-Martín, Yuxuan Zhang
arXiv5 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv

Cite

BibTeX RIS

BibTeX

@misc{jorgensen2026linkmiddlecut,
  title = {{Link-middle-cut lower bounds for Clifford circuit synthesis}},
  author = {Søren Fuglede Jørgensen},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.16208},
  eprint = {2609.16208},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.16208},
}

RIS

TY  - UNPB
TI  - Link-middle-cut lower bounds for Clifford circuit synthesis
AU  - Søren Fuglede Jørgensen
PY  - 2026
DA  - 2026/09/14
PB  - arXiv
DO  - 10.48550/arxiv.2609.16208
UR  - https://arxiv.org/abs/2609.16208
AB  - 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.
ER  -

Abstract

Related

Cite