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

Quantum Information and Computation

Rational approximations and quantum algorithms with postselection

Urmila Mahadev, Ronald de Wolf

Published Mar 1, 2015• 9 citations
Publisher

Abstract

We study the close connection between rational functions that approximate a given Boolean function, and quantum algorithms that compute the same function using postselection. We show that the minimal degree of the former equals (up to a factor of 2) the minimal query complexity of the latter. We give optimal (up to constant factors) quantum algorithms with postselection for the Majority function, slightly improving upon an earlier algorithm of Aaronson. Finally we show how Newman's classic theorem about low-degree rational approximation of the absolute-value function follows from these algorithms.

DOI
10.26421/qic15.3-4-5

Related papers

Rational approximations and quantum algorithms with postselection

Urmila Mahadev, Ronald de Wolf

We study the close connection between rational functions that approximate a given Boolean function, and quantum algorithms that compute the same function using postselection. We show that the minimal degree of the former equals (up to a factor of 2) the minimal query complexity of the latter. We give optimal (up to constant factors) quantum algorithms with postselection for the Majority function, slightly improving upon an earlier algorithm of Aaronson. Finally we show how Newman's classic theorem about low-degree rational approximation of the absolute-value function follows from these algorithms.

arXiv:1401.0912•Jan 5, 2014•4 citations

Post-selected Classical Query Complexity

Chris Cade

We study classical query algorithms with post-selection, and find that they are closely connected to rational functions with nonnegative coefficients. We show that the post-selected classical query complexity of a Boolean function is equal to the minimal degree of a rational function with nonnegative coefficients that approximates it (up to a factor of two). For post-selected quantum query algorithms, a similar relationship was shown by Mahadev and de Wolf, where the rational approximations are allowed to have negative coefficients. Using our characterisation, we find an exponentially large separation between post-selected classical query complexity and post-selected quantum query complexity, by proving a lower bound on the degree of rational approximations (with nonnegative coefficients) to the Majority function. This lower bound can be generalised to arbitrary symmetric functions, and allows us to find an unbounded separation between non-deterministic quantum and post-selected classical query complexity. All lower bounds carry over into the communication complexity setting. We show that the zero-error variants of post-selected query algorithms are equivalent to non-deterministic classical query algorithms, which in turn are characterised by nonnegative polynomials, and for some problems require exponentially more queries to the input than their bounded-error counterparts. Finally, we describe a post-selected query algorithm for approximating the Majority function, and an efficient query algorithm for approximate counting.

arXiv:1804.10010•Apr 26, 2018•1 citation

The quantum query complexity of approximating the median and related statistics

Ashwin Nayak, Felix Wu

