Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2209.15009

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

Richik Sengupta, Jacob Biamonte

Published Sep 29, 2022• 0 citations
arXivHTMLPDF

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 = λ$ for $λ\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.

DOI
10.48550/arxiv.2209.15009

Related papers

Quadratizations of symmetric pseudo-Boolean functions: sub-linear bounds on the number of auxiliary variables

Endre Boros, Yves Crama, Elisabeth Rodríguez-Heck

The problem of minimizing a pseudo-Boolean function with no additional constraints arises in a variety of applications.A quadratization is a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques.Using the well-known result that a pseudo-Boolean function can be uniquely expressed as a multilinear polynomial, any pseudo-Boolean function can be quadratized by providing a quadratization for negative monomials and one for positive monomials.A desirable property for a quadratization is to introduce small number of auxiliary variables.For the case of negative monomials there exists a quadratization using a single auxiliary variable which is, in addition, submodular.However, much less is known for positive monomials.The best lower bound on the number of variables required by a quadratization in the literature is n-1 2 .We present here new quadratizations of the positive monomial that significantly improve this lower bound decreasing it to a logarithmic bound.This lower bound is derived from a more general result, stating that a quadratization with a logarithmic number of variables can be defined for exact kout-of-n functions, which is a more general class of symmetric functions.Moreover, for exact k-out-of-n functions we also prove that a logarithmic number of variables is necessary when requiring certain symmetry conditions to the quadratization.Finally, we provide quadratizations for general symmetric functions using O( √ n) auxiliary variables.This upper bound nicely matches a lower bound of Ω( √ n) variables that was recently introduced.

ISAIM•Jan 4, 2018•7 citations

Quadratic reformulations for the optimization of pseudo-boolean functions

Yves Crama, Sourour Elloumi, Amélie Lambert +1 more

We investigate various solution approaches for the uncon-strained minimization of a pseudo-boolean function. Moreprecisely, we assume that the original function is expressedas a real-valued polynomial in 0-1 variables, of degree threeor more, and we consider a generic family of two-step ap-proaches for its minimization. First, a quadratic reformu-lation step aims at transforming the minimization probleminto an equivalent constrained or unconstrained quadratic0-1 minimization problem (where “equivalent” means herethat a minimizer of the original function can be easily de-duced from a minimizer of the reformulation). Second, anoptimization step handles the obtained equivalent quadraticproblem.We provide a unified presentation of several quadratic re-formulation schemes proposed in the literature, e.g., (An-thony et al. 2017; Buchheim and Rinaldi 2007; Rodr ́ıguez-Heck 2018; Rosenberg 1975), and we review several meth-ods that can be applied in the optimization step, includinga standard linearization procedure (Fortet 1959) and moreelaborate convex quadratic reformulations, as in (Billionnetand Elloumi 2007; Billionnet, Elloumi, and Lambert 2012,2016; Elloumi, Lambert, and Lazare 2021). We discuss theimpact of the reformulation scheme on the efficiency of theoptimization step and we illustrate our discussion with somecomputational results on different classes of instances.

•Jan 3, 2022•0 citations

Regular realization of symmetric functions using reversible logic

Marek A. Perkowski, Paweł Kerntopf, Andrzej Buller +7 more

Reversible logic is of increasing importance to many future computer technologies. We introduce a regular structure to realize symmetric functions in binary reversible logic. This structure, called a 2*2 net structure, allows for a more efficient realization of symmetric functions than the methods introduced by the other authors. Our synthesis method allows us to realize arbitrary symmetric function in a completely regular structure of reversible gates with relatively little "garbage". Because every Boolean function can be made symmetric by repeating input variables, our method is applicable to arbitrary multi-input multi-output Boolean functions and realizes such arbitrary function in a circuit with a relatively small number of additional gate outputs. The method can also be used in classical logic. Its advantages in terms of numbers of gates and inputs/outputs are especially seen for symmetric or incompletely specified functions with many outputs.

Euromicro Conference on Digital System Design (DSD)•Nov 13, 2002•51 citations

On the Representation of Boolean and Real Functions as Hamiltonians for Quantum Computing

Stuart Hadfield

Mapping functions on bits to Hamiltonians acting on qubits has many applications in quantum computing. In particular, Hamiltonians representing Boolean functions are required for applications of quantum annealing or the quantum approximate optimization algorithm to combinatorial optimization problems. We show how such functions are naturally represented by Hamiltonians given as sums of Pauli Z operators (Ising spin operators) with the terms of the sum corresponding to the function’s Fourier expansion. For many classes of Boolean functions which are given by a compact description, such as a Boolean formula in conjunctive normal form that gives an instance of the satisfiability problem, it is #P-hard to compute its Hamiltonian representation, i.e., as hard as computing its number of satisfying assignments. On the other hand, no such difficulty exists generally for constructing Hamiltonians representing a real function such as a sum of local Boolean clauses each acting on a fixed number of bits as is common in constraint satisfaction problems. We show composition rules for explicitly constructing Hamiltonians representing a wide variety of Boolean and real functions by combining Hamiltonians representing simpler clauses as building blocks, which are particularly suitable for direct implementation as classical software. We further apply our results to the construction of controlled-unitary operators, and to the special case of operators that compute function values in an ancilla qubit register. Finally, we outline several additional applications and extensions of our results to quantum algorithms for optimization. A goal of this work is to provide a design toolkit for quantum optimization which may be utilized by experts and practitioners alike in the construction and analysis of new quantum algorithms, and at the same time to provide a unified framework for the various constructions appearing in the literature.

arXiv:1804.09130•ACM Transactions on Quantum Computing•Dec 21, 2021•86 citations

Classification of Boolean functions by the invariants of their matrix representation

