51 research outputs found
High-entropy dual functions over finite fields and locally decodable codes
No full textWe show that for infinitely many primes p, there exist dual functions of order k over Fnp that cannot be approximated in L∞-distance by polynomial phase functions of degree k−1. This answers in the negative a natural finite-field analog of a problem of Frantzikinakis on L∞-approximations of dual functions over N (a.k.a. multiple correlation sequences) by nilsequences
Quasirandom Quantum Channels
No full textMixing (or quasirandom) properties of the natural transition matrix associated to a graph can be quantified by its distance to the complete graph. Different mixing properties correspond to different norms to measure this distance. For dense graphs, two such properties known as spectral expansion and uniformity were shown to be equivalent in seminal 1989 work of Chung, Graham and Wilson. Recently, Conlon and Zhao extended this equivalence to the case of sparse vertex transitive graphs using the famous Grothendieck inequality.
Here we generalize these results to the non-commutative, or "quantum", case, where a transition matrix becomes a quantum channel. In particular, we show that for irreducibly covariant quantum channels, expansion is equivalent to a natural analog of uniformity for graphs, generalizing the result of Conlon and Zhao. Moreover, we show that in these results, the non-commutative and commutative (resp.) Grothendieck inequalities yield the best-possible constants
Bounding Quantum-Classical Separations for Classes of Nonlocal Games
No full textWe bound separations between the entangled and classical values for several classes of nonlocal t-player games. Our motivating question is whether there is a family of t-player XOR games for which the entangled bias is 1 but for which the classical bias goes down to 0, for fixed t. Answering this question would have important consequences in the study of multi-party communication complexity, as a positive answer would imply an unbounded separation between randomized communication complexity with and without entanglement. Our contribution to answering the question is identifying several general classes of games for which the classical bias can not go to zero when the entangled bias stays above a constant threshold. This rules out the possibility of using these games to answer our motivating question. A previously studied set of XOR games, known not to give a positive answer to the question, are those for which there is a quantum strategy that attains value 1 using a so-called Schmidt state. We generalize this class to mod-m games and show that their classical value is always at least 1/m + (m-1)/m t^{1-t}. Secondly, for free XOR games, in which the input distribution is of product form, we show beta(G) >= beta^*(G)^{2^t} where beta(G) and beta^*(G) are the classical and entangled biases of the game respectively. We also introduce so-called line games, an example of which is a slight modification of the Magic Square game, and show that they can not give a positive answer to the question either. Finally we look at two-player unique games and show that if the entangled value is 1-epsilon then the classical value is at least 1-O(sqrt{epsilon log k}) where k is the number of outputs in the game. Our proofs use semidefinite-programming techniques, the Gowers inverse theorem and hypergraph norms
Quasirandomness in quantum information theory
No full textWe study quasirandomness in several contexts in quantum information theory. Roughly speaking, an object is quasirandom if it shares properties with a random object. What these properties are, depends on the context.Consider, for example, uniformly random 3-regular graphs. They have the property that they are likely highly connected, while at the same time the number of edges is quite small (the graph is “sparse”). Highly connected refers to the property that, for example, a random walk on the graph mixes very rapidly: after a small number of steps, the position of the walker is close to uniformly random. So when an explicit 3-regular graph has this property as well, we say that it is quasirandom.Among other things, interesting objects whose quasirandomness we study in this dissertation are linear maps from matrices to matrices or complex-valued functions on a finite abelian group. These objects appear in quantum information theory in the form of quantum channels or the amplitudes of quantum states for example.For quantum channels, we study the equivalence of certain quasirandom properties: we generalize the theory of quasirandom graphs to quantum information theory showing that “expansion” and “uniformity” are equivalent for very symmetric quantum channels.For quantum states we consider the notion of rank, where you want to express a quantum state in terms of a minimal number of simpler states called stabilizer states, this is the stabilizer rank. In this case, random quantum states have “high” stabilizer rank and we want to know if an explicit quantum state, say the magic state, has high stabilizer rank. Here we shed light on this problem by looking at this problem from a different perspective, through the lens of higher-order Fourier analysis
The tautological ring of Mg,n via Pandharipande-Pixton-Zvonkine r-spin relations
No full textWe use relations in the tautological ring of the moduli spaces Mg,n derived by Pandharipande, Pixton, and Zvonkine from the Givental formula for the r-spin Witten class in order to obtain some restrictions on the dimensions of the tautological rings of the open moduli spacesMg,n. In particular, we give a new proof for the result of Looijenga (for n = 1) and Buryak et al. (for n > 2) that dimRg-1(Mg,n) ≤ n. We also give a new proof of the result of Looijenga (for n = 1) and Ionel (for arbitrary n > 1) that Ri(Mg,n) = 0 for i > g and give some estimates for the dimension of Ri(Mg,n) for i ≤ g - 2
High-entropy dual functions over finite fields and locally decodable codes
No full textWe show that for infinitely many primes p, there exist dual functions of order k over Fnp that cannot be approximated in L∞-distance by polynomial phase functions of degree k−1. This answers in the negative a natural finite-field analog of a problem of Frantzikinakis on L∞-approximations of dual functions over N (a.k.a. multiple correlation sequences) by nilsequences
Dual functions not approximable by higher-order characters
No full textDual functions, known in ergodic theory as multiple correlation sequences, are an important but poorly-understood class of functions in additive combinatorics. An example of such a function is one that, given a subset A and element d, counts the number of arithmetic progressions in A with common difference d.
To make progress on an equally poorly-understood probabilistic version of Szemerédi's theorem with random common differences, it has been suggested to determine if dual functions can be decomposed in terms of "higher-order characters" (polynomial phases or nilsequences) plus a small error function. Conjectured bounds for Szemerédi's theorem with random differences were motivated by an apparent expectation that the error can always be taken to have small L_inf norm. It turns out that this is too much to hope for. In this talk we discuss counterexamples to such decompositions, ideas of which originate from coding theory.
This is based on joint works with Ben Green and Farrokh Labib.</p
High-entropy dual functions over finite fields and locally decodable codes
No full textWe show that for infinitely many primes p, there exist dual functions of order k over Fnp that cannot be approximated in L∞-distance by polynomial phase functions of degree k−1. This answers in the negative a natural finite-field analog of a problem of Frantzikinakis on L∞-approximations of dual functions over N (a.k.a. multiple correlation sequences) by nilsequences
High-entropy dual functions over finite fields and locally decodable codes
No full textWe show that for infinitely many primes p, there exist dual functions of order k over Fnp that cannot be approximated in L∞-distance by polynomial phase functions of degree k−1. This answers in the negative a natural finite-field analog of a problem of Frantzikinakis on L∞-approximations of dual functions over N (a.k.a. multiple correlation sequences) by nilsequences
- …
