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:1709.08985 · ACM Transactions on Computation Theory

All Classical Adversary Methods Are Equivalent for Total Functions

Andris Ambainis, Martins Kokainis, Krišjānis Prūsis, Jevgēnijs Vihrovs, Aleksejs Zajakins

Published Jan 28, 2021• 0 citations
arXivHTMLPDF

Abstract

We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions and are equal to the fractional block sensitivity fbs( f ). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. This equivalence also implies that for total functions, the relational adversary is equivalent to a simpler lower bound, which we call rank-1 relational adversary. For partial functions, we show unbounded separations between fbs( f ) and other adversary bounds, as well as between the adversary bounds themselves. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than √ n ⋅ bs( f ), where n is the number of variables and bs( f ) is the block sensitivity. Then, we exhibit a partial function f that matches this upper bound, fbs( f ) = Ω (√ n ⋅ bs( f )).

DOI
10.1145/3442357

Related papers

On Fractional Block Sensitivity.

Raghav Kulkarni, Avishay Tal

In this paper we study the fractional block sensitivity of Boolean functions. Recently, Tal [Tal13] and Gilmer, Saks, and Srinivasan [GSS13] independently introduced this complexity measure, denoted by fbs(f), and showed that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by RC(f), which was introduced by Aaronson [Aar03]. In this paper, we relate the fractional block sensitivity to other complexity measures such as sensitivity s(f) and approximate degree deg(f). As a consequence we obtain the following results: 1. We show that deg(f) = Ω( √ RC(f)), solving an open question posed by Aaronson [Aar03]. This also implies that deg(f) = Ω(QC(f)), where QC(f) is the quantum certificate complexity of f. As both deg(f) and QC(f) serve as lower bounds for the bounded error quantum query complexity, this shows that deg(f) is always a tighter lower bound compared to QC(f). 2. (a) We show that every transitive function on n variables must have RC(f) = Ω(n), QC(f) = Ω(n) and deg(f) = Ω(n), and note that all these bounds are tight. This is a strengthening of the previous lower bounds given by [SYZ04] and [Sun07]. (b) We show that Chakraborty’s [Cha11] example of a transitive function with s(f) = O(n) is optimal unless there is better than quadratic separation between the block sensitivity and the sensitivity. 3. Using fractional block sensitivity, we show that the zero error randomized decision tree complexity, R0(f), is upper bounded by O(R2(f) 2 · logR2(f)) where R2(f) is the two-sided bounded error randomized decision tree complexity of f . This improves the previous best relation between these two complexity measures given by Midrijanis [Mid05] of R0(f) = O(R2(f) 2 · log n) (where n is the number of variables). 4. We show that the (non-negative weight) adversary methods to lower bound the bounded error quantum query complexity of f can not give better bounds than √ RC(f)RC(f). This refines the earlier bound of √ C0(f)C1(f) by Spalek and Szegedy [SS06] and strengthens the so called certificate complexity barrier to its randomized analogue. ∗Centre for Quantum Technologies, Singapore Email: kulraghav@gmail.com †The Weizmann Institute of Science, Rehovot, Israel. Email: avishay.tal@weizmann.ac.il. Research supported by an Adams Fellowship of the Israel Academy of Sciences and Humanities, by an Israel Science Foundation grant and by the Israeli Centers of Research Excellence (I-CORE) program. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Revision 1 of Report No. 168 (2013)

Chicago Journal of Theoretical Computer Science•Jan 1, 2013•5 citations

Lower bounds on quantum query complexity for symmetric functions

Rajat Mittal, Sanjay S Nair, Sunayana Patro

One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.

•Oct 25, 2021•0 citations

On Query-To-Communication Lifting for Adversary Bounds

Anurag Anshu, Shalev Ben-David, Srijita Kundu

We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1) We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2) Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3) Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.

•Dec 7, 2020•1 citation

On Query-To-Communication Lifting for Adversary Bounds

Anshu, Anurag, Shalev Ben-David, Srijita Kundu

We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1) We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2) Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3) Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.

arXiv:2012.03415•Leibniz international proceedings in informatics•Dec 7, 2020•0 citations

An adversary for algorithms

Troy Lee, Rajat Mittal, Ben W. Reichardt +1 more

The general adversary bound is a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. It is known to be tight up to constant factors for functions (total or partial) with boolean output and binary input alphabet. We show that the general adversary bound is tight for any function whatsoever, with potentially non-boolean input or output alphabets. We also show that quantum query complexity exhibits a remarkable composition property: Q ( f(g(x), . . . , g(x)) ) = O ( Q(f)Q(g) ) for any compatible functions f, g. This was previously known only in the boolean case. Both of these results are obtained by defining a new, but closely related, semi-definite program that we call the witness size. The minimization formulation of the witness size adds constraints compared with the general adversary bound to enable dual solutions to correspond to eigenvalue-zero eigenvectors of certain graphs. While the witness size can be strictly larger than the adversary bound, we show that it can be at most a factor of two larger.

•Nov 12, 2010•7 citations

On Block Sensitivity and Fractional Block Sensitivity

Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs

