Quantum signal processing (QSP), which is a general technique for construction of 1-qubit rotation operators, is a strong framework for quantum algorithm design. We consider a scenario of information-theoretically secure computation for QSP: n parties who have private angle parameters make the evaluator perform the QSP from the sum of their angles in a privacy-preserving manner through noninteractive communication. In this scenario, we construct a private simultaneous messages (PSM) protocol for QSP, named Private QSP (PQSP). As an application, we construct an efficient PSM protocol for symmetric Boolean functions with an evaluator of 1-qubit workspace by adapting PQSP to the 1-qubit quantum algorithm for symmetric Boolean functions of Maslov et al. [1]. We also show that the technique of PQSP works for the 1-qubit program for Boolean functions of Cosentino et al. [2]. We construct an efficient PSM protocol for Boolean functions computable by O(log n)-depth circuits with an evaluator of 1-qubit writable workspace from their 1-qubit program [3]. Such efficient PSM protocols with space-bounded classical evaluators have not been known so far.Quantum signal processing (QSP), which is a general technique for construction of 1-qubit rotation operators, is a strong framework for quantum algorithm design. We consider a scenario of information-theoretically secure computation for QSP: n parties who have private angle parameters make the evaluator perform the QSP from the sum of their angles in a privacy-preserving manner through noninteractive communication. In this scenario, we construct a private simultaneous messages (PSM) protocol for QSP, named Private QSP (PQSP). As an application, we construct an efficient PSM protocol for symmetric Boolean functions with an evaluator of 1-qubit workspace by adapting PQSP to the 1-qubit quantum algorithm for symmetric Boolean functions of Maslov et al. [1]. We also show that the technique of PQSP works for the 1-qubit program for Boolean functions of Cosentino et al. [2]. We construct an efficient PSM protocol for Boolean functions computable by O(log n)-depth circuits with an evaluator of 1-qubit writable workspace from their 1-qubit program [3]. Such efficient PSM protocols with space-bounded classical evaluators have not been known so far.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesMar 6, 20250 citations

Stochastic Diagonalization

Hans A. De Raedt, Kristel F. L. Michielsen

Springer proceedings in physicsJan 1, 19990 citations

Few-helping-card Protocols for Some Wider Class of Symmetric Boolean Functions with Arbitrary Ranges

Hayato Shikata, Daiki Miyahara, Takaaki Mizuki

In card-based cryptography, which uses a physical deck of cards to realize secure multiparty computations, a one-bit value is usually encoded by a pair of cards. Thus, when performing a secure computation of an n-input Boolean function, a sequence of 2n cards representing n bits is needed for input, and some helping cards are typically added to form a protocol. In 2020, Ruangwises and Itoh constructed a card-based protocol for a symmetric Boolean function with an arbitrary range using two helping cards. (Note that a symmetric Boolean function depends only on the number of 1s in its input). At the same time, they showed that the helping cards can be eliminated if the target function is limited to “doubly symmetric” Boolean functions (also known as symmetric self-anti-dual functions). A doubly symmetric Boolean function satisfies the following for all k: when inputting exactly a number k of 1s, the output is the same as the output when inputting exactly a number n − k of 1s. In this paper, we loosen the restriction on doubly symmetric Boolean functions by fixing k = 0, and construct new protocols which require less than two helping cards for that wider class of symmetric Boolean functions. Specifically, we design a one-helping-card protocol for any n > 4, and helping-card-free protocols for n = 3 and n = 4.In card-based cryptography, which uses a physical deck of cards to realize secure multiparty computations, a one-bit value is usually encoded by a pair of cards. Thus, when performing a secure computation of an n-input Boolean function, a sequence of 2n cards representing n bits is needed for input, and some helping cards are typically added to form a protocol. In 2020, Ruangwises and Itoh constructed a card-based protocol for a symmetric Boolean function with an arbitrary range using two helping cards. (Note that a symmetric Boolean function depends only on the number of 1s in its input). At the same time, they showed that the helping cards can be eliminated if the target function is limited to “doubly symmetric” Boolean functions (also known as symmetric self-anti-dual functions). A doubly symmetric Boolean function satisfies the following for all k: when inputting exactly a number k of 1s, the output is the same as the output when inputting exactly a number n − k of 1s. In this paper, we loosen the restriction on doubly symmetric Boolean functions by fixing k = 0, and construct new protocols which require less than two helping cards for that wider class of symmetric Boolean functions. Specifically, we design a one-helping-card protocol for any n > 4, and helping-card-free protocols for n = 3 and n = 4.

ACM ASIA Public-Key Cryptography Workshop (APKC)Jun 20, 20239 citations

Stochastic diagonalization

Hans A. De Raedt

Physics ReportsAug 1, 199352 citations

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

Richik Sengupta, Jacob Biamonte

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.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.

arXiv:2209.15009Sep 29, 20220 citations

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.