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.

  • $\begingroup$ Does this answer your question? CSS Code in disguise, in particular this answer. $\endgroup$ Oct 13, 2023 at 17:37
  • $\begingroup$ @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. $\endgroup$ Oct 14, 2023 at 0:39
  • $\begingroup$ 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. $\endgroup$ Oct 14, 2023 at 19:56
  • $\begingroup$ 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. $\endgroup$ Oct 14, 2023 at 20:07


Your Answer

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