TY - JOUR T1 - Quantum Lattice Sieving Y1 - 2021 A1 - Nishant Rodrigues A1 - Brad Lackey AB -

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.

UR - https://arxiv.org/abs/2110.13352 ER - TY - JOUR T1 - Morphisms in categories of nonlocal games Y1 - 2018 A1 - Brad Lackey A1 - Nishant Rodrigues AB -

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.

UR - https://arxiv.org/abs/1810.10074 ER - TY - JOUR T1 - Nonlocal games, synchronous correlations, and Bell inequalities Y1 - 2017 A1 - Brad Lackey A1 - Nishant Rodrigues AB -

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.

UR - https://arxiv.org/abs/1707.06200 ER -