Chaotic Roots of the Modular Multiplication Dynamical System in Shor's Algorithm
arXiv:2306.16446 · doi:10.1103/PhysRevResearch.6.L032046
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.
arXiv comment5+7 pages, 3+1 figures
References in corpus (14)
- Semiclassical Foundation of Universality in Quantum Chaos
- Periodic-Orbit Theory of Universality in Quantum Chaos
- Experimental Implementation of the Quantum Baker's Map
- Classical 1D maps, quantum graphs and ensembles of unitary matrices
- Entropy of semiclassical measures of the Walsh-quantized baker's map
- Monitoring Quantum Simulators via Quantum Non-Demolition Couplings to Atomic Clock Qubits
- Realizing the quantum baker's map on an NMR quantum computer
- Dynamical quantum ergodicity from energy level statistics
- Quantum Variance and Ergodicity for the baker's map
- The classical limit for a class of quantum baker's maps
- Generalized Quantum Baker Maps as perturbations of a simple kernel
- Shuffling cards, factoring numbers, and the quantum baker's map
- A Canonical Quantization of the Baker's Map
- The modular multiplication operator and the quantized bakers maps