Chaotic Roots of the Modular Multiplication Dynamical System in Shor's Algorithm

Connected to paperThis paper is a preprint and has not been certified by peer review

Chaotic Roots of the Modular Multiplication Dynamical System in Shor's Algorithm


Abu Musa Patoary, Amit Vikram, Laura Shou, Victor Galitski


Shor's factoring algorithm, believed to provide an exponential speedup over classical computation, relies on finding the period of an exactly periodic quantum modular multiplication operator. This exact periodicity is the hallmark of an integrable system, which is paradoxical from the viewpoint of quantum chaos, given that the classical limit of the modular multiplication operator is a highly chaotic system that occupies the "maximally random" Bernoulli level of the classical ergodic hierarchy. In this work, we approach this apparent paradox from a quantum dynamical systems viewpoint, and consider whether signatures of ergodicity and chaos may indeed be encoded in such an "integrable" quantization of a chaotic system. We show that Shor's modular multiplication operator, in specific cases, can be written as a superposition of quantized A-baker's maps exhibiting more typical signatures of quantum chaos and ergodicity. This work suggests that the integrability of Shor's modular multiplication operator may stem from the interference of other "chaotic" quantizations of the same family of maps, and paves the way for deeper studies on the interplay of integrability, ergodicity and chaos in and via quantum algorithms.

Follow Us on

1 comment


The research presented in the article takes an intriguing dive into the domain of quantum computation, particularly focusing on Shor’s factoring algorithm. As a foundational algorithm in quantum computing, Shor’s algorithm presents an exponential speedup compared to its classical counterparts. At the core of this algorithm is an operation known as quantum modular multiplication, which exhibits a fascinating trait of periodicity.

In the world of dynamical systems, this periodic behavior characterizes what we call an “integrable system”. However, this presents a paradox. When we transition to the classical limit, the modular multiplication operator seems to evolve into a chaotic system, reaching the “maximally random” Bernoulli level in the classical ergodic hierarchy. This transition from order to chaos, when moving from quantum to classical realms, forms the crux of the paradox that the research investigates.

The study proposes that, counter-intuitively, signatures of chaos and ergodicity might be hidden within the ostensibly orderly quantum version of the operation. The researchers explore this by demonstrating that, in specific scenarios, Shor’s modular multiplication operator can be recast as a superposition of quantized versions of another type of chaotic system known as the A-baker’s map.

This line of inquiry suggests a captivating hypothesis: the “order” we see in Shor’s modular multiplication might be the outcome of quantum interference among various chaotic quantizations of the same family of maps. In essence, the “chaos” at the quantum level might not be absent but rather subtly hidden. The findings open a pathway to delve deeper into the relationship between chaos, ergodicity, and integrability in the context of quantum algorithms, a realm where quantum and classical worlds intriguingly intertwine.
But one may ask oneself, how can this type of research, help us? Or how can this research help me and my loved ones?
Well let’s put it this way, this type of research helps us in several ways:

 1. Understanding Quantum Algorithms: By exploring and understanding the underlying structures and behaviors of quantum algorithms like Shor’s, we can develop more efficient or robust algorithms. This could lead to practical applications in a variety of fields, including cryptography, materials science, and drug discovery.
 2. Advancing Quantum Computing: The deeper understanding of the behavior of quantum systems, especially in relation to classical systems, helps to advance the field of quantum computing itself. It helps to solve technical challenges, develop new methods, and guides the design of future quantum hardware.
 3. Bridging Quantum and Classical Physics: This kind of research aids in building a bridge between the quantum and classical realms. By investigating the parallels and divergences between these two realms, we could unlock new insights about the fundamental laws of physics, which can have far-reaching implications.
 4. Exploring Quantum Chaos: The research into “quantum chaos” – the study of how chaotic behavior in classical systems manifests in quantum systems – is a burgeoning field. These insights could be relevant in understanding complex quantum systems and phenomena like quantum entanglement and quantum decoherence.

In essence, the research is pushing the boundaries of our understanding of quantum mechanics and computing. The more we understand, the more effectively we can utilize quantum computing, potentially revolutionizing a variety of fields by enabling computations that are currently impossible for classical computers.

Add comment