Consider the gate used in Simon's Algorithm. It operates on a control register and target register, changing state like: $|\textbf{x}\rangle|\textbf{y}\rangle->|\textbf{x}\rangle|\textbf{y}\oplus f(x)\rangle$.As I am working on an universal way to simulate operations on qubits, I've been using a matrix representation of gates, which allowed me to transform even pretty complicated states without much concern about transform's correctness. However, I can't really see how would I represent a gate like shown above with a matrix (or how would I build such a matrix knowing x, y and f(x)?)How can such gates operating on multiple qubits be represented with matrices?Alternatively, having a vector states representing x and y and knowing f how can I transform y? (If all qubits in x are set in equally-weighted superposition of 0 and 1, I guess I'd need to calculate f for all possible x states, but how should I apply the results to y then?)
Multi-qubit gates matrix representation
quantum computing
The first thing to recognize is that this is a permutation matrix where each row and column contains a single $1$ entry with the remaining entries being $0$.  This follows from the fact that $x$ and $y$ represent classical bit strings and $f$ is a classical boolean function.  Let's take the basic case where $x$ is from the space of $n$ bit strings, $y$ is a single bit, and $\mathcal{f}$ maps $\{0,1\}^n$ to $\{0,1\}$. The operation then functions on $n+1$ bits and is represented by a $2^{n+1} \times 2^{n+1}$ matrix. If you let the binary number $xy$ index the matrix columns, then for column $xy$ set row $x(f(x) \oplus y)$ to 1 and all other rows to 0. Let's look at an example from Deutsch's algorithm. Let $x$ be from $\{0,1\}$ and $f$ be bit negation, i.e. $f(0) = 1$ and $f(1) = 0$.  From here we compute, for each row, the column number containing the 1.$\begin{array}{cc}\mbox{column} & \mbox{row with 1} \\00 & 0(0 \oplus 1) = 01 \\01 & 0(1 \oplus 1) = 00 \\10 & 1(1 \oplus 1) = 10 \\11 & 1(1 \oplus 0) = 11 \end{array} $This gives us the matrix$ \left( \begin{array}{cc}0 & 1 & 0 & 0 \\1 & 0 & 0 & 0 \\0 & 0 & 1 & 0 \\0 & 0 & 0 & 1 \end{array} \right) $This generalizes to when $y$ is more than a single bit. 