Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2306.16446 · Physical Review Research

Chaotic roots of the modular multiplication dynamical system in Shor's algorithm

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

Published Aug 28, 2024• 9 citations
arXivHTMLPDF

Abstract

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. Published by the American Physical Society 2024

DOI
10.1103/physrevresearch.6.l032046

Related papers

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

Abu Musa Patoary

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.

•Jan 1, 2025•0 citations

Modular multiplication operator and quantized baker’s maps

Arul Lakshminarayan

The modular multiplication operator, a central subroutine in Shor's factoring algorithm, is shown to be a coherent superposition of two quantum baker's maps when the multiplier is 2. The classical limit of the maps being completely chaotic, it is shown that there exist perturbations that push the modular multiplication operator into regimes of generic quantum chaos with spectral fluctuations that are those of random matrices. For the initial state of relevance to Shor's algorithm we study fidelity decay due to phase and bit-flip errors in a single qubit and show exponential decay with shoulders at multiples or half-multiples of the order. A simple model is used to gain some understanding of this behavior.

arXiv:0707.2155•Physical Review A•Oct 24, 2007•7 citations

Quantum chaos in the spectrum of operators used in Shor’s algorithm

Krishnendu Maity, Arul Lakshminarayan

We provide compelling evidence for the presence of quantum chaos in the unitary part of the operator usually employed in Shor's factoring algorithm. In particular we analyze the spectrum of this part after proper desymmetrization and show that the fluctuations of the eigenangles as well as the distribution of the eigenvector components follow the circular unitary ensemble of random matrices, of relevance to quantized chaotic systems that violate time-reversal symmetry. However, as the algorithm tracks the evolution of a single state, it is possible to employ other operators; in particular, it is possible that the generic quantum chaos found above becomes of a nongeneric kind such as is found in the quantum cat maps and in toy models of the quantum baker's map.

arXiv:quant-ph/0604111•Physical Review E•Sep 15, 2006•15 citations

Shuffling cards, factoring numbers and the quantum baker's map

Arul Lakshminarayan

It is pointed out that an exactly solvable permutation operator, viewed as the quantization of cyclic shifts, is useful in constructing a basis in which to study the quantum baker's map, a paradigm system of quantum chaos. In the basis of this operator the eigenfunctions of the quantum baker's map are compressed by factors of around five or more. We show explicitly its connection to an operator that is closely related to the usual quantum baker's map. This permutation operator has interesting connections to the art of shuffling cards as well as to the quantum factoring algorithm of Shor via the quantum order finding one. Hence we point out that this well-known quantum algorithm makes crucial use of a quantum chaotic operator, or at least one that is close to the quantization of the left-shift, a closeness that we also explore quantitatively.

arXiv:nlin/0505057•Journal of Physics A Mathematical and General•Aug 31, 2005•12 citations

Shor's Factoring Algorithm and Modular Exponentiation Operators

Robert Singleton

We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.

arXiv:2306.09122•Quanta•Sep 15, 2023•15 citations

Quantum Chaos as an Essential Resource for Full Quantum State Controllability

Lukas Beringer, Mathias Steinhuber, Klaus Richter +1 more

Using the key properties of chaos, i.e. ergodicity and exponential instability, as a resource to control classical dynamics has a long and considerable history. However, in the context of controlling "chaotic" quantum unitary dynamics, the situation is far more tenuous. The classical concepts of exponential sensitivity to trajectory initial conditions and ergodicity do not directly translate into quantum unitary evolution. Nevertheless properties inherent to quantum chaos can take on those roles: i) the dynamical sensitivity to weak perturbations, measured by the fidelity decay, serves a similar purpose as the classical sensitivity to initial conditions; and ii) paired with the fact that quantum chaotic systems are conjectured to be statistically described by random matrix theory, implies a method to translate the ergodic feature into the control of quantum dynamics. With those two properties, it can be argued that quantum chaotic dynamical systems, in principle, allow for full controllability beyond a characteristic time that scales only logarithmically with system size and $\hbar^{-1}$. In the spirit of classical targeting, it implies that it is possible to fine tune the immense quantum interference with weak perturbations and steer the system from any initial state into any desired target state, subject to constraints imposed by conserved quantities. In contrast, integrable dynamics possess neither ergodicity nor exponential instability, and thus the weak perturbations apparently must break the integrability for control purposes. The main ideas are illustrated with the quantum kicked rotor. The production of revivals, cat-like entangled states, and the transition from any random state to any other random state is possible as demonstrated.

