We address the problem of computing the COMPARISON and ADDITION functions of two n-bit numbers using circuits of (nonmonotone) MAJORITY gates. Given n Boolean variables sl,. . . ,2;, E { -1, l}, a non-monotone MAJORITY gate (in the va.riables 2,) is a Boolean function whose value is the sign of E~z;, where each E, is either 1 or -1. We construct a.n explicit sparse polynomial whose sign computes the COMPAR,ISON function of two integers. Similar polynomials are constructed for computing all the bits of the summation of the two integers. This supplies explicit constructions of depth-2 polynomial-size circuits computing these functions, which use only non-monotone MAJORITY gates. These constructions are optimal in terms of the depth and can be used to obtain the best known explicit constructions of MAJORITY circuits for other functions like the product of two n-bit numbers and the maximum of n n-bit numbers (see [3] and [SI). A crucial ingredient in our a.pproach is the construction of a discrete version of a sparse polynomial-one that has a, large absolute value for a single a.ssignment and extremely small absolute values for all other assignments. We construct sparse delta polynomials using generator matrices of certain linear block codes. In the rest of this summa.ry we sketch the ideas rehted to the construction for the COMPARISON function. More details a.nd related results appea.r in [I].
We address the problem of computing the COMPARISON and ADDITION functions of two n-bit numbers using circuits of (nonmonotone) MAJORITY gates. Given n Boolean variables sl,. . . ,2;, E { -1, l}, a non-monotone MAJORITY gate (in the va.riables 2,) is a Boolean function whose value is the sign of E~z;, where each E, is either 1 or -1. We construct a.n explicit sparse polynomial whose sign computes the COMPAR,ISON function of two integers. Similar polynomials are constructed for computing all the bits of the summation of the two integers. This supplies explicit constructions of depth-2 polynomial-size circuits computing these functions, which use only non-monotone MAJORITY gates. These constructions are optimal in terms of the depth and can be used to obtain the best known explicit constructions of MAJORITY circuits for other functions like the product of two n-bit numbers and the maximum of n n-bit numbers (see [3] and [SI). A crucial ingredient in our a.pproach is the construction of a discrete version of a sparse polynomial-one that has a, large absolute value for a single a.ssignment and extremely small absolute values for all other assignments. We construct sparse delta polynomials using generator matrices of certain linear block codes. In the rest of this summa.ry we sketch the ideas rehted to the construction for the COMPARISON function. More details a.nd related results appea.r in [I].
A polynomial threshold function (PTF) is defined as the sign of a polynomial p : {0,1}^n ->R. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth. - Satisfiability (#SAT). We give the first zero-error randomized algorithm faster than exhaustive search that counts the number of satisfying assignments of a given constant-depth circuit with a super-linear number of wires whose gates are s-sparse PTFs, for s almost quadratic in the input size of the circuit; here a PTF is called s-sparse if its underlying polynomial has at most s monomials. More specifically, we show that, for any large enough constant c, given a depth-d circuit with (n^{2-1/c})-sparse PTF gates that has at most n^{1+epsilon_d} wires, where epsilon_d depends only on c and d, the number of satisfying assignments of the circuit can be computed in randomized time 2^{n-n^{epsilon_d}} with zero error. This generalizes the result by Chen, Santhanam and Srinivasan (CCC, 2016) who gave a SAT algorithm for constant-depth circuits of super-linear wire complexity with linear threshold function (LTF) gates only. - Quantified derandomization. The quantified derandomization problem, introduced by Goldreich and Wigderson (STOC, 2014), asks to compute the majority value of a given Boolean circuit, under the promise that the minority-value inputs to the circuit are very few. We give a quantified derandomization algorithm for constant-depth PTF circuits with a super-linear number of wires that runs in quasi-polynomial time. More specifically, we show that for any sufficiently large constant c, there is an algorithm that, given a degree-Delta PTF circuit C of depth d with n^{1+1/c^d} wires such that C has at most 2^{n^{1-1/c}} minority-value inputs, runs in quasi-polynomial time exp ((log n)^{O (Delta^2)}) and determines the majority value of C. (We obtain a similar quantified derandomization result for PTF circuits with n^{Delta}-sparse PTF gates.) This extends the recent result of Tell (STOC, 2018) for constant-depth LTF circuits of super-linear wire complexity. - Pseudorandom generators. We show how the classical Nisan-Wigderson (NW) generator (JCSS, 1994) yields a nontrivial pseudorandom generator for PTF circuits (of unrestricted depth) with sub-linearly many gates. As a corollary, we get a PRG for degree-Delta PTFs with the seed length exp (sqrt{Delta * log n})* log^2(1/epsilon).
A linear circuit for computing an N × N matrix M is a circuit with N inputs corresponding to the entries of a vector x and N outputs corresponding to the entries of the transformed vector Mx, and where each gate computes a linear combination of its inputs. Each gate may have unbounded fan-in, and the size of the circuit is the number of wires. This model captures most known algorithms for computing linear transforms, and (in the constant-depth or 'synchronous' settings) is equivalent to factoring M as the product of sparse matrices. We give new, smaller constructions of constant-depth linear circuits for computing any matrix which is the Kronecker power of a fixed matrix. A standard argument (e.g., the mixed product property of Kronecker products, or a generalization of the Fast Walsh-Hadamard transform) shows that any such N × N matrix has a depth-2 circuit of size O(N1.5). We improve on this for all such matrices, and especially for some such matrices of particular interest: • For any integer q > 1 and any matrix which is the Kronecker power of a fixed q × q matrix, we construct a depth-2 circuit of size O(N1.5-aq), where aq > 0 is a positive constant depending only on q. No bound beating size O(N1.5) was previously known for any q > 2. • For the case q = 2, i.e., for any matrix which is the Kronecker power of a fixed 2 × 2 matrix, we construct a depth-2 circuit of size O(N1.446), improving the prior best size O(N1.493) [Alman, 2021]. • For the Walsh-Hadamard transform, we construct a depth-2 circuit of size O(N1.443), improving the prior best size O(N1.476) [Alman, 2021]. • For the disjointness matrix (the communication matrix of set disjointness, or equivalently, the matrix for the linear transform that evaluates a multilinear polynomial on all 0/1 inputs), we construct a depth-2 circuit of size O(N1.258), improving the prior best size O(N1.272) [Jukna and Sergeev, 2013]. Our constructions also generalize to improving the standard construction for any depth ≤ O (log N). Our main technical tool is an improved way to convert a nontrivial circuit for any matrix into a circuit for its Kronecker powers. Our new bounds provably could not be achieved using the approaches of prior work.
The class ACC⁰ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with AND, NOT and MOD_m gates, where m is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that MAJORITY does not belong to ACC⁰. A few years ago, Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach towards this conjecture. Torus polynomials approximate Boolean functions when the fractional part of their value on Boolean points is close to half the value of the function. They reduced the conjecture that MAJORITY ∉ ACC⁰ to a conjecture concerning the non-existence of low degree torus polynomials that approximate MAJORITY. We reduce the non-existence problem further, to a statement about finding feasible solutions for an infinite family of linear programs. The main advantage of this statement is that it allows for incremental progress, which means finding feasible solutions for successively larger collections of these programs. As an immediate first step, we find feasible solutions for a large class of these linear programs, leaving only a finite set for further consideration. Our method is inspired by the method of dual polynomials, which is used to study the approximate degree of Boolean functions. Using our method, we also propose a way to progress further. We prove several additional key results with the same method, which include: - A lower bound on the degree of symmetric torus polynomials that approximate the AND function. As a consequence, we get a separation that symmetric torus polynomials are weaker than their asymmetric counterparts. - An error-degree trade-off for symmetric torus polynomials approximating the MAJORITY function, strengthening the corresponding result of Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019). - The first lower bounds against torus polynomials approximating AND, showcasing the power of the machinery we develop. This lower bound nearly matches the corresponding upper bound. Hence, we get an almost complete characterization of the torus polynomial approximation degree of AND. - Lower bounds against asymmetric torus polynomials approximating MAJORITY, or AND, in the very low error regime. This partially answers a question posed in Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) about error-reduction for torus polynomials.
Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.
In this work, we prove the strongest known lower bounds for QAC0, allowing polynomially many gates and ancillae. Our main results show that:
(1) Depth-3 QAC0 circuits cannot compute PARITY, and require Ω(exp(n)) gates to compute MAJORITY.
(2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size.
We develop new classical simulation techniques for QAC0 to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth 2 approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC0 circuits, which can compute PARITY exactly in depth 2 (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth 2 QAC0 circuits, regardless of size, cannot exactly synthesize an n-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 2 exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems