<p>In quantum computing theory, the well-known Deutsch’s problem and Deutsch–Jozsa problem can be equivalent to symmetric Boolean functions. Meanwhile, sensitivity of Boolean functions is a quite important complexity measure in the query model. So far, whether symmetry means high-sensitivity problems is still considered as a challenge. In symmetric setting, based on whether all inputs in <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11128_2025_4714_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">$\{0,1\}^{n}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> <mi>n</mi> </msup> </math></EquationSource> </InlineEquation> are defined, this paper investigates sensitivity of total and partial Boolean functions, respectively. Firstly, we point out that the computation of sensitivity requires at most <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11128_2025_4714_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">$n+1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> classical queries or <i>n</i> quantum queries. Secondly, we show that the lower bound of sensitivity is not less than <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11128_2025_4714_Article_IEq3.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="10" /> </InlineMediaObject> <EquationSource Format="TEX">$\frac{n}{2}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> </math></EquationSource> </InlineEquation> except for the sensitivity 0. Finally, we discover and prove some non-trivial bounds on the number of symmetric (total and partial) Boolean functions with each possible sensitivity.</p>

Sensitivity of symmetric Boolean functions

期刊论文
发表日期：

2025年3月24日

查看全文

Guoliang Xu,
Mengsi Zhang,
Binbin Zhang,
Tianyin Wang,
Yumei Zhang

摘要

In quantum computing theory, the well-known Deutsch’s problem and Deutsch–Jozsa problem can be equivalent to symmetric Boolean functions. Meanwhile, sensitivity of Boolean functions is a quite important complexity measure in the query model. So far, whether symmetry means high-sensitivity problems is still considered as a challenge. In symmetric setting, based on whether all inputs in $\{0,1\}^{n}$ ${0, 1}^{n}$ are defined, this paper investigates sensitivity of total and partial Boolean functions, respectively. Firstly, we point out that the computation of sensitivity requires at most $n+1$ $n + 1$ classical queries or n quantum queries. Secondly, we show that the lower bound of sensitivity is not less than $\frac{n}{2}$ $\frac{n}{2}$ except for the sensitivity 0. Finally, we discover and prove some non-trivial bounds on the number of symmetric (total and partial) Boolean functions with each possible sensitivity.