To achieve large-scale fault-tolerant quantum computation, it may be easier to combine many small sets of qubits than to construct a single large set. For example via quantum error correction with block codes, or distributed quantum processors utilizing shared entanglement. In these regimes, the time or error budget of the overall quantum computation may be dominated by non-local operations. Hence, it is worthwhile to minimize the number of these operations. We consider the case where both non-local and local connectivity may be arbitrarily restricted, and give an asymptotically optimal synthesis method for distributed CNOT and Clifford circuits, based on block-matrix Gaussian elimination. We extend this to all Clifford+RZ circuits by generalizing the Pauli exponential circuit representation; this naturally integrates with existing methods for optimizing T-count. As an application, we show how to implement CNOT circuits in a CSS code encoding n logical qubits in k blocks using O(nk) inter-block transversal CNOTs and intra-block Pauli measurements.
To achieve large-scale fault-tolerant quantum computation, it may be easier to combine many small sets of qubits than to construct a single large set. For example via quantum error correction with block codes, or distributed quantum processors utilizing shared entanglement. In these regimes, the time or error budget of the overall quantum computation may be dominated by non-local operations. Hence, it is worthwhile to minimize the number of these operations. We consider the case where both non-local and local connectivity may be arbitrarily restricted, and give an asymptotically optimal synthesis method for distributed CNOT and Clifford circuits, based on block-matrix Gaussian elimination. We extend this to all Clifford+RZ circuits by generalizing the Pauli exponential circuit representation; this naturally integrates with existing methods for optimizing T-count. As an application, we show how to implement CNOT circuits in a CSS code encoding n logical qubits in k blocks using O(nk) inter-block transversal CNOTs and intra-block Pauli measurements.
Efficiently implementing Clifford circuits is crucial for quantum error correction and quantum algorithms. Linear reversible circuits, equivalent to circuits composed of CNOT\xspace gates, have important applications in classical computing. In this work we present methods for CNOT\xspace and general Clifford circuit synthesis which can be used to minimise either the entangling two-qubit gate count or the circuit depth. We present three families of algorithms - optimal synthesis which works on small circuits, A* synthesis for intermediate-size circuits and greedy synthesis for large circuits. We benchmark against existing methods, including rustiq, tket and qiskit and show that our approach results in circuits with lower two-qubit gate count. For encoding circuits, our methods outperform previous reinforcement learning results and find a lower two-qubit gate count circuit for the Golay code than previously known. The algorithms have been implemented in a GitHub repository for use by the classical and quantum computing community.
Preparing arbitrary logical states is a central primitive for universal fault-tolerant quantum computation and the cost of encoded-state preparation contributes directly to the overall resource overhead. This makes the synthesis of efficient general-state encoding circuits an important problem, particularly with respect to two-qubit gate count and circuit depth. Yet the synthesis of such encoders has been studied less extensively than general Clifford circuit synthesis or the preparation of specific logical Pauli-eigenstates. In this work, we develop methods for synthesizing efficient encoders for arbitrary stabilizer codes. We formulate encoder synthesis as a search over stabilizer tableaus and introduce greedy and rollout-based algorithms that exploit the freedom among stabilizer-equivalent realizations of the same encoding isometry. For code families with a modular structure, such as generalized concatenated and holographic codes, we show how large encoders can be assembled from optimized local constituent encoders, and we use SMT-based exact synthesis to obtain optimal local circuits for small instances. We further evaluate the proposed methods on a broad set of stabilizer codes, including holographic and quantum low-density parity-check (qLDPC) codes, and compare them against recent encoder-synthesis methods and existing constructions from the literature, obtaining improvements of up to 43% in two-qubit gate count and up to 70% in depth. Our results support the optimization of encoded-state preparation in several fault-tolerant quantum-computing schemes, and all methods are openly available as part of the Munich Quantum Toolkit.
Decoherence jeopardizes the entanglement of fragile quantum states, and is among the foremost challenges towards engineering scalable quantum computers. Realizing quantum circuit implementation with small qubit count and shallow circuit depth is necessary due to the linear scaling of decoherence rate with qubit count and circuit depth. Conversely, reasonable correction of small unitary errors can be achieved by using surface codes along with a transversal gate set to protect quantum information from decoherence. In this paper, we analyze and report the upper bound of non-Clifford phase-depth for different mapping schemes and synthesis approaches. We introduce a synthesis methodology based on lookup-table (LUT) networks, wherein the Boolean logic translates into fault-tolerant quantum logic using Clifford+ Z N group with zero ancillary cost. We also present fault-tolerant synthesis techniques for k -LUT network using additional ancillary lines with exponential phase-count and unit phase-depth.
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.
Although with some yet severe limitations, Physical working Quantum Computers are becoming available for end users. Such devices are based on the rules of Quantum Mechanics, which state that physical systems evolve through unitary transformations. However, as in the classical case, in order to have a model of computation, such unitary evolutions are expressed/approximated inside Quantum Computers in terms of a finite set of one/two qubit operations (i.e., through a universal set of gates). Single qubit gates are fault-tolerant, while the same cannot be said for two qubit gates. Hence, unitary matrices adopted in Quantum Algorithms must be synthesized in terms of this universal set of operations to obtain a quantum circuit. In such synthesis procedure we prefer circuits with minimum number of qubits and with minimum circuit depth. Clifford+T universal set is one of the most adopted in the literature for synthesis. In such set we have 3 single qubit gates and the CNOT, which is a two qubit gate. Many efforts have been directed to devise algorithms that synthesize general unitary matrices into Clifford+T circuits. These algorithms usually tend to optimize circuit depth or eventually the number of T gates. Since two qubit gates are not fault tolerant, in this work we propose an ASP based technique to minimize the number of CNOT gates inside a Clifford+T circuit. Moreover, in real world quantum computers, qubit are usually connected to each other according to some particular topology, thus providing further constraints. Two qubit gates —hence, CNOT gate— can be directly applied only to pair of gates that are connected. Such constraint has to be taken into account during the synthesis of CNOT minimal circuits. We propose an ASP model to solve the problem of synthesizing CNOT minimal circuits under topological constraints. We provide experimental evidence of the scalability of our proposal.
Clifford circuit optimization is an important step in the quantum compilation pipeline. Major compilers employ heuristic approaches. While they are fast, their results are often suboptimal. Minimization of noisy gates, like 2-qubit CNOT gates, is crucial for practical computing. Exact approaches have been proposed to fill the gap left by heuristic approaches. Among these are SAT based approaches that optimize gate count or depth, but they suffer from scalability issues. Further, they do not guarantee optimality on more important metrics like CNOT count or CNOT depth. A recent work proposed an exhaustive search only on Clifford circuits in a certain normal form to guarantee CNOT count optimality. But an exhaustive approach cannot scale beyond 6 qubits. In this paper, we incorporate search restricted to Clifford normal forms in a SAT encoding to guarantee CNOT count optimality. By allowing parallel plans, we propose a second SAT encoding that optimizes CNOT depth. By taking advantage of flexibility in SAT based approaches, we also handle connectivity restrictions in hardware platforms, and allow for qubit relabeling. We have implemented the above encodings and variations in our open source tool Q-Synth. In experiments, our encodings significantly outperform existing SAT approaches on random Clifford circuits. We consider practical VQE and Feynman benchmarks to compare with TKET and Qiskit compilers. In all-to-all connectivity, we observe reductions up to 32.1% in CNOT count and 48.1% in CNOT depth. Overall, we observe better results than TKET in the CNOT count and depth. We also experiment with connectivity restrictions of major quantum platforms. Compared to Qiskit, we observe up to 30.3% CNOT count and 35.9% CNOT depth further reduction.