Watrous conjectured that the randomized and quantum query complexities of symmetric functions are polynomially equivalent, which was resolved by Aaronson & Ambainis (2014) and was later improved by Chailloux (2019) and Ben-David et al. (2020). This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="37_2025_263_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="26" /> </InlineMediaObject> <EquationSource Format="TEX">$1/2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. Our contributions include the following:<OrderedList> <ListItem> <ItemNumber>1.</ItemNumber> <ItemContent> We analyze the optimal success probabilities of quantum and randomized query algorithms of two fundamental partial symmetric Boolean functions given a fixed number of queries. </ItemContent> </ListItem> <ListItem> <ItemNumber>2.</ItemNumber> <ItemContent> We establish that for any total symmetric Boolean function <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="37_2025_263_Article_IEq10.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">$f$</EquationSource> <EquationSource Format="MATHML"><math> <mi>f</mi> </math></EquationSource> </InlineEquation>, if a quantum algorithm uses <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="37_2025_263_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$T$</EquationSource> <EquationSource Format="MATHML"><math> <mi>T</mi> </math></EquationSource> </InlineEquation> queries to compute <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="37_2025_263_Article_IEq10.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">$f$</EquationSource> <EquationSource Format="MATHML"><math> <mi>f</mi> </math></EquationSource> </InlineEquation> with success probability <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="37_2025_263_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">$1/2+\beta$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> <mo>+</mo> <mi>β</mi> </mrow> </math></EquationSource> </InlineEquation>, then there exists a randomized algorithm using <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="37_2025_263_Article_IEq5.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">$O(T^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>T</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> queries to compute <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="37_2025_263_Article_IEq10.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">$f$</EquationSource> <EquationSource Format="MATHML"><math> <mi>f</mi> </math></EquationSource> </InlineEquation> with success probability <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="37_2025_263_Article_IEq7.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="82" /> </InlineMediaObject> <EquationSource Format="TEX">$1/2+\Omega{\delta\beta^2}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> <mo>+</mo> <mi mathvariant="normal">Ω</mi> <mrow> <mi>δ</mi> <msup> <mi>β</mi> <mn>2</mn> </msup> </mrow> </mrow> </math></EquationSource> </InlineEquation> on a <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="37_2025_263_Article_IEq8.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">$1-\delta$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>-</mo> <mi>δ</mi> </mrow> </math></EquationSource> </InlineEquation> fraction of inputs, where <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="37_2025_263_Article_IEq9.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">$\beta,\delta$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>β</mi> <mo>,</mo> <mi>δ</mi> </mrow> </math></EquationSource> </InlineEquation> can be arbitrarily small positive values. Moreover, we prove a randomized version of Aaronson-Ambainis Conjecture (Aaronson & Ambainis 2014) for symmetric Boolean functions in the regime where the success probability of algorithms can be arbitrarily close to 1/2. </ItemContent> </ListItem> <ListItem> <ItemNumber>3.</ItemNumber> <ItemContent> We present tight polynomial equivalence for several fundamental complexity measures of partial symmetric Boolean functions. </ItemContent> </ListItem> </OrderedList>

On the Fine-Grained Query Complexity of Symmetric Functions

期刊论文
发表日期：

2025年2月6日

查看全文

Supartha Podder,
Penghui Yao,
Zekun Ye

摘要

Watrous conjectured that the randomized and quantum query complexities of symmetric functions are polynomially equivalent, which was resolved by Aaronson & Ambainis (2014) and was later improved by Chailloux (2019) and Ben-David et al. (2020). This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to $1/2$ $1 / 2$ . Our contributions include the following: 1.

We analyze the optimal success probabilities of quantum and randomized query algorithms of two fundamental partial symmetric Boolean functions given a fixed number of queries.

We establish that for any total symmetric Boolean function $f$ $f$ , if a quantum algorithm uses $T$ $T$ queries to compute $f$ $f$ with success probability $1/2+\beta$ $1 / 2 + β$ , then there exists a randomized algorithm using $O(T^2)$ $O (T^{2})$ queries to compute $f$ $f$ with success probability $1/2+\Omega{\delta\beta^2}$ $1 / 2 + Ω δ β^{2}$ on a $1-\delta$ $1 - δ$ fraction of inputs, where $\beta,\delta$ $β, δ$ can be arbitrarily small positive values. Moreover, we prove a randomized version of Aaronson-Ambainis Conjecture (Aaronson & Ambainis 2014) for symmetric Boolean functions in the regime where the success probability of algorithms can be arbitrarily close to 1/2.

We present tight polynomial equivalence for several fundamental complexity measures of partial symmetric Boolean functions.