, which transforms the orthonormal basis |n) according to The goal is to reduce the right-hand side in this expression into a tractable tensor product, from which a simple QFT gate circuit can be constructed. I focus on the imaginary- exponential terms in Eq. (Q1), namely exp(2irkn/N), where k, n = 0...N - 1. From this point on, we assume that N is exactly a power of two, i.e., N = 2K, where K > 1 is an integer. We now expand the integer k according to the possible binary representation k = k12k-1+kz2k-2 +...+ kk20, where ekp=0,1a and k = 1, 2 K, and express the ratio k/N according to k12-1+k22-2+k2 Substituting this representation into the exponential in Eq. (Q1), and introducing next the tensor notation |k) = 1k1k2 kk) we obtain Quantum Fourier transform circuit This result shows that QFT |n) can be decomposed indeed into a K-tensor product. In this decomposition, each term, indexed by p, is actually made of the two contributions: kp=0,1 Hence, we can develop Eq. (Q5) according to: FT)1 = X The next step is to simplify further each of the exponential terms in Eq. (Q6). To do this, we substitute the binary expansion for integers n, namely, n = n12K-1 + n22K-2 + + nk-12'+nn22, where nq = 0, 1, in each of the exponents, which gives + nk . In the above, I have put in parentheses all the integer terms, to separate them from the other terms that are defined as fractions of powers of two. Clearly, the integer terms do not contribute to the imaginary exponential. The consequence of this can be generalized under the formula Appendix Q nk-2) nk-1) Figure Q1 Gate circuit corresponding to first three output qubits. From Eqs. (Q6)-(Q8), we finally obtain a nice closed-formed expression for the QFT tensor product: QFT)(1 nk), we have the following relation for each of the gate outputs Considering the first output qubits we have QFTwh (Q10) which shows that (within the normalization factor 2K/2) the QFT circuit wire corresponds either to the identity gate I (with input NK = 0) or the Hadamard gate H (with input NK = 1). We ca