We investigate the relation between the block sensitivity $\text{bs}(f)$ and fractional block sensitivity $\text{fbs}(f)$ complexity measures of Boolean functions. While it is known that $\text{fbs}(f) = O(\text{bs}(f)^2)$, the best known separation achieves $\text{fbs}(f) = \left(\frac{1}{3\sqrt2} +o(1)\right) \text{bs(f)}^{3/2}$. We improve the constant factor and show a family of functions that give $\text{fbs}(f) = \left(\frac{1}{\sqrt6}-o(1)\right) \text{bs}(f)^{3/2}.$

arXiv:1810.02393•Oct 4, 2018•0 citations
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions and are equal to the fractional block sensitivity fbs( f ). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. This equivalence also implies that for total functions, the relational adversary is equivalent to a simpler lower bound, which we call rank-1 relational adversary. For partial functions, we show unbounded separations between fbs( f ) and other adversary bounds, as well as between the adversary bounds themselves. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than √ n ⋅ bs( f ), where n is the number of variables and bs( f ) is the block sensitivity. Then, we exhibit a partial function f that matches this upper bound, fbs( f ) = Ω (√ n ⋅ bs( f )).
In this paper we study the fractional block sensitivity of Boolean functions. Recently, Tal [Tal13] and Gilmer, Saks, and Srinivasan [GSS13] independently introduced this complexity measure, denoted by fbs(f), and showed that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by RC(f), which was introduced by Aaronson [Aar03]. In this paper, we relate the fractional block sensitivity to other complexity measures such as sensitivity s(f) and approximate degree deg(f). As a consequence we obtain the following results: 1. We show that deg(f) = Ω( √ RC(f)), solving an open question posed by Aaronson [Aar03]. This also implies that deg(f) = Ω(QC(f)), where QC(f) is the quantum certificate complexity of f. As both deg(f) and QC(f) serve as lower bounds for the bounded error quantum query complexity, this shows that deg(f) is always a tighter lower bound compared to QC(f). 2. (a) We show that every transitive function on n variables must have RC(f) = Ω(n), QC(f) = Ω(n) and deg(f) = Ω(n), and note that all these bounds are tight. This is a strengthening of the previous lower bounds given by [SYZ04] and [Sun07]. (b) We show that Chakraborty’s [Cha11] example of a transitive function with s(f) = O(n) is optimal unless there is better than quadratic separation between the block sensitivity and the sensitivity. 3. Using fractional block sensitivity, we show that the zero error randomized decision tree complexity, R0(f), is upper bounded by O(R2(f) 2 · logR2(f)) where R2(f) is the two-sided bounded error randomized decision tree complexity of f . This improves the previous best relation between these two complexity measures given by Midrijanis [Mid05] of R0(f) = O(R2(f) 2 · log n) (where n is the number of variables). 4. We show that the (non-negative weight) adversary methods to lower bound the bounded error quantum query complexity of f can not give better bounds than √ RC(f)RC(f). This refines the earlier bound of √ C0(f)C1(f) by Spalek and Szegedy [SS06] and strengthens the so called certificate complexity barrier to its randomized analogue. ∗Centre for Quantum Technologies, Singapore Email: kulraghav@gmail.com †The Weizmann Institute of Science, Rehovot, Israel. Email: avishay.tal@weizmann.ac.il. Research supported by an Adams Fellowship of the Israel Academy of Sciences and Humanities, by an Israel Science Foundation grant and by the Israeli Centers of Research Excellence (I-CORE) program. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Revision 1 of Report No. 168 (2013)
One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1) We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2) Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3) Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1) We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2) Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3) Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.
The general adversary bound is a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. It is known to be tight up to constant factors for functions (total or partial) with boolean output and binary input alphabet. We show that the general adversary bound is tight for any function whatsoever, with potentially non-boolean input or output alphabets. We also show that quantum query complexity exhibits a remarkable composition property: Q ( f(g(x), . . . , g(x)) ) = O ( Q(f)Q(g) ) for any compatible functions f, g. This was previously known only in the boolean case. Both of these results are obtained by defining a new, but closely related, semi-definite program that we call the witness size. The minimization formulation of the witness size adds constraints compared with the general adversary bound to enable dual solutions to correspond to eigenvalue-zero eigenvectors of certain graphs. While the witness size can be strictly larger than the adversary bound, we show that it can be at most a factor of two larger.
We investigate the relation between the block sensitivity bs(f)\text{bs}(f)bs(f) and fractional block sensitivity fbs(f)\text{fbs}(f)fbs(f) complexity measures of Boolean functions. While it is known that fbs(f)=O(bs(f)2)\text{fbs}(f) = O(\text{bs}(f)^2)fbs(f)=O(bs(f)2), the best known separation achieves fbs(f)=(132+o(1))bs(f)3/2\text{fbs}(f) = \left(\frac{1}{3\sqrt2} +o(1)\right) \text{bs(f)}^{3/2}fbs(f)=(32​1​+o(1))bs(f)3/2. We improve the constant factor and show a family of functions that give fbs(f)=(16−o(1))bs(f)3/2.\text{fbs}(f) = \left(\frac{1}{\sqrt6}-o(1)\right) \text{bs}(f)^{3/2}.fbs(f)=(6​1​−o(1))bs(f)3/2.