How to calculate the evolution of ket states through a simple quantum circuit?

Question

I am having difficulties with the calculations of qubits. I think I can do them, but it feels so massivly inefficient!

In this tutorial grover's algorithm for example, there's a simple oracle given for the binary bitcombination '110': (bit-order is as usual swapped, so most significant bit is q2 - at least I think so)

what I've tried so far:

let $a = |110\rangle$

the first step I thought would be to apply the $X$ on the top bit and the Hadamard on the bottom bit so:

$a' = |111\rangle$

$a'' = \frac{1}{\sqrt{2}}(|011\rangle - |111\rangle)$

next I would think: only when the second and third bit are equal to 1 then the first bit swaps:

$a''' = \frac{1}{\sqrt{2}}(|111\rangle - |011\rangle)$

next I negate the top (third) bit:

$a^{4'} = \frac{1}{\sqrt{2}}(|110\rangle - |010\rangle)$

and finally I use Hadamard on the bottom (first) bit:

$\displaystyle a^{5'} = \frac{1}{2} \Big(|010\rangle - |110\rangle -\big(|010\rangle + |110\rangle\big)\Big)$

$= -|110\rangle$

and yes, thats exactly what I want. But is there a way to calculate this alternively with some matrices or tensors? where I can use the form of

$ |110\rangle = \begin{pmatrix} 0\\0\\0\\0\\0\\0\\1\\0 \end{pmatrix}$

How can I represent the layer with $X$ and $H$ mixed?

Answer 1

First of all: the bit-order that you use is not the conventional one in quantum computing. We usually use the convention that $$ |x_1 x_2 \dots x_n \rangle = |x_1\rangle \otimes |x_2\rangle \otimes \dots \otimes |x_n\rangle, $$ i.e. the "first" bit $x_1$ corresponds to the "first" qubit which is usually the top one in the circuit notation. I agree, this is completely arbitrary.

Now to your actual question: There is nothing wrong with your calculation. You could have noticed that conjugating by $H$ on the target qubit turns $CCX$ into $CCZ$. This would have saved two steps in your calculation.

Of course, you can instead express everything in terms of 3-qubit matrices (which are of size $2^3\times 2^3 = 8\times 8$). Then, the $X$ / $H$ layer would be represented by the matrix $X\otimes \mathbb{I}\otimes H$ where $\mathbb{I}$ is the identity matrix.

But please don't do this. This is highly inefficient, especially if you deal with an arbitrary number of qubits. The whole point of local gates is that they can be applied locally. This only requires updating the local states which can be done efficiently as long as the number of terms in your superposition is not too big. On the contrary, multiplying $n$-qubit matrices is always inefficient.