Search for: All records

QAC0 is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore as a quantum counterpart of AC0, along with the conjecture that QAC0 circuits cannot compute PARITY. In this work, we make progress on this long-standing conjecture: we show that any depth-𝑑 QAC0 circuit requires 𝑛^{1+3^{−𝑑}} ancillae to compute a function with approximate degree Θ(𝑛), which includes PARITY, MAJORITY and MOD_𝑘. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first lower bound on the super-linear sized QAC0. Regarding PARITY, we show that any further improvement on the size of ancillae to 𝑛^{1+exp(−𝑜(𝑑))} would imply that PARITY ∉ QAC0. These lower bounds are derived by giving low-degree approximations to QAC0 circuits. We show that a depth-𝑑 QAC0 circuit with 𝑎 ancillae, when applied to low-degree operators, has a degree (𝑛 + 𝑎)^{1−3^{−𝑑}} polynomial approximation in the spectral norm. This implies that the class QLC0, corresponding to linear size QAC0 circuits, has an approximate degree 𝑜(𝑛). This is a quantum generalization of the result that LC0 circuits have an approximate degree 𝑜(𝑛) by Bun, Kothari, and Thaler. Our result also implies that QLC0 ≠ NC1. 

We give a public key encryption scheme that is provably secure against poly-size adversaries, assuming nlogαn hardness of the standard planted clique conjecture, for any α ∈ (0,1), and a relatively mild hardness conjecture about noisy k-LIN over expanders that is not known to imply public-key encryption on its own. Both of our conjectures correspond to natural average-case variants of NP-complete problems and have been studied for multiple decades, with unconditional lower bounds supporting them in a variety of restricted models of computation. Our encryption scheme answers an open question in a seminal work by Applebaum, Barak, and Wigderson [STOC’10]. 

his paper presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm’s solution and that of an optimal solution. A universal algorithm’s solution sol for a clustering problem is said to be an (α, β)-approximation if for all subsets of clients C', it satisfies sol(C') ≤ α ⋅ opt(C') + β ⋅ mr, where opt(C') is the cost of the optimal solution for clients C' and mr is the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives of k-median, k-means, and k-center that achieve (O(1), O(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other 𝓁_p-objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that (α, β)-approximation is NP-hard if α or β is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1), O(1))-approximation is the strongest type of guarantee obtainable for universal clustering. 

We consider the fundamental problems of determining the rooted and global edge and vertex connectivities (and computing the corresponding cuts) in directed graphs. For rooted (and hence also global) edge connectivity with small integer capacities we give a new randomized Monte Carlo algorithm that runs in time Õ(n²). For rooted edge connectivity this is the first algorithm to improve on the Ω(n³) time bound in the dense-graph high-connectivity regime. Our result relies on a simple combination of sampling coupled with sparsification that appears new, and could lead to further tradeoffs for directed graph connectivity problems. We extend the edge connectivity ideas to rooted and global vertex connectivity in directed graphs. We obtain a (1+ε)-approximation for rooted vertex connectivity in Õ(nW/ε) time where W is the total vertex weight (assuming integral vertex weights); in particular this yields an Õ(n²/ε) time randomized algorithm for unweighted graphs. This translates to a Õ(KnW) time exact algorithm where K is the rooted connectivity. We build on this to obtain similar bounds for global vertex connectivity. Our results complement the known results for these problems in the low connectivity regime due to work of Gabow [Harold N. Gabow, 1995] for edge connectivity from 1991, and the very recent work of Nanongkai et al. [Nanongkai et al., 2019] and Forster et al. [Sebastian Forster et al., 2020] for vertex connectivity.