Search

We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an $n$-qubit channel $E$ and an observable $O$, we aim to learn the mapping \begin{equation*} \rho \mapsto \mathrm{Tr}(O E[\rho]) \end{equation*} to within a small error for most $\rho$ sampled from a distribution $D$. Previously, Huang, Chen, and Preskill proved a surprising result that even if $E$ is arbitrary, this task can be solved in time roughly $n^{O(\log(1/\epsilon))}$, where $\epsilon$ is the target prediction error. However, their guarantee applied only to input distributions $D$ invariant under all single-qubit Clifford gates, and their algorithm fails for important cases such as general product distributions over product states $\rho$. In this work, we propose a new approach that achieves accurate prediction over essentially any product distribution $D$, provided it is not "classical" in which case there is a trivial exponential lower bound. Our method employs a "biased Pauli analysis," analogous to classical biased Fourier analysis. Implementing this approach requires overcoming several challenges unique to the quantum setting, including the lack of a basis with appropriate orthogonality properties. The techniques we develop to address these issues may have broader applications in quantum information., Comment: 20 pages, comments welcome

The periodic tiling conjecture asserts that if a region $\Sigma\subset \mathbb R^d$ tiles $\mathbb R^d$ by translations then it admits at least one fully periodic tiling. This conjecture is known to hold in $\mathbb R$, and recently it was disproved in sufficiently high dimensions. In this paper, we study the periodic tiling conjecture for polygonal sets: bounded open sets in $\mathbb R^2$ whose boundary is a finite union of line segments. We prove the periodic tiling conjecture for any polygonal tile whose vertices are rational. As a corollary of our argument, we also obtain the decidability of tilings by rational polygonal sets. Moreover, we prove that any translational tiling by a rational polygonal tile is weakly-periodic, i.e., can be partitioned into finitely many singly-periodic pieces., Comment: 15 pages, 6 figures

Log-concave sampling has witnessed remarkable algorithmic advances in recent years, but the corresponding problem of proving lower bounds for this task has remained elusive, with lower bounds previously known only in dimension one. In this work, we establish the following query lower bounds: (1) sampling from strongly log-concave and log-smooth distributions in dimension $d\ge 2$ requires $\Omega(\log \kappa)$ queries, which is sharp in any constant dimension, and (2) sampling from Gaussians in dimension $d$ (hence also from general log-concave and log-smooth distributions in dimension $d$) requires $\widetilde \Omega(\min(\sqrt\kappa \log d, d))$ queries, which is nearly sharp for the class of Gaussians. Here $\kappa$ denotes the condition number of the target distribution. Our proofs rely upon (1) a multiscale construction inspired by work on the Kakeya conjecture in geometric measure theory, and (2) a novel reduction that demonstrates that block Krylov algorithms are optimal for this problem, as well as connections to lower bound techniques based on Wishart matrices developed in the matrix-vector query literature., Comment: 46 pages, 2 figures

In this paper we prove a uniform Fourier restriction estimate over the class of simple curves where the last coordinate function can be extended to a holomorphic function of bounded frequency in a sufficiently large disc. The proof is based on a decomposition scheme for this class of functions., Comment: 22 pages

