Spectral Properties of Boolean Functions, Graphs and Graph States
Spectral Properties of Boolean Functions, Graphs and Graph States
复制标题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Constanza Riera
中科院分区：
文献类型：
--
作者：
Constanza Riera
通过对布尔函数关于一组选定的局部酉变换的谱分析，给出了布尔函数弯曲性质的推广。将二次布尔函数与简单图联系起来，证明了某些图变换所产生的轨道可以在某些酉变换集的谱内找到。二次布尔函数关于这些变换的平坦谱与它所关联的邻接矩阵的修改版本有关。用该方法求出了混凝土递推结构的平面谱。我们推导了图的交错多项式（在一个或两个变量中）的光谱解释，并将其中一个与相关量子态纠缠的量子测量联系起来。我们描述了一个二次布尔函数的谱值。我们给出了一个用修正的交错多项式表示二元线性码的权层次的公式。我们也推导了图上枢轴操作的谱解释，并将此操作推广到超图。我们枚举少量顶点的不相等枢轴轨道的数目。对于{I，H}n变换集，我们构造了具有大量平坦谱的二阶以上布尔函数族，并计算了这个数的下界。我们展示了如何通过枢轴操作来改变布尔函数的度数。最后，我们给出了关于选择好的变换集的大范围向量谱的具体公式。
Generalisations of the bent property of a Boolean function are presented, by proposing spectral analysis of the Boolean function with respect to a well-chosen set of local unitary transforms. Quadratic Boolean functions are related to simple graphs and it is shown that the orbit generated by some graph transforms can be found within the spectra of certain unitary transform sets. The flat spectra of a quadratic Boolean function with respect to those transforms are related to modified versions of its associated adjacency matrix. The flat spectra of concrete recursive structures are found using this method. We derive a spectral interpretation of the interlace polynomials (in one or two variables) of a graph and we relate to one of them a quantum measure of entanglement of the associated quantum state. We characterise the values of the spectra of a quadratic Boolean function. We give a formula for the weight hierarchy for a binary linear code in terms of a modified interlace polynomial. We derive as well a spectral interpretation of the pivot operation on a graph and generalise this operation to hypergraphs. We enumerate the number of inequivalent pivot orbits for small numbers of vertices. We also construct a family of Boolean functions of degree higher than two with a large number of flat spectra with respect to the {I,H}n set of transforms, and compute a lower bound on this number. We show how to change the degree of a Boolean function via pivot operation. Finally, we give concrete formulae for the spectra of a wide range of vectors with respect to well-chosen transforms sets.