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• 15 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•7 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•9 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•10 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•75 citations

Isospectral Twirling and Quantum Chaos

Lorenzo Leone, Salvatore F. E. Oliviero, Alioscia Hamma

We show that the most important measures of quantum chaos, such as frame potentials, scrambling, Loschmidt echo and out-of-time-order correlators (OTOCs), can be described by the unified framework of the isospectral twirling, namely the Haar average of a k-fold unitary channel. We show that such measures can then always be cast in the form of an expectation value of the isospectral twirling. In literature, quantum chaos is investigated sometimes through the spectrum and some other times through the eigenvectors of the Hamiltonian generating the dynamics. We show that thanks to this technique, we can interpolate smoothly between integrable Hamiltonians and quantum chaotic Hamiltonians. The isospectral twirling of Hamiltonians with eigenvector stabilizer states does not possess chaotic features, unlike those Hamiltonians whose eigenvectors are taken from the Haar measure. As an example, OTOCs obtained with Clifford resources decay to higher values compared with universal resources. By doping Hamiltonians with non-Clifford resources, we show a crossover in the OTOC behavior between a class of integrable models and quantum chaos. Moreover, exploiting random matrix theory, we show that these measures of quantum chaos clearly distinguish the finite time behavior of probes to quantum chaos corresponding to chaotic spectra given by the Gaussian Unitary Ensemble (GUE) from the integrable spectra given by Poisson distribution and the Gaussian Diagonal Ensemble (GDE).

arXiv:2011.06011•Entropy•Aug 19, 2021•38 citations
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.
We show that the most important measures of quantum chaos, such as frame potentials, scrambling, Loschmidt echo and out-of-time-order correlators (OTOCs), can be described by the unified framework of the isospectral twirling, namely the Haar average of a k-fold unitary channel. We show that such measures can then always be cast in the form of an expectation value of the isospectral twirling. In literature, quantum chaos is investigated sometimes through the spectrum and some other times through the eigenvectors of the Hamiltonian generating the dynamics. We show that thanks to this technique, we can interpolate smoothly between integrable Hamiltonians and quantum chaotic Hamiltonians. The isospectral twirling of Hamiltonians with eigenvector stabilizer states does not possess chaotic features, unlike those Hamiltonians whose eigenvectors are taken from the Haar measure. As an example, OTOCs obtained with Clifford resources decay to higher values compared with universal resources. By doping Hamiltonians with non-Clifford resources, we show a crossover in the OTOC behavior between a class of integrable models and quantum chaos. Moreover, exploiting random matrix theory, we show that these measures of quantum chaos clearly distinguish the finite time behavior of probes to quantum chaos corresponding to chaotic spectra given by the Gaussian Unitary Ensemble (GUE) from the integrable spectra given by Poisson distribution and the Gaussian Diagonal Ensemble (GDE).