There Are No Post-Quantum Weakly Pseudo-Free Families in Any Nontrivial Variety of Expanded Groups

• URL: http://arxiv.org/abs/2302.10847v2
• Date: Mon, 15 Jul 2024 19:24:48 GMT
• Title: There Are No Post-Quantum Weakly Pseudo-Free Families in Any Nontrivial Variety of Expanded Groups
• Authors: Mikhail Anokhin,
• Abstract summary: We show that there are no post-quantum weakly pseudo-free families in $mathfrak V$, even in the worst-case setting and/or the black-box model. Also, we define and study some types of weak pseudo-freeness for families of computational and black-box $Omega$-algebras.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Let $\Omega$ be a finite set of finitary operation symbols and let $\mathfrak V$ be a nontrivial variety of $\Omega$-algebras. Assume that for some set $\Gamma\subseteq\Omega$ of group operation symbols, all $\Omega$-algebras in $\mathfrak V$ are groups under the operations associated with the symbols in $\Gamma$. In other words, $\mathfrak V$ is assumed to be a nontrivial variety of expanded groups. In particular, $\mathfrak V$ can be a nontrivial variety of groups or rings. Our main result is that there are no post-quantum weakly pseudo-free families in $\mathfrak V$, even in the worst-case setting and/or the black-box model. In this paper, we restrict ourselves to families $(H_d\mathbin|d\in D)$ of computational and black-box $\Omega$-algebras (where $D\subseteq\{0,1\}^*$) such that for every $d\in D$, each element of $H_d$ is represented by a unique bit string of length polynomial in the length of $d$. In our main result, we use straight-line programs to represent nontrivial relations between elements of $\Omega$-algebras. Note that under certain conditions, this result depends on the classification of finite simple groups. Also, we define and study some types of weak pseudo-freeness for families of computational and black-box $\Omega$-algebras.

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)
• Some new infinite families of non-$p$-rational real quadratic fields [0.0]
  We give a simple methodology for constructing an infinite family of simultaneously non-$p_j$-rational real fields, unramified above any of the $p_j$. One feature of these techniques is that they may be used to yield fields $K=mathbbQ(sqrtD)$ for which a $p$-power cyclic component of the torsion group of the Galois groups of the maximal abelian pro-$p$-extension of $K$ unramified outside primes above $p$, is of size $pa
  arXiv  Detail & Related papers  (2024-06-20T18:00:51Z)
• Almost-idempotent quantum channels and approximate $C^*$-algebras [0.03922370499388702]
  We prove that any finite-dimensional $varepsilon$-$C*$ algebra is $O(varepsilon)$-isomorphic to a genuine $C*$ algebra.
  arXiv  Detail & Related papers  (2024-05-03T18:59:50Z)
• Dimension-free Remez Inequalities and norm designs [48.5897526636987]
  A class of domains $X$ and test sets $Y$ -- termed emphnorm -- enjoy dimension-free Remez-type estimates. We show that the supremum of $f$ does not increase by more than $mathcalO(log K)2d$ when $f$ is extended to the polytorus.
  arXiv  Detail & Related papers  (2023-10-11T22:46:09Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• Monogamy of entanglement between cones [68.8204255655161]
  We show that monogamy is not only a feature of quantum theory, but that it characterizes the minimal tensor product of general pairs of convex cones. Our proof makes use of a new characterization of products of simplices up to affine equivalence.
  arXiv  Detail & Related papers  (2022-06-23T16:23:59Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  The observables associated with a quantum system $S$ form a non-commutative algebra $mathcal A_S$. It is assumed that a density matrix $rho$ can be determined from the expectation values of observables. Abelian algebras do not have inner automorphisms, so the measurement apparatus can determine mean values of observables.
  arXiv  Detail & Related papers  (2021-12-14T16:29:53Z)
• 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)
• 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)
• Combining Semilattices and Semimodules [0.0]
  We show that the composition of $mathcal P$ with $mathcal S$ by means of such $delta$ yields almost the monad of convex subsets previously introduced by Jacobs. We provide a handy characterisation of the canonical weak lifting of $mathcal P$ to $mathbbEM(mathcal S)$ as well as an algebraic theory for the resulting composed monad.
  arXiv  Detail & Related papers  (2020-12-29T14:44:13Z)

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.