The exact lower bound of CNOT-complexity for fault-tolerant quantum Fourier transform
Qiqing Xia Huiqin Xie Li Yang


A background-estimation technique for the detection of extended gamma-ray structures with IACTs
     T. Wach 1 A. Mitchell 1 L. Mohrmann 2
    September 9, 2024
===============================================================================================





§ ABSTRACT 
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-R_k 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-R_k 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.








§ INTRODUCTION

A lower bound exists on the time for quantum gates due to physical limitations, making it necessary to study the optimal implementation of quantum circuits. Especially, the quantum Fourier transform (QFT) <cit.> is a key subroutine in many quantum algorithms, such as Shor's algorithm for solving integer factorization and discrete logarithm problems <cit.>, quantum amplitude estimation <cit.>, phase estimation <cit.>, solving systems of linear equations <cit.>, quantum arithmetic <cit.> and various fast quantum algorithms for solving hidden subgroup problems <cit.>. The efficient execution of the QFT on quantum computers is crucial for the success of algorithms. One of its significant applications is to break the cryptosystems such as RSA <cit.> and ElGamal <cit.>. One of the most feasible candidates for these large-scale quantum computations is fault-tolerant quantum computation (FTQC) <cit.>. FTQC must further rely on the Clifford gates and T gates, and any single-qubit gate can be approximated to an arbitrary accuracy using a circuit composed of these gates. However, the T gate requires ancillary states and CNOT gates for transversal implementation, which is relatively expensive <cit.>. The number of T gates can serve as a first-order approximation of the resources for physically implementing a quantum circuit.

Currently, there are two main methods for optimizing the number of T gates in QFT circuits. One method is to define an approximate version of the QFT (AQFT) <cit.> by removing all rotation gates with angles below a certain threshold, thereby optimizing the number of T gates for the AQFT <cit.>. The other is to decompose the controlled-R_k gates in the QFT circuit and use gate synthesis or state distillation methods to approximate the single-qubit gates. In <cit.>, this work compares the resources for gate synthesis and state distillation, concluding that gate synthesis is a better method for implementing the fault-tolerant QFT. The optimal method for gate synthesis is provided by Solovay-Kitaev algorithm <cit.>, and the number of T gates for approximating any single-qubit gate is 𝒪(log^3.97/ϵ). Based on this, <cit.> uses a numerical method to find the fault-tolerant approximation properties of the phase rotation gates in exponential time. The optimization methods for the number of T gates required to approximate any single-qubit gate include probabilistic algorithms with feedback <cit.>, efficient random algorithms <cit.>, using Repeat-Until-Success circuits <cit.>, using auxiliary qubits <cit.>, efficient approximation algorithms achieving accuracy 10^-15 <cit.>, rounding off a unitary to a unitary over the ring 𝒵[i,1/√(2)] <cit.>, and probabilistic approximation for Z-rotation gates based on the gridsynth algorithm <cit.>.

These related works focus on optimizing the number of logical T gates associated with the QFT using approximation algorithms. However, the specific implementation of a quantum computer is influenced by physical factors, as it is fundamentally a physical system. In FTQC, the CNOT gate is regarded as the main cause of quantum errors <cit.> and has a longer execution time than single-qubit gates. The computational complexity of quantum algorithms can be reduced to the number of CNOT gates <cit.>, and minimizing the number of CNOT gates is typically regarded as a secondary optimization objective, such as optimizing the number of CNOT gates in the quantum circuit for Shor's algorithm <cit.>. However, the problem of CNOT-optimal quantum circuit synthesis over gate sets consisting of CNOT and phase gates is NP-complete <cit.>. In some cases, optimizations aimed at reducing the number of T gates can result in a significant increase in the number of CNOT gates. Fortunately, we have found a method to make up for the explosion of CNOT gates with cost savings by optimizing T gates. Proving the ancilla-assisted gate synthesis with the minimum number of CNOT gates is challenging, while it is provable for the ancilla-free gate synthesis. Thus, in this way, we can obtain the exact lower bound of CNOT gate complexity for fault-tolerant QFT, which is different from previous works. To our knowledge, there has not been such an analysis before. This analysis is of great significance and can provide a reference for active defense in a quantum setting.

Our contributions 
In this paper, we consider the logical resources and fault-tolerance resources of the QFT. The logical resources are measured by the number of T gates, which is called the T-count. Since the fault-tolerant implementation of the T gate relies on CNOT gates, the fault-tolerance resources are measured by the number of CNOT gates, which is called the CNOT-count. In more detail, our main contributions are as follows:

    
  * First, we find an ancilla-free gate synthesis method for a controlled-R_k gate with the minimum T-count and we have provided the corresponding proof. Interestingly, this method also achieves the minimum fault-tolerant CNOT-count. When the controlled-R_k is decomposed in different ways, it generates different single-qubit gates in addition to CNOT gates. Since current quantum computers cannot implement all single-qubit gates, as a generalization we propose an algorithm to exactly compute the minimum T-count for approximating any single-qubit gate with any given accuracy by using Hadamard gates and T gates. This algorithm uses analytical methods to avoid traversing all quantum states in the normalized space and uses numerical methods to determine whether the error conditions are satisfied. Afterwards, we prove that the exact lower bound problem of the T-count for the QFT is at least as hard as the K-SAT problem and it is an NP-complete problem.
    
    
  * Furthermore, we provide a transversal implementation of Z-rotation gates satisfying certain conditions with the minimum CNOT-count and analyze the minimum CNOT-count for transversally implementing the T gate. We then compute the exact lower bound of CNOT gate complexity for fault-tolerant QFT with different input lengths at the current maximum fault-tolerant accuracy 10^-2 <cit.>. In particular, we estimate the lower bound of the effective execution time of the QFT based on Steane code on ion trap computers, which can provide a reference for quantum computation based on the QFT. Finally, we discuss that determining the best possible value of c in 𝒪(log^c(1/ϵ)) implied by the Solovay–Kitaev theorem is at least NP-hard, and the circuit optimization problem is at least QMA-hard.





§ PRELIMINARIES



 §.§ Common quantum gates

