Suguru Tamaki

It is known that several sub-universal quantum computing models, such as the IQP model, the Boson sampling model, the one-clean qubit model, and the random circuit model, cannot be classically simulated in polynomial time under certain conjectures in classical complexity theory. Recently, these results have been improved to ``fine-grained" versions where even exponential-time classical simulations are excluded assuming certain classical fine-grained complexity conjectures. All these fine-grained results are, however, about the hardness of strong simulations or multiplicative-error sampling. It was open whether any fine-grained quantum supremacy result can be shown for a more realistic setup, namely, additive-error sampling. In this paper, we show the additive-error fine-grained quantum supremacy (under certain complexity assumptions). As examples, we consider the IQP model, a mixture of the IQP model and log-depth Boolean circuits, and Clifford+<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math> circuits. Similar results should hold for other sub-universal models.

A Boolean function f : {0, 1}n → {0, 1} is weighted symmetric if there exist a function g : ℤ → {0, 1} and integers w0,w1, . . . ,wn such that f(x1, . . . , xn) = g(w0 + ∑n i=1 wixi) holds. In this paper, we present algorithms for the circuit satisfiability problem of bounded depth circuits with AND, OR, NOT gates and a limited number of weighted symmetric gates. Our algorithms run in time super-polynomially faster than 2n even when the number of gates is super-polynomial and the maximum weight of symmetric gates is nearly exponential. With an additional trick, we give an algorithm for the maximum satisfiability problem that runs in time poly(nt) ·2n-n1/O(t) for instances with n variables, O(nt) clauses and arbitrary weights. To the best of our knowledge, this is the first moderately exponential time algorithm even for Max 2SAT instances with arbitrary weights. Through the analysis of our algorithms, we obtain average-case lower bounds and compression algorithms for such circuits and worst-case lower bounds for majority votes of such circuits, where all the lower bounds are against the generalized Andreev function. Our average-case lower bounds might be of independent interest in the sense that previous ones for similar circuits with arbitrary symmetric gates rely on communication complexity lower bounds while ours are based on the restriction method.

Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the known case analyses can also be used to prove average case circuit lower bounds, that is, lower bounds on the size of approximations of an explicit function. In this paper, we provide a general framework for proving worst/average case lower bounds for circuits and upper bounds for #SAT that is built on ideas of Chen and Kabanets. A proof in such a framework goes as follows. One starts by fixing three parameters: A class of circuits, a circuit complexity measure, and a set of allowed substitutions. The main ingredient of a proof goes as follows: By going through a number of cases, one shows that for any circuit from the given class, one can find an allowed substitution such that the given measure of the circuit reduces by a sufficient amount. This case analysis immediately implies an upper bound for #SAT. To obtain worst/average case circuit complexity lower bounds one needs to present an explicit construction of a function that is a disperser/extractor for the class of sources defined by the set of substitutions under consideration. We show that many known proofs (of circuit size lower bounds and upper bounds for #SAT) fall into this framework. Using this framework, we prove the following new bounds: Average case lower bounds of 3.24n and 2.59n for circuits over U2 and B2, respectively (though the lower bound for the basis B2is given for a quadratic disperser whose explicit construction is not currently known), and faster than 2n #SAT-algorithms for circuits over U2 and B2of size at most 3.24n and 2.99n, respectively. Here by B2 we mean the set of all bivariate Boolean functions, and by U2the set of all bivariate Boolean functions except for parity and its complement.

A two-prover one-round game is a fundamental combinatorial optimization problem arising from such areas as interactive proof systems, hardness of approximation, cryptography and quantum mechanics. The parallel repetition theorem states that for any two-prover one-round game with value smaller than 1, k-fold parallel repetition reduces the value of the game exponentially in k. The theorem was originally proved by Raz (SICOMP 1998) and later simplified and improved by Holenstein (Theory of Computing 2009) and Rao (SICOMP 2011). All the known proofs are based on information theoretic arguments. Very recently, Dinur and Steurer (STOC 2014) obtained a new proof of the parallel repetition theorem based on a matrix analysis argument. In this paper, we describe a special case of Dinur and Steurer's proof. We also describe an application of the parallel repetition theorem to inapproximability results of two-prover one-round games. Our presentation is almost self-contained in the sense that we only assume the PCP theorem. To do so, we also present proofs for the necessary results related to algebraic graph theory and hardness of approximation.

We present improved exponential time exact algorithms for Max SAT. Our algorithms run in time of the form O(2(1-μ(c))n) for instances with n variables and m = cn clauses. In this setting, there are three incomparable currently best algorithms: a deterministic exponential space algorithm with μ(c) = 1/O(c log c) due to Dantsin andWolpert [SAT 2006], a randomized polynomial space algorithm with μ(c) = 1/O(c log3 c) and a deterministic polynomial space algorithm with μ(c) = 1/O(c2 log2 c) due to Sakai, Seto and Tamaki [Theory Comput. Syst., 2015]. Our first result is a deterministic polynomial space algorithm with μ(c) = 1/O(c log c) that achieves the previous best time complexity without exponential space or randomization. Furthermore, this algorithm can handle instances with exponentially large weights and hard constraints. The previous algorithms and our deterministic polynomial space algorithm run super-polynomially faster than 2n only if m = O(n2). Our second results are deterministic exponential space algorithms for Max SAT with μ(c) = 1/O((c log c)2/3) and for Max 3-SAT with μ(c) = 1/O(c1/2) that run super-polynomially faster than 2n when m = o(n5/2/ log5/2 n) and m = o(n3/ log2 n) respectively.

A temporal constraint language Γ is a set of relations with first-order definitions in (Q &lt ). Let CSP(Γ) denote the set of constraint satisfaction problem instances with relations from Γ. CSP(Γ) admits robust approximation if, for any ∈≥ 0, given a (1-∈)-satisfiable instance of CSP(Γ), we can compute an assignment that satisfies at least a (1-f(∈))-fraction of constraints in polynomial time. Here, f(∈) is some function satisfying f(∈) = 0 and lim ∈→0 f(∈) = 0. Firstly, we give a qualitative characterization of robust approximability: Assuming the Unique Games Conjecture, we give a necessary and sufficient condition on Γ under which CSP(Γ) admits robust approximation. Secondly, wegive a quantitative characterization of robust approximability: Assuming the Unique Games Conjecture, we precisely characterize how f(∈) depends on ∈ for each Γ. We show that our robust approximation algorithms can be run in almost linear time.

The planar Halos calculus (PHC) is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. The degree-d planar Hajos calculus (PHC(d)) is PHC with the restriction that all the graphs that appear in the construction (including a final graph) must have maximum degree at most d. We prove the followings: (1) If PHC is polynomially bounded, then for any d &gt;= 4, PHC(d + 2) can generate any non-3-colorable planar graphs of maximum degree at most d in polynomial steps. (2) If PHC can generate any non-3-colorable planar graphs of maximum degree 4 in polynomial steps, then PHC is polynomially bounded.

The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the Hajos calculus is polynomially bounded. (C) 2009 Elsevier B.V. All rights reserved.

The Hajós calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. If all non-3-colorable graphs can be constructed in polynomial steps by the calculus, then NP=co-NP holds. Up to date, however, it remains open whether there exists a family of graphs that cannot be generated in polynomial steps. To attack this problem, we propose two graph calculi PHC and PHC* that generate non-3-colorable planar graphs, where intermediate graphs in the calculi are also restricted to be planar. Then we prove that PHC and PHC* are sound and complete. We also show that PHC* can polynomially simulate PHC.