The Optimization and Application of 3-Bit Hermitian Gates and Multiple Control Toffoli Gates

Abstract

The well-known 3-bit Hermitian gate (a Toffoli gate) has been implemented using Clifford+T circuits. Compared with the Peres gate, its implementation circuit requires more controlled-not (cnot) gates. However, the Peres gate is not Hermitian. This article reports four 3-bit Hermitian gates named LI gates, whose realized circuits have the same T-count, T-depth, and cnot-count as the Peres gate. Furthermore, two decomposition methods of a multiple-control Toffoli (MCT) gate are proposed for different primary optimization goals. Then, we design the equality, less-than, and full comparators with the minimum circuit width using proposed Hermitian gates and optimized MCT gates. A fault-tolerant circuit is required for robust quantum computing. Clifford+T circuits are accepted solutions for fault-tolerant implementation. Considering T-count, T-depth, cnot-count, and circuit width as the primary optimization goals, we design the optimized Clifford+T circuits of three comparators using LI gates and optimized MCT gates. Comparison and analysis show that the proposed comparators have better overall performances for T-count, T-depth, cnot-count, and circuit width than the best-known comparators without quantum measurements.

Keywords

• Multiple control Toffoli (MCT) gate
• quantum algorithm
• quantum circuit
• quantum comparator
• quantum optimizing method