We briefly recall Clifford and T quantum gates, including universal gates and Pauli-X (Y, Z) gates. Their circuit symbols and matrix representations are shown in Figure <ref>.

Here, {H, S, T, CNOT} is called the standard set of universal gates. When the Pauli matrices are exponentiated, they will produce three types of useful unitary matrices, namely, the rotation operators around the x̂, ŷ and ẑ axes, defined as follows:


    R_x(θ)≡ e^-iθ X/2=cos θ/2I-isin θ/2X=[   cos θ/2 -isin θ/2; -isin θ/2   cos θ/2 ],   
       R_y(θ)≡ e^-iθ Y/2=cos θ/2I-isin θ/2Y=[  cos θ/2 -sin θ/2;  sin θ/2  cos θ/2 ],   
       R_z(θ)≡ e^-iθ Z/2=cos θ/2I-isin θ/2Z=[ e^-iθ/2       0;       0  e^iθ/2 ],

if rotating by an angle θ around the axis n̂=(n_x,n_y,n_z), then the rotation operator can be denoted as
    
    R_n̂(θ)=cosθ/2I-isinθ/2(n_xX+n_yY+n_zZ),

these rotation operators play a crucial role in decomposing controlled unitary operators.



 §.§ Approximating controlled single-qubit unitary operators

We first introduce a lemma on the decomposition of a single-qubit unitary operator and a theorem on the decomposition of its controlled operator, as proven in <cit.>:

Suppose U is a unitary operator on a single qubit, then there exist real numbers α,β,γ and δ∈ [0,2π), such that

    U=e^iαR_z(β)R_y(γ)R_z(δ) =[  e^i(α-β/2-δ/2)cosγ/2 -e^i(α-β/2+δ/2)sinγ/2;  e^i(α+β/2-δ/2)sinγ/2  e^i(α+β/2+δ/2)cosγ/2 ].


It can be extended to a more general case: suppose m̂ and n̂ are non-parallel real unit vectors in the three-dimensional space, then U can be written as

    U=e^iαR_n̂(β)R_m̂(γ)R_n̂(δ),

for appropriate choices of α,β,γ and δ.


For any controlled single-qubit unitary operator controlled-U, up to a global phase, it can be decomposed into two CNOT gates and three single-qubit unitary operators, the theorem is as follows:

Suppose U is a unitary gate on a single qubit, then there exist single-qubit unitary operators P≡ e^iα/2R_z(α), A≡ R_z(β)R_y(γ/2),B≡ R_y(-γ/2)R_z(-(δ+β)/2),C≡ R_z((δ-β)/2), such that ABC=I and U=e^iαAXBXC, where α is a global phase factor. Then, the controlled-U operation is C(U)=(P⊗ A) · CNOT · (I⊗ B) · CNOT · (I⊗ C). The circuit implementation is shown in Figure <ref>.



The set of universal gates {H, S, T, CNOT} is discrete, while the set of unitary operations is continuous. Approximating any unitary operation using this discrete set will inevitably introduce errors, as defined in <cit.>:

    Let U and V be two unitary operators on the same state space, where U is the desired target unitary operator and V is the unitary operator actually implemented. Define the error when V is implemented instead of U as
    
    E(U,V)=max_|ψ⟩||(U-V)|ψ⟩||

where the maximum takes all normalized quantum states |ψ⟩ in the state space.


The Solovay–Kitaev theorem <cit.> is one of the most important fundamental results in the theory of quantum computation. It shows that for any single-qubit gate U and given any ϵ>0, U can be approximated to an accuracy ϵ with 𝒪(log^c(1/ϵ)) finite gates.

    Let SU(2) be the set of all single-qubit unitary matrices with determinant 1, and 𝒢 be a finite set of elements in SU(2) including its own inverses, used to simulate other single-qubit gates. Let g_1⋯ g_l (g_i∈𝒢, i=1,⋯,l) be a word of length l from 𝒢, 𝒢_l be the set of all words of length at most l, and ⟨𝒢⟩ be the set of all words with finite length. If ⟨𝒢⟩ is dense in SU(2), then 𝒢_l is an ϵ-net in SU(2) for l=𝒪(log^c(1/ϵ)), where c ≈ 2 when using the measure E(·,·), or c ≈ 4 when using the trace distance D(·,·), as D(·,·)=2E(·,·). In our work, we use the measure E(·,·) as show in Definition <ref>.




 §.§ The quantum Fourier transform


The QFT is a linear operator on an orthonormal basis |0⟩,⋯,|N-1⟩, and its action on the basis states is

    |j⟩1/√(N)∑_k=0^N-1e^2π ijk/N|k⟩.

Equivalently, the action on an arbitrary state can be written

    ∑_j=0^N-1x_j|j⟩1/√(N)∑_k=0^N-1y_k|k⟩,

where y_k is the discrete Fourier transform of the amplitudes x_j, y_k=∑_j=0^N-1x_je^2π ijk/N.


The QFT is a unitary transformation, and thus it can be implemented as a dynamic process on a quantum computer as follows:


1
Useful product representation of the QFT

    
  * First, suppose N=2^n, and represent j in binary as j_1j_2⋯ j_n, then j=j_12^n-1+j_22^n-2+⋯+j_n.
    
    
  * After performing the QFT on the basis state |j⟩, then we can obtain the useful product representation:
    
    |j_1,⋯,j_n⟩1/2^n/2(|0⟩+e^2π i0.j_n|1⟩)(|0⟩+e^2π i0.j_n-1j_n|1⟩)⋯(|0⟩+e^2π i0.j_1j_2⋯ j_n|1⟩),

    where 0.j_ℓj_ℓ+1⋯ j_m=j_ℓ/2+j_ℓ+1/2^2+⋯+j_m/2^m-ℓ+1 is a binary fraction.

    
  * Each tensor product component can be implemented by a controlled single-qubit unitary operation (controlled-R_k). Here, the single-qubit gate R_k denotes the unitary transformation
     
    R_k=[          1          0;          0 e^2π i/2^k ].






According to the useful product representation of the QFT in Eq. (<ref>), we introduce the construction of effective quantum circuits for the QFT <cit.>, as shown in Figure <ref>.


