Realization of an arbitrary structure of perfect distinguishability of
states in general probability theory
- URL: http://arxiv.org/abs/2301.06553v1
- Date: Mon, 16 Jan 2023 18:33:39 GMT
- Title: Realization of an arbitrary structure of perfect distinguishability of
states in general probability theory
- Authors: Mih\'aly Weiner
- Abstract summary: All subsets with a single element are of course in $mathcal A$, and since smaller collections are easier to distinguish, if $Hin mathcal A$ and $L subset H$ then $Lin mathcal A$; in other words, $mathcal A$ is a so-called $textitindependence system$ on the set of indices $[n]$.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Let $s_1,s_2,\ldots s_n$ be states of a general probability theory, and
$\mathcal A$ be the set of all subsets of indices $H \subset
[n]\equiv\{1,2,\ldots n\}$ such that the states $(s_j)_{j\in H}$ are jointly
perfectly distinguishable. All subsets with a single element are of course in
$\mathcal A$, and since smaller collections are easier to distinguish, if $H\in
\mathcal A$ and $L \subset H$ then $L\in \mathcal A$; in other words, $\mathcal
A$ is a so-called $\textit{independence system}$ on the set of indices $[n]$.
In this paper it is shown that every independence system on $[n]$ can be
realized in the above manner.
Related papers
- Efficient Continual Finite-Sum Minimization [52.5238287567572]
We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization.
Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires.
We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
arXiv Detail & Related papers (2024-06-07T08:26:31Z) - Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
We are given a set of random samples $(mathbfx_i,y_i) in [-1,1]n times mathbbR$ that are noisy versions of $(mathbfx_i,p(mathbfx_i)$.
The goal is to output a $hatp$, within an $ell_in$-distance of at most $O(sigma)$ from $p$.
arXiv Detail & Related papers (2024-03-14T15:04:45Z) - Mapping the space of quantum expectation values [0.0]
For a quantum system with Hilbert space $cal H$ of dimension $N$, a basic question is to understand the set $E_S subset mathbbRn$ of points $vece$.
A related question is to determine whether a given set of expectation values $vec$ lies in $E_S$.
arXiv Detail & Related papers (2023-10-19T19:17:42Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm.
Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
arXiv Detail & Related papers (2022-02-10T16:10:41Z) - Fair Representation Clustering with Several Protected Classes [13.53362222844008]
We study the problem of fair $k$-median where each cluster is required to have a fair representation of individuals from different groups.
We present an $O(log k)$-approximation algorithm that runs in time $nO(ell)$.
arXiv Detail & Related papers (2022-02-03T03:45:45Z) - How to check universality of quantum gates? [0.0]
Our first criterion states that $mathcalSsubset G_d:=U(d)$ is universal if and only if $mathcalS$ forms a $delta$-approximate $t(d)$-design.
Our second universality criterion says that $mathcalSsubset G_d$ is universal if and only if the centralizer of $mathcalSt(d),t(d)=Uotimes t(d)otimes t(d)|U
arXiv Detail & Related papers (2021-11-06T11:58:32Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
arXiv Detail & Related papers (2021-09-06T14:21:43Z) - Simplest non-additive measures of quantum resources [77.34726150561087]
We study measures that can be described by $cal E(rhootimes N) =E(e;N) ne Ne$.
arXiv Detail & Related papers (2021-06-23T20:27:04Z) - A Note on Rough Set Algebra and Core Regular Double Stone Algebras [0.0]
In our Main Theorem we show $R_theta$ with $|theta_u| > 1 forall u in U$ to be isomorphic to $TP_E$ and $C_3E$, and that the three CRDSA's are complete and atomic.
In our Main Corollary we show explicitly how we can embed such $R_theta$ in $TP_U$, $C_3U$, respectively, $phicirc alpha_r:R_thetahookright
arXiv Detail & Related papers (2021-01-07T00:32:03Z) - 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) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model.
Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
arXiv Detail & Related papers (2020-02-09T03:39:46Z)
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.