Let $U$ be a unitary $n$-qubit transformation that applies a Hadamard on the $k$-th qubit and the identity on all the others. How would I go about calculating $U_{ij}=\langle i | U | j \rangle$ in polynomial time? Calculating all of $U$ is not feasible in polynomial time as it is a $2^n \times 2^n$ matrix.


1 Answer 1


If $|i\rangle$ and $|j\rangle$ are from computational basis, then we can write $$ U = I \otimes I ~\otimes ... \otimes ~H ~\otimes ... \otimes ~ I \otimes I $$ $$ \langle i | = \langle i_1| \otimes \langle i_2| ~\otimes ... \otimes ~\langle i_k| ~\otimes ... \otimes ~ \langle i_{n-1}| \otimes \langle i_n| $$ $$ |j \rangle = |j_1\rangle \otimes |j_2\rangle ~\otimes ... \otimes ~ |j_k\rangle ~\otimes ... \otimes ~ | j_{n-1}\rangle \otimes | j_n\rangle $$ where every $i_x$ and $j_x$ are $0$ or $1$.

Then the product $\langle i | U | j \rangle$ will be $$ \langle i | U | j \rangle = \langle i_1| j_1\rangle \otimes \langle i_2| j_2\rangle~\otimes ... \otimes ~\langle i_k|H|j_k\rangle ~\otimes ... \otimes ~ \langle i_{n-1}| j_{n-1}\rangle\otimes \langle i_n|j_n\rangle = $$ $$ = \langle i_1| j_1\rangle \cdot \langle i_2| j_2\rangle~\cdot ... \cdot ~\langle i_k|H|j_k\rangle ~\cdot ... \cdot ~ \langle i_{n-1}| j_{n-1}\rangle\cdot \langle i_n|j_n\rangle $$ $$ = \delta_{i_1j_1} \cdot \delta_{i_2j_2}~\cdot ... \cdot ~\langle i_k|H|j_k\rangle ~\cdot ... \cdot ~ \delta_{i_{n-1}j_{n-1}}\cdot \delta_{i_nj_n} $$ where $\delta_{i_xj_x} = 1$ if $i_x = j_x$ and $0$ otherwise.

If $|i\rangle$ and $|j\rangle$ are not from computational basis, then it's impossible to compute it that fast, because you need exponential number of parameters just to define $|i\rangle$ or $|j\rangle$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.