Short answer Yes. Shor’s algorithm admits substantial time–memory (depth–qubit) tradeoffs. There isn’t a single hard qubit threshold beyond which you suddenly can factor and below which you can’t. If you are “one qubit short” of a particular circuit layout, you can often recompile to save that qubit at the cost of longer runtime. However, there is a fundamental floor: you need on the order of n logical qubits to factor an n‑bit modulus at all. If you have fewer than about n + constant logical qubits, you can’t even represent the necessary register values, and no amount of runtime helps.

What the qubits are used for in Shor

• Output/value register: ≈ n qubits to hold residues modulo N (values 0,…,N−1). This is unavoidable.
• Control/phase-estimation register: textbook presentations use ≈ 2n qubits, but this can be reduced to a single qubit by using a semi-classical quantum Fourier transform (measure-as-you-go with classical feedforward).
• Arithmetic workspace (ancillas): used to implement reversible modular multiplication/exponentiation. You can trade these ancillas against circuit depth using known pebbling and in-place arithmetic techniques.

Known tradeoffs and qubit counts

• Semi-classical QFT (Griffiths–Niu): replaces the 2n-qubit control register with a single qubit used repeatedly, at the cost of serializing the phase-estimation steps. This slashes the qubit count by ≈ 2n with only a modest constant-factor time overhead.
• Low-qubit Shor implementations:
  • Beauregard (2003): 2n + 3 logical qubits using Fourier-basis arithmetic.
  • Häner, Roetteler, Svore (2017) and follow-ons; Gidney & Ekerå (2019): around 2n + 2 logical qubits with Toffoli-based arithmetic and other optimizations.
• Lower bounds: You need at least ≈ n qubits for the value register plus a few more to make the modular arithmetic reversible; Zalka argued a bound of n + O(1). Below this, factoring via Shor is impossible because you can’t represent the necessary quantum states.

What “one qubit short” means in practice

• If you are one qubit short relative to a specific circuit design, you can often:
  • Switch to a semi-classical QFT (if you weren’t already), saving ≈ 2n qubits from the control register.
  • Use arithmetic with fewer ancillas (e.g., in-place adders, pebbling/unncomputation), increasing circuit depth/gate count but freeing one or more qubits.
  • Use “dirty ancilla” techniques or serialize parts of the modular exponentiation to lower peak qubit usage.
• If you are below the inherent ≈ n + constant logical-qubit floor, you cannot make quantum progress on Shor’s order-finding at all; the machine is effectively as useless for this task as a very small (e.g., 2‑qubit) device.

About “making progress” with too few qubits

• You cannot checkpoint a quantum state to classical memory and resume later; intermediate quantum states can’t be saved classically.
• The algorithm already works by accumulating classical information across runs (each run yields phase bits that are combined via continued fractions). Time–memory tradeoffs let you restructure the computation so that fewer qubits are needed at any one time, but you still need enough qubits concurrently to hold the value register and perform reversible modular arithmetic.

Takeaways

• Time–memory tradeoffs absolutely exist for Shor’s algorithm. The large control register can be reduced to one qubit; ancilla usage in arithmetic can be pushed down at the cost of greater depth.
• Practical low-qubit designs use about 2n + O(1) logical qubits today. There is a theoretical floor around n + O(1). Below that floor, no progress is possible; above it, being “one qubit short” of a given design is usually fixable by redesigning the circuit, paying with more time. References: Griffiths–Niu (semiclassical QFT), Beauregard (2n+3), Häner–Roetteler–Svore (≈2n+2), Gidney–Ekerå (resource-optimized factoring).