Construction of $\varepsilon_{d}$-ASIC-POVMs via $2$-to-$1$ PN functions and the Li bound

• URL: http://arxiv.org/abs/2310.06418v3
• Date: Thu, 8 Feb 2024 16:37:34 GMT
• Title: Construction of $\varepsilon_{d}$-ASIC-POVMs via $2$-to-$1$ PN functions and the Li bound
• Authors: Meng Cao and Xiantao Deng
• Abstract summary: We prove that all $2$-to-$1$ perfect nonlinear (PN) functions can be used for constructing $varepsilon_q$-ASIC-POVMs. We show that the set of vectors corresponding to the $varepsilon_q$-ASIC-POVM forms a biangular frame. The construction of $varepsilon_q+1$-ASIC-POVMs is based on a multilicative character sum estimate called the Li bound.
• Score: 28.746561122145483
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Symmetric informationally complete positive operator-valued measures (SIC-POVMs) in finite dimension $d$ are a particularly attractive case of informationally complete POVMs (IC-POVMs), which consist of $d^{2}$ subnormalized projectors with equal pairwise fidelity. However, it is difficult to construct SIC-POVMs, and it is not even clear whether there exists an infinite family of SIC-POVMs. To realize some possible applications in quantum information processing, Klappenecker et al. [37] introduced an approximate version of SIC-POVMs called approximately symmetric informationally complete POVMs (ASIC-POVMs). In this paper, we construct a class of $\varepsilon_{d}$-ASIC-POVMs in dimension $d=q$ and a class of $\varepsilon_{d}$-ASIC-POVMs in dimension $d=q+1$, respectively, where $q$ is a prime power. We prove that all $2$-to-$1$ perfect nonlinear (PN) functions can be used for constructing $\varepsilon_{q}$-ASIC-POVMs. We show that the set of vectors corresponding to the $\varepsilon_{q}$-ASIC-POVM forms a biangular frame. The construction of $\varepsilon_{q+1}$-ASIC-POVMs is based on a multiplicative character sum estimate called the Li bound. We show that the set of vectors corresponding to the $\varepsilon_{q+1}$-ASIC-POVM forms an asymptotically optimal codebook. We characterize "how close" the $\varepsilon_{q}$-ASIC-POVMs (resp. $\varepsilon_{q+1}$-ASIC-POVMs) are from being SIC-POVMs of dimension $q$ (resp. dimension $q+1$). Finally, we explain the significance of constructing $\varepsilon_{d}$-ASIC-POVMs.

Related papers

• 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)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Enhancing the Harrow-Hassidim-Lloyd (HHL) algorithm in systems with large condition numbers [0.0]
  We demonstrate the ability of Psi-HHL to handle situations involving large $mathcalkappa$ matrices. We consider matrices up to size $256 times 256$ that reach $mathcalkappa$ of about 466.
  arXiv  Detail & Related papers  (2024-07-31T14:41:30Z)
• SIC-POVMs and orders of real quadratic fields [0.0]
  We consider the problem of counting and classifying symmetric informationally complete positive operator-valued measures (SICs or SIC-POVMs) We show the number of known equivalence classes of Weyl--Heisenberg covariant SICs in dimension $d$. We conjecture the equality extends to all $dgeq 4$.
  arXiv  Detail & Related papers  (2024-07-10T21:05:23Z)
• SIC-POVMs and the Knaster's Conjecture [0.0]
  We use the Bloch sphere representation of SIC-POVMs to prove the Knaster's conjecture for the geometry of SIC-POVMs. We also prove the existence of a continuous family of generalized SIC-POVMs where $(n2-1)$ of the matrices have the same value of $Tr(rhok)$.
  arXiv  Detail & Related papers  (2024-05-27T00:31:03Z)
• Conditions for the existence of positive operator valued measures [0.0]
  A sufficient condition for the existence of $(N,M)$-POVMs is presented. Necessary conditions are derived for the existence of optimal $(N,M)$-POVMs.
  arXiv  Detail & Related papers  (2023-10-18T20:09:47Z)
• Learning linear dynamical systems under convex constraints [4.4351901934764975]
  We consider the problem of identification of linear dynamical systems from $T$ samples of a single trajectory. $A*$ can be reliably estimated for values $T$ smaller than what is needed for unconstrained setting.
  arXiv  Detail & Related papers  (2023-03-27T11:49:40Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly. We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
  arXiv  Detail & Related papers  (2022-09-30T04:15:44Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)

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.