Optimal Representation of (123) from the Symmetric Group S3 in terms of Quantum Circuits

Abstract

The symmetric group plays a vital role in abstract algebra, impacting mathematics and physics. Quantum circuits, especially in communication, utilize strategies like the CNOT gate and local unitary gates, influencing quantum cost. Minimizing this cost is crucial by using the fewest non-local unitary gates. The existing works proves that representing the element (12) in S₂ requires at least three CNOT gates, however, the representation of CNOT gates with the minimal quantum cost is still unexplored. This study focuses on the element (123) in S₃, aiming to reduce quantum costs. Using the Strassen tensor, we find the Schmidt rank for (123) is 7. With this, we prove that achieving (123) with only 2 CNOT gates is impractical. Exhaustive enumeration rules out 3 or 4 CNOT gates. We analyze circuit states after each CNOT gate application to eliminate non-equivalent configurations. Finally, we propose a construction using 6 CNOT gates for (123). We introduce theorems for cataloging non-equivalent circuits, tracking states pre- and post-CNOT gate operations, and computing outputs. Whether 5 CNOT gates suffice for (123) remains open. These theorems can extend to optimal circuit representations for other symmetric group elements, like (1234) and (12345).