Jonathan Allcock

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})$.

We explore the power of the unbounded Fan-Out gate and the Global Tunable gates generated by Ising-type Hamiltonians in constructing constant-depth quantum circuits, with particular attention to quantum memory devices. We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. These gates include the Fan-In gates defined by x>|b> —> |x>|b+ f(x)> for x in 0,1^n and b in 0,1, where f is a Boolean function. The first of our constructions is based on computing the one-hot encoding of the control register |x>, while the second is based on Boolean analysis and exploits different representations of f such as its Fourier expansion. Via these constructions, we obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices — Quantum Random Access Memory (QRAM) and Quantum Random Access Gate (QRAG) — of memory size n. The implementation based on one-hot encoding requires either O(n log(n)łogłog(n)) ancillae and O(n log(n)) Fan-Out gates or O(n log(n)) ancillae and 6 Global Tunable gates. On the other hand, the implementation based on Boolean analysis requires only 2 Global Tunable gates at the expense of O(n^2) ancillae.