The wonderful Shor algorithm really got things started in the field of quantum computing. It promises to split large numbers into their prime factors and so break most public key cryptography. However, we can all breathe a sigh of relief as it will be years before it is practical - or will it?

I am firmly of the opinion that the interest in quantum computers is really all about, and pretty much only about, breaking RSA, elliptic curve and similar cryptographic schemes. Despite there being lots of algorithms for essentially simulating physical systems - mostly oriented towards drug discovery - I really don't think that many of the current attempts at building a quantum computer would be funded without Shor.

Every quantum computing beginner is introduced to Shor's algorithm - usually towards the end of the Quantum Computing 101 course. You don't need that much understanding of how quantum computers work to appreciate Shor's algorithm, but it is subtle and, if you are like me, you spend a lot of time thinking about why it works. It really is yet another example of a quantum simulation, but one in which the ratios of numbers influence the physical outcome.

The problem with the algorithm is that it needs a lot of bits and gates to factor numbers with lots of bits. So many that it is well out of the reach of the sort of real quantum computers that we have built so far. At best we can factor 15 into 3x5, which isn't worrying in the slightest!

The problem is that the algorithm is very sensitive to noise and hence to make it practical we need error correction and even more bits and gates. Indeed the requirements are huge - estimates are that cracking a 2048-bit RSA key would need 4000 qubits and 10 million gates. This is likely to keep encryption safe for another 20 to 30 years if such a large machine is indeed practical.

Despite people thinking about it for 30 years, not much has happened until recently to improve Shor's algorithm, but now a paper by Oded Regev of New York University provides a significant reduction in the demands made on the quantum computer.

It is difficult to explain what the new idea is, but as the paper says:

"The algorithm can be thought of as a multidimensional analogue of Shor’s algorithm."

There is also a classical post-processing step that recovers the exact factors. To quote:

Theorem 1.1. Let N be an n-bit number and assume that for d = √ n and O(log n)-bit numbers b₁, . . . , b_d, there exists a vector in L \ L₀ of norm at most T = exp(O( √ n)). Then, there is a classical polynomial-time algorithm that outputs a non-trivial factor of N using √ n + 4 calls to a quantum circuit of size O(n ^3/2 log n).

The point is that we are getting a result by repeatedly using a smaller number of qubits and a classical algorithm to process the results. Shor's algorithm needs O(n²) gates so O(n ^3/2 log n) gates is a worthwhile reduction.

There are some disadvantages, however. In particular, the algorithm needs some sort of quantum memory to store intermediate results. Even so, it is the first improvement in 30 years and the principle could be applied to other quantum algorithms.

Of course, even if we can factor big numbers, it probably won't have the impact it might have had if it had been almost instantly possible. The reason is, that with a threat of quantum computers, everything that matters is moving to encryption methods that cannot be cracked using factoring. The main value will likely be reading old messages.

More Information

An Efficient Quantum Factoring Algorithm

Related Articles

Peter Shor Gains Frontiers Of Knowledge Award

Proof Of Quantum Supremacy? 

Quantum Computers Animated       

A Quantum Computer Finds Factors 

Solve The Riemann Hypothesis With A Quantum Computer

Boson Sampling Tests Quantum Computing       

$100,000 Prize For Proving Quantum Computers Are Impossible

NYT on the Future of Computing

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:1871962706>

<ASIN:B096MZY7JM>