I am reading the very basics about CSS codes in the Nielsen & Chuang.

On page 450 of this book is explained how the ancillas are used to detect a bit-flip error on the encoded data.

We consider $C_2 \subset C_1$ two classical linear error correcting codes, and we focus on $CSS(C_1,C_2)$.

We consider the state:

$$ |x+C_2 \rangle = \frac{1}{\sqrt{|C_2|}} \sum_{y \in C_2} |x+y\rangle$$

We assume this state has received bit-flip and phase errors described by $e_1$ and $e_2$ respectively. Thus it becomes:

$$ |\psi\rangle = \frac{1}{\sqrt{|C_2|}} \sum_{y \in C_2} (-1)^{(x+y).e_2}|x+y+e_1\rangle $$

Now, the book says:

To detect where bit flips occurred it is convenient to introduce an ancilla containing sufficient qubits to store the syndrome for the code C1, and initially in the all zero state $|0\rangle$.We use reversible computation to apply the parity matrix H1 for the code C1,taking $|x+y+e_1\rangle |0\rangle$ to $|x+y+e_1\rangle |H_1(x+y+e_1)\rangle=|x + y + e \rangle |H_1e_1 \rangle$

My question is simply: How do we do the transformation $|0\rangle \rightarrow |H_1(x+y+e_1)\rangle$ for the ancilla ? For me it would require to know $|H_1(x+y+e_1)\rangle$ and then find the appropriate unitary to make the transformation $|0\rangle \rightarrow |H_1(x+y+e_1)\rangle$. But we are not supposed to know the state that is encoded and if we measure it we may destroy it.

So how can we know which transformation to apply to make: $|0\rangle \rightarrow |H_1(x+y+e_1)\rangle$ ? I don't understand the argument of reversible computation.

[edit] : I actually just thought about using CNOT between the qubits and the ancillas to first to $|x+y+e_1\rangle |0\rangle \rightarrow |x+y+e_1\rangle |x+y+e_1\rangle$. But then we need to apply $H_1$ on the ancillas. But it is not a unitary operation so how can we do it on a quantum circuit ?


1 Answer 1


Let's express this slightly differently. You need a unitary operation that implements $$ |x\rangle|0\rangle\mapsto |x\rangle|H_1x\rangle. $$ I'm not saying this is necessarily the best way of doing it (there will be far more insightful strategies), but you could certainly write this out for all possible values of $x$. As such, you'd be able to write out the matrix operation corresponding to the unitary. The point is that this must work for every input $x$, not only for the $x+y+e_1$ that is relevant to you at a specific moment.

If you now want a more reasonable strategy to approach this calculation, just think about calculating a single bit of the ancilla, corresponding to a single row of the parity check matrix. What calculation is it you're actually performing? What does a 1 in the parity check matrix tell you? (bitwise addition of all the bits in $x$ where the corresponding bit value in the row is 1). Controlled-not is great at performing bitwise addition between the two inputs, writing the output on the target qubit.

Let's imagine the first row of the parity check matrix is $(1,0,1,1)$. There are 4 bit values, so we have $x=(x_1,x_2,x_3,x_4)$. Hence the inner product between the two just gives $x_1\oplus x_3\oplus x_4$. How do we compute this value with a quantum circuit?enter image description here

  • $\begingroup$ You suggest me to directly find the unitary doing what you wrote in your first equation. About your last paragraph: the p'th bit of the ancilla will be the scalar product between $x$ and the p'th line of the parity check matrix $H_1$ (which is by construction orthogonal to all the columns of the generator matrix $G_1$). However I don't see how it can help me to find a circuit associated to the unitary ? $\endgroup$ Jul 30, 2019 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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