2024/09/04 by Qiqing Xia, Xia, Qiqing, Huiqin Xie +3
Computer Science · Engineering · #FOS: Physical sciences #Optical Network Technologies #PAPR reduction in OFDM #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2409.02506
openalex publication_date 2024/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The quantum Fourier transform (QFT) is a crucial subroutine in many quantum algorithms. In this paper, we study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. First, we consider approximating the ancilla-free controlled-Rk in the QFT logical circuit with a standard set of universal gates, aiming to minimize the number of T gates. Various single-qubit gates are generated in addition to CNOT gates when the controlled-Rk is decomposed in different ways, we propose an algorithm that combines numerical and analytical methods to exactly compute the minimum T gate count for approximating any single-qubit gate with any given accuracy. Afterwards, we prove that the exact lower bound problem of T gate complexity for the QFT is NP-complete. Furthermore, we provide the transversal implementation of universal quantum gates and prove that it has the minimum number of CNOT gates and analyze the minimum CNOT count for transversally implementing the T gate. We then exactly compute the exact lower bound of CNOT gate complexity for fault-tolerant QFT with the current maximum fault-tolerant accuracy 10-2. Our work can provide a reference for designing algorithms based on active defense in a quantum setting.