We analyze quantum computers which perform Shor's factoring algorithm, paying attention to asymptotic properties as the number L of qubits is increased. Using numerical simulations and a general theory of the stabilities of many-body quantum states, we show the following: Anomalously fluctuating states (AFSs), which have anomalously large fluctuations of additive operators, appear in various stages of the computation. For large L, they decohere at anomalously great rates by weak noises that simulate noises in real systems. Decoherence of some of the AFSs is fatal to the results of the computation, whereas decoherence of some of the other AFSs does not have strong influence on the results of the computation. When such a crucial AFS decoheres, the probability of getting the correct computational result is reduced approximately proportional to ${L}^{2}.$ The reduction thus becomes anomalously large with increasing L, even when the coupling constant to the noise is rather small. Therefore, quantum computations should be improved in such a way that all AFSs appearing in the algorithms do not decohere at such great rates in the existing noises.
We analyze quantum computers which perform Shor's factoring algorithm, paying attention to asymptotic properties as the number L of qubits is increased. Using numerical simulations and a general theory of the stabilities of many-body quantum states, we show the following: Anomalously fluctuating states (AFSs), which have anomalously large fluctuations of additive operators, appear in various stages of the computation. For large L, they decohere at anomalously great rates by weak noises that simulate noises in real systems. Decoherence of some of the AFSs is fatal to the results of the computation, whereas decoherence of some of the other AFSs does not have strong influence on the results of the computation. When such a crucial AFS decoheres, the probability of getting the correct computational result is reduced approximately proportional to L2. The reduction thus becomes anomalously large with increasing L, even when the coupling constant to the noise is rather small. Therefore, quantum computations should be improved in such a way that all AFSs appearing in the algorithms do not decohere at such great rates in the existing noises.
We demonstrate that, in the case of Shor's algorithm for factoring, highly mixed states will allow efficient quantum computation, indeed factorization can be achieved efficiently with just one initial pure qubit and a supply of initially maximally mixed qubits (Parker, S. and Plenio, M. B., 2000, Phys. Rev. Lett., 85, 3049). This leads us to ask how this affects the entanglement in the algorithm. We thus investigate the behaviour of entanglement in Shor's algorithm for small numbers of qubits by classical computer simulation of the quantum computer at different stages of the algorithm. We find that entanglement is an intrinsic part of the algorithm and that the entanglement through the algorithm appears to be closely related to the amount of mixing. Furthermore, if the computer is in a highly mixed state any attempt to remove entanglement by further mixing of the algorithm results in a significant decrease in its efficiency.
We study effects of imperfections induced by residual couplings between qubits on the accuracy of Shor's algorithm using numerical simulations of realistic quantum computations with up to 30 qubits. The factoring of numbers up to N=943 show that the width of peaks, which frequencies allow to determine the factors, grow exponentially with the number of qubits. However, the algorithm remains operational up to a critical coupling strength ϵc which drops only polynomially with log2N. The numerical dependence of ϵc on log2N is explained by analytical estimates that allows one to obtain the scaling for functionality of Shor's algorithm on realistic quantum computers with a large number of qubits.
Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.
We formulate and numerically simulate the single control qubit Shor algorithm for the case of static imperfections induced by residual couplings between qubits. This allows us to study the accuracy of Shor's algorithm with respect to these imperfections using numerical simulations of realistic quantum computations with up to nq=18 computational qubits allowing to factor numbers up to N=205193. We confirm that the algorithm remains operational up to a critical coupling strength ϵc which drops only polynomially with log2N. The obtained numerical dependence of ϵc on log2N is in a good agreement with the analytical estimates that allows to obtain the scaling for functionality of Shor's algorithm on realistic quantum computers with a large number of qubits.
In quantum systems of a macroscopic size V, such as interacting many particles and quantum computers with many qubits, there exist pure states such that fluctuations of some intensive operator A is anomalously large, = O(V^0), which is much larger than that assumed in thermodynamics, = O(1/V). By making full use of the locality, we show, starting from Hamiltonians of macroscopic degrees of freedom, that such states decohere at anomalously fast rates when they are weakly perturbed from environments.
Quantum computing, with its transformative potential in solving complex problems, faces a critical challenge: coupling with the environment and the consequent decoherence of quantum systems. This article examines the state of the art on the subject, providing a theoretical basis for understanding how environmental interactions impact quantum algorithms. Quantum coherence, a fundamental element of quantum mechanics, allows quantum states to exist in superposition. However, interaction with the environment triggers decoherence, resulting in the loss of this coherence and affecting the accuracy of the results of quantum algorithms. The study investigates the mechanisms of environmental coupling, such as interactions with photons, fluctuations in magnetic fields, and other external factors. Additionally, the impact of decoherence on notable algorithms, such as Shor's algorithm, is explored, analyzing its implications for the efficiency in determining results. Contemporary mitigation strategies, including quantum error correction techniques applied to this algorithm, are also discussed. The results highlight that decoherence represents a significant obstacle to the practical application of quantum computing in scientific, organizational and social problems. In parallel, a promising set of tools to mitigate or avoid the effects of decoherence is being developed, advancing the viability of quantum computers as applicable technologies.