Can we learn anything interesting about a claw by taking the square-root-of-NOT of each qubit?

Question

Consider being given a circuit for a two-to-one Boolean function $f$ from $n$ (qu)bits to $m\ge n-1$ (qu)bits, and prepare the following state:

$$\frac{1}{\sqrt {2^n}}\sum_0^{2^n-1}|x\rangle|f(x)\rangle.$$

Upon measuring the second register in the computational basis and returning a value $y$, our first register collapses to a claw $\frac{1}{\sqrt 2}\big (|x_1\rangle+|x_2\rangle\big )$, with $f(x_1)=f(x_2)=y$.

We can then measure the first register in the computational basis to return either $x_1$ or $x_2$. However, it's rather remarkable and it's not too hard to show that measuring the first register in the Hadamard basis instead of the computational basis returns a string $d$ satisfying a rather peculiar Boolean condition: namely, if the first register is measured in the Hadamard basis then the parity of the Hamming weight/one's count of $d\wedge(x_1\oplus x_2)$ is $0\bmod 2$. This observation is central Simon's algorithm, and is key to many of the more recent cryptographic applications of quantum computers. It can be hard to classically determine pairs $(d,y)$ satisfying this Boolean test given only black-box access to, or even a circuit for, $f(x)$.

But, the Hadamard gate is not the only single-qubit interfering gate that we can apply to the first register. Another, only slightly less famous gate is $\sqrt{\text{NOT}}$, conventionally defined as:

$$\sqrt {\text{NOT}} = \frac{1}{2}\left( {\begin{array}{*{20}{c}} {1 + i}&{1 - i}\\ {1 - i}&{1 + i} \end{array}} \right),$$

or, up to a global phase, as:

$$\sqrt {\text{NOT}} = \frac{1}{{\sqrt 2 }}\left( {\begin{array}{*{20}{c}} 1&{ - i}\\ { - i}&1 \end{array}} \right).$$

My question is, then, can we say anything non-obvious about the string $d'$ that we might get from measuring a claw $\frac{1}{\sqrt 2}\big (|x_1\rangle+|x_2\rangle\big )$ in the square-root-of-NOT basis as opposed to the Hadamard basis? For example, could the sting $d'$ be orthogonal not to the XOR $(x_1\oplus x_2)$, but to the XNOR thereof? How about if $f$ were promised not to be two-to-one but rather four-to-one?

Or, more likely, is $d'$ over the square-root-of-not basis somehow the "same as" $d$ over the Hadamard basis, e.g., equivalent up to a rotation and/or a global phase?

---

^{This question was partially inspired by a conversation with @JRT here.}

Answer 1

A direct calculation yields: $$\left(\sqrt{\text{NOT}}\right)^{\otimes n}=\frac{1}{\sqrt{2^n}}\sum_{x,d}(-\mathrm{i})^{h(x\oplus d)}|d\rangle\!\langle x|$$ with $h$ being the Hamming weight. If $f$ is 2-to-1, then we'll have a superposition of two preimages $x_1$ and $x_2$, which means that we'll end up with the state: $$\frac{1}{\sqrt{2^{n+1}}}\sum_d(-\mathrm{i})^{h\left(x_1\oplus d\right)}\left(1+(-\mathrm{i})^{h\left(x_2\oplus d\right)-h\left(x_1\oplus d\right)}\right)|y\rangle\,.$$ In particular, the only $d$s with a non-zero amplitude are those such that $h\left(x_1\oplus d\right)- h\left(x_2\oplus d\right)\neq2\pmod4$. This can be written as $\left\langle(-1)^{d}\middle|x_1-x_2\right\rangle\neq2\pmod4$, where $(-1)^d$ is to be understood as the vector having $(-1)^{d_i}$ as its coefficients.

I think it can be shown that it is hard to produce such a $(d, y)$ pair classically, but I don't have a formal proof about it. It's not equivalent to the Hadamard case, but definitely similar.