Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more

• URL: http://arxiv.org/abs/2510.06848v1
• Date: Wed, 08 Oct 2025 10:13:16 GMT
• Title: Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Authors: Jonathan Allcock, Joao F. Doriguello, Gábor Ivanyos, Miklos Santha,
• Abstract summary: We develop a generalisation of Bell sampling to qudits of all $dgeq 2$.<n>New unitary maps four copies of any stabiliser state $|mathcalSrangle$ to four copies of its complex conjugate $|mathcalSastrangle$.<n>We demonstrate the utility of our new Bell sampling technique by lifting several known results from qubits to qudits for any $dgeq 2$.
• Score: 1.1149587110540697
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $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$: 1. Learning stabiliser states in $O(n^3)$ time with $O(n)$ samples; 2. Solving the Hidden Stabiliser Group Problem in $\tilde{O}(n^3/\varepsilon)$ time with $\tilde{O}(n/\varepsilon)$ samples; 3. Testing whether $|\psi\rangle$ has stabiliser size at least $d^t$ or is $\varepsilon$-far from all such states in $\tilde{O}(n^3/\varepsilon)$ time with $\tilde{O}(n/\varepsilon)$ samples; 4. Clifford circuits with at most $n/2$ single-qudit non-Clifford gates cannot prepare pseudorandom states; 5. Testing whether $|\psi\rangle$ 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})$.

Related papers

• A note on polynomial-time tolerant testing stabilizer states [6.458742319938316]
  We show an improved inverse theorem for the Gowers-$3$ of $n$-qubit quantum states $|psirangle. For every $gammageq 0$, if the $textsfGowers(|psi rangle,3)8 geq gamma then stabilizer fidelity of $|psirangle$ is at least $gammaC$ for some constant $C>1$.
  arXiv  Detail & Related papers  (2024-10-29T16:49:33Z)
• Learning junta distributions, quantum junta states, and QAC$^0$ circuits [0.0]
  We consider the problems of learning junta distributions, their quantum counterparts (quantum junta states) and $mathsfQAC0$ circuits.<n>We show that $n$-qubit $mathsfQAC0$ circuits with size $s$, depth $d$ and $a$ auxiliary qubits can be learned from $2O(log(s22a)d)log (n)$ copies of the Choi state.
  arXiv  Detail & Related papers  (2024-10-21T09:39:20Z)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  We propose a piecewise stationary linear bandit (PSLB) model where the quality of an arm is measured by its return averaged over all contexts. PS$varepsilon$BAI$+$ is guaranteed to identify an $varepsilon$-optimal arm with probability $ge 1-delta$ and with a minimal number of samples.
  arXiv  Detail & Related papers  (2024-10-10T06:15:42Z)
• Polynomial-time tolerant testing stabilizer states [4.65004369765875]
  An algorithm is given copies of an unknown $n$-qubit quantum state $|psirangle promised $(i)$ $|psirangle$. We show that for every $varepsilon_1>0$ and $varepsilonleq varepsilon_C$, there is a $textsfpoly that decides which is the case. Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-$3$ norm of quantum states and new bounds on stabilizer covering for
  arXiv  Detail & Related papers  (2024-08-12T16:56:33Z)
• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  We construct coresets of size $tilde O(varepsilon-2d)$ for $p2$ and $tilde O(varepsilon-pdp/2)$ for $p>2$. For $1p2$, every matrix has a subset of $tilde O(varepsilon-1k)$ rows which spans a $(varepsilon-1k)$-approximately optimal $k$-dimensional subspace for $ell_p$ subspace approximation
  arXiv  Detail & Related papers  (2024-06-04T15:50:42Z)
• Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits [0.824969449883056]
  Bell sampling fails when used on quemphdits of dimension $d>2$. We propose new quantum algorithms to circumvent the use of Bell sampling on qudits.
  arXiv  Detail & Related papers  (2024-05-10T09:44:23Z)
• Improved Stabilizer Estimation via Bell Difference Sampling [0.43123403062068827]
  We study the complexity of learning quantum states in various models with respect to the stabilizer formalism. We prove that $Omega(n)$ $T$gates are necessary for any Clifford+$T$ circuit to prepare pseudorandom quantum states. We show that a modification of the above algorithm runs in time.
  arXiv  Detail & Related papers  (2023-04-27T01:58:28Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  We show how all properties of a quantum manifold of states are fully described by a gauge-invariant Bargmann. We show how our results have immediate applications to the modern theory of polarization.
  arXiv  Detail & Related papers  (2022-05-30T18:01:34Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  We learn the set of $epsilon$-optimal goal-conditioned policies attaining all states that are incrementally reachable within $L$ steps. DisCo is the first algorithm that can return an $epsilon/c_min$-optimal policy for any cost-sensitive shortest-path problem.
  arXiv  Detail & Related papers  (2020-12-29T14:06:09Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.