As can be seen from Figure <ref>, the efficient quantum circuit for the QFT requires n Hadamard gates, n(n-1)/2 controlled-R_k gates, and ⌊n/2⌋ swap gates.



§ THE EXACT LOWER BOUND PROBLEM OF T-COUNT FOR THE QFT

Although the standard QFT circuit is typically implemented in a specific way, as shown in Figure <ref>, the QFT circuit is not unique and can achieve the same function through equivalent circuit transformations. Therefore, all QFT circuits must be equivalent to the circuit shown in Figure <ref>, and thus we can aim to analyze the exact lower bound of the T-count for the QFT based on the circuit in Figure <ref>.


 §.§ Algorithm for approximating the ancilla-free controlled-R_k with the minimum T-count

Since current quantum computers cannot implement all single-qubit gates, the ancilla-free gate synthesis approximates single-qubit gates with the Hadamard gate and T gate. To approximate the controlled-R_k operation, the ancilla-free controlled-R_k can be decomposed into single-qubit gates in addition to CNOT gates. However, when different decomposition methods are used, the single-qubit gates decomposed from the controlled-R_k are also different. To approximate different single-qubit gates, we introduce a theorem from <cit.>, for which we have revised the relevant content. The theorem states that any single-qubit unitary operation can be approximated to arbitrary accuracy using the Hadamard gate and T gate, as follows:

    Up to an unimportant global phase, T has the same effect as R_z(π/4), and HTH has the same effect as R_x(π/4). Combining these two operations, according to Eq. (<ref>), we obtain
    
    
    T(HTH)   =e^iπ/4R_z(π/4)R_x(π/4)
       =e^iπ/4(cosπ/8I-isinπ/8Z)(cosπ/8I-isinπ/8X)
       =e^iπ/4((cosπ/8)^2I-isinπ/8(cosπ/8(X+Z)+sinπ/8Y))
       =e^iπ/4[ 1+e^-iπ/4/2 e^-iπ/4-1/2;  1-e^iπ/4/2  1+e^iπ/4/2 ].


Using only the Hadamard gate and T gate, the rotation operator R_n̂(θ)=R_z(π/4)R_x(π/4) can be constructed to approximate any rotation operator around the n̂ axe, where cosθ/2=(cosπ/8)^2, n̂=sinπ/8/sinθ/2(cosπ/8,sinπ/8,cosπ/8). Let R_m̂(θ))=HR_n̂(θ)H, m̂=sinπ/8/sinθ/2(cosπ/8,-sinπ/8,cosπ/8), n̂ and m̂ are real unit vectors that are not parallel in the three-dimensional space. According to Eq. (<ref>), there exist appropriate positive integers n_1,n_2,n_3,

    E(U,R_n̂(θ))^n_1HR_n̂(θ)^n_2HR_n̂(θ)^n_3)<ϵ,

where ϵ is the desired accuracy. For any given single-qubit operator U and any ϵ>0, a quantum circuit consisting only of Hadamard gates and T gates can approximate U within ϵ.


Based on Theorem <ref>, we propose an algorithm for exactly computing the minimum resources required to approximate any single-qubit unitary operator U with a given accuracy using V=R_n̂(θ)^n_1HR_n̂(θ)^n_2H R_n̂(θ)^n_3. The algorithm is as follows:



In Algorithm <ref>, the minimum resources are measured by the minimum of n_1+n_2+n_3. The minimum T-count is twice min n_sum, Since R_n̂(θ)=THTH,R_m̂(θ)=HTHT.


Since a computer is a discrete computing device, it is impossible to traverse all |ψ⟩ in the normalized space. To avoid this problem and ensure that our algorithm is exact, we combine numerical and analytical methods to perform a mathematical transformation in step 9 of Algorithm <ref>, transforming this traversal problem into an extremum determination problem. The analytical method can avoid traversing all quantum states in the normalized space, and the numerical method can be used to determine whether the error conditions are satisfied. When the accuracy of the extremum computed by computers is much smaller than ϵ, step 10 will not result in any misjudgment. The transformation is as follows:


1
Mathematical computation in step 9 of Algorithm <ref>

    
  * Let |ψ⟩=cosω/2|0⟩+e^iφsinω/2|1⟩, ω∈ [0,π],φ∈ [0,2π), then |ψ⟩=[     cosω/2; e^iφsinω/2 ].
    
    
  * Let f(ω, φ)=||(U-V)|ψ⟩||, where f(ω, φ) is a continuous function over the domain. Then, compute the norm of the two-dimensional vector (U-V)|ψ⟩ for each set of n_1,n_2,n_3.

    
  * Compute the partial derivatives ∂ f/∂ω and ∂ f/∂φ of the function f(ω, φ) with respect to ω and φ such that ∂ f/∂ω=0 and ∂ f/∂φ=0.
    
        
  * If ∂ f/∂ω=0 has no solution, then ∂ f/∂ω>0 (or<0) always holds, and the local maximum point is the boundary point (π,φ_0) (or (0,φ_0)).
        
  * If ∂ f/∂φ=0 has no solution, then ∂ f/∂φ>0 (or<0) always holds, and f(ω, 0)≠ f(ω, 2π), which contradicts f(ω, 0)=f(ω, 2π)! Therefore, ∂ f/∂φ=0 must have a solution.
        
  * If both ∂ f/∂ω=0 and ∂ f/∂φ=0 have solutions, then the possible extremum points (ω_0,φ_0) are found.
    
    
    
  * Compute the second-order partial derivatives of the function f at (ω_0,φ_0) and construct the Hessian matrix D as follows:
    
    D=[ ∂^2 f/∂ω^2 ∂^2 f/∂ω∂φ; ∂^2 f/∂φ∂ω ∂^2 f/∂φ^2 ].

    
    
  * Compute the determinant (D) of the Hessian matrix D and determine the extremum point (ω_0,φ_0):
    
        
  * If (D)>0 and ∂^2 f/∂ω^2<0, then (ω_0,φ_0) is a local maximum point.
        
  * If (D)>0 and ∂^2 f/∂ω^2>0, then (ω_0,φ_0) is a local minimum point.
        
  * If (D)<0, then (ω_0,φ_0) is not an extremum point.
        
  * If (D)=0, then (ω_0,φ_0) may be a local maximum or minimum point.
    
    
    
  * By comparing the function values at all possible local extremum points and boundary points, determine the global maximum E(U,V)=max (f(ω,φ)).





