Can a quantum computer with insufficient qubits to factor an integer of a given size make any progress in factoring it? For example, what if a quantum computer is only one qubit short of what is necessary to attack a specific integer? Is it capable of making any progress in factoring it, or would it be just as useless as a 2 qubit machine? Assume qubits refer to logical qubits in a general-purpose cryptanalytic quantum computer with sufficient quantum error correction to solve the problem of decoherence.

Given that qubits can be thought of as the memory for quantum computers, I am essentially asking if time-memory tradeoffs are possible with Shor's algorithm when too few qubits are available.

  • 3
    $\begingroup$ This answer from Quantum Computing.SE gives some interesting references in the third paragraph. $\endgroup$ – kelalaka Mar 10 '19 at 8:59
  • $\begingroup$ Quantum computers, like classical ones, needs a minimum amount of memory to calculate any given pair of algorithm and input. This is why Turing completeness assumes infinite memory. Even quantum computers can only evaluate the the possibilities that fits in the qubit memory it has. Every algorithm and input has different limits, but it always exists. Exceeding the minimum necessary memory allows you to add further optimizations to attempt to improve performance. However, sometimes you can break the algorithm into smaller individual steps that each need less memory. $\endgroup$ – Natanael Mar 10 '19 at 23:14
  • $\begingroup$ Interesting question. One problem certainly could occur when you have less qubits than the number of the period $r$ ($a^r \bmod N$). This would probably mess up the inverse quantum fourier transform which amplifies the correct period (quantum wave interference), thus rendering the whole computation impractical. In that case you can't find $r$. $\endgroup$ – AleksanderRas Mar 11 '19 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.