quant-pharXiv:2512.13384•Dec 16, 2025•0 citations
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. Published by the American Physical Society 2024
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.
The modular multiplication operator, a central subroutine in Shor's factoring algorithm, is shown to be a coherent superposition of two quantum baker's maps when the multiplier is 2. The classical limit of the maps being completely chaotic, it is shown that there exist perturbations that push the modular multiplication operator into regimes of generic quantum chaos with spectral fluctuations that are those of random matrices. For the initial state of relevance to Shor's algorithm we study fidelity decay due to phase and bit-flip errors in a single qubit and show exponential decay with shoulders at multiples or half-multiples of the order. A simple model is used to gain some understanding of this behavior.
We provide compelling evidence for the presence of quantum chaos in the unitary part of the operator usually employed in Shor's factoring algorithm. In particular we analyze the spectrum of this part after proper desymmetrization and show that the fluctuations of the eigenangles as well as the distribution of the eigenvector components follow the circular unitary ensemble of random matrices, of relevance to quantized chaotic systems that violate time-reversal symmetry. However, as the algorithm tracks the evolution of a single state, it is possible to employ other operators; in particular, it is possible that the generic quantum chaos found above becomes of a nongeneric kind such as is found in the quantum cat maps and in toy models of the quantum baker's map.
It is pointed out that an exactly solvable permutation operator, viewed as the quantization of cyclic shifts, is useful in constructing a basis in which to study the quantum baker's map, a paradigm system of quantum chaos. In the basis of this operator the eigenfunctions of the quantum baker's map are compressed by factors of around five or more. We show explicitly its connection to an operator that is closely related to the usual quantum baker's map. This permutation operator has interesting connections to the art of shuffling cards as well as to the quantum factoring algorithm of Shor via the quantum order finding one. Hence we point out that this well-known quantum algorithm makes crucial use of a quantum chaotic operator, or at least one that is close to the quantization of the left-shift, a closeness that we also explore quantitatively.
We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.
Using the key properties of chaos, i.e. ergodicity and exponential instability, as a resource to control classical dynamics has a long and considerable history. However, in the context of controlling "chaotic" quantum unitary dynamics, the situation is far more tenuous. The classical concepts of exponential sensitivity to trajectory initial conditions and ergodicity do not directly translate into quantum unitary evolution. Nevertheless properties inherent to quantum chaos can take on those roles: i) the dynamical sensitivity to weak perturbations, measured by the fidelity decay, serves a similar purpose as the classical sensitivity to initial conditions; and ii) paired with the fact that quantum chaotic systems are conjectured to be statistically described by random matrix theory, implies a method to translate the ergodic feature into the control of quantum dynamics. With those two properties, it can be argued that quantum chaotic dynamical systems, in principle, allow for full controllability beyond a characteristic time that scales only logarithmically with system size and ℏ−1\hbar^{-1}ℏ−1. In the spirit of classical targeting, it implies that it is possible to fine tune the immense quantum interference with weak perturbations and steer the system from any initial state into any desired target state, subject to constraints imposed by conserved quantities. In contrast, integrable dynamics possess neither ergodicity nor exponential instability, and thus the weak perturbations apparently must break the integrability for control purposes. The main ideas are illustrated with the quantum kicked rotor. The production of revivals, cat-like entangled states, and the transition from any random state to any other random state is possible as demonstrated.