01239nas a2200121 4500008004100000245002800041210002800069260001500097520092800112100002301040700001701063856003701080 2021 eng d00aQuantum Lattice Sieving0 aQuantum Lattice Sieving c10/26/20213 a

Lattices are very important objects in the effort to construct cryptographic primitives that are secure against quantum attacks. A central problem in the study of lattices is that of finding the shortest non-zero vector in the lattice. Asymptotically, sieving is the best known technique for solving the shortest vector problem, however, sieving requires memory exponential in the dimension of the lattice. As a consequence, enumeration algorithms are often used in place of sieving due to their linear memory complexity, despite their super-exponential runtime. In this work, we present a heuristic quantum sieving algorithm that has memory complexity polynomial in the size of the length of the sampled vectors at the initial step of the sieve. In other words, unlike most sieving algorithms, the memory complexity of our algorithm does not depend on the number of sampled vectors at the initial step of the sieve.

1 aRodrigues, Nishant1 aLackey, Brad uhttps://arxiv.org/abs/2110.1335200683nas a2200109 4500008004100000245004600041210004600087520036300133100001700496700002300513856003700536 2018 eng d00aMorphisms in categories of nonlocal games0 aMorphisms in categories of nonlocal games3 a

Synchronous correlations provide a class of nonlocal games that behave like functions between finite sets. In this work we examine categories whose morphisms are games with synchronous classical, quantum, or general nonsignaling correlations. In particular, we characterize when morphisms in these categories are monic, epic, sections, or retractions.

1 aLackey, Brad1 aRodrigues, Nishant uhttps://arxiv.org/abs/1810.1007401239nas a2200121 4500008004100000245006800041210006600109260001500175520085000190100001701040700002301057856003701080 2017 eng d00aNonlocal games, synchronous correlations, and Bell inequalities0 aNonlocal games synchronous correlations and Bell inequalities c2017/09/213 a

A nonlocal game with a synchronous correlation is a natural generalization of a function between two finite sets, and has recently appeared in the context of quantum graph homomorphisms. In this work we examine analogues of Bell's inequalities for synchronous correlations. We show that, unlike general correlations and the CHSH inequality, there can be no quantum Bell violation among synchronous correlations with two measurement settings. However we exhibit explicit analogues of Bell's inequalities for synchronous correlations with three measurement settings and two outputs, provide an analogue of Tsirl'son's bound in this setting, and give explicit quantum correlations that saturate this bound.

1 aLackey, Brad1 aRodrigues, Nishant uhttps://arxiv.org/abs/1707.06200