Linear Programming Bounds on $k$-Uniform States

• URL: http://arxiv.org/abs/2503.02222v1
• Date: Tue, 04 Mar 2025 02:53:55 GMT
• Title: Linear Programming Bounds on $k$-Uniform States
• Authors: Yu Ning, Fei Shi, Tao Luo, Xiande Zhang,
• Abstract summary: The existence of $k$-uniform states has been a widely studied problem due to their applications in several quantum information tasks.<n>We establish several improved non-existence results and bounds on $k$-uniform states.
• Score: 13.489334588619041
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The existence of $k$-uniform states has been a widely studied problem due to their applications in several quantum information tasks and their close relation to combinatorial objects like Latin squares and orthogonal arrays. With the machinery of quantum enumerators and linear programming, we establish several improved non-existence results and bounds on $k$-uniform states. 1. First, for any fixed $l\geq 1$ and $q\geq 2$, we show that there exists a constant $c$ such that $(\left\lfloor{n/2}\right\rfloor-l)$-uniform states in $(\mathbb{C}^q)^{\otimes n}$ do not exist when $n\geq cq^2+o(q^2)$. The constant $c$ equals $4$ when $l=1$ and $6$ when $l=2$, which generalizes Scott's bound (2004) for $l=0$. 2. Second, when $n$ is sufficiently large, we show that there exists a constant $\theta<1/2$ for each $q \le 9$, such that $k$-uniform states in $(\mathbb{C}^q)^{\otimes n}$ exist only when $k\leq \theta n$. In particular, this provides the first bound (to the best of our knowledge) of $k$ for $4\leq q\leq 9$ and confirms a conjecture posed by Shi et al. (2023) when $q=5$ in a stronger form. 3. Finally, we improve the shadow bounds given by Shi et al. (2023) by a constant for $q = 3,4,5$ and small $n$. When $q=4$, our results can update some bounds listed in the code tables maintained by Grassl (2007--2024).

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• 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)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Bounds on $k$-Uniform Quantum States [22.266687858571363]
  We provide new upper bounds on the parameter $k$ for the existence of $k$-uniform states in $(mathbbCd)otimes N$. Since a $k$-uniform state in $(mathbbCd)otimes N$ corresponds to a pure $(N,1,k+1)_d$ quantum error-correcting codes, we also give new upper bounds on the minimum distance $k+1$ of pure $(N,1,k+1))_d$ quantum error-correcting codes
  arXiv  Detail & Related papers  (2023-10-10T07:38:13Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
  arXiv  Detail & Related papers  (2023-07-11T08:51:53Z)
• 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)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  tightest statistical query (SQ) lower bounds for learnining halfspaces in the presence of Massart noise. We show that for arbitrary $eta in [0,1/2]$ every SQ algorithm achieving misclassification error better than $eta$ requires queries of superpolynomial accuracy.
  arXiv  Detail & Related papers  (2022-01-24T17:33:19Z)
• 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)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

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.