Multi-qubit gates matrix representation

Question

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?)

Answer 1

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.

Answer 2

So basically, such gates operate on a joined register (which may be looked at as joined high-part (control) and low-part (target). Let's say that HL represents the state of such joined register (and H is the part of bits representing the control state's index before join, and L is the part representing target state's index). The matrix representation of such gate would have 1 in row HL and column H(L xor f(H)) for every possible HL.