We give new proofs of the description convex hulls of space curves $\gamma : [a,b] \mapsto \mathbb{R}^{d}$ having totally positive torsion. These are curves such that all the leading principal minors of $d\times d$ matrix $(\gamma', \gamma'', \ldots, \gamma^{(d)})$ are positive. In particular, we recover parametric representation of the boundary of the convex hull, different formulas for its surface area and the volume of the convex hull, and the solution to a general moment problem corresponding to $\gamma$., Comment: 36 pages, 10 figures. The main results of the paper follow (or are included) in two monographs M.G. Krein and A. A. Nudelman, The Markov Moment Problem and Extremal Problems; and S. Karlin and W. J. Studden, Tchebycheff Systems: With Applications in Analysis and Statistics. In our paper we give a new self contained proofs of these results

We prove that for $d\geq 0$ and $k\geq 2$, for any subset $A$ of a discrete cube $\{0,1\}^d$, the $k-$higher energy of $A$ (the number of $2k-$tuples $(a_1,a_2,\dots,a_{2k})$ in $A^{2k}$ with $a_1-a_2=a_3-a_4=\dots=a_{2k-1}-a_{2k}$) is at most $|A|^{\log_{2}(2^k+2)}$, and $\log_{2}(2^k+2)$ is the best possible exponent. We also show that if $d\geq 0$ and $2\leq k\leq 10$, for any subset $A$ of a discrete cube $\{0,1\}^d$, the $k-$additive energy of $A$ (the number of $2k-$tuples $(a_1,a_2,\dots,a_{2k})$ in $A^{2k}$ with $a_1+a_2+\dots+a_k=a_{k+1}+a_{k+2}+\dots+a_{2k}$) is at most $|A|^{\log_2{ \binom{2k}{k}}}$, and $\log_2{ \binom{2k}{k}}$ is the best possible exponent. We discuss the analogous problems for the sets $\{0,1,\dots,n\}^d$ for $n\geq 2$., Comment: 16 pages, 3 figures

In this paper we study an autocorrelation inequality proposed by Barnard and Steinerberger. The study of these problems is motivated by a classical problem in additive combinatorics. We establish the existence of extremizers to this inequality, for a general class of weights, including Gaussian functions (as studied by the second author and Ramos) and characteristic function (as originally studied by Barnard and Steinerberger). Moreover, via a discretization argument and numerical analysis, we find some almost optimal approximation for the best constant allowed in this inequality. We also discuss some other related problem about autoconvolutions., Comment: 14 pages, 1 table, 1 figure

We consider decoupling for a fractal subset of the parabola. We reduce studying $l^{2}L^{p}$ decoupling for a fractal subset on the parabola $\{(t, t^2) : 0 \leq t \leq 1\}$ to studying $l^{2}L^{p/3}$ decoupling for the projection of this subset to the interval $[0, 1]$. This generalizes the decoupling theorem of Bourgain-Demeter in the case of the parabola. Due to the sparsity and fractal like structure, this allows us to improve upon Bourgain-Demeter's decoupling theorem for the parabola. In the case when $p/3$ is an even integer we derive theoretical and computational tools to explicitly compute the associated decoupling constant for this projection to $[0, 1]$. Our ideas are inspired by the recent work on ellipsephic sets by Biggs using nested efficient congruencing., Comment: 28 pages, typos corrected, references updated, to appear in Math. Z

The aim of this paper is to prove a uniform Fourier restriction estimate for certain $2-$dimensional surfaces in $\mathbb R^{2n}$. These surfaces are the image of complex polynomial curves $\gamma(z) = (p_1(z), \dots, p_n(z))$, equipped with the complex equivalent to the affine arclength measure. This result is a complex-polynomial counterpart to a previous result by Stovall [Sto16] in the real setting. As a means to prove this theorem we provide an alternative proof of a geometric inequality by Dendrinos and Wright [DW10] that extends the result to complex polynomials., Comment: 31 pages, 1 figure

In urban spatial networks, there is an interdependency between neighborhood roles and the transportation methods between neighborhoods. In this paper, we classify docking stations in bicycle-sharing networks to gain insight into the human mobility patterns of three major United States cities. We propose novel time-dependent stochastic block models (SBMs), with degree-heterogeneous blocks and either mixed or discrete block membership, which classify nodes based on their time-dependent activity patterns. We apply these models to (1) detect the roles of bicycle-sharing docking stations and (2) describe the traffic within and between blocks of stations over the course of a day. Our models successfully uncover work, home, and other districts; they also reveal activity patterns in these districts that are particular to each city. Our work has direct application to the design and maintenance of bicycle-sharing systems, and it can be applied more broadly to community detection in temporal and multilayer networks with heterogeneous degrees., Comment: revised version