4 ms·

I like these kinds of bit twiddling puzzles. One that I recently did was for iterating over possible errors of weight w in a quantum stabilizer code (for [1]).

I like these kinds of bit twiddling puzzles. One that I recently did was for iterating over possible errors of weight w in a quantum stabilizer code (for [1]). In a classical code this would just be the problem in the blog post, since there's only one type of error (bit flips). In a quantum code you have bit flips (X) but also phase flips (Z) and combination-bit-and-phase-flips (Y) all having weight 1. So the problem becomes: given ints (x, z) find the next (x2, z2) such that popcnt(x2 | z2) == popcnt(x | z). The solution I came up with, which is likely very suboptimal, was to iterate over single-integer solutions for a given weight. Then, for each single-integer solution m, iterate over the pairs x,z where x|z == m. Here's python pseudocode for the second part: def pair_sat_increment(x: int, z: int, m: int) -> Tuple[int, int]: """Returns the next (x, z) such that x | z == m.""" inc = x & z up = ~inc inc |= ~m inc += 1 inc &= m up &= inc z &= inc | ~x z ^= x & up x ^= up return x, z [1]: https://github.com/quantumlib/Stim/issues/397 https://github.com/quantumlib/Stim/issues/397

pbsd 3y ago
A simple way to do the latter is for(u64 x = -m & m; ;x = (x - m) & m) { const u64 r = x ^ m; for(u64 t = -x & x; ; t = (t - x) & x) { const u64 z = r | t; // Use (x,z) if(t == 0) break; } if(x==0) break; }
- Strilanc 3y ago
  Nice. You need to initialize x to 0 instead of -m&m though, or you miss the solution with x=0.
  - pbsd 3y ago
    x=0 is the last solution to be hit the way I wrote it.
    - Strilanc 3y ago
      It's possible I misdiagnosed the issue. But I implemented the code and ran it and counted the solutions, and one was missing. I changed that line and it fixed it, and the solution that was missing is the one I described. In any case, it's a nice succinct trick for iterating through the values compatible with a mask. Getting the boundary conditions right is less important than knowing the trick.

pbsd 3y ago

A simple way to do the latter is for(u64 x = -m & m; ;x = (x - m) & m) { const u64 r = x ^ m; for(u64 t = -x & x; ; t = (t - x) & x) { const u64 z = r | t; // Use (x,z) if(t == 0) break; } if(x==0) break; }

Strilanc 3y ago
Nice. You need to initialize x to 0 instead of -m&m though, or you miss the solution with x=0.
- pbsd 3y ago
  x=0 is the last solution to be hit the way I wrote it.
  - Strilanc 3y ago
    It's possible I misdiagnosed the issue. But I implemented the code and ran it and counted the solutions, and one was missing. I changed that line and it fixed it, and the solution that was missing is the one I described. In any case, it's a nice succinct trick for iterating through the values compatible with a mask. Getting the boundary conditions right is less important than knowing the trick.