Suppose I know a set of stabilizer generators of a qubit quantum code. Is there a systematic (and possibly efficient) way to transform this set of generators to a different set (generating the same code) with lowest possible weights? I suspect that there is no efficient way, because this problem looks very similar to the shortest basis problem of lattices which is conjectured to be very hard.

  • $\begingroup$ I guess a first and easier question is whether you can do this for parity checks of classical codes. $\endgroup$
    – smapers
    Mar 11, 2020 at 16:06
  • $\begingroup$ there will be a systematic way of doing it using, for example, binary programming. As for efficient? I don't really know, but intuition suggests not. Binary programming iteself is NP-complete and I'd guess you can encode hard instances within this specfic problem. But that's hardly a rigorous aswer ;) $\endgroup$
    – DaftWullie
    Mar 12, 2020 at 9:03
  • $\begingroup$ Computing the distance (weight of lowest weight check) of a linear code is NP-hard. Even approximating it is hard (doi.org/10.1109/SFFCS.1999.814620). $\endgroup$ Jan 10 at 22:45


Your Answer

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

Browse other questions tagged or ask your own question.