# Definition of quantum junta is not basis independent: isn't this a problem?

A quantum $$k$$-junta is defined as a unitary matrix $$U$$ acting on $$n$$ qubits which has the form $$U = V \otimes \mathbb I$$ where $$V$$ is a unitary acting some $$k < n$$ of the qubits. The fact that a unitary has this form has implications for the dynamics of the quantum system it acts on. For instance, this means that only $$k$$ of the $$n$$ qubits are evolving non-trivially. So, it seems that the fact that a unitary is a junta should be a basis-independent definition, since it corresponds to a physical property of a system, which doesn't care what basis it is mathematically described in.

However, this is not the case. Take for instance the $$1$$-junta $$U = \sigma_Z \otimes \mathbb I_2$$ and consider $$P = CNOT$$. Then, changing into the $$CNOT$$ basis gives $$\tilde U = (CNOT) U (CNOT^\dagger) = \sigma_Z \otimes \sigma_Z$$. In this new basis, $$U$$ now acts non-trivially on both qubits and hence is a $$2$$-junta (or we can say it is not a junta at all since it acts on all its qubits). This seems to be a problem for results such as this one, which provide an algorithm for testing whether a given unitary is a junta given an oracle for the junta. If the blackbox is not working in the right basis, the algorithm would incorrectly label a junta as not being a junta.

Is there any way to reconcile this, or would one have to develop a way for finding the basis in which a unitary has the form a $$k$$-junta with the smallest $$k$$?

(Put another way: you could ask the question "is there a basis such that the $$n$$-qubit unitary $$U$$ is a junta?". The answer would be straightforward if you were allowed an arbitrary basis: if $$U$$ has (up to) $$2^k$$ different eigenvalues $$\lambda_i$$, which all partition into sets of $$2^{n-k}$$ identical values, you can certainly choose the spectral basis and permute the labels such that you can write it as $$(\sum_i\lambda_i|i\rangle\langle i|)\otimes I.$$ This is necessary and sufficient, I believe.)