We provide a lemma concerning the property of Algorithm <ref> as follows:

    
    Given a unitary operator U and a positive integer N_0≥ 3, if the minimum resources can be found within the search space 𝒪(N_0^3), then the execution process of Algorithm <ref> can be regarded as a function h(ϵ) related to the accuracy ϵ>0. h(ϵ) is a monotonically decreasing function, and h(ϵ)≥ 3 always holds. In particular, h(ϵ)=0 if and only if ϵ=0, and U is a matrix representation of a combination of the Clifford and T gates, or the identity matrix.


    Let ϵ_2>ϵ_1>0, if E≤ϵ_1, then the minimum resources satisfying the condition is h(ϵ_1), which must satisfy the condition E≤ϵ_2. Thus, h(ϵ_1)≥ h(ϵ_2). Conversely, if E≤ϵ_2, then the minimum resources satisfying the condition is h(ϵ_2), which does not necessarily satisfy the condition E≤ϵ_1. We need to continue to perform Algorithm <ref>, which ensures that h(ϵ_1)>h(ϵ_2). Therefore, h(ϵ_1)≥ h(ϵ_2), we conclude that h(ϵ) is a monotonically decreasing function.
    
    According to Theorem <ref>, n1,n2,n3 are all positive integers, h(ϵ)≥ 3 always holds. When h(ϵ)=0, it means that U does not need to be approximated, then ϵ=0. Thus, U is a matrix representation of a combination of the Clifford gate and the T gate, or the identity matrix.



