Shor's algorithm with fewer (pure) qubits

Abstract

In this note we consider optimised circuits for implementing Shor's quantum factoring algorithm. First I give a circuit for which none of the about 2n qubits need to be initialised (though we still have to make the usual 2n measurements later on). Then I show how the modular additions in the algorithm can be carried out with a superposition of an arithmetic sequence. This makes parallelisation of Shor's algorithm easier. Finally I show how one can factor with only about 1.5n qubits, and maybe even fewer.

12 pages

References in corpus (3)

• Addition on a Quantum Computer
• Efficient factorization with a single pure qubit and $logN$ mixed qubits
• Factoring in a Dissipative Quantum Computer

Cited by in corpus (7)

• Pretending to factor large numbers on a quantum computer
• Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures
• Towards security recommendations for public-key infrastructures for production environments in the post-quantum era
• Gauge Theory Couplings on Anisotropic Lattices
• Logic Synthesis for Fault-Tolerant Quantum Computers
• Windowed quantum arithmetic
• Approximate encoded permutations and piecewise quantum adders