Learning

Abstract: Bell sampling is a simple yet powerful tool based on measuring two copies of a quantum state in the Bell basis, and has found applications in a plethora of problems related to stabiliser states and measures of magic. However, it was not known how to generalise the procedure from qubits to $d$-level systems -- qudits -- for all dimensions $d > 2$ in a useful way. Indeed, a prior work of the authors (arXiv'24) showed that the natural extension of Bell sampling to arbitrary dimensions fails to provide meaningful information about the quantum states being measured. In this paper, we overcome the difficulties encountered in previous works and develop a useful generalisation of Bell sampling to qudits of all dimensions $d\geq 2$. At the heart of our primitive is a new unitary, based on Lagrange's four-square theorem, that maps four copies of any stabiliser state $|\mathcal{S}\rangle$ to four copies of its complex conjugate $|\mathcal{S}^\ast\rangle$ (up to some Pauli operator), which may be of independent interest. We then demonstrate the utility of our new Bell sampling technique by lifting several known results from qubits to qudits for any $d\geq 2$ (which involves working with submodules instead of subspaces): 1. Learning an unknown stabiliser state $|\mathcal{S}\rangle\in(\mathbb{C}^d)^{\otimes n}$ in $O(n^3)$ time with $O(n)$ samples; 2. Solving the Hidden Stabiliser Group Problem (a stabiliser version of the State Hidden Subgroup Problem) in $\widetilde{O}(n^3/\varepsilon)$ time with $\widetilde{O}(n/\varepsilon)$ samples; 3. Testing whether $|\psi\rangle\in(\mathbb{C}^d)^{\otimes n}$ has stabiliser size (a generalisation of stabiliser dimension for submodules) at least $d^t$ or is $\varepsilon$-far from all such states in $\widetilde{O}(n^3/\varepsilon)$ time with $\widetilde{O}(n/\varepsilon)$ samples if $\varepsilon = O(d^{-2})$; 4. Testing whether $|\psi\rangle\in(\mathbb{C}^d)^{\otimes n}$ is Haar-random or the output of a Clifford circuit augmented with less than $n/2$ single-qudit non-Clifford gates in $O(n^3)$ time using $O(n)$ samples. As a corollary, we show that Clifford circuits with at most $n/2$ single-qudit non-Clifford gates cannot prepare pseudorandom states, an exponential improvement over previous works; 5. Testing whether $|\psi\rangle\in(\mathbb{C}^d)^{\otimes n}$ has stabiliser fidelity at least $1-\varepsilon_1$ or at most $1-\varepsilon_2$ with $O(d^2/\varepsilon_2)$ samples if $\varepsilon_1 = 0$ or $O(d^2/\varepsilon_2^2)$ samples if $\varepsilon_1 = O(d^{-2})$.

Abstract: We consider the problem of Clifford testing, which asks whether a black-box $n$-qubit unitary is a Clifford unitary or at least $\varepsilon$-far from every Clifford unitary. We give the first 4-query Clifford tester, which decides this problem with probability~$\mathrm{poly}(\varepsilon)$. This contrasts with the minimum of 6 copies required for the closely-related task of stabilizer testing. We show that our tester is tolerant, by adapting techniques from tolerant stabilizer testing to our setting. In doing so, we settle in the positive a conjecture of Bu, Gu and Jaffe, by proving a polynomial inverse theorem for a non-commutative Gowers 3-uniformity norm. We also consider the restricted setting of single-copy access, where we give an $O(n)$-query Clifford tester that requires no auxiliary memory qubits or adaptivity. We complement this with a lower bound, proving that any such, potentially adaptive, single-copy algorithm needs at least $\Omega(n^{1/4})$ queries. To obtain our results, we leverage the structure of the commutant of the Clifford group, obtaining several technical statements that may be of independent interest.