Based on Lemma <ref>, we propose a property theorem about approximating the decomposition of unitary operators around the ẑ axis to analyze the minimum resources, as follows:

    R_Z(β_0) is a known rotation operator, and the sum of the resources for approximating its decomposition into n+1 rotation operators R_Z(β_0-β_1-⋯-β_n)R_Z(β_1)⋯ R_Z(β_n) is minimum if and only if β_1=⋯=β_n=0.


    For any given set of β_1,⋯,β_n and accuracy ϵ, we consider the following cases:
    
        Case 1: R_Z(β_0)=R_Z(β_0-β_1-⋯-β_n)R_Z(β_1)⋯ R_Z(β_n), let E(R_Z(β_0),V)<ϵ,E(R_Z(β_0-β_1-⋯-β_n),V_0)<ϵ_0,E(R_Z(β_1),V_1)<ϵ_1,⋯,E(R_Z(β_n),V_n)<ϵ_n,ϵ_0+ϵ_1+⋯+ϵ_n=ϵ, corresponding to the functions h(ϵ),h_0(ϵ_0),h_1(ϵ_1),⋯ h_n(ϵ_n), respectively. Here, V,V_0,⋯,V_n are the actual approximation operators of R_Z(β_0), R_Z(β_0-β_1-⋯-β_n),R_Z(β_1),⋯,R_Z(β_n) respectively.
        
        Case 2: R_Z(β_0-β_1-⋯-β_n)=R_Z(β_0)R_Z(-β_1)⋯ R_Z(-β_n), let E(R_Z(β_0-β_1-⋯-β_n),V_0')<ϵ,E(R_Z(β_0),V')<ϵ',E(R_Z(-β_1),V_1')<ϵ_1',⋯, E(R_Z(-β_n),V_n')<ϵ_n',ϵ'+ϵ_1'+⋯+ϵ_n'=ϵ, corresponding to the functions h_0(ϵ),h(ϵ'),h_1'(ϵ_1'),⋯,h_n'(ϵ_n'), respectively. Here, V',V_0',⋯,V_n' are the actual approximation operators of R_Z(β_0), R_Z(β_0-β_1-⋯-β_n),R_Z(-β_1),⋯,R_Z(-β_n) respectively.
    
    Case 1 and Case 2 can be transformed into each other and are equivalent, meaning that a known rotation operator around the ẑ axis can be decomposed into a set of rotation operators around the ẑ axis. Thus, h(ϵ)≤ h_0(ϵ_0)+h_1(ϵ_1)+⋯ +h_n(ϵ_n) for Case 1, and h_0(ϵ) ≤ h(ϵ')+h_1'(ϵ_1')+⋯ +h_n'(ϵ_n') for Case 2; or h(ϵ)≥ h_0(ϵ_0)+h_1(ϵ_1)+⋯ +h_n(ϵ_n) for Case 1, and h_0(ϵ) ≥ h(ϵ')+h_1'(ϵ_1')+⋯ +h_n'(ϵ_n') for Case 2. Here, h, h_0,⋯,h_n, h_1' ⋯,h_n' depend only on rotation operators. V, V_0,⋯, V_n, V', V_0' ⋯,V_n' depend on rotation operators and accuracy. Additionally, h(ϵ) is a constant for different sets of β_1,⋯,β_n.
    
    Now using the proof by contradiction, suppose h_0(ϵ) ≥ h(ϵ')+h_1'(ϵ_1')+⋯ +h_n'(ϵ_n'), then h_0(ϵ)≥ h(ϵ)+h_1'(ϵ)+⋯ +h_n'(ϵ) according to Lemma <ref>. Consequently, we have h_0(ϵ_0)+h_1(ϵ_1)+⋯ +h_n(ϵ_n) ≥ h_0(ϵ)+h_1(ϵ)+⋯ +h_n(ϵ) ≥ h(ϵ)+h_1'(ϵ)+⋯ +h_n'(ϵ)+h_1(ϵ)+⋯ +h_n(ϵ) ≥ h(ϵ), contradiction! In conclusion, h_0(ϵ) ≤ h(ϵ')+h_1'(ϵ_1')+⋯ +h_n'(ϵ_n') and h(ϵ)≤ h_0(ϵ_0)+h_1(ϵ_1)+⋯ +h_n(ϵ_n). That is, the resources for directly approximating R_Z(β_0) are minimum, achieving h(ϵ), if and only if β_1=⋯=β_n=0. 




 §.§ Complexity analysis

We now focus on the exact lower bound problem of the T-count for the QFT. We propose the following theorem, which states that a controlled single-qubit unitary operator satisfying certain conditions can be decomposed into one CNOT gate and two single-qubit gates that are conjugate transposes of each other.

    A unitary operator controlled-(UX) can be decomposed into one CNOT gate and two single-qubit gates that are conjugate transposes of each other, if and only if U=e^iαR_z(β)R_y(γ)R_z(β).


    Necessary condition: UX can written as e^iα'/2A'X(A')^†, then U=e^iα'/2A'X(A')^†X. According to Theorem <ref> and Eq. (<ref>), up to a global phase, A'≡ R_z(β)R_y(γ/2), A'^†≡ R_y(-γ/2)R_z(-β). Therefore, U=e^iαR_z(β)R_y(γ)R_z(β).
     
    Sufficient condition:
    U=e^iαR_z(β)R_y(γ)R_z(β), according to Eq. (<ref>), then δ=β. According to Theorem <ref>, let A=R_z(β)R_y(γ/2), B=R_y(-γ/2)R_z(-β), C=I, then UX=e^iαAXB, where B=A^†. Therefore, controlled-(UX) can be decomposed into one CNOT gate and two single-qubit gates that are mutually conjugate transpose.



The method for decomposing the ancilla-free controlled-R_k, as shown in Figure <ref>, requires the minimum T-count when A=I or C=I. The minimum T-count are the sum of those for approximating R_z(-π /2^k) and R_z(π /2^k).


    Suppose that there exists a decomposition method, as shown in Figure <ref>. Here, U=R_k, r is the number of CNOT gates, and P is the phase shift gate.
    
    When r is an odd number, let U_3=⋯=U_r+1=I, then R_k=U_1XU_2X. Therefore, R_k=U'X can be decomposed into one CNOT and two single-qubit gates U_1,U_2 that are mutually conjugate transpose, where U'=U_1XU_2. Combining Eq. (<ref>) and Eq. (<ref>), we can obtain
    
    R_k=[          1          0;          0 e^2π i/2^k ]=[  e^i(α-β/2-δ/2)cosγ/2 -e^i(α-β/2+δ/2)sinγ/2;  e^i(α+β/2-δ/2)sinγ/2  e^i(α+β/2+δ/2)cosγ/2 ].

    Thus, we have α=π /2^k, β+δ=π/2^k-1, γ=0, then R_k=e^iπ/2^kR_z(π/2^k-1). According to Theorem <ref>, R_kX=e^iπ/2^kR_z(π/2^k-1)R_y(π)R_z(-π) is satisfied if and only if k=1, i.e., R_k=Z. 
    
    Therefore, r can only be an even number for k=2,⋯,n. U_1,⋯,U_r+1 are the operators R_z(θ_1),⋯, R_z(θ_r+1) that rotate around the ẑ axis, then
    
    {   U_1U_2⋯ U_r+1=I ⟺θ_1+θ_2+⋯+θ_r+θ_r+1=0,
       U_1XU_2X⋯ XU_rXU_r+1=R_z(β+δ) ⟺θ_1-θ_2+⋯-θ_r+θ_r+1=β+δ,
        .

thus, θ_1+θ_3+⋯+θ_r+1=β+δ/2, θ_2+θ_4+⋯+θ_r=-β+δ/2. According to Theorem <ref>, if and only if there exist a certain θ_i=β+δ/2 for i=2ℓ-1, where ℓ=1,⋯,r/2+1, a certain θ_j=-β+δ/2 for j=2ℓ, where ℓ=1,⋯,r/2, the resources reach their minimum. At this point, r=2, this decomposition method corresponds to the one shown in Figure <ref>, where A=I or C=I. From Eq. (<ref>), A_k=R_z(β), B_k=R_z(-π /2^k), C_k=R_z(π /2^k-β), β∈[0,2π) for each k=2,⋯,n. Let β=0,  or π/2^k, A_K=I,C_k=R_z(π /2^k), or C_K=I,A_k=R_z(π /2^k), then the resources reach their minimum, i.e., the sum of those for approximating R_z(-π /2^k) and R_z(π /2^k). 


When k is fixed (the controlled-R_k is determined), then B_k is determined, while A_k,C_k are not unique and are related to β. To obtain the minimum resources, it is theoretically necessary to traverse β∈ (0,2π) and then compute the sum of the minimum resources min n_(A_k+C_k) for approximating A_k,C_k.
However, it is interesting that according to Proposition <ref>, the minimum sum of the resources for approximating A_k,C_k and B_k is equivalent to using Algorithm <ref> to compute the sum of those for approximating R_z(π /2^k) and R_z(-π /2^k). According to Remark <ref>, it follows that the minimum T-count is twice their resources. The exact lower bound problem of the T-count for the QFT can be considered as the problem of
determining an integer N_0 such that the minimum T-count for approximating R_z(π /2^k) or R_z(-π/2^k) with given accuracy ϵ can be found in the search space 𝒪(N_0^3), for all k=3,⋯,n. We call the problem ELBP_T-count. 

To show the NP-completeness of ELBP_T-count, we recall the K-SAT problem ((K≥ 3)) <cit.>. Given a finite set of boolean variables X={x_1,x_2,⋯,x_n},|X|=n, a set of clauses C={C_1,C_2,⋯,C_m},|C|=m,C=C_1  C_2 ⋯ C_m, each C_i is a disjunctive normal form consisting of K variables. Consider whether there exists a truth value assignment for a set of Boolean variables such that C is true. It is known that the K-SAT problem is a class of NP-complete problems <cit.>, hence we can use a reduction from K-SAT problem to prove NP-completeness of ELBP_T-count. We propose the following theorem:


     ELBP_T-count is NP-complete. 


    Given an integer N_0≥ 3, the search space is ∑_n_sum=3^N_0∑_n_1=1^n_sum-2(n_sum-n_1-1)=1/6N_0(N_0-1)(N_0-2)=𝒪(N_0^3) according to steps 4-6 in Algorithm <ref>. As shown in Theorem <ref>, N_0=𝒪(log^c(1/ϵ)), so the search space is logarithmic polynomial.
    
    Given an accuracy ϵ and a positive integer N_1=𝒪(log^c(1/ϵ)), let K=1/6N_1(N_1-1)(N_1-2)=𝒪(N_1^3). An instance of the K-SAT problem is (ℓ_31ℓ_32⋯ℓ_3K) (ℓ_31ℓ_32⋯ℓ_3K)⋯ (ℓ_n1ℓ_n2⋯ℓ_nK) (ℓ_n1ℓ_n2⋯ℓ_nK), we construct an instance of ELBP_T-count, where a finite set of boolean variables L={ℓ_31,ℓ_32,⋯,ℓ_3K,⋯, ℓ_n1,ℓ_n2,⋯,ℓ_nK}, |L|=(n-2)K, a set of clauses C={C_31,C_32,C_41,C_42,⋯,C_n1,C_n2}, |C|=2(n-2), C=C_31 C_32 C_41 C_42⋯ C_n1 C_n2, each C_k1 or C_k2, k=3,⋯,n is a disjunctive normal form consisting of K variables. Here,  means taking the minimum value "min", and  means taking the maximum value "max". 
    
    If the variable ℓ_kj or ℓ_kj is true for k=3,⋯,n,j=1,⋯,K, then the error E_kj is recorded, otherwise it is assigned ∞ and recorded, where E_kj for a certain k is the error for a certain R_z(π /2^k) or R_z(-π /2^k)  and differnet j corresponds to different V in the search space 𝒪(N_1^3) using Algorithm <ref>. Let ϵ'=max (E_31,E_32,⋯,E_3K,⋯,E_n1,E_n2,⋯,E_nK). If each clause is true, then at least one variable in each clause is true and ϵ' ≠∞; Otherwise, at least one clause is false, and then ϵ'=∞. Therefore, the boolean formula is satisfiable if and only if ϵ' ≠∞. This means that the minimum T-count for approximating R_z(π /2^k) or R_z(-π/2^k) with the accuracy ϵ' can be found in the search space 𝒪(N_1^3) using Algorithm <ref>, for all k=3,⋯,n. Determine N_0=N_1 when ϵ' < ϵ, then 
    the minimum T-count for approximating R_z(π /2^k) or R_z(-π/2^k) can be found in the search space 𝒪(N_0^3); otherwise, it cannot.
    
     Clearly ELBP_T-count is in NP, as the mathematical computation in step 9 of Algorithm <ref> is polynomial-time computable when given an N_0, and hence step 10 can be efficiently verified. It suffices to show NP-hardness by reducing the K-SAT problem to ELBP_T-count, and hence ELBP_T-count is NP-complete.





§ THE EXACT LOWER BOUND OF CNOT-COUNT FOR THE FAULT-TOLERANT QFT

From section 3, we known that ELBP_T-count is an NP-complete problem and the fault-tolerant CNOT-count is positively correlated with the T-count. Therefore, the exact lower bound problem of CNOT-count for the fault-tolerant QFT is also NP-complete. Nevertheless, we can still compute its exact lower bound under partial fault-tolerant accuracy. We now turn to the transversal implementation of universal quantum gates with the minimum CNOT-count.


 §.§ Universal fault-tolerant quantum gates with the minimum CNOT-count

The universal gates can be implemented transversely without requiring a fault-tolerant construction in FTQC except for the T gate equivalent to the rotation operator R_z(π/4), so we need to consider the fault-tolerant construction of Z-rotation gates. Similar to the fault-tolerant construction of the T gate in <cit.>, we provide a general fault-tolerant construction for U=e^iθ/2R_z(θ) that cannot be implemented transversely without requiring a fault-tolerant construction, as shown in Figure <ref>.


Here, the auxiliary state |Θ⟩ is a +1 eigenstate of the operator UXU^†=R_z(2θ)X.

Let M=e^iθR_z(2θ), we observe the single-qubit operator MX with eigenvalue ± 1, and its fault-tolerant measurement is shown in Figure <ref>.

Here, P is a phase shift gate, P=e^-iθ/2R_z(-θ), and M' is the fault-tolerant operator that can be implemented transversely for M without requiring a fault-tolerant construction. The framed parts are the preparation, verification, and final decoding of the cat state |Cat⟩=1/√(2)(|0_C⟩+|1_C⟩). If the cat state is successfully prepared, then


    |Cat⟩|0_L⟩   1/√(2)(|0_C⟩|0_L⟩+e^2iθ|1_C⟩|1_L⟩)
       1/√(2)(|0_C⟩|0_L⟩+e^iθ|1_C⟩|1_L⟩)
       = 1/√(2)( |0_C⟩+|1_C⟩/√(2)|0_L⟩+e^iθ|1_L⟩/√(2)+ |0_C⟩-|1_C⟩/√(2)|0_L⟩-e^iθ|1_L⟩/√(2))
       1/√(2)( |0⟩|0_L⟩+e^iθ|1_L⟩/√(2)+ |1⟩|0_L⟩-e^iθ|1_L⟩/√(2)),

where |0_L⟩ and |1_L⟩ denote the encoding states of logical |0⟩ and |1⟩, respectively.

We use the above fault-tolerant measurement method to prepare the auxiliary state |Θ⟩. If the measurement result is +1, it can be considered to have been prepared correctly; if it is -1, a fault-tolerant Z operation needs to be applied to change the state.

Next, we propose a proposition regarding the minimum CNOT-count used in the general fault-tolerant construction in Figure <ref> and Figure <ref>. The proposition is as follows:

The fault-tolerant construction of the single-qubit gate U rotating around the ẑ axis, as shown in Figure <ref>, requires the minimum CNOT-count. The preparation of the auxiliary state, as shown in Figure <ref>, also requires the minimum CNOT-count.


For U=e^iθ/2R_z(θ) that cannot be implemented transversally without requiring a fault-tolerant construction, auxiliary qubits are required. We use only m CNOT gates for transversal implementation to swap the auxiliary qubit |0⟩ with the data qubit |ψ⟩ when one logical qubit is encoded into m physical qubits, as shown in Figure <ref>.
    

Here, it uses the minimum CNOT-count to implement the swap operation, since it is impossible to implement the interaction between two qubits using only single-qubit gates.


The swap operation in Figure <ref> only implements the exchange of data qubits to auxiliary qubits by measuring the original data qubits. In general, at least three CNOT gates are required when implementing the swap operation between two arbitrary quantum states, as shown in Figure <ref>.


Applying the relations UXU^†=R_z(2θ)X and (U⊗ I) · CNOT=CNOT · (U⊗ I), we can obtain the fault-tolerant construction of U in Figure <ref>.
Let |ψ⟩=a|0⟩+b|1⟩, then perform a fault-tolerant CNOT operation, giving

    1/√(2)[|0⟩(a|0⟩+b|1⟩)+e^iθ|1⟩(a|1⟩+b|0⟩)] =1/√(2)[(a|0⟩+be^iθ|1⟩)|0⟩+(b|0⟩+ae^iθ|1⟩)|1⟩].

Finally, measure the second qubit. If the result is 0, the process is complete; otherwise, apply the UXU^† operation to the remaining qubits.

In Figure <ref>, the preparation of the auxiliary state must rely on the auxiliary qubits, and the preparation of the cat state has already reached the minimum CNOT-count using m-1 CNOT gates. According to Theorem <ref>, the fault-tolerant controlled-M'X can be decomposed into m CNOT gates for transverse implementation and other single-qubit gates, which has reached the minimum CNOT-count. Therefore, we use the minimum CNOT-count to make U transverse implementation.


From the above analysis, controlled-M must be implemented transversely without requiring a fault-tolerant construction in theory, where M=e^iθR_z(2θ). For R_k=e^iπ/2^kR_z(π/2^k-1), it is clear that for θ=π/2^k-1 with k > 3, this condition is not satisfied. In particular, when θ=π/4 with k = 3, then U=T,M=S,M'=ZS. According to Theorem <ref>, the controlled-M'X can be decomposed into one CNOT gate and two single-qubit gates A=R_z(3/4π)=e^-3iπ/8TS and B=R_z(-3/4π)=e^3iπ/8S^†T^†, where T^†=T^7, S^†=S^3. Fortunately, the standard set of universal gates {H, S, T, CNOT} can construct all physical quantum gates. 

Therefore, combining Figure <ref> and Figure <ref>, at least 4m fault-tolerant CNOT gates are required to transversely implement the fault-tolerant T gate (without considering the encoding circuits).




 §.§ Result analysis

We set the accuracy ϵ to the current maximum fault-tolerant accuracy 10^-2 <cit.> in FTQC and compute the minimum resources min n_sum for approximating R_z(π /2^k) and R_z(-π /2^k) for different values of k using  Algorithm <ref>. According to Remark <ref>, the minimum T-count is 2min n_sum. The minimum T-count for approximating R_z(π /2^k) and R_z(-π /2^k) for different k are shown in Table <ref>.


In Table <ref>, when k≥ 9, the minimum T-count remains unchanged at 1972. This is because as k increases, R_z(π /2^k) and R_z(-π /2^k) gradually approach the identity matrix and become insufficiently sensitive to this accuracy. When k=2, the controlled-R_2 is the controlled-S. According to Theorem <ref>, it can be decomposed into one T gate, one T^† gate, and two CNOT gates. The T^† can be approximated using Algorithm <ref> and the minimum resources min n_sum are 206 with ϵ=10^-2, i.e., the minimum T-count is 412. Compared with T^†=T^7, only seven T gates are required with zero error. Therefore, when k=2, the minimum T-count for controlled-S is 8.

We analyze the minimum CNOT-count for the fault-tolerant QFT with different lengths. If the input length of the QFT is n, there are n(n-1)/2 controlled-R_k in Figure <ref>, including (n-1) controlled-R_2, (n-2) controlled-R_3, ⋯, two controlled-R_n-1, and one controlled-R_n. According to Proposition <ref>, the decomposition method for approximating the controlled-R_k with the minimum T-count is to decompose it into one R_z(π/2^k), one R_z(-π/2^k) and two CNOT gates, where the minimum T-count for approximating R_z(π /2^k) and R_z(-π /2^k) are shown in Table <ref>. At this point, the required fault-tolerant CNOT-count is also minimum. Additionally, the final stage of the QFT requires ⌊n/2⌋ swap gates, which can be implemented by 3·⌊n/2⌋ CNOT gates without any auxiliary qubits, according to Remark <ref>. 

From section 4.1, we know that at least 4m fault-tolerant CNOT gates are required for the transversal fault-tolerant T gate, while the logical CNOT gate can be implemented transversally without requiring a fault-tolerant construction, using only m fault-tolerant CNOT gates. Therefore, the exact lower bound  of CNOT gates (ELB_CNOT-count) for the fault-tolerant QFT with different input lengths n is


    num(CNOT)=(n(n-1)/2· 2+⌊n/2⌋· 3)m+num(T)· 4m ,

where num(T) is the sum of the minimum T-count with k=2,3,⋯,n. When the accuracy is at most 10^-2, the ELB_CNOT-count for the fault-tolerant QFT with different n is shown in Figure <ref>.


The operation time of fault-tolerant CNOT gates is limited by inherent physical limitations. Especially, in ion trap quantum computers, the CNOT operation between two qubits utilizes collective excitation particles such as phonons to transmit interactions, which makes the operation efficiency limited by the propagation speed of media such as phonons. Moreover, the CNOT gates in ion traps can only be operated serially. Even if different CNOT gates involve different qubits, they cannot be operated in parallel. Therefore, CNOT gates significantly affect the operation time of quantum algorithms. In <cit.>, Yang et al. for the first time estimated the average lower bound of the time for a single physical CNOT operation in an ion trap quantum computer by analyzing the phonon speed, which is 2.85 × 10^-4 s. 

In cryptographic systems, common input lengths include 64-bit, 128-bit, 256-bit, 512-bit, 1024-bit, 2048-bit, and even 4096-bit. We particularly compute their ELB_CNOT-count and estimate the lower bound of their time for the fault-tolerant QFT, as shown in Table <ref>. 



In particular, when m=7, taking the famous Steane code as an example <cit.>. For shorter input lengths n, such as some lightweight cryptography, the time required to operate QFT on a quantum computer is very short, while for n=2048 and n=4096, the time is relatively long, 380.169 days and 1524.462 days respectively, which is about more than one year and more than four years. This analysis of ELB_CNOT-count can provide a reference for the idea of active defense in a quantum setting.

The search space of the minimum resources for approximating R_z(π /2^k) or R_z(-π /2^k) is 𝒪(N_0^3) for all k=3,⋯,n. In fact, as the accuracy decreases, it is challenging to determine an integer N_0 such that the minimum T-count for approximating them with given accuracy ϵ can be found within the search pace 𝒪(N_0^3) in polynomial time, given an integer N_0. For example, given the integer N_0=2^11, we have verified that the minimum T-count cannot be found in the search space 𝒪(2^33) when the accuracy is ϵ=10^-3, which implies that the search space of the minimum T-count may be much larger than 𝒪(2^33). This entire process is actually very time-consuming and requires continuously attempting to determine the value of N_0 so that the minimum T-count is found for all Z-rotation operators.



§ DISCUSSION

As shown in Theorem <ref>, the Solovay–Kitaev theorem <cit.> states that any single-qubit gate can be approximated to an accuracy ϵ with 𝒪(log ^c(1/ϵ)) gates from the discrete universal set. This number of gates grows polylogarithmically with decreasing accuracy, which is probably acceptable for almost all practical applications. It has been proven in <cit.> that the value of c cannot be less than 1 and lies between 1 and 2, close to 2, though determining the best possible value remains an open problem. We believe that the problem is at least an NP-hard problem. When the accuracy ϵ is small enough, there exists an accuracy ϵ_0 and a constant C', such that when ϵ<ϵ_0, Algorithm <ref> can be regarded as a function h(ϵ)≤ C'log ^c(1/ϵ), and the smaller ϵ is, the closer h(ϵ) is to C'log ^c(1/ϵ). Therefore, if ϵ_2<ϵ_1≪ϵ_0, h(ϵ_2)/h(ϵ_1)≈(log (1/ϵ_2)/log (1/ϵ_1))^c, where h(ϵ_1),h(ϵ_2) can be computed based on Algorithm <ref>. The K-SAT problem, including 
four clauses, can be reduced to this problem of determining an positive integer N_0 such that h(ϵ_1) and h(ϵ_2) exist for approximating U with accuracy ϵ_1 and ϵ_2 respectively in the search space 𝒪(N_0^3), given a single-qubit unitary operator U, thereby this problem is at least as hard as the K-SAT problem. As a subroutine for computing the value of c, we believe that determining the best possible value is at least NP-hard.

The unique structure of the QFT circuit makes finding its optimal circuit relatively easy. However, equivalence check is QMA-complete <cit.>, meaning that verifying whether two different circuits yield the same unitary transformation is QMA-complete. Quantum circuit optimization involves finding its optimal circuit in the set of different circuits with the equivalence class of a certain unitary transformation. Therefore, the circuit optimization problems, including but not limited to quantum algorithms based on the QFT,  are at least QMA-hard, i.e., given a quantum circuit, it is challenging to find its optimal version. Specifically, optimizing the circuit for Shor's algorithm is at least QMA-hard. Focusing on optimizing the CNOT-count, optimizing quantum circuits for arithmetic operations such as modular addition, modular multiplication, and modular exponentiation that are fundamental to quantum circuit decomposition, is a challenging task that typically requires continuous optimization during the design stage.

The order-finding and factoring problems based on the QFT provide evidence that quantum computers may be more powerful than classical computers, posing a credible challenge to the strong Church–Turing thesis. Our work can introduce new connotations for quantum adversaries. From a practical point of view, if efficient algorithms based on the QFT can be implemented within a meaningful time frame on a quantum computer, then they can be used to break some cryptosystems such as RSA. Otherwise, the development of quantum computers is unlikely to threaten the security of those classical cryptosystems.



§ CONCLUSION

In this paper, we study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. We first analyze the complexity of ELBP_T-count and have shown that this problem is NP-complete. When the ancilla-free controlled-R_k is decomposed in different ways, it generates different single-qubit gates in addition to CNOT gates. As a generalization, we propose an algorithm to exactly compute the minimum T-count for approximating any single-qubit gate with any given accuracy. This algorithm combines numerical and analytical methods to avoid traversing all quantum states in the normalized space and exactly determine whether the error conditions are satisfied. We then provide a property of the proposed algorithm to analyze the minimum resources, aiming to show the NP-completeness of ELBP_T-count and compute the ELB_CNOT-count for the fault-tolerant QFT. 

Due to the NP-completeness of ELBP_T-count, it would appear that computing the ELB_CNOT-count for the fault-tolerant QFT with any given accuracy is intractable. Nevertheless, we can still compute the ELB_CNOT-count under partial fault-tolerant accuracy. We have proved that the transversal implementation of universal quantum gates reaches the minimum CNOT-count. Furthermore, we approximate the Z-rotation gates after decomposing the ancilla-free controlled-R_k with the current maximum fault-tolerant accuracy 10^-2 and provide the ELB_CNOT-count with different input lengths. In particular, we estimate the lower bound of the effective execution time for the QFT based on Steane code on ion trap computers. For shorter input lengths n, such as some lightweight cryptography, the time required to operate the QFT on an ion trap computer is very short. When n=2048 and n=4096, the time required is relatively long compared to lightweight cryptography, which is 380.169 days and 1524.462 days respectively.

Finally, we discuss that determining the best possible value of c in 𝒪(log^c(1/ϵ)) implied by the Solovay–Kitaev theorem is at least an NP-hard problem, and the circuit optimization problem, such as Shor's algorithm, is at least a QMA-hard problem. Our work can introduce new connotations for quantum adversaries and provide a reference for the idea of active defense based on the QFT.



§ ACKNOWLEDGEMENT

This work was supported by the Beijing Natural Science Foundation (Grant No.4234084).

unsrt

 
