discrete subgroup

Virtual Lattice Coding & Crypto Meeting: NISQ Edition

Lattice-based approaches are emerging as a common theme in modern cryptography and coding theory. In communications, they are useful mathematical tools to construct powerful error-correction codes achieving the capacity of wireless channels. In cryptography, they are used to building lattice-based schemes with provable security, better asymptotic efficiency, resilience against quantum attacks and new functionalities such as fully homomorphic encryption.

This meeting — on Friday, 29 April 2022 — is aimed at connecting the two communities with a common interest in lattices. It will consist of several talks on related topics, with a format aimed at encouraging interaction.

Programme

14:30 - 15:30 | Florian Mintert: Quantum Mechanical Approaches to the Shortest Vector Problem with Currently Available Quantum Hardware

The advent of fully-functioning quantum computers would drastically change our used cryptographic protocols because classically hard problems might be efficiently solvable on a quantum computer. A problem that is believed to be hard even for a quantum computer is the shortest vector problem. I will discuss formulating the shortest vector problem as an algorithm that can be executed on quantum mechanical hardware. Since currently available hardware is limited in terms of qubit number and quality of logical operations, I will focus on approaches that might perform well also with limited hardware.

paper

16:00 - 17:00 | Miloš Prokop: Variational Quantum Solutions to the Shortest Vector Problem

I will discuss how (efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to solve SVP. Specifically, we’ll focus on mapping the problem to that of finding the ground state of a suitable Hamiltonian operator:

  1. we establish new bounds for lattice enumeration, this allows us to obtain new bounds (resp. estimates) for the number of qubits required per dimension for any lattices (resp. random q-ary lattices) to solve SVP
  2. we exclude the zero vector from the optimization space by proposing (a) a different classical optimization loop or alternatively (b) a new mapping to the Hamiltonian. These improvements allow us to solve SVP in dimension up to 28 in a quantum emulation, significantly more than what was previously achieved, even for special cases.

Finally, we extrapolate the size of NISQ devices that is required to be able to solve instances of lattices that are hard even for the best classical algorithms and find that with ≈ 103 noisy qubits such instances can be tackled.

pre-print

Venue

Zoom

Registration

Everyone is welcome.