On Symmetric Pseudo-Boolean Functions: Factorization, Kernels and Applications

• URL: http://arxiv.org/abs/2209.15009v2
• Date: Tue, 22 Aug 2023 12:23:36 GMT
• Title: On Symmetric Pseudo-Boolean Functions: Factorization, Kernels and Applications
• Authors: Richik Sengupta and Jacob Biamonte
• Abstract summary: We prove that any symmetric pseudo-Boolean function can be equivalently expressed as a power series or factorized. We use these results to analyze symmetric pseudo-Boolean functions appearing in the literature of spin glass energy functions, quantum information and tensor networks.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A symmetric pseudo-Boolean function is a map from Boolean tuples to real numbers which is invariant under input variable interchange. We prove that any such function can be equivalently expressed as a power series or factorized. The kernel of a pseudo-Boolean function is the set of all inputs that cause the function to vanish identically. Any $n$-variable symmetric pseudo-Boolean function $f(x_1, x_2, \dots, x_n)$ has a kernel corresponding to at least one $n$-affine hyperplane, each hyperplane is given by a constraint $\sum_{l=1}^n x_l = \lambda$ for $\lambda\in \mathbb{C}$ constant. We use these results to analyze symmetric pseudo-Boolean functions appearing in the literature of spin glass energy functions (Ising models), quantum information and tensor networks.

Related papers

• Shift-invariant functions and almost liftings [0.0]
  We investigate shift-invariant vectorial Boolean functions on $n$bits that are lifted from Boolean functions on $k$bits, for $kleq n$. We show that if a Boolean function with diameter $k$ is an almost lifting, the maximum number of collisions of its lifted functions is $2k-1$ for any $n$. We search for functions in the class of almost liftings that have good cryptographic properties and for which the non-bijectivity does not cause major security weaknesses.
  arXiv  Detail & Related papers  (2024-07-16T17:23:27Z)
• Uniform $\mathcal{C}^k$ Approximation of $G$-Invariant and Antisymmetric Functions, Embedding Dimensions, and Polynomial Representations [0.0]
  We show that the embedding dimension required is independent of the regularity of the target function, the accuracy of the desired approximation, and $k$. We also provide upper and lower bounds on $K$ and show that $K$ is independent of the regularity of the target function, the desired approximation accuracy, and $k$.
  arXiv  Detail & Related papers  (2024-03-02T23:19:10Z)
• On the Rational Degree of Boolean Functions and Applications [1.8125795677957914]
  It is conjectured that $mathrmrdeg(f)$ is unboundedly related to $mathrmdeg(f)$. symmetric functions have rational degree $mathrmdeg(f)/2$ and monotone functions have rational degree at least $sqrtmathrmdeg(f)$.
  arXiv  Detail & Related papers  (2023-10-12T03:14:44Z)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  Given two monotone prime functions $f:0,1n to 0,1$ and $g:0,1n to 0,1$ the dualization problem consists in determining if $g$ is the dual of $f$. We present a quantum computing algorithm that solves the decision version of the dualization problem in time.
  arXiv  Detail & Related papers  (2023-08-28T18:12:54Z)
• Towards Antisymmetric Neural Ansatz Separation [48.80300074254758]
  We study separations between two fundamental models of antisymmetric functions, that is, functions $f$ of the form $f(x_sigma(1), ldots, x_sigma(N)) These arise in the context of quantum chemistry, and are the basic modeling tool for wavefunctions of Fermionic systems.
  arXiv  Detail & Related papers  (2022-08-05T16:35:24Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  We show how all properties of a quantum manifold of states are fully described by a gauge-invariant Bargmann. We show how our results have immediate applications to the modern theory of polarization.
  arXiv  Detail & Related papers  (2022-05-30T18:01:34Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Convexity of a certain operator trace functional [1.1470070927586014]
  In this article the operator trace function $ Lambda_r,s(A)[K, M] := operatornametr(K*Ar M Ar K)s$ is introduced and its convexity and concavity properties are investigated. This function has a direct connection to several well-studied operator trace functions that appear in quantum information theory.
  arXiv  Detail & Related papers  (2021-09-23T17:51:46Z)
• 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)
• Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem [4.549831511476248]
  We show that for any total Boolean function $f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$: The degree of $f$ is at mosttrivial quadratic in the approximate degree of $f$. We show that if $f$ is a non monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $mathrmQ(f)=Omega(n)$, which is also optimal.
  arXiv  Detail & Related papers  (2020-10-23T19:21:28Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
  arXiv  Detail & Related papers  (2020-02-23T22:51:52Z)

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.