1

I suspect that if the standard form of a code is $$H = \begin{pmatrix} H_X & 0 \\ 0 & H_Z \end{pmatrix}~, \quad(1)$$ then I can claim that the code is CSS.

They way I'm thinking about this problem is a scenario in which someone hands me a check matrix $H'$, they don't tell me whether it's CSS or not, and it's not in the form (1). Can I claim that it's CSS if its standard form is like (1)?

In CSS Code in disguise it is shown that a stabilizer code $H$ is a CSS code if and only if $H$ has transversal CNOT. In principle I could use this to check whether $H'$ is CSS or not, but it is a procedure whose cost scales exponentially with the size of $H'$ and I would like to find a cheaper alternative.

Jan Olle
  • 81
  • 3
  • Does this answer your question? CSS Code in disguise, in particular this answer. – Abdullah Khalid Oct 13 '23 at 17:37
  • @AbdullahKhalid can you please explain to other close vote reviewers why that post answers this question? The term "standard form" doesn't even appear there. In the meantime I have removed the second question asked in this post, so that the question can't be closed for asking more than one question in the post. – user1271772 No more free time Oct 14 '23 at 00:39
  • I was a little hasty in the close tag. The summary of the top two answers and comments on them is: if you can transform $H'$ into a CSS like form via row operations (that's what the standard form is), indeed you show that the code is CSS. But there is further discussion about how your adversary can disguise a CSS code with local Hadarmards that will prevent the above procedure from succeeding. In other words, the implication holds only one way. – Abdullah Khalid Oct 14 '23 at 19:56
  • Also please note that creating the standard form is equivalent to Gaussian reduction, whose common algorithms are $\mathcal{O}(n^3)$ (where we assume that the number of stabilizer generators are $\mathcal{O}(n)$). But the CNOT test, also consumes the same number of operations: For each of the $\mathcal{O}(n)$ stabilizer generators, computing the conjugacy is $\mathcal{O}(n)$, followed by $\mathcal{O}(n^2)$ operations to check if the outputs are in the stabilizer. – Abdullah Khalid Oct 14 '23 at 20:07

0 Answers0