Let X = (z,, , z,-,) be a sequence of n numbers.For 6 > 0, we say that 5; is an e-approximate median if the number of elements strictly less than zi and the number of elements strictly greater than zi are each less than (1 + 6):.We consider the quantum query complexity of computing an c-approximate median, given the sequence X as an oracle.We prove a lower bound of n(min{t,n}) queries for any quantum algorithm that computes an r-approximate median with any constant probability greater than l/2.We also show how an c-approximate median may be computed with 0( $ log(t) log log( $)) oracle queries, which rep resents an improvement over an earlier algorithm due to Grover [ll, 121.Thus, the lower bound we obtain is essentially optimal.The upper and the lower bound both hold in the comparison tree model as well.Our lower bound result is an application of the polynomial paradigm recently introduced to quantum complexity theory by Be& et ol.[l].The main ingredient in the proof is a polynomial degree lower bound far real multilinear polynomials that "approximate" symmetric partial boolean functions.The degree bound extends a result of Patti[15] and also immediately yields lower bounds for the problems of approximating the kth-smallest element, approximating the mean of a sequence of numbers, and approximately counting the number of ones of a boolean function.All bounds obtained come within a polylogarithmic factor of the optimal (as we show by presenting algorithms where no such optimal or near optimal algorithms were known), thus demonstrating the power of the polynomial method.

arXiv:quant-ph/9804066•ACM Symposium on Theory of Computing (STOC)•May 1, 1999•224 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

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Scott Aaronson, Andris Ambainis, Jānis Iraids +2 more

We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.

arXiv:1511.08682•Leibniz international proceedings in informatics•Nov 27, 2015•31 citations

How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?

Andris Ambainis, Ronald de Wolf

It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n/log log n), and we exhibit quantum algorithms for two functions where this bound is achieved.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2013•2 citations
We study the close connection between rational functions that approximate a given Boolean function, and quantum algorithms that compute the same function using postselection. We show that the minimal degree of the former equals (up to a factor of 2) the minimal query complexity of the latter. We give optimal (up to constant factors) quantum algorithms with postselection for the Majority function, slightly improving upon an earlier algorithm of Aaronson. Finally we show how Newman's classic theorem about low-degree rational approximation of the absolute-value function follows from these algorithms.
We study the close connection between rational functions that approximate a given Boolean function, and quantum algorithms that compute the same function using postselection. We show that the minimal degree of the former equals (up to a factor of 2) the minimal query complexity of the latter. We give optimal (up to constant factors) quantum algorithms with postselection for the Majority function, slightly improving upon an earlier algorithm of Aaronson. Finally we show how Newman's classic theorem about low-degree rational approximation of the absolute-value function follows from these algorithms.
We study classical query algorithms with post-selection, and find that they are closely connected to rational functions with nonnegative coefficients. We show that the post-selected classical query complexity of a Boolean function is equal to the minimal degree of a rational function with nonnegative coefficients that approximates it (up to a factor of two). For post-selected quantum query algorithms, a similar relationship was shown by Mahadev and de Wolf, where the rational approximations are allowed to have negative coefficients. Using our characterisation, we find an exponentially large separation between post-selected classical query complexity and post-selected quantum query complexity, by proving a lower bound on the degree of rational approximations (with nonnegative coefficients) to the Majority function. This lower bound can be generalised to arbitrary symmetric functions, and allows us to find an unbounded separation between non-deterministic quantum and post-selected classical query complexity. All lower bounds carry over into the communication complexity setting. We show that the zero-error variants of post-selected query algorithms are equivalent to non-deterministic classical query algorithms, which in turn are characterised by nonnegative polynomials, and for some problems require exponentially more queries to the input than their bounded-error counterparts. Finally, we describe a post-selected query algorithm for approximating the Majority function, and an efficient query algorithm for approximate counting.
Let X = (z,, , z,-,) be a sequence of n numbers.For 6 > 0, we say that 5; is an e-approximate median if the number of elements strictly less than zi and the number of elements strictly greater than zi are each less than (1 + 6):.We consider the quantum query complexity of computing an c-approximate median, given the sequence X as an oracle.We prove a lower bound of n(min{t,n}) queries for any quantum algorithm that computes an r-approximate median with any constant probability greater than l/2.We also show how an c-approximate median may be computed with 0( $ log(t) log log( $)) oracle queries, which rep resents an improvement over an earlier algorithm due to Grover [ll, 121.Thus, the lower bound we obtain is essentially optimal.The upper and the lower bound both hold in the comparison tree model as well.Our lower bound result is an application of the polynomial paradigm recently introduced to quantum complexity theory by Be& et ol.[l].The main ingredient in the proof is a polynomial degree lower bound far real multilinear polynomials that "approximate" symmetric partial boolean functions.The degree bound extends a result of Patti[15] and also immediately yields lower bounds for the problems of approximating the kth-smallest element, approximating the mean of a sequence of numbers, and approximately counting the number of ones of a boolean function.All bounds obtained come within a polylogarithmic factor of the optimal (as we show by presenting algorithms where no such optimal or near optimal algorithms were known), thus demonstrating the power of the polynomial method.
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 show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.