Most work in quantum circuit optimization has been performed in isolation from the results of quantum fault-tolerance. Here we present a polynomial-time algorithm for optimizing quantum circuits that takes the actual implementation of fault-tolerant logical gates into consideration. Our algorithm resynthesizes quantum circuits composed of Clifford group and T gates, the latter being typically the most costly gate in fault-tolerant models, e.g., those based on the Steane or surface codes, with the purpose of minimizing both T-count and T-depth. A major feature of the algorithm is the ability to resynthesize circuits with ancillae at effectively no additional cost, allowing space-time trade-offs to be easily explored. The tested benchmarks show up to 65.7% reduction in T-count and up to 87.6% reduction in T-depth without ancillae, or 99.7% reduction in T-depth using ancillae.
Most work in quantum circuit optimization has been performed in isolation from the results of quantum fault-tolerance. Here we present a polynomial-time algorithm for optimizing quantum circuits that takes the actual implementation of fault-tolerant logical gates into consideration. Our algorithm resynthesizes quantum circuits composed of Clifford group and T gates, the latter being typically the most costly gate in fault-tolerant models, e.g., those based on the Steane or surface codes, with the purpose of minimizing both T-count and T-depth. A major feature of the algorithm is the ability to resynthesize circuits with ancillae at effectively no additional cost, allowing space-time trade-offs to be easily explored. The tested benchmarks show up to 65.7% reduction in T-count and up to 87.6% reduction in T-depth without ancillae, or 99.7% reduction in T-depth using ancillae.
Abstract An important part of reaping computational advantage from a quantum computer is to reduce the quantum resources needed to implement a desired quantum algorithm. Quantum algorithms that are too large to be practical on noisy intermediate scale quantum devices will require fault-tolerant error correction. This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, in this paper we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford + T gate set. The Clifford + T gate set is a universal gate set and in this group, using state-of-the-art surface codes, the T gate is by far the most expensive component to implement fault-tolerantly. So it is important to minimize the number of T gates necessary for a fault-tolerant implementation. Our primary interest is to compute a circuit for a given n -qubit unitary U , using the minimum possible number of T gates (called the T-count of unitary U ). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of U . In its decision version the goal is to decide if the T-count is at most some positive integer m . Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of U . We give a provable classical algorithm that solves COUNT-T (decision) in time O N 2 ( c − 1 ) ⌈ m c ⌉ p o l y ( m , N ) and space O N 2 ⌈ m c ⌉ p o l y ( m , N ) , where N = 2 n and c ⩾ 2. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of N 0.7457 off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal circuit and has space and time complexity poly( m , N ), under some assumptions. In our heuristic algorithm we developed a novel way of pruning the search space. While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent), there is a large improvement by going from exponential to polynomial scaling with m . We implemented our heuristic algorithm with up to 4 qubit unitaries and obtained a significant improvement in time. For all benchmark and random unitaries we studied, the T-count returned by our algorithm is at most the T-count of their circuits shown in previous papers.
The Clifford+T gate library consisting of Hadamard, T, and CNOT gates has attracted much interest in quantum circuit synthesis, particularly due to its applicability to fault tolerant realizations. Since fault tolerant implementations of the T gate have very high latency, recent work in this area is aiming at minimizing the number of T stages, referred to as the T-depth. In this paper, we present an approach to exploit additional ancilla qubits in the mapping of reversible circuits consistina of multiple controlled Toffoli gates (MCT gates) into califford+T quantum circuits, with the primary optimization objective to minimize the T-depth. Our proposed approach takes advantage of and generalizes earlier work on corresponding mapping algorithms. An experimental evaluation shows that our approach leads to a significant T-depth reduction compared to earlier approaches.
Hamiltonian simulation is a key quantum algorithm for modeling complex systems. To implement a Hamiltonian simulation, it is typically decomposed into a list of Pauli strings, each corresponds to an RZ rotation gate with many Clifford gates. These RZ gates are generally synthesized into a sequence of Clifford and T gates in fault-tolerant quantum computers, where the T-gate count and T-gate depth are critical metrics for such systems. In this paper, we propose NCF, a compilation framework that reduces both the T-gate count and T-gate depth for Hamiltonian simulation. NCF partitions Pauli strings into groups, where each group can be conjugated (i.e., transformed) into a list of Pauli strings that apply quantum gates on a restricted subset of qubits, allowing for simultaneous synthesis of the whole group and reducing both T-gate count and depth. Experimental results demonstrate that NCF achieves an average reduction of 57.4%, 49.1%, and 49.0% in T-gate count, T-gate depth, and Clifford count, respectively, compared to the state-of-the-art method.
The Clifford+ T gate set is commonly used to perform universal quantum computation. In such setup the T gate is typically much more expensive to implement in a fault-tolerant way than Clifford gates. To improve the feasibility of fault-tolerant quantum computing it is then crucial to minimize the number of T gates. Many algorithms, yielding effective results, have been designed to address this problem. It has been demonstrated that performing a pre-processing step consisting of reducing the number of Hadamard gates in the circuit can help to exploit the full potential of these algorithms and thereby lead to a substantial T -count reduction. Moreover, minimizing the number of Hadamard gates also restrains the number of additional qubits and operations resulting from the gadgetization of Hadamard gates, a procedure used by some compilers to further reduce the number of T gates. In this work we tackle the Hadamard gate reduction problem, and propose an algorithm for synthesizing a sequence of π /4 Pauli rotations with a minimal number of Hadamard gates. Based on this result, we present an algorithm which optimally minimizes the number of Hadamard gates lying between the first and the last T gate of the circuit.
Abstract Fault-tolerant quantum computation (FTQC) schemes using large block codes that encode k > 1 qubits in n physical qubits can potentially reduce the resource overhead to a great extent because of their high encoding rate. However, the fault-tolerant (FT) logical operations for the encoded qubits are difficult to find and implement, which usually takes not only a very large resource overhead but also long in situ computation time. In this paper, we focus on Calderbank–Shor–Steane [[ n , k , d ]] (CSS) codes and their logical FT Clifford circuits. We show that the depth of an arbitrary logical Clifford circuit can be implemented fault-tolerantly in O (1) steps in situ via either Knill or Steane syndrome measurement circuit, with the qualified ancilla states efficiently prepared. Particularly, for those codes satisfying k / n ∼ Θ(1), the resource scaling for Clifford circuits implementation on the logical level can be the same as on the physical level up to a constant, which is independent of code distance d . With a suitable pipeline to produce ancilla states, our scheme requires only a modest resource cost in physical qubits, physical gates, and computation time for very large scale FTQC.
The Clifford+T quantum gate library has attracted much interest in the design of quantum circuits, particularly since the contained operations can be implemented in a fault-tolerant manner. Since fault tolerant implementations of the T gate have very high latency, synthesis and optimization are aiming at minimizing the number of T stages, referred to as the T-depth. In this paper, we present an approach to map mixed polarity multiple controlled Toffoli gates into Clifford+T quantum circuits. Our approach is based on the multiple control Toffoli mapping algorithms proposed by Barenco et al., which are given T-depth optimized Clifford+T translations. Experiments show that our approach leads to a significant T-depth reduction of 54% on average.