Pseudorandomness from Subset States

• URL: http://arxiv.org/abs/2312.09206v1
• Date: Thu, 14 Dec 2023 18:36:16 GMT
• Title: Pseudorandomness from Subset States
• Authors: Tudor Giurgica-Tiron (Stanford University) and Adam Bouland (Stanford University)
• Abstract summary: We show it is possible to obtain quantum pseudorandomness and pseudoentanglement from random subset states. We show that the trace distance is negligibly small, as long as the subsets are of an appropriate size.
• Score: 0.34476492531570746
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show it is possible to obtain quantum pseudorandomness and pseudoentanglement from random subset states -- i.e. quantum states which are equal superpositions over (pseudo)random subsets of strings. This answers an open question of Aaronson et al. [arXiv:2211.00747], who devised a similar construction augmented by pseudorandom phases. Our result follows from a direct calculation of the trace distance between $t$ copies of random subset states and the Haar measure, via the representation theory of the symmetric group. We show that the trace distance is negligibly small, as long as the subsets are of an appropriate size which is neither too big nor too small. In particular, we analyze the action of basis permutations on the symmetric subspace, and show that the largest component is described by the Johnson scheme: the double-cosets of the symmetric group $\mathbb{S}_N$ by the subgroup $\mathbb{S}_t \times \mathbb{S}_{N-t}$. The Gelfand pair property of this setting implies that the matrix eigenbasis coincides with the symmetric group irreducible blocks, with the largest eigenblock asymptotically approaching the Haar average. An immediate corollary of our result is that quantum pseudorandom and pseudoentangled state ensembles do not require relative phases.

Related papers

• On lower bounds of the density of planar periodic sets without unit distances [55.2480439325792]
  We introduce a novel approach to estimating $m_1(mathbbR2)$ by reformulating the problem as a Maximal Independent Set (MIS) problem on graphs constructed from flat torus. Our experimental results supported by theoretical justifications of proposed method demonstrate that for a sufficiently wide range of parameters this approach does not improve the known lower bound.
  arXiv  Detail & Related papers  (2024-11-20T12:07:19Z)
• Wigner's Theorem for stabilizer states and quantum designs [0.6374763930914523]
  We describe the symmetry group of the stabilizer polytope for any number $n$ of systems and any prime local dimension $d$. In the qubit case, the symmetry group coincides with the linear and anti-linear Clifford operations. We extend an observation of Heinrich and Gross and show that the symmetries of fairly general sets of Hermitian operators are constrained by certain moments.
  arXiv  Detail & Related papers  (2024-05-27T18:00:13Z)
• Realizing triality and $p$-ality by lattice twisted gauging in (1+1)d quantum spin systems [0.0]
  We define the twisted Gauss law operator and implement the twisted gauging of the finite group on the lattice. We show the twisted gauging is equivalent to the two-step procedure of first applying the SPT entangler and then untwisted gauging.
  arXiv  Detail & Related papers  (2024-05-23T18:00:02Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  We show that products exponentiated sums of $S(N)$ permutations with random phases match the first $2Omega(n)$ moments of the Haar measure. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the method.
  arXiv  Detail & Related papers  (2024-04-25T17:08:34Z)
• Symmetry-restricted quantum circuits are still well-behaved [45.89137831674385]
  We show that quantum circuits restricted by a symmetry inherit the properties of the whole special unitary group $SU(2n)$. It extends prior work on symmetric states to the operators and shows that the operator space follows the same structure as the state space.
  arXiv  Detail & Related papers  (2024-02-26T06:23:39Z)
• Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
  A subset state with respect to $S$, a subset of the computational basis, is [ frac1sqrt|S|sum_iin S |irangle. We show that for any fixed subset size $|S|=s$ such that $s = 2n/omega(mathrmpoly(n))$ and $s=omega(mathrmpoly(n))$, a random subset state is information-theoretically indistinguishable from a Haar random state even provided
  arXiv  Detail & Related papers  (2023-12-23T15:52:46Z)
• Towards Antisymmetric Neural Ansatz Separation [48.80300074254758]
  We study separations between two fundamental models of antisymmetric functions, that is, functions $f$ of the form $f(x_sigma(1), ldots, x_sigma(N)) These arise in the context of quantum chemistry, and are the basic modeling tool for wavefunctions of Fermionic systems.
  arXiv  Detail & Related papers  (2022-08-05T16:35:24Z)
• When Random Tensors meet Random Matrices [50.568841545067144]
  This paper studies asymmetric order-$d$ spiked tensor models with Gaussian noise. We show that the analysis of the considered model boils down to the analysis of an equivalent spiked symmetric textitblock-wise random matrix.
  arXiv  Detail & Related papers  (2021-12-23T04:05:01Z)
• Statistics of the Spectral Form Factor in the Self-Dual Kicked Ising Model [0.0]
  We show that at large enough times the probability distribution agrees exactly with the prediction of Random Matrix Theory. This behaviour is due to a recently identified additional anti-unitary symmetry of the self-dual kicked Ising model.
  arXiv  Detail & Related papers  (2020-09-07T16:02:29Z)
• Combining Determinism and Indeterminism [0.0]
  We show that the bi-immune symmetric group is dense in Sym$(mathbbN)$ with respect to the pointwise convergence topology. The complete structure of the bi-immune symmetric group and its subgroups generated by one or more bi-immune rearrangements is unknown.
  arXiv  Detail & Related papers  (2020-09-02T01:30:00Z)
• A Concentration of Measure and Random Matrix Approach to Large Dimensional Robust Statistics [45.24358490877106]
  This article studies the emphrobust covariance matrix estimation of a data collection $X = (x_1,ldots,x_n)$ with $x_i = sqrt tau_i z_i + m$. We exploit this semi-metric along with concentration of measure arguments to prove the existence and uniqueness of the robust estimator as well as evaluate its limiting spectral distribution.
  arXiv  Detail & Related papers  (2020-06-17T09:02:26Z)

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.