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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
