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.

  • 1
    $\begingroup$ 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 $\endgroup$ Aug 8 '21 at 14:07
  • $\begingroup$ @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. $\endgroup$
    – glS
    Aug 8 '21 at 16:36
  • $\begingroup$ @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. $\endgroup$ Aug 8 '21 at 21:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Karthik PC
    Aug 9 '21 at 13:31
  • 1
    $\begingroup$ @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. $\endgroup$
    – glS
    Aug 9 '21 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.