A. B. Lapshin

A variant of matrix representation for Boolean functions is designed such that these functions can be classified by matrix invariants. By way of example, the Deutsch problem is solved to illustrate the advantages of this classification.

Automation and Remote Control•Jul 1, 2006•1 citation

Symmetric and anti-symmetric quantum functions

John Robert Burger

This paper introduces and analyzes symmetric and anti-symmetric quantum binary functions. Generally, such functions uniquely convert a given computational basis state into a different basis state, but with either a plus or a minus sign. Such functions may serve along with a constant function (in a Deutsch-Jozsa type of algorithm) to provide 2**n deterministic qubit combinations (for n qubits) instead of just one.

arXiv:cs/0304016•Apr 10, 2003•1 citation
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 nnn-variable symmetric pseudo-Boolean function f(x1,x2,…,xn)f(x_1, x_2, \dots, x_n)f(x1​,x2​,…,xn​) has a kernel corresponding to at least one nnn-affine hyperplane, each hyperplane is given by a constraint ∑l=1nxl=λ\sum_{l=1}^n x_l = λ∑l=1n​xl​=λ for λ∈Cλ\in \mathbb{C}λ∈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.
The problem of minimizing a pseudo-Boolean function with no additional constraints arises in a variety of applications.A quadratization is a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques.Using the well-known result that a pseudo-Boolean function can be uniquely expressed as a multilinear polynomial, any pseudo-Boolean function can be quadratized by providing a quadratization for negative monomials and one for positive monomials.A desirable property for a quadratization is to introduce small number of auxiliary variables.For the case of negative monomials there exists a quadratization using a single auxiliary variable which is, in addition, submodular.However, much less is known for positive monomials.The best lower bound on the number of variables required by a quadratization in the literature is n-1 2 .We present here new quadratizations of the positive monomial that significantly improve this lower bound decreasing it to a logarithmic bound.This lower bound is derived from a more general result, stating that a quadratization with a logarithmic number of variables can be defined for exact kout-of-n functions, which is a more general class of symmetric functions.Moreover, for exact k-out-of-n functions we also prove that a logarithmic number of variables is necessary when requiring certain symmetry conditions to the quadratization.Finally, we provide quadratizations for general symmetric functions using O( √ n) auxiliary variables.This upper bound nicely matches a lower bound of Ω( √ n) variables that was recently introduced.
We investigate various solution approaches for the uncon-strained minimization of a pseudo-boolean function. Moreprecisely, we assume that the original function is expressedas a real-valued polynomial in 0-1 variables, of degree threeor more, and we consider a generic family of two-step ap-proaches for its minimization. First, a quadratic reformu-lation step aims at transforming the minimization probleminto an equivalent constrained or unconstrained quadratic0-1 minimization problem (where “equivalent” means herethat a minimizer of the original function can be easily de-duced from a minimizer of the reformulation). Second, anoptimization step handles the obtained equivalent quadraticproblem.We provide a unified presentation of several quadratic re-formulation schemes proposed in the literature, e.g., (An-thony et al. 2017; Buchheim and Rinaldi 2007; Rodr ́ıguez-Heck 2018; Rosenberg 1975), and we review several meth-ods that can be applied in the optimization step, includinga standard linearization procedure (Fortet 1959) and moreelaborate convex quadratic reformulations, as in (Billionnetand Elloumi 2007; Billionnet, Elloumi, and Lambert 2012,2016; Elloumi, Lambert, and Lazare 2021). We discuss theimpact of the reformulation scheme on the efficiency of theoptimization step and we illustrate our discussion with somecomputational results on different classes of instances.
Reversible logic is of increasing importance to many future computer technologies. We introduce a regular structure to realize symmetric functions in binary reversible logic. This structure, called a 2*2 net structure, allows for a more efficient realization of symmetric functions than the methods introduced by the other authors. Our synthesis method allows us to realize arbitrary symmetric function in a completely regular structure of reversible gates with relatively little "garbage". Because every Boolean function can be made symmetric by repeating input variables, our method is applicable to arbitrary multi-input multi-output Boolean functions and realizes such arbitrary function in a circuit with a relatively small number of additional gate outputs. The method can also be used in classical logic. Its advantages in terms of numbers of gates and inputs/outputs are especially seen for symmetric or incompletely specified functions with many outputs.
Mapping functions on bits to Hamiltonians acting on qubits has many applications in quantum computing. In particular, Hamiltonians representing Boolean functions are required for applications of quantum annealing or the quantum approximate optimization algorithm to combinatorial optimization problems. We show how such functions are naturally represented by Hamiltonians given as sums of Pauli Z operators (Ising spin operators) with the terms of the sum corresponding to the function’s Fourier expansion. For many classes of Boolean functions which are given by a compact description, such as a Boolean formula in conjunctive normal form that gives an instance of the satisfiability problem, it is #P-hard to compute its Hamiltonian representation, i.e., as hard as computing its number of satisfying assignments. On the other hand, no such difficulty exists generally for constructing Hamiltonians representing a real function such as a sum of local Boolean clauses each acting on a fixed number of bits as is common in constraint satisfaction problems. We show composition rules for explicitly constructing Hamiltonians representing a wide variety of Boolean and real functions by combining Hamiltonians representing simpler clauses as building blocks, which are particularly suitable for direct implementation as classical software. We further apply our results to the construction of controlled-unitary operators, and to the special case of operators that compute function values in an ancilla qubit register. Finally, we outline several additional applications and extensions of our results to quantum algorithms for optimization. A goal of this work is to provide a design toolkit for quantum optimization which may be utilized by experts and practitioners alike in the construction and analysis of new quantum algorithms, and at the same time to provide a unified framework for the various constructions appearing in the literature.