Clifford testing: algorithms and lower bounds

• URL: http://arxiv.org/abs/2510.07164v1
• Date: Wed, 08 Oct 2025 16:02:07 GMT
• Title: Clifford testing: algorithms and lower bounds
• Authors: Marcel Hinsche, Zongbo Bao, Philippe van Dordrecht, Jens Eisert, Jop Briët, Jonas Helsen,
• Abstract summary: 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.<n>We show that our tester is tolerant, by adapting techniques from tolerant stabilizer testing to our setting.
• Score: 2.678461526933908
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• The non-Clifford cost of random unitaries [0.2796197251957244]
  We explore the ensemble of $t$-doped Clifford circuits on $n$ qubits.<n>We establish rigorous convergence bounds towards unitary $k$-designs.<n>We derive analytic expressions for the operator twirling over the ensemble of random doped Clifford circuits.
  arXiv  Detail & Related papers  (2025-05-15T09:28:10Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Single-copy stabilizer testing [0.0]
  We consider the problem of testing whether an unknown $n$-qubit quantum state $|psirangle$ is a stabilizer state. We give an algorithm solving this problem using $O(n)$ copies, and conversely prove that $Omega(sqrtn)$ copies are required for any algorithm.
  arXiv  Detail & Related papers  (2024-10-10T14:39:47Z)
• Testing the Feasibility of Linear Programs with Bandit Feedback [53.40256244941895]
  We develop a test based on low-regret algorithms and a nonasymptotic law of iterated logarithms. We prove that this test is reliable, and adapts to the signal level,' $Gamma,$ of any instance. We complement this by a minimax lower bound $(Omegad/Gamma2)$ for sample costs of reliable tests.
  arXiv  Detail & Related papers  (2024-06-21T20:56:35Z)
• Low-depth Clifford circuits approximately solve MaxCut [44.99833362998488]
  We introduce a quantum-inspired approximation algorithm for MaxCut based on low-depth Clifford circuits. Our algorithm finds an approximate solution of MaxCut on an $N$-vertex graph by building a depth $O(N)$ Clifford circuit.
  arXiv  Detail & Related papers  (2023-10-23T15:20:03Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  We propose a new, simplified high probability analysis of AdaGrad for smooth, non- probability problems. We present our analysis in a modular way and obtain a complementary $mathcal O (1 / TT)$ convergence rate in the deterministic setting. To the best of our knowledge, this is the first high probability for AdaGrad with a truly adaptive scheme, i.e., completely oblivious to the knowledge of smoothness.
  arXiv  Detail & Related papers  (2022-04-06T13:50:33Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Unitary Subgroup Testing [8.282602586225831]
  We study problems with the group $mathcalG$ as the trivial subgroup (i.e. identity testing) or the Pauli or Clifford group and their $q$-ary extension. Our main result is an equivalence between Pauli testing, Clifford testing and Identity testing.
  arXiv  Detail & Related papers  (2021-04-08T08:12:25Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
  arXiv  Detail & Related papers  (2020-12-31T18:24:41Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  We study the problem of testing discrete distributions with a focus on the high probability regime. We provide the first algorithms for closeness and independence testing that are sample-optimal, within constant factors.
  arXiv  Detail & Related papers  (2020-09-14T16:09:17Z)
• Hadamard-free circuits expose the structure of the Clifford group [9.480212602202517]
  The Clifford group plays a central role in quantum randomized benchmarking, quantum tomography, and error correction protocols. We show that any Clifford operator can be uniquely written in the canonical form $F_HSF$. A surprising connection is highlighted between random uniform Clifford operators and the Mallows distribution on the symmetric group.
  arXiv  Detail & Related papers  (2020-03-20T17:51:36Z)
• Efficient unitary designs with a system-size independent number of non-Clifford gates [2.387952453171487]
  It takes exponential resources to produce Haar-random unitaries drawn from the full $n$-qubit group. Unitary $t-designs mimic the Haar-$-th moments. We derive novel bounds on the convergence time of random Clifford circuits to the $t$-th moment of the uniform distribution on the Clifford group.
  arXiv  Detail & Related papers  (2020-02-21T19:41:07Z)

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.