Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where depth corresponds to the number of adaptive query rounds and the computation per l...
详细信息
ISBN:
(纸本)9798400703836
Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where depth corresponds to the number of adaptive query rounds and the computation per layer corresponds to the number of parallel queries per round. We achieve the strongest known separation between quantum algorithms with r versus r-1 rounds of adaptivity. We do so by using the k-fold Forrelation problem introduced by Aaronson and Ambainis (SICOMP18). For k=2r, this problem can be solved using an r round quantum algorithm with only one query per round, yet we show that any r-1 round quantum algorithm needs an exponential (in the number of qubits) number of parallel queries per round. Our results are proven following the fourier analytic machinery developed in recent works on quantum-classical separations. The key new component in our result are bounds on the fourier weights of quantum query algorithms with bounded number of rounds of adaptivity. These may be of independent interest as they distinguish the polynomials that arise from such algorithms from arbitrary bounded polynomials of the same degree.
We prove that for every decision tree, the absolute values of the fourier coefficients of a given order l >= 1 sum to at most c(l) root((d)(l)) (1 + log n)(l-1), where n is the number of variables, d is the tree de...
详细信息
We prove that for every decision tree, the absolute values of the fourier coefficients of a given order l >= 1 sum to at most c(l) root((d)(l)) (1 + log n)(l-1), where n is the number of variables, d is the tree depth, and c > 0 is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal [Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]. The bounds prior to our work degraded rapidly with l, becoming trivial already at l = root d. As an application, we obtain, for every integer k >= 1, a partial boolean function on n bits that has bounded-error quantum query complexity at most k and randomized query complexity (Omega) over tilde (n(1) (1)(2k)). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis [SIAM J. Comput., 47 (2018), pp. 982-1038] and Bravyi et al. [Classical Algorithms for Forrelation, arXiv preprint, 2021]. Prior to our work, the best known separation was polynomially weaker: O(1) versus Omega (n(2/3-epsilon)) for any epsilon > 0 [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]. As another application, we obtain an essentially optimal separation of O(log n) versus Omega (n(1-epsilon)) for bounded-error quantum versus randomized communication complexity for any epsilon > 0. The best previous separation was polynomially weaker: O(log n) versus Omega(n(2/3-epsilon)) (this is implicit in [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]).
We prove that for every decision tree, the absolute values of the fourier coefficients of given order t >= 1 sum to at most (cd/t)(t/2)(1 + log n)((t-1)/2), where n is the number of variables, d is the tree depth, ...
详细信息
ISBN:
(纸本)9781450380539
We prove that for every decision tree, the absolute values of the fourier coefficients of given order t >= 1 sum to at most (cd/t)(t/2)(1 + log n)((t-1)/2), where n is the number of variables, d is the tree depth, and c > 0 is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal (arxiv 2019;FOCS 2020). The bounds prior to our work degraded rapidly with t, becoming trivial already at t = root d. As an application, we obtain, for every integer k >= 1, a partial boolean function on n bits that has bounded-error quantum query complexity at most inverted right perpendiculark/2inverted left perpendicular and randomized query complexity (Omega) over tilde (n(1-1/k)). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015). Prior to our work, the best known separation was polynomially weaker: O(1) versus Omega(n(2/3-epsilon)) for any epsilon > 0 (Tal, FOCS 2020). As another application, we obtain an essentially optimal separation of O(log n) versus Omega(n(1-epsilon)) for bounded-error quantum versus randomized communication complexity, for any epsilon > 0. The best previous separation was polynomially weaker: O(log n) versus Omega(n(2/3-epsilon)) (implicit in Tal, FOCS 2020).
Given a boolean function f : { -1, l}(n) -> { -1, 1}, define the fourier distribution to be the distribution on subsets of [n], where each S subset of [n] is sampled with probability (f) over cap (S)(2). The Fourie...
详细信息
ISBN:
(纸本)9783959771405
Given a boolean function f : { -1, l}(n) -> { -1, 1}, define the fourier distribution to be the distribution on subsets of [n], where each S subset of [n] is sampled with probability (f) over cap (S)(2). The fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [24] seeks to relate two fundamental measures associated with the fourier distribution: does there exist a universal constant C > 0 such that H((f) over cap (2)) <= C . Inf(f), where H((f) over cap (2)) is the Shannon entropy of the fourier distribution of f and Inf(f) is the total influence of f? In this paper we present three new contributions towards the FEI conjecture: (i) Our first contribution shows that H((f) over cap (2)) <= 2 . aUC(circle plus) (f), where aUC(circle plus) (f) is the average unambiguous parity-certificate complexity of f . This improves upon several bounds shown by Chakraborty et al. [16]. We further improve this bound for unambiguous DNFs. (ii) We next consider the weaker fourier Min-entropy-Influence (FMEI) conjecture posed by O'Donnell and others [43, 40] which asks if H-infinity ((f) over cap (2)) <= C . lnf(f), where H-infinity ((f) over cap (2)) is the min-entropy of the fourier distribution. We show H-infinity ((f) over cap (2)) <= 2 . C-min(circle plus)(f), where C-min(circle plus )(f) is the minimum parity certificate complexity of f. We also show that for all epsilon >= 0, we have H-infinity ((f) over cap (2)) <= 2log(parallel to(f) over cap parallel to(1,epsilon) 1(1 - epsilon)) , where parallel to(f) over cap parallel to(1,epsilon )is the approximate spectral norm of f. As a corollary, we verify the FMEI conjecture for the class of read-k DNFs (for constant k). (iii) Our third contribution is to better understand implications of the FEI conjecture for the structure of polynomials that 1/3-approximate a boolean function on the boolean cube. We pose a conjecture: no flat polynomial (whose non-zero fourier coefficients have the same magnitude) of degree d and spars
Given a boolean function f : {-1.1}(n) {-1, 1), define the fourier distribution to be the distribution on subsets of [n], where each S subset of [n] is sampled with probability (f) over cap (S)(2). The fourier Entropy...
详细信息
Given a boolean function f : {-1.1}(n) {-1, 1), define the fourier distribution to be the distribution on subsets of [n], where each S subset of [n] is sampled with probability (f) over cap (S)(2). The fourier Entropy-influence (FEI) conjecture of Friedgut and Kalai [28] seeks to relate two fundamental measures associated with the fourier distribution: does there exist a universal constant C > 0 such that H((f) over cap (2)) <= C . Inf(f ), where H((f) over cap (2)) is the Shannon entropy of the fourier distribution of f and Inf(f) is the total influence of f? In this article, we present three new contributions toward the FEI conjecture: (1) Our first contribution shows that H((f) over cap (2)) <= 2 . aUC(circle plus)(f), where aUC(circle plus)(f) is the average unambiguous parity-certificate complexity off. This improves upon several bounds shown by Chakraborty et al. [20]. We further improve this bound for unambiguous DNFs. We also discuss how our work makes Mansour's conjecture for DNFs a natural next step toward resolution of the FEI conjecture. (2) We next consider the weaker fourier Min-entropy-influence (FMEI) conjecture posed by O'Donnell and others [50, 53], which asks if H-infinity((f) over cap (2)) <= C . Inf(f ), where H-infinity((f) over cap (2)) is the min-entropy of the fourier distribution. We show H-infinity((f) over cap (2)) <= 2 . C-min(circle plus) (f), where C-min(circle plus) (f ) is the minimum parity-certificate complexity of f. We also show that for all epsilon >= 0, we have H-infinity((f) over cap (2)) <= 2 log(parallel to(f) over cap parallel to(1,epsilon)/(1-epsilon)), where parallel to(f) over cap parallel to(1,epsilon) is the approximate spectral norm of f . As a corollary, we verify the FMEI conjecture for the class of read-k DN Fs (for constant k). (3) Our third contribution is to better understand implications of the FEI conjecture for the structure of polynomials that 1/3-approximate a boolean function on the boolean cube. We pose a
For a class F of formulas (general de Morgan or read-once de Morgan), the shrinkage exponent Gamma(F) is the parameter measuring the reduction in size of a formula F is an element of F after F is hit with a random res...
详细信息
For a class F of formulas (general de Morgan or read-once de Morgan), the shrinkage exponent Gamma(F) is the parameter measuring the reduction in size of a formula F is an element of F after F is hit with a random restriction. A boolean function f:{0,1}(n) -> {1,-1} is fourier-concentrated if, when viewed in the fourier basis, f has most of its total mass on "low-degree" coefficients. We show a direct connection between the two notions by proving that shrinkage implies fourier concentration: For a shrinkage exponent Gamma(F), a formula F is an element of F of size s will have most of its fourier mass on the coefficients of degree up to about s(F)(1/Gamma). More precisely, for a boolean function f:{0,1}(n) -> {1,-1} computable by a formula of (large enough) size s and for any parameter r > 0, Sigma(A subset of[n] :) (1/Gamma)(vertical bar A vertical bar >= s).r (f) over cap (A)(2) <= s . polylog(s) . exp(-r(Gamma/Gamma-1)/S-o(1)), where G is the shrinkage exponent for the corresponding class of formulas: Gamma=2 for de Morgan formulas, and Gamma=1/log(2)(root 5 - 1) approximate to 3.27 for read-once de Morgan formulas. This fourier concentration result is optimal, to within the o(1) term in the exponent of s. As a standard application of these fourier concentration results, we get that subquadratic-size de Morgan formulas have negligible correlation with parity. We also show the tight Theta(s(1/Gamma)) bound on the average sensitivity of read-once formulas of size s, which mirrors the known tight bound Theta(root s) on the average sensitivity of general de Morgan s-size formulas.
In a very strong positive result for passive learning algorithms, Bshouty et al. showed that DNF expressions are efficiently learnable in the uniform random walk model. It is natural to ask whether the more expressive...
详细信息
In a very strong positive result for passive learning algorithms, Bshouty et al. showed that DNF expressions are efficiently learnable in the uniform random walk model. It is natural to ask whether the more expressive class of thresholds of parities (TOP) can also be learned efficiently in this model, since both DNF and TOP are efficiently uniform-learnable from queries. However, the time bounds of the algorithms of Bshouty et al. are exponential for TOP. We present a new approach to weak parity learning that leads to quasi-efficient uniform random walk learnability of TOP. We also introduce a more general random walk model and give two positive results in this new model: DNF is efficiently learnable and juntas are efficiently agnostically learnable.
In a very strong positive result for passive learning algorithms, Bshouty et al. showed that DNF expressions are efficiently learnable in the uniform random walk model. It is natural to ask whether the more expressive...
详细信息
In a very strong positive result for passive learning algorithms, Bshouty et al. showed that DNF expressions are efficiently learnable in the uniform random walk model. It is natural to ask whether the more expressive class of thresholds of parities (TOP) can also be learned efficiently in this model, since both DNF and TOP are efficiently uniform-learnable from queries. However, the time bounds of the algorithms of Bshouty et al. are exponential for TOP. We present a new approach to weak parity learning that leads to quasi-efficient uniform random walk learnability of TOP. We also introduce a more general random walk model and give two positive results in this new model: DNF is efficiently learnable and juntas are efficiently agnostically learnable.
暂无评论