Shor's algorithm with fewer (pure) qubits

2006/01/15 by Christof Zalka, Zalka, Christof · 2 citations
Computer Science · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata

paper · pdf · doi:10.48550/arxiv.quant-ph/0601097

openalex publication_date 2006/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Addition on a Quantum Computer

Cited by

• Parallel Spooky Pebbling Makes Regev Factoring More Practical
• Characterizing Space-Constrained Implementability of Quantum Instruments via Signaling Conditions

Related

• Implementation of Shor's Algorithm on a Linear Nearest Neighbour Qubit Array
• Using Shor's algorithm on near term Quantum computers: a reduced version
• Implementation of Shor Algorithm: Factoring a 4096-Bit Integer Under Specific Constraints
• Fast versions of Shor's quantum factoring algorithm
• A Modular, Adaptive, and Scalable Quantum Factoring Algorithm