1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I actually believe your answer is better than my own. Thanks $\endgroup$ – 3yakuya Feb 7 '15 at 9:22
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

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