Talks

Variational Quantum Circuits, which include examples of quantum approximate optimization algorithms (QAOA),  variational quantum eigensolver (VQE), and quantum neural-networks (QNN), are predicted to be one of the most important near-term quantum applications, not only because of their potential promises as classical neural-networks but also because of their feasibility on near-term noisy intermediate size quantum (NISQ) machines. This talk reports some progress toward a principled understanding of the training of variational quantum circuits. First, I will demonstrate the difficulty of training by constructing an example with exponentially many local optima,  however,  due to a differential nature from classical neural-networks. Second, I will explain how to facilitate the training by incorporating the optimal-transport norm in the context of quantum generative adversarial networks (GANs), as well as its application in compressing quantum circuits in practical uses.

We will review recent work on quantum Machine Learning with a focus on longer-term quantum algorithms. We will discuss challenges and prospects for such algorithms and ways of bringing them closer to practical solutions.

Elliptic curves play a prominent role in cryptography. For instance, the hardness of the elliptic curve discrete logarithm problem is a foundational assumption in public key cryptography. Drinfeld modules are positive characteristic function field analogues of elliptic curves. It is natural to ponder the existence/security of Drinfeld module analogues of elliptic curve cryptosystems. But the Drinfeld module discrete logarithm problem is easy even on a classical computer. Beyond discrete logarithms, elliptic curve isogeny based cryptosystems have have emerged as candidates for post-quantum cryptography, including supersingular isogeny Diffie-Hellman (SIDH) and commutative supersingular isogeny Diffie-Hellman (CSIDH) protocols. We formulate Drinfeld module analogues of these elliptic curve isogeny based cryptosystems and devise classical polynomial time algorithms to break these Drinfeld analogues catastrophically.  

The Hidden Subgroup Problem (HSP) aims at capturing all problems that are susceptible to be solvable in quantum polynomial time following the blueprints of Shor’s celebrated algorithm. Successful solutions to this problems over various commutative groups allow to efficiently perform number-theoretic tasks such as factoring or finding discrete logarithms. The latest successful generalization (Eisenträger et al. STOC 2014) considers the problem of finding a full-rank lattice as the hidden subgroup of the continuous vector space R^m , even for large dimensions m. It unlocked new cryptanalytic algorithms (Biasse-Song SODA 2016, Cramer et al. EUROCRYPT 2016 and 2017), in particular to find mildly short vectors in ideal lattices. The cryptanalytic relevance of such a problem raises the question of a more refined and quantitative complexity analysis. In the light of the increasing physical difficulty of maintaining a large entanglement of qubits, the degree of concern may be different whether the above algorithm requires only linearly many qubits or a much larger polynomial amount of qubits. This is the question we start addressing with this work. We propose a detailed analysis of (a variation of) the aforementioned HSP algorithm, and conclude on its complexity as a function of all the relevant parameters. Our modular analysis is tailored to support the optimization of future specialization to cases of cryptanalytic interests. We suggest a few ideas in this direction.