%0 Journal Article %D 2021 %T Quantum Lattice Sieving %A Nishant Rodrigues %A Brad Lackey %X

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.

%8 10/26/2021 %G eng %U https://arxiv.org/abs/2110.13352 %0 Journal Article %D 2018 %T Morphisms in categories of nonlocal games %A Brad Lackey %A Nishant Rodrigues %X

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.

%G eng %U https://arxiv.org/abs/1810.10074 %0 Journal Article %D 2017 %T Nonlocal games, synchronous correlations, and Bell inequalities %A Brad Lackey %A Nishant Rodrigues %X

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.

%8 2017/09/21 %G eng %U https://arxiv.org/abs/1707.06200