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

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.

Figure 1

The nearest-neighbor spacing distribution of eigenangles from an ensemble consisting of 5115 level spacings for the case when the first register has $10$ qubits and the number to be factored is $29$. The smooth curve shows the circular unitary ensemble (CUE) distribution of random matrix theory.

Figure 2

The intensities of a typical eigenstate of the operator $F^{-1}{\Lambda }_{j}H$ for the same case as in Fig. 1. The complete eigenstate of the unitary part of Shor’s algorithm is a tensor product of such states with eigenstates of the shift permutation operator.

Figure 3

The cumulative distribution $\xi \left(x\right)$ of the intensities of the eigenstate shown in Fig. 2, these being normalized so that the mean is unity. Shown as a smooth curve is the random matrix theory expectation $1-e^{-x}$.