The Shor algorithm leverages quantum parallelism to reduce the time complexity of integer factorization to polynomial level, yet its core component—the controlled modular multiplication gate—suffers from high circuit depth \(O(n^{2} )\) and substantial resource consumption, which hinder practical implementations. This paper presents a qubit parallelism - based optimization scheme that decomposes bit - by - bit weighted sums into independently controlled parallel modular addition operations, constructing a simultaneous addition gate array and achieving efficient accumulation through reversible modular arithmetic units. Specifically, the scheme designs a collaborative mechanism among control, accumulation, and auxiliary registers: each bit of the control register independently governs a double - controlled modular addition gate, enabling parallel execution of \(n\) - channel addition operations via quantum state superposition to eliminate the sequential timing dependencies of traditional architectures. The overflow flag of accumulation results is extracted using quantum Fourier transform (QFT), and modular subtraction is performed in parallel based on the highest - bit signal to ensure the correctness of modular arithmetic. Theoretical analysis demonstrates that this approach reduces circuit depth from the exponential \(O(n^{2} )\) of conventional sequential structures to linear \(O(n)\) , and optimizes the number of gate operations from \(O(n^{2} k_{\max } )\) to \(O(nk_{\max } )\) . By introducing \(n\) auxiliary qubits, it achieves polynomial - level depth optimization, providing an efficient implementation pathway for highly parallel quantum hardware.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Optimization of Shor's Algorithm Based on Quantum Parallelism

  • Shuaishuai Zhu,
  • Ming Yuan

摘要

The Shor algorithm leverages quantum parallelism to reduce the time complexity of integer factorization to polynomial level, yet its core component—the controlled modular multiplication gate—suffers from high circuit depth \(O(n^{2} )\) and substantial resource consumption, which hinder practical implementations. This paper presents a qubit parallelism - based optimization scheme that decomposes bit - by - bit weighted sums into independently controlled parallel modular addition operations, constructing a simultaneous addition gate array and achieving efficient accumulation through reversible modular arithmetic units. Specifically, the scheme designs a collaborative mechanism among control, accumulation, and auxiliary registers: each bit of the control register independently governs a double - controlled modular addition gate, enabling parallel execution of \(n\) - channel addition operations via quantum state superposition to eliminate the sequential timing dependencies of traditional architectures. The overflow flag of accumulation results is extracted using quantum Fourier transform (QFT), and modular subtraction is performed in parallel based on the highest - bit signal to ensure the correctness of modular arithmetic. Theoretical analysis demonstrates that this approach reduces circuit depth from the exponential \(O(n^{2} )\) of conventional sequential structures to linear \(O(n)\) , and optimizes the number of gate operations from \(O(n^{2} k_{\max } )\) to \(O(nk_{\max } )\) . By introducing \(n\) auxiliary qubits, it achieves polynomial - level depth optimization, providing an efficient implementation pathway for highly parallel quantum hardware.