On combinatorial structures in linear codes
- URL: http://arxiv.org/abs/2309.16411v1
- Date: Thu, 28 Sep 2023 13:03:41 GMT
- Title: On combinatorial structures in linear codes
- Authors: Nou\'edyn Baspin
- Abstract summary: If the codes are classical we show instead that the $K_i$'s are $tildeOmegaleft(k/nright)$-expander.
In particular, we show that the BPT bound for classical codes is tight in all Euclidean dimensions.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work we show that given a connectivity graph $G$ of a $[[n,k,d]]$
quantum code, there exists $\{K_i\}_i, K_i \subset G$, such that $\sum_i
|K_i|\in \Omega(k), \ |K_i| \in \Omega(d)$, and the $K_i$'s are
$\tilde{\Omega}( \sqrt{{k}/{n}})$-expander. If the codes are classical we show
instead that the $K_i$'s are $\tilde{\Omega}\left({{k}/{n}}\right)$-expander.
We also show converses to these bounds. In particular, we show that the BPT
bound for classical codes is tight in all Euclidean dimensions. Finally, we
prove structural theorems for graphs with no "dense" subgraphs which might be
of independent interest.
Related papers
- Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input.
We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
arXiv Detail & Related papers (2024-02-23T12:22:03Z) - An advance in the arithmetic of the Lie groups as an alternative to the
forms of the Campbell-Baker-Hausdorff-Dynkin theorem [0.7373617024876725]
The exponential of an operator or matrix is widely used in quantum theory, but it sometimes can be a challenge to evaluate.
Here it is proven that $rm eabf X+bbf Y$ is equivalent to $rm epbf Zrm eqbf Xrm e-pbf Z$ for scalar $p$ and $q$.
arXiv Detail & Related papers (2024-01-28T19:20:02Z) - Quantum and classical query complexities of functions of matrices [0.0]
We show that for any continuous function $f(x):[-1,1]rightarrow [-1,1]$, the quantum query complexity of computing $brai f(A) ketjpm varepsilon/4$ is lower bounded by $Omega(widetildedeg_varepsilon(f))$.
arXiv Detail & Related papers (2023-11-13T00:45:41Z) - Embedding Inequalities for Barron-type Spaces [4.184052796218818]
We show that the constants do not depend on the input dimension $d$, suggesting that the embedding is effective in high dimensions.
We also show that the lower and upper bound are both tight.
arXiv Detail & Related papers (2023-05-30T14:45:51Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n.
We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
arXiv Detail & Related papers (2022-09-04T10:01:39Z) - On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss
Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$ [0.24366811507669117]
Let $mathcalM$ be a compact $d$-dimensional submanifold of $mathbbRN$ with reach $tau$ and volume $V_mathcal M$.
We prove that a nonlinear function $f: mathbbRN rightarrow mathbbRmm exists with $m leq C left(d / epsilon2right) log left(fracsqrt[d]V_math
arXiv Detail & Related papers (2022-06-07T15:10:46Z) - 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) - Matrix hypercontractivity, streaming algorithms and LDCs: the large
alphabet case [5.88864611435337]
We prove a hypercontractive inequality for matrix-valued functions defined over large alphabets.
We show that every streaming algorithm in the adversarial model achieving a $(r-varepsilon)$-approximation requires $Omega(n1-2/t)$ quantum space.
arXiv Detail & Related papers (2021-09-06T16:56:19Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets.
Two types of structural assumptions lead to better pseudo-regret bounds.
arXiv Detail & Related papers (2021-03-10T07:33:03Z) - The quantum query complexity of composition with a relation [78.55044112903148]
Belovs gave a modified version of the negative weight adversary method, $mathrmADV_relpm(f)$.
A relation is efficiently verifiable if $mathrmADVpm(f_a) = o(mathrmADV_relpm(f))$ for every $a in [K]$.
arXiv Detail & Related papers (2020-04-14T12:07:20Z) - 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.