Represent the $n$-qubit $2^n\times2^n$ size Hadamard/quantum Fourier transform unitary square matrix as product of $k$ two-level unitary matrices

I wish to know if it is possible to express the n-qubit Hadamard unitary square matrix of size $$2^n * 2^n$$ as a product of 'k' two-level unitary square matrices where 'k' is of the order of polynomial in 'n'. By order is meant the Big-O notation of computational complexity theory. By the 2-level matrix, I mean the definition in the book "Quantum Computation and quantum information" by Nielsen and Chuang, section 4.5.1 "Two level unitary gates are universal", pp. 189. A two-level unitary matrix is a unitary matrix which acts non-trivially only on two-or-fewer vector components.

I also wish to know if the same decomposition into 'k' two-level unitary square matrices can be done to a Quantum Fourier Transform (QFT) unitary square matrix of n-qubits of size $$2^n * 2^n$$ where 'k' is of the order of polynomial in 'n'.

I have read that the two-level unitary gates/square matrices are universal.

Any help in this regard is highly appreciated.

• If the unitaries belong to $U(N)$ then this can always be done; see doi.org/10.1103/PhysRevLett.73.58 and doi.org/10.1364/OPTICA.3.001460 and doi.org/10.1103/PhysRevA.97.022328 for various schemes. If they do not (and thus do not conserve something like the total number of ground-state qubits) then these schemes do not apply Aug 8 '21 at 14:07
• @QuantumMechanic if I remember correctly, Reck's and similar schemes provide decompositions of $N\times N$ unitaries in terms of $\mathcal O(N^2)$ two-level ones. OP is asking for decompositions using $\mathcal O({\rm poly}(\log N))$ two-level unitaries I think, which clearly can only be done for specific cases. You can definitely do it for the Hadamard, as that can be written as a tensor product $\bigotimes_{k=1}^n H$, where $2^n=N$, and each one-qubit unitary is a two-level unitary.
– glS
Aug 8 '21 at 16:36
• @glS I think you're mixing representations: The Reck etc. schemes are unitaries in $U(N)$, so they can be applied to $N=n$ qubits with $\mathcal{O}(n^2)$ two-level unitaries. These do not describe all unitaries acting on $n$ qubits, but they certainly are a subset of them. I.e., we do not need to use $\log N$ but simply $N$ here. Aug 8 '21 at 21:03
• I was browsing through stackexchange and found the following post in Physics Stackexchange. physics.stackexchange.com/questions/532215/… I believe the above post resolves the question that it is NOT possible to decompose Hadamard/QFT matrices into polynomial number of two-level matrices. Please let me know if I am wrong. Aug 9 '21 at 13:31
• @KarthikPC I'm not sure that answer addresses this question. That argument only shows that some $d\times d$ matrices need more than $d-1$ two-level ones. There are however certainly matrices which do not (as a trivial example, a two-level unitary can be decomposed using just a single two-level unitary...). You are right that what I said before for the Hadamard isn't accurate though: even single-qubit gates aren't two-level.The core issue is that talking about "two-level matrices" isn't really natural in the context of qubits, because those aren't easy gates to implement with qubits systems.
– glS
Aug 9 '21 at 21:48