We tackle the problem of Clifford isometry compilation, i.e, how to synthesize a Clifford isometry into an executable quantum circuit. We propose a simple framework for synthesis that only exploits the elementary properties of the Clifford group and one equation of the symplectic group. We highlight the versatility of our framework by showing that several normal forms of the literature are natural corollaries. We recover the state of the art two-qubit gate depth necessary for the execution of a Clifford circuit on an LNN architecture, concomitantly with another work. We also propose practical synthesis algorithms for Clifford isometries with a focus on Clifford operators, graph states and codiagonalization of Pauli rotations. Benchmarks show that in all three cases we improve the 2-qubit gate count and depth of random instances compared to the state-of-the-art methods. We also improve the execution of practical quantum chemistry experiments.
We tackle the problem of Clifford isometry compilation, i.e, how to synthesize a Clifford isometry into an executable quantum circuit. We propose a simple framework for synthesis that only exploits the elementary properties of the Clifford group and one equation of the symplectic group. We highlight the versatility of our framework by showing that several normal forms of the literature are natural corollaries. We recover the state of the art two-qubit gate depth necessary for the execution of a Clifford circuit on an LNN architecture, concomitantly with another work. We also propose practical synthesis algorithms for Clifford isometries with a focus on Clifford operators, graph states and codiagonalization of Pauli rotations. Benchmarks show that in all three cases we improve the 2-qubit gate count and depth of random instances compared to the state-of-the-art methods. We also improve the execution of practical quantum chemistry experiments.
Quantum computers are only as powerful as the compilers that optimize the circuits they run. As quantum hardware scales, reducing gate counts and circuit depth becomes critical for practical computation. This work implements a core synthesis algorithm in OCaml that maps arbitrary Cliffords to circuits, a fundamental building block in quantum circuit compilation. The Clifford synthesis implementation is designed around how LambdaPC thinks about quantum computation, through Pauli operators. It frames synthesis as a search problem: given a Clifford tableau, find a path to the identity by applying gates. Working factor by factor, it reduces each Pauli pair (P, Q) to a canonical (Z_i, X_i) form using single-qubit Clifford gates and TQE gates, until the full tableau is decomposed into an executable circuit. The main challenge was working within LambdaPC's typed representation, where n-qubit Paulis are encoded as nested pairs. This required helper functions to extract Pauli data from those structures and pattern-matching logic to find minimal gate sequences, laying the groundwork for end-to-end Clifford compilation in LambdaPC.
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.
The efficiency of compiling high-level quantum algorithms into instruction sets native to quantum computers defines the moment in the future when we will be able to solve interesting and important problems on quantum computers. In my work I focus on the new methods for compiling single qubit operations that appear in many quantum algorithms into single qubit operations natively supported by several popular architectures. In addition, I study several questions related to synthesis and optimization of multiqubit operations. \n \n \nWhen studying the single qubit case, I consider two native instruction sets. The first one is Clifford+T; it is supported by conventional quantum computers implementing fault tolerance protocols based on concatenated and surface codes, and by topological quantum computers based on Ising anyons. The second instruction set is the one supported by topological quantum computers based on Fibonacci anyons. I show that in both cases one can use the number theoretic structure of the problem and methods of computational algebraic number theory to achieve improvements over the previous state of the art by factors ranging from 10 to 1000 for instances of the problem interesting in practice. This order of improvement might make certain interesting quantum computations possible several years earlier. \n \n \nThe work related to multiqubit operations is on exact synthesis and optimization of Clifford+T and Clifford circuits. I show an exact synthesis algorithm for unitaries generated by Clifford+T circuits requiring exponentially less number of gates than previous state of the art. For Clifford circuits two directions are studied: the algorithm for finding optimal circuits acting on a small number of qubits and heuristics for larger circuits optimization. The techniques developed allows one to reduce the size of encoding and decoding circuits for quantum error correcting codes by 40-50\\% and also finds their applications in randomized benchmarking protocols.
Quantum error-correcting codes are used to protect qubits involved in quantum computation. This process requires logical operators to be translated into physical operators acting on physical quantum states. In this article, we propose a mathematical framework for synthesizing physical circuits that implement logical Clifford operators for stabilizer codes. Circuit synthesis is enabled by representing the desired physical Clifford operator in CN×Nas a 2m × 2m binary symplectic matrix, where N = 2m. We prove two theorems that use symplectic transvections to efficiently enumerate all binary symplectic matrices that satisfy a system of linear equations. As a corollary, we prove that for an [[m, k]] stabilizer code every logical Clifford operator has 2r(r+1)/2symplectic solutions, where r = m - k, up to stabilizer degeneracy. The desired physical circuits are then obtained by decomposing each solution into a product of elementary symplectic matrices, that correspond to elementary circuits. This enumeration of all physical realizations enables optimization over the ensemble with respect to a suitable metric. Furthermore, we show that any circuit that normalizes the stabilizer can be transformed into a circuit that centralizes the stabilizer, while realizing the same logical operation. Our method of circuit synthesis can be applied to any stabilizer code, and this paper discusses a proof of concept synthesis for the [[6, 4, 2]] CSS code. Programs implementing the algorithms in this article, which includes routines to solve for binary symplectic solutions of general linear systems and our overall LCS (logical circuit synthesis) algorithm, can be found at https://github.com/nrenga/symplectic-arxiv18a
In this letter, we introduce a method to synthesize an n-qubit Clifford unitary C from the stabilizer tableau of its inverse C†, using ancilla qubits and measurements. The procedure uses ancillary ∣+⟩ states, controlled-Paulis, X-basis measurements and single-qubit Pauli corrections on the data qubits (based on the measurement results). This introduces a new normal form for Clifford synthesis, with the number of two-qubit gates required exactly equal to the weight of the stabilizer tableau, and a depth linear in n.
Quantum error-correcting codes can be used to protect qubits involved in quantum computation. This requires that logical operators acting on protected qubits be translated to physical operators (circuits) acting on physical quantum states. We propose a mathematical framework for synthesizing physical circuits that implement logical Clifford operators for stabilizer codes. Circuit synthesis is enabled by representing the desired physical Clifford operator in CN×Nas a 2m×2m binary sym-plectic matrix, where N=2m. We show that for an [[ m, m-k ]] stabilizer code every logical Clifford operator has 2k(k+1)/2symplectic solutions, and we enumerate them efficiently using symplectic transvections. The desired circuits are then obtained by writing each of the solutions as a product of elementary symplectic matrices. For a given operator, our assembly of all of its physical realizations enables optimization over them with respect to a suitable metric. Our method of circuit synthesis can be applied to any stabilizer code, and this paper provides a proof of concept synthesis of universal Clifford gates for the well-known [[ 6,4,2 ]] code. Programs implementing our algorithms can be found at https://github.com/nrenga/symplectic-arxiv18a.