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
- 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)
For $4 leq d leq 90$, we show the number of known equivalence classes of Weyl--Heisenberg covariant SICs in dimension $d$.
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) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators.
Key to our solution is a novel projection technique based on ideas from harmonic analysis.
Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
arXiv Detail & Related papers (2024-05-10T09:58:47Z) - 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) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model.
Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$.
Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
arXiv Detail & Related papers (2023-08-16T06:46:37Z) - 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) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
We consider episodic reinforcement learning in reward-mixing Markov decision processes (RMMDPs)
Our goal is to learn a near-optimal policy that nearly maximizes the $H$ time-step cumulative rewards in such a model.
arXiv Detail & Related papers (2022-10-05T22:52:00Z) - 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.