- Transversality is a simple and effective method for implementing quantum computation fault-tolerantly. However, no quantum error-correcting code (QECC) can transversally implement a quantum universal gate set (Eastin and Knill, Phys. Rev. Lett., 102, 110502). Since reversible classical computation is often a dominating part of useful quantum computation, whether or not it can be implemented transversally is an important open problem. We show that, other than a small set of non-additive codes that we cannot rule out, no binary QECC can transversally implement a classical reversible universal gate set. In particular, no such QECC can implement the Toffoli gate transversally. We prove our result by constructing an information theoretically secure (but inefficient) quantum homomorphic encryption (ITS-QHE) scheme inspired by Ouyang et al. (arXiv:1508.00938). Homomorphic encryption allows the implementation of certain functions directly on encrypted data, i.e. homomorphically. Our scheme builds on almost any QECC, and implements that code's transversal gate set homomorphically. We observe a restriction imposed by Nayak's bound (FOCS 1999) on ITS-QHE, implying that any ITS quantum fully homomorphic scheme (ITS-QFHE) implementing the full set of classical reversible functions must be highly inefficient. While our scheme incurs exponential overhead, any such QECC implementing Toffoli transversally would still violate this lower bound through our scheme.
- We derive a lower bound on the differential entropy of a log-concave random variable $X$ in terms of the $p$-th absolute moment of $X$. The new bound leads to a reverse entropy power inequality with an explicit constant, and to new bounds on the rate-distortion function and the channel capacity. Specifically, we study the rate-distortion function for log-concave sources and distortion measure $| x - \hat x|^r$, and we establish that the difference between the rate distortion function and the Shannon lower bound is at most $\log(2 \sqrt{\pi e}) \approx 2.5$ bits, independently of $r$ and the target distortion $d$. For mean-square error distortion, the difference is at most $\log (\sqrt{2 \pi e}) \approx 2$ bits, regardless of $d$. The bounds can be further strengthened if the source, in addition to being log-concave, is symmetric. In particular, we establish that for mean-square error distortion, the difference is at most $\log (\sqrt{\pi e}) \approx 1.5$ bits, regardless of $d$. We also provide bounds on the capacity of memoryless additive noise channels when the noise is log-concave. We show that the difference between the capacity of such channels and the capacity of the Gaussian channel with the same noise power is at most $\log(\sqrt {2\pi e}) \approx 2$ bits, and at most $\log (\sqrt{\pi e}) \approx 1.5$ bits if the noise is symmetric log-concave. Our results generalize to the case of vector $X$ with possibly dependent coordinates, and to $\gamma$-concave random variables. Our proof technique leverages tools from convex geometry.
- Apr 26 2017 math.OC arXiv:1704.07785v1Many real-world control systems, such as the smart grid and human sensorimotor control systems, have decentralized components that react quickly using local information and centralized components that react slowly using a more global view. This paper seeks to provide a theoretical framework for how to design controllers that are decomposed across timescales in this way. The framework is analogous to how the network utility maximization framework uses optimization decomposition to distribute a global control problem across independent controllers, each of which solves a local problem; except our goal is to decompose a global problem temporally, extracting a timescale separation. Our results highlight that decomposition of a multi-timescale controller into a fast timescale, reactive controller and a slow timescale, predictive controller can be near-optimal in a strong sense. In particular, we exhibit such a design, named Multi-timescale Reflexive Predictive Control (MRPC), which maintains a per-timestep cost within a constant factor of the offline optimal in an adversarial setting.
- Principal component analysis (PCA) is a fundamental dimension reduction tool in statistics and machine learning. For large and high-dimensional data, computing the PCA (i.e., the singular vectors corresponding to a number of dominant singular values of the data matrix) becomes a challenging task. In this work, a single-pass randomized algorithm is proposed to compute PCA with only one pass over the data. It is suitable for processing extremely large and high-dimensional data stored in slow memory (hard disk) or the data generated in a streaming fashion. Experiments with synthetic and real data validate the algorithm's accuracy, which has orders of magnitude smaller error than an existing single-pass algorithm. For a set of high-dimensional data stored as a 150 GB file, the proposed algorithm is able to compute the first 50 principal components in just 24 minutes on a typical 24-core computer, with less than 1 GB memory cost.
- Apr 26 2017 math.RT arXiv:1704.07655v1We provide criteria for the cyclotomic quiver Hecke algebras of type C to be semisimple. In the semisimple case, we construct the irreducible modules.
- We offer a general Bayes theoretic framework to tackle the model selection problem under a two-step prior design: the first-step prior serves to assess the model selection uncertainty, and the second-step prior quantifies the prior belief on the strength of the signals within the model chosen from the first step. We establish non-asymptotic oracle posterior contraction rates under (i) a new Bernstein-inequality condition on the log likelihood ratio of the statistical experiment, (ii) a local entropy condition on the dimensionality of the models, and (iii) a sufficient mass condition on the second-step prior near the best approximating signal for each model. The first-step prior can be designed generically. The resulting posterior mean also satisfies an oracle inequality, thus automatically serving as an adaptive point estimator in a frequentist sense. Model mis-specification is allowed in these oracle rates. The new Bernstein-inequality condition not only eliminates the need of constructing explicit tests with exponentially small type I and II errors, but also suggests the `intrinsic' metric to use in a given statistical experiment, both as a loss function and as an entropy measurement. This gives a unified reduction scheme for many experiments considered in Ghosal & van der Vaart(2007) and beyond. As an illustration for the scope of our general results in concrete applications, we consider (i) trace regression, (ii) shape-restricted isotonic/convex regression, (iii) high-dimensional partially linear regression and (iv) covariance matrix estimation in the sparse factor model. These new results serve either as theoretical justification of practical prior proposals in the literature, or as an illustration of the generic construction scheme of a (nearly) minimax adaptive estimator for a multi-structured experiment.
- Apr 26 2017 math.GR arXiv:1704.07811v1
- Apr 26 2017 math.CA arXiv:1704.07810v1
- Apr 26 2017 math.AP arXiv:1704.07801v1
- Apr 26 2017 math.GT arXiv:1704.07792v1
- Apr 26 2017 math.DG arXiv:1704.07788v1
- Apr 26 2017 math.CO arXiv:1704.07784v1
- Apr 26 2017 math.CO arXiv:1704.07775v1
- Apr 26 2017 math.OC arXiv:1704.07773v1
- Apr 26 2017 math.OC arXiv:1704.07770v1
- Apr 26 2017 math.AG arXiv:1704.07768v1
- Apr 26 2017 math.CO arXiv:1704.07752v1
- Apr 26 2017 math.GT arXiv:1704.07739v1
- Apr 26 2017 math.DS arXiv:1704.07731v1
- Apr 26 2017 math.CV arXiv:1704.07726v1
- Apr 26 2017 math.CO arXiv:1704.07714v1
- Apr 26 2017 math.NT arXiv:1704.07701v1
- Apr 26 2017 math.NA arXiv:1704.07698v1
- Apr 26 2017 math.GT arXiv:1704.07689v1
- Apr 26 2017 math.DS arXiv:1704.07686v1
- Apr 26 2017 math.DS arXiv:1704.07682v1
- Apr 26 2017 math.NA arXiv:1704.07674v1
- Apr 26 2017 math.CO arXiv:1704.07667v1