Questions to Ask About Any Quantum Algorithm for Factoring Semiprimes

Seemingly every month, a new report comes out for some purported advance in a quantum algorithm to factor semiprimes, but these reports never concisely and clearly, most of the critical details that are needed to reasonably evaluate the value and utility of these purported advances. This informal note offers a relatively simple set of questions to ferret out the most important and useful details.

Although my focus is Shor’s original semiprime factoring algorithm as published by Shor himself, there can be adaptations, derivatives, or alternatives that have varying degrees of fidelity to Shor’s original paper.

In any case, these basic questions and considerations are relevant to all purported implementations of Shor’s factoring algorithm — or alternative algorithms.

1. How large a (small) semiprime can the given factoring algorithm factor on the best current quantum hardware?
2. How far must current hardware advance before it can factor ANY relatively small semiprime, like 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 44, 48, 50, 56, 64, 72, 80, 96, 100, 128, 160, or 256 bits, even far short of anything considered cryptographically relevant. Besides qubit count, what error rate, maximum circuit depth (implying maximum coherence time divided by gate execution time), maximum circuit size, and how fine a granularity of qubit rotation are required even to cope with these relatively small semiprimes, let alone larger semiprimes, still far short of cryptographically-significant semiprimes?
3. What is the largest semiprime that can be factored by the algorithm running on a quantum simulator? Maybe separate cases for running on a laptop, a high-end desktop, a standard high-end commodity server, and running on a specialized GPU-based system.
4. What adaptations were made beyond what was contained in Shor’s original paper? A brief summary.
5. Do the authors consider their algorithm to be 100% true to Shor’s original algorithm, as published? If yes, that’s a problem since the proposed algorithm was incomplete, with gaps, and was more of an outline than a finished, polished, implementable algorithm, and that most of the discussion now is focused on ALTERNATIVES to Shor’s original factoring algorithm that are HYPOTHESIZED to be somewhat more implementable, and that are related to Shor’s original factoring algorithm in name only, and only SOME of its original math. Paying homage to Shor is admirable, but not so practical, and very misleading.
6. Separate from what the authors actually say, what do other experts say about what the algorithm is or isn’t relative to the algorithm as originally published by Shor? Is it the original, an adaptation, a derivative, or an alternative algorithm?
7. How many shots and how does that scale with the semiprime size (bit count)? Especially for the smaller semiprimes listed previously above. How many shots per trial random base? How many random bases are likely to be required? Again, as the size of the semiprime scales.
8. How many bits does the quantum Fourier transform need to produce, accurately, to obtain the correct order? How does this scale relative to the input size?
9. How many terms does the quantum Fourier transform require to calculate each bit of the resulting bits of the transform? How does this scale relative to the input size?
10. Does the quantum circuit portion of the algorithm deterministically, reliably, produce the order, or is significant classical post-processing needed to massage the circuit result to infer the order, maybe even requiring additional shots or retrying with a fresh random base?
11. Does the algorithm suffer from the halting problem, since there is only a probability that a given random base will produce the correct order? Or does it have a hardwired cutoff and then some probability and frequency for failure to factor the input semiprime, and how does the cutoff, probability, and frequency scale relative to the input semiprime size (bit count)?
12. How does the algorithm behave with respect to malformed input? Cases should include not a semiprime, prime, composite with more than two factors, prime power, zero, one, has leading zeros, has trailing zeros, all ones — a Mersenne semi-prime, technically okay, sort of, but dubious, power of two — all zeros but one bit on, technically a prime power, excessive length well beyond maximum semiprime size that the combination of algorithm, machine, and any configuration limits can handle. Does the algorithm produce a clear error code for each case of malformed input?
13. How deep an analysis does the paper do for potential for denial of service attacks for a system using the factoring algorithm — that processing a malformed, or even correctly formed input, could cause the system to malfunction or possibly hang in an infinite loop?
14. Does the algorithm perform better when p and q are close to the same length, or when their lengths are very different?
15. When simulating the algorithm for small semiprimes, with what frequency does it fail to find a factor for a given random input base? What is the maximum number of retries to find a factor for a given input semiprime — how many random bases need to be tried?
16. Does the paper do an explicit — and credible — analysis of what granularity of qubit and gate rotation the algorithm requires and compare that to what granularity of rotation can be achieved on any current and projected real quantum computer. At present, NOBODY bothers to characterize this metric for current hardware let alone project it for realistic future hardware, let alone characterize it theoretically.

These questions should be applied to:

1. Published papers for semiprime factoring algorithms.
2. Press releases for semiprime factoring algorithms.
3. Technical media articles for semiprime factoring algorithms.
4. General media articles for semiprime factoring algorithms.
5. Social media posts referring to semiprime factoring algorithms.
6. Conference presentations and panel discussions referring to semiprime factoring algorithms.
7. Cocktail party discussions of semiprime factoring algorithms.

There’s still way too much hand-waving required for a venture which should be practical and not require ANY hand-waving.

Wild claims that factoring of cryptographically-significant semiprimes can or will or even might be or become practical completely undermine the credibility of this venture. No one should be seduced by all of the hand-waving and dubious and unproven assumptions. But, alas, so many are!

Maybe have we at least advanced to the level where people might be willing to admit that Shor’s original factoring algorithm can NEVER be implemented on any real current, projected, or even theoretically possible quantum computer, in part because the proposed algorithm was incomplete, with gaps, and more of an outline than a finished, polished, implementable algorithm, and that most of the discussion now is focused on ALTERNATIVES to Shor’s original factoring algorithm that are HYPOTHESIZED to be somewhat more implementable, and that are related to Shor’s original factoring algorithm in name only, and only SOME of its original math? Paying homage to Shor is admirable, but not so practical, and very misleading.

References

• References for Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer
• https://jackkrupansky.medium.com/references-for-shors-algorithm-for-cracking-strong-encryption-using-a-quantum-computer-6c87edec0d9e

For more of my writing: My Five Main Areas of Focus.