No-go theorems for sublinear-depth group designs
- URL: http://arxiv.org/abs/2506.16005v1
- Date: Thu, 19 Jun 2025 03:51:18 GMT
- Title: No-go theorems for sublinear-depth group designs
- Authors: Maxwell West, Diego García-Martín, N. L. Diaz, M. Cerezo, Martin Larocca,
- Abstract summary: We prove that no subset of $G$ consisting of sublinear-depth one-dimensional circuits with local gates can form an approximate $k$-design over $G$.<n>For most of the groups we consider we find that such ensembles can, with high probability, be distinguished from $k$-designs by a single shot of a constant-depth measurement.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a long-standing and fundamental problem in quantum information theory. Recently it was shown that one can obtain approximate designs over the unitary group with depths scaling logarithmically in the number of qubits, but that no sublinear-depth approximate designs exist over the orthogonal group. Here we derive, for any group $G$ possessing an invariant state $G^{\otimes k} \lvert\Psi\rangle= \lvert\Psi\rangle$, a lower bound on the diamond distance between the $k$\textsuperscript{th} moment operator of any ensemble of elements of $G$, and that of the Haar measure over $G$. We then use this bound to prove that for many groups of interest, no subset of $G$ consisting of sublinear-depth one-dimensional circuits with local gates can form an approximate $k$-design over $G$. More generally, on a $D$-dimensional lattice, our results imply that such group designs require depths scaling at least as $n^{1/D}$. Moreover, for most of the groups we consider we find that such ensembles can, with high probability, be distinguished from $k$-designs by a single shot of a constant-depth measurement. Among other examples, we show that there is a constant separation between (a) the maximum depth and gate count for which no circuit can approximate even the second moment of random matchgate circuits, and (b) the depth and gate count required to implement the matchgate Haar distribution exactly. We furthermore rule out the existence of sublinear-depth $8$-designs over the Clifford group. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over $G$ using any circuit comprised of a sublinear number of gates generated by Pauli strings.
Related papers
- Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits [6.844618776091756]
An approximate unitary $k$-design is an ensemble of unitaries and measure over which the average is close to a Haar random ensemble up to the first $k$ moments.
We construct multiplicative-error approximate unitary $k$-design ensembles for which communication between subsystems is $O(1)$ in the system size.
arXiv Detail & Related papers (2024-07-10T17:43:23Z) - Random unitaries in extremely low depth [0.8680580889074451]
We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over $n$ qubits in $log n$ depth.<n>In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in $textpoly(log n)$ depth, and in all-to-all-connected circuits in $textpoly(log log n)$ depth.
arXiv Detail & Related papers (2024-07-10T15:27:48Z) - 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) - Unitary k-designs from random number-conserving quantum circuits [0.0]
Local random circuits scramble efficiently and accordingly have a range of applications in quantum information and quantum dynamics.
We show that finite moments cannot distinguish the ensemble that local random circuits generate from the Haar ensemble on the entire group of number-conserving unitaries.
arXiv Detail & Related papers (2023-06-01T18:00:00Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model.
This learning model is widely used as an abstract computational model for most generic learning algorithms.
arXiv Detail & Related papers (2023-05-09T20:53:27Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis.
We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$.
Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
arXiv Detail & Related papers (2022-08-19T18:00:34Z) - 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) - Adaptive constant-depth circuits for manipulating non-abelian anyons [65.62256987706128]
Kitaev's quantum double model based on a finite group $G$.
We describe quantum circuits for (a) preparation of the ground state, (b) creation of anyon pairs separated by an arbitrary distance, and (c) non-destructive topological charge measurement.
arXiv Detail & Related papers (2022-05-04T08:10:36Z) - Quantum double aspects of surface code models [77.34726150561087]
We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry.
We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
arXiv Detail & Related papers (2021-06-25T17:03:38Z) - A deep network construction that adapts to intrinsic dimensionality
beyond the domain [79.23797234241471]
We study the approximation of two-layer compositions $f(x) = g(phi(x))$ via deep networks with ReLU activation.
We focus on two intuitive and practically relevant choices for $phi$: the projection onto a low-dimensional embedded submanifold and a distance to a collection of low-dimensional sets.
arXiv Detail & Related papers (2020-08-06T09:50:29Z) - Epsilon-nets, unitary designs and random quantum circuits [0.11719282046304676]
Epsilon-nets and approximate unitary $t$-designs are notions of unitary operations relevant for numerous applications in quantum information and quantum computing.
We prove that for a fixed $d$ of the space, unitaries constituting $delta$-approx $t$-expanders form $epsilon$-nets for $tsimeqfracd5/2epsilon$ and $delta=left(fracepsilon3/2dright)d2$.
We show that approximate tdesigns can be generated
arXiv Detail & Related papers (2020-07-21T15:16:28Z)
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.