skip to main content

Title: Finite-Function-Encoding Quantum States
We introduce finite-function-encoding (FFE) states which encode arbitrary d -valued logic functions, i.e., multivariate functions over the ring of integers modulo d , and investigate some of their structural properties. We also point out some differences between polynomial and non-polynomial function encoding states: The former can be associated to graphical objects, that we dub tensor-edge hypergraphs (TEH), which are a generalization of hypergraphs with a tensor attached to each hyperedge encoding the coefficients of the different monomials. To complete the framework, we also introduce a notion of finite-function-encoding Pauli (FP) operators, which correspond to elements of what is known as the generalized symmetric group in mathematics. First, using this machinery, we study the stabilizer group associated to FFE states and observe how qudit hypergraph states introduced in Ref. \cite{2017PhRvA..95e2340S} admit stabilizers of a particularly simpler form. Afterwards, we investigate the classification of FFE states under local unitaries (LU), and, after showing the complexity of this problem, we focus on the case of bipartite states and especially on the classification under local FP operations (LFP). We find all LU and LFP classes for two qutrits and two ququarts and study several other special classes, pointing out the relation between maximally entangled FFE states and complex Butson-type Hadamard matrices. Our investigation showcases also the relation between the properties of FFE states, especially their LU classification, and the theory of finite rings over the integers.  more » « less
Award ID(s):
2011074 1713868
Author(s) / Creator(s):
; ; ; ; ; ;
Date Published:
Journal Name:
Page Range / eLocation ID:
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Generalized permutahedra are polytopes that arise in combinatorics, algebraic geometry, representation theory, topology, and optimization. They possess a rich combinatorial structure. Out of this structure we build a Hopf monoid in the category of species.

    Species provide a unifying framework for organizing families of combinatorial objects. Many species carry a Hopf monoid structure and are related to generalized permutahedra by means of morphisms of Hopf monoids. This includes the species of graphs, matroids, posets, set partitions, linear graphs, hypergraphs, simplicial complexes, and building sets, among others. We employ this algebraic structure to define and study polynomial invariants of the various combinatorial structures.

    We pay special attention to the antipode of each Hopf monoid. This map is central to the structure of a Hopf monoid, and it interacts well with its characters and polynomial invariants. It also carries information on the values of the invariants on negative integers. For our Hopf monoid of generalized permutahedra, we show that the antipode maps each polytope to the alternating sum of its faces. This fact has numerous combinatorial consequences.

    We highlight some main applications:

    We obtain uniform proofs of numerous old and new results about the Hopf algebraic and combinatorial structures of these families. In particular, we give optimal formulas for the antipode of graphs, posets, matroids, hypergraphs, and building sets. They are optimal in the sense that they provide explicit descriptions for the integers entering in the expansion of the antipode, after all coefficients have been collected and all cancellations have been taken into account.

    We show that reciprocity theorems of Stanley and Billera–Jia–Reiner (BJR) on chromatic polynomials of graphs, order polynomials of posets, and BJR-polynomials of matroids are instances of one such result for generalized permutahedra.

    We explain why the formulas for the multiplicative and compositional inverses of power series are governed by the face structure of permutahedra and associahedra, respectively, providing an answer to a question of Loday.

    We answer a question of Humpert and Martin on certain invariants of graphs and another of Rota on a certain class of submodular functions.

    We hope our work serves as a quick introduction to the theory of Hopf monoids in species, particularly to the reader interested in combinatorial applications. It may be supplemented with Marcelo Aguiar and Swapneel Mahajan’s 2010 and 2013 works, which provide longer accounts with a more algebraic focus.

    more » « less
  2. null (Ed.)
    We give new and efficient black-box reconstruction algorithms for some classes of depth-3 arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More specifically, we provide efficient learning algorithms that run in randomized polynomial time over general fields and in deterministic polynomial time over and for the following classes: 1) Set-multilinear depth-3 circuits of constant top fan-in ((k) circuits). As a consequence of our algorithm, we obtain the first polynomial time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for d dimensional tensors for any d, but is interesting even for d=3. 2) Sums of powers of constantly many linear forms ((k) circuits). As a consequence we obtain the first polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. 3) Multilinear depth-3 circuits of constant top fan-in (multilinear (k) circuits). Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields (see. Karnin-Shpilka 09’). Prior to our work, the only polynomial-time or even subexponential-time algorithms known (deterministic or randomized) for subclasses of (k) circuits that also work over large/infinite fields were for the setting when the top fan-in k is at most 2 (see Sinha 16’ and Sinha 20’). 
    more » « less
  3. null (Ed.)

    We consider the regression problem of estimating functions on $ \mathbb{R}^D $ but supported on a $ d $-dimensional manifold $ \mathcal{M} ~~\subset \mathbb{R}^D $ with $ d \ll D $. Drawing ideas from multi-resolution analysis and nonlinear approximation, we construct low-dimensional coordinates on $ \mathcal{M} $ at multiple scales, and perform multiscale regression by local polynomial fitting. We propose a data-driven wavelet thresholding scheme that automatically adapts to the unknown regularity of the function, allowing for efficient estimation of functions exhibiting nonuniform regularity at different locations and scales. We analyze the generalization error of our method by proving finite sample bounds in high probability on rich classes of priors. Our estimator attains optimal learning rates (up to logarithmic factors) as if the function was defined on a known Euclidean domain of dimension $ d $, instead of an unknown manifold embedded in $ \mathbb{R}^D $. The implemented algorithm has quasilinear complexity in the sample size, with constants linear in $ D $ and exponential in $ d $. Our work therefore establishes a new framework for regression on low-dimensional sets embedded in high dimensions, with fast implementation and strong theoretical guarantees.

    more » « less
  4. Megow, Nicole ; Smith, Adam (Ed.)
    We study the question of local testability of low (constant) degree functions from a product domain 𝒮_1 × … × 𝒮_n to a field 𝔽, where 𝒮_i ⊆ 𝔽 can be arbitrary constant sized sets. We show that this family is locally testable when the grid is "symmetric". That is, if 𝒮_i = 𝒮 for all i, there is a probabilistic algorithm using constantly many queries that distinguishes whether f has a polynomial representation of degree at most d or is Ω(1)-far from having this property. In contrast, we show that there exist asymmetric grids with |𝒮_1| = ⋯ = |𝒮_n| = 3 for which testing requires ω_n(1) queries, thereby establishing that even in the context of polynomials, local testing depends on the structure of the domain and not just the distance of the underlying code. The low-degree testing problem has been studied extensively over the years and a wide variety of tools have been applied to propose and analyze tests. Our work introduces yet another new connection in this rich field, by building low-degree tests out of tests for "junta-degrees". A function f:𝒮_1 × ⋯ × 𝒮_n → 𝒢, for an abelian group 𝒢 is said to be a junta-degree-d function if it is a sum of d-juntas. We derive our low-degree test by giving a new local test for junta-degree-d functions. For the analysis of our tests, we deduce a small-set expansion theorem for spherical/hamming noise over large grids, which may be of independent interest. 
    more » « less
  5. Byrka, Jaroslaw ; Meka, Raghu (Ed.)
    In this work, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over F₂. We show the following results for multilinear forms and tensors. Correlation bounds. We show that a random d-linear form has exponentially low correlation with low-degree polynomials. More precisely, for d = 2^{o(k)}, we show that a random d-linear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{-k(1-o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving near-optimal bounds on the bias of a random d-linear form, which is in turn proved by giving near-optimal bounds on the probability that a sum of t random d-dimensional rank-1 tensors is identically zero. Tensor rank vs Bias. We show that if a 3-dimensional tensor has small rank then its bias, when viewed as a 3-linear form, is large. More precisely, given any 3-dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3-linear form f_T(X₁, X₂, X₃) : = ∑_{(i₁, i₂, i₃) ∈ [k]³} T(i₁, i₂, i₃)⋅ X_{1,i₁}⋅ X_{2,i₂}⋅ X_{3,i₃} is at least (3/4)^t. This bias vs tensor-rank connection suggests a natural approach to proving nontrivial tensor-rank lower bounds. In particular, we use this approach to give a new proof that the finite field multiplication tensor has tensor rank at least 3.52 k, which is the best known rank lower bound for any explicit tensor in three dimensions over F₂. Moreover, this relation between bias and tensor rank holds for d-dimensional tensors for any fixed d. 
    more » « less