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 :(
Can you please give some concrete examples? For example, how is the group defined? How big is N? Thanks
Post the link of the problem so we know it is not from a live contest.
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
Sorry, lol. Also, it is not like there are much red cheaters anyway so it was a joke LOL.
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?
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).
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)$$$.
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.
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.