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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.