Unitary Subgroup Testing

• URL: http://arxiv.org/abs/2104.03591v3
• Date: Tue, 22 Nov 2022 07:27:21 GMT
• Title: Unitary Subgroup Testing
• Authors: Zvika Brakerski, Devika Sharma, Guy Weissenberg
• Abstract summary: 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.
• Score: 8.282602586225831
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of $\textit{subgroup testing}$ for a quantum circuit $C$: given access to $C$, determine whether it implements a unitary that is $a$-close or $b$-far from a subgroup $\mathcal{G}$ of the unitary group. It encompasses the problem of exact testing, property testing and tolerant testing. In this work, we study these problems with the group $\mathcal{G}$ as the trivial subgroup (i.e. identity testing) or the Pauli or Clifford group and their $q$-ary extension, and a $\textit{promise}$ version of these problems where $C$ is promised to be in some subgroup of the unitaries that contains $\mathcal{G}$ (e.g. identity testing for Clifford circuits). Our main result is an equivalence between Pauli testing, Clifford testing and Identity testing. We derive the equivalence between Clifford and Identity testing by showing a structural property of the Clifford unitaries. Namely, that their (normalized) trace lies in the discrete set $\{2^{-k/2}: k \in \mathbb{N}\} \cup \{0\}$, regardless of the dimension. We also state and prove the analogous property for the $q$-ary Cliffords. This result allows us to analyze a very simple single-query identity test under the Clifford/Pauli promise. To prove the equivalence between Pauli and Identity testing, we analyze the conjugation action of a non-Pauli unitary on the Pauli group and show that its distance from the Pauli group affects the number of fixed points. We believe that these results are of interest, independent of their application to establish the equivalences. We use the equivalences to compare (and thus establish) computational hardness for the problems of Pauli and Clifford testing.

Related papers

• 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)
• 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)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
  Uniformity testing is one of the most well-studied problems in property testing. It is known that the optimal sample complexity to distinguish the uniform distribution on $m$ elements from any $epsilon$-far distribution with $1-delta probability is $n. We show that the collisions tester achieves a sharp maximal constant in the number of standard deviations of separation between uniform and non-uniform inputs.
  arXiv  Detail & Related papers  (2022-06-21T20:43:53Z)
• 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)
• Testing matrix product states [5.225550006603552]
  We study the problem of testing whether an unknown state $|psirangle$ is a matrix product state (MPS) in the property testing model. MPS are a class of physically-relevant quantum states which arise in the study of quantum many-body systems.
  arXiv  Detail & Related papers  (2022-01-05T21:10:50Z)
• A Kernel Test for Causal Association via Noise Contrastive Backdoor Adjustment [18.791409397894835]
  We develop a non-parametric method to test the textitdo-null hypothesis $H_0:; p(y|textit do(X=x))=p(y)$ against the general alternative. We demonstrate that backdoor-HSIC (bd-HSIC) is calibrated and has power for both binary and continuous treatments under a large number of confounders.
  arXiv  Detail & Related papers  (2021-11-25T19:12:37Z)
• 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)
• Sample optimal Quantum identity testing via Pauli Measurements [11.98034899127065]
  We show that $Theta(mathrmpoly(n)cdotfrac4nepsilon2)$ is the sample complexity of testing whether two $n$-qubit quantum states $rho$ and $sigma$ are identical or $epsilon$-far in trace distance using two-outcome Pauli measurements.
  arXiv  Detail & Related papers  (2020-09-24T06:54:09Z)
• 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)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

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.