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:quant-ph/0604111 · Physical Review E

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

Krishnendu Maity, Arul Lakshminarayan

Published Sep 15, 2006• 14 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreve.74.035203

Related papers

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•6 citations

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

Abu Musa Patoary, Amit Vikram, Laura Shou +1 more

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

arXiv:2306.16446•Physical Review Research•Aug 28, 2024•3 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

Using the Hadamard and related transforms for simplifying the spectrum of the quantum baker's map

Arul Lakshminarayan, N. Meenakshisundaram

We rationalize the somewhat surprising efficacy of the Hadamard transform in simplifying the eigenstates of the quantum baker's map, a paradigmatic model of quantum chaos. This allows us to construct closely related, but new, transforms that do significantly better, thus nearly solving many states of the quantum baker's map. These transforms, which combine the standard Fourier and Hadamard transforms in an interesting manner, are constructed from eigenvectors of the shift permutation operator that are also simultaneous eigenvectors of bit-flip (parity) and possess bit-reversal (time-reversal) symmetry.

arXiv:nlin/0603002•Journal of Physics A Mathematical and General•Aug 18, 2006•9 citations

Operator scrambling and quantum chaos

Chen, Xiao, Tianci Zhou

Operator scrambling is a crucial ingredient of quantum chaos. Specifically, in the quantum chaotic system, a simple operator can become increasingly complicated under unitary time evolution. This can be diagnosed by various measures such as square of the commutator (out-of-time-ordered correlator), operator entanglement entropy etc. In this paper, we discuss operator scrambling in three representative models: a chaotic spin-$1/2$ chain with spatially local interactions, a 2-local spin model and the quantum linear map. In the first two examples, although the speeds of scrambling are quite different, a simple Pauli spin operator can eventually approach a "highly entangled" operator with operator entanglement entropy taking a volume law value (close to the Page value). Meanwhile, the spectrum of the operator reduced density matrix develops a universal spectral correlation which can be characterized by the Wishart random matrix ensemble. In the second example, we further connect the 2-local model into a one dimensional chain and briefly discuss the operator scrambling there. In contrast, in the quantum linear map, although the square of commutator can increase exponentially with time, a simple operator does not scramble but performs chaotic motion in the operator basis space determined by the classical linear map. We show that once we modify the quantum linear map such that operator can mix in the operator basis, the operator entanglement entropy can grow and eventually saturate to its Page value, thus making it a truly quantum chaotic model.

arXiv:1804.08655•Apr 23, 2018•38 citations

Parametric correlations in non-Hermitian quantum chaos: random matrix approach

Yan V. Fyodorov, Bertrand Lacroix-A-Chez-Toine

Motivated by the surge of interest in statistics of non-Hermitian random matrices as a framework for description of universal characteristics of dissipative chaotic quantum many-body systems, we address the problem of characterizing the parametric correlations of spectral densities. Considering parameter-dependent ensemble of complex Ginibre matrices we derive an explicit, closed-form expression for the parametric number covariance in the systems of symmetry class $\mathbf{A}$ for eigenvalues in a circular domain containing on average a finite number of eigenvalues in the spectral bulk. This behavior is expected to be universal, as further supported by numerical evidence for the real Ginibre ensemble, non-Hermitian Bernoulli Wigner matrices and bi-unitarily invariant ensembles. We also discuss a relation between parametric correlations of spectral densities and the distribution of the so-called eigenvector non-orthogonality factor, which attracted considerable interest in recent years.

quant-pharXiv:2606.20824•Jun 22, 2026
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.
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.
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
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 rationalize the somewhat surprising efficacy of the Hadamard transform in simplifying the eigenstates of the quantum baker's map, a paradigmatic model of quantum chaos. This allows us to construct closely related, but new, transforms that do significantly better, thus nearly solving many states of the quantum baker's map. These transforms, which combine the standard Fourier and Hadamard transforms in an interesting manner, are constructed from eigenvectors of the shift permutation operator that are also simultaneous eigenvectors of bit-flip (parity) and possess bit-reversal (time-reversal) symmetry.
Operator scrambling is a crucial ingredient of quantum chaos. Specifically, in the quantum chaotic system, a simple operator can become increasingly complicated under unitary time evolution. This can be diagnosed by various measures such as square of the commutator (out-of-time-ordered correlator), operator entanglement entropy etc. In this paper, we discuss operator scrambling in three representative models: a chaotic spin-1/21/21/2 chain with spatially local interactions, a 2-local spin model and the quantum linear map. In the first two examples, although the speeds of scrambling are quite different, a simple Pauli spin operator can eventually approach a "highly entangled" operator with operator entanglement entropy taking a volume law value (close to the Page value). Meanwhile, the spectrum of the operator reduced density matrix develops a universal spectral correlation which can be characterized by the Wishart random matrix ensemble. In the second example, we further connect the 2-local model into a one dimensional chain and briefly discuss the operator scrambling there. In contrast, in the quantum linear map, although the square of commutator can increase exponentially with time, a simple operator does not scramble but performs chaotic motion in the operator basis space determined by the classical linear map. We show that once we modify the quantum linear map such that operator can mix in the operator basis, the operator entanglement entropy can grow and eventually saturate to its Page value, thus making it a truly quantum chaotic model.
Motivated by the surge of interest in statistics of non-Hermitian random matrices as a framework for description of universal characteristics of dissipative chaotic quantum many-body systems, we address the problem of characterizing the parametric correlations of spectral densities. Considering parameter-dependent ensemble of complex Ginibre matrices we derive an explicit, closed-form expression for the parametric number covariance in the systems of symmetry class A\mathbf{A}A for eigenvalues in a circular domain containing on average a finite number of eigenvalues in the spectral bulk. This behavior is expected to be universal, as further supported by numerical evidence for the real Ginibre ensemble, non-Hermitian Bernoulli Wigner matrices and bi-unitarily invariant ensembles. We also discuss a relation between parametric correlations of spectral densities and the distribution of the so-called eigenvector non-orthogonality factor, which attracted considerable interest in recent years.