INTERPLAY OF CHAOS AND INTEGRABILITY: FROM SHOR’S ALGORITHM TO SOLITONS

Abstract

The RSA (Rivest–Shamir–Adleman) encryption is believed to be secure because there is no known classical algorithm which can calculate the prime factors of a number in polynomial time. Shor’s algorithm can, in principle, solve this problem in polynomial time on a scalable quantum computer. Shor’s algorithm is an application of quantum phase estimation where one factorizes a number by finding the periodicity of the modular multiplication operator. Quantum modular multiplication is related to classical Bernoulli map which is chaotic. However modular multiplication itself is periodic. It raises the question: is thereany signature of chaos in modular multiplication? In this dissertation we show that the answer is yes. We prove that modular multiplication is a linear combination of chaotic quantized baker’s maps. The periodicity of modular multiplication arises from ‘destructive interference’ of chaotic maps. Building on this result, we design a quantum circuit for modular multiplication whose complexity is on par with most of the available circuits. A novel feature of our circuit is that it is based entirely on discrete Fourier transform and its variants. In the last part of this dissertation we study integrability of discrete Gross-Neveu model. We show that the action of discrete Gross-Neveu model has a minimum corresponding to soliton solutions. We further explore the connection between solitons and reflectionless potential using tools from discrete supersymmetry.