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$?


1 Answer 1


The definition that you give of a quantum junta is in relation to a tensor product structure. Such structures (and things like entanglement) only make sense if you have some sort of definitive structure (e.g. particles separated by large distances), such that the only bases you would ever talk about are local with respect to that tensor product. In the example that you give, the controlled-not is violating that locality principle. For the black-box style problems, you have a very definite tensor product structure because each of the inputs is individually identifiable. So, their algorithms should work (in principle) under any local basis change (i.e. at the single-quibt level) but it certainly does not make sense to talk about it with respect to an arbitrary basis.

(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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.