13
$\begingroup$

This question is certainly somewhat opinion-based, but hopefully not hopelessly so.

The granddaddy of all applications for an efficient period finding or factoring capability (e.g. Shor's algorithm) is obviously breaking the public-key cryptography systems that currently encrypt Internet traffic.

But if we could eventually implement Shor's algorithm on a large-scale quantum computer, would it have any other useful applications, whether for pure math research or out in the "real world"?

This question is inspired by an essay by Boaz Barak, in which he mentions that he doesn't know of any reason why efficient factoring is inherently interesting other than for cryptography.

Two scope clarifications:

  1. I know that the quantum Fourier transform at the heart of Shor's algorithm has other potential practical applications, e.g. for solving large linear systems via the HHL algorithm, but I'm specifically wondering about period finding and factoring, and not general ultra-fast Fourier transforms.
  2. I know that the existence of an efficient quantum factoring algorithm has huge implications for computational complexity theory: it provides perhaps the strongest evidence we have (a) that BPP != BQP, (b) against the extended Church-Turing thesis, and (c) depending on your philosophical beliefs, perhaps against the real-world feasibility of building a fault-tolerant quantum computer. But I'm wondering about actually executing such an algorithm, not about its existence or properties.
$\endgroup$
0

1 Answer 1

10
$\begingroup$

I'm not sure about "real world", but studies around multiplicative functions (e.g., aliquot sequences) will definitely benefit from the availability of a fast factorization method. At very least it will allow to verify, refine, or refute existing conjectures with extensive computational evidence.

Also, there is a list of OEIS sequences "needing factors", which gives other examples of topics unrelated to cryptography but relying on integer factorization.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.