egor_bb's blog

Finding number of certain strings in the group of 2N-bit strings
By egor_bb, history, 3 years ago, In English

Hi! There is a practical problem that reduces to the following:

You are given some 2N-bit strings that generate a group with XOR operation (subgroup of all 2N-bit strings). The goal is to find the number of elements in the group satisfying the following property in any reasonable time:

  • Split the 2N-bit string into N pairs of adjacent bits, for example $$$01111011 > (01)(11)(10)(11)$$$
  • The number of $$$(11)$$$ pairs should be odd (in the example there are two such pairs, so we don’t count it)

The faster the better, but ideas on speeding up the brute force are also welcome. I’m stuck at the moment and don’t even understand how to Google it properly :(

  • Vote: I like it
  • +49
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please give some concrete examples? For example, how is the group defined? How big is N? Thanks

→ Reply
»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Post the link of the problem so we know it is not from a live contest.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Come on dude it’s a problem arising in quantum chemistry on quantum computers, you can Google something like qubit ADAPT-VQE if you want

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +29 Vote: I do not like it

      Sorry, lol. Also, it is not like there are much red cheaters anyway so it was a joke LOL.

      → Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Hmm, haven't touched group theory in 4 years, but how is what you're saying different from taking the span of some given strings? My understanding of what you're asking for is you give me a set of length-2N strings, and we want to compute the number of strings in their span (when considering a string as an element of $$$Z_2^{2n}$$$) with odd number of 11s aligned at odd positions (assuming 1-indexed), is that the same?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same for me regarding the group theory X_X

    By analyzing the span of the given strings I can find the size of the group generated by them. However, the strings satisfying "odd number of 11s" do not form a subgroup, for example, the string of all 0s does not satisfy the criterion. I can reduce the initial group to a certain set of generators, but then I'm struggling to understand how to count the "good" strings in their span (without explicitly generating them which is infeasible).

    → Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Well, here is an $$$O(2^n n^2)$$$ brute-force idea. Let's brute-force the mask of $$$(11)$$$ pairs and allow the rest of the pairs to be arbitrary. The number of strings that satisfy the fixed mask can be found using Gaussian elimination ― we just want to force some bits to be equal to one, obtaining a smaller subgroup at the end with size $$$2^{\textrm{basis_size}}$$$. Then use inclusion-exclusion to obtain the counts of strings where exactly the fixed mask has $$$(11)$$$ pairs, i.e. all other pairs are not $$$(11)$$$.

→ Reply
»
3 years ago, # |
  Vote: I like it +75 Vote: I do not like it

I think this can be done in polynomial time by reducing it to counting the number of roots of a quadratic polynomial over $$$\mathbb{F}_2$$$. You can try tracing references of this paper for how to do that in polynomial time.

For example, suppose we have a basis $$$\{0011, 1010, 0101\}$$$. Each element can be written uniquely as $$$a(0011)\oplus b(1010)\oplus c(0101)$$$ where $$$a,b,c\in\mathbb{F}_2$$$.

The first bit is $$$b$$$ and the second bit is $$$c$$$, so the first pair of bits form a $$$(11)$$$ iff $$$bc=1$$$. The third bit equals $$$a+b$$$ and the fourth bit equals $$$a+c$$$, so the second pair of bits form a $$$(11)$$$ iff $$$(a+b)(a+c)=1$$$. (All polynomials are over $$$\mathbb{F}_2$$$).

Hence, the number of pairs of $$$(11)$$$ is even if and only if $$$bc+(a+b)(a+c)=0$$$. So we just need to count the roots of this polynomial.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, that seems to be exactly the solution I looked for! I will dig into counting the number of roots in the polynomial as the reduction looks correct.

    → Reply