(See the top of this set of postings.)
Obviously, the main thing we're talking about here is Shor's algorithm. I have not been privy to the conversations of cryptographers in creating post-quantum crypto, though we'll take a short look at that below. But there are very few people in the world who understand better than I do what it takes to actually run the full version of Shor's algorithm on a potentially real machine.
Obviously, the main thing we're talking about here is Shor's algorithm. I have not been privy to the conversations of cryptographers in creating post-quantum crypto, though we'll take a short look at that below. But there are very few people in the world who understand better than I do what it takes to actually run the full version of Shor's algorithm on a potentially real machine.
A full implementation of Shor's algorithm consists of two quantum phases: modular exponentiation, followed by the quantum Fourier transform. (I'm assuming you're familiar with the main ideas behind Shor, how it uses interference to build patterns in the quantum register that can reveal the period of a function that allows us to find the factors of a large semi-prime number.)
The key insight may be the behavior of the QFT, but the bulk of the execution time will be in the modular exponentiation phase. This is actually one of the areas that I worked on in my Ph.D. thesis.
Some of the important parts of this were published in Physical Review A.
In my thesis there is a plot that I think is useful, which we updated and published in our Communications of the ACM article:
https://m-cacm.acm.org/magazines/2013/10/168172-a-blueprint-for-building-a-quantum-computer/fulltext
We worked out detailed performance estimates, including hardware requirements and quantum error correction, in some of our papers:
and
There were other, contemporary important papers on how to implement Shor, including Fowler et al., https://arxiv.org/abs/quant-ph/0402196 who discussed Shor on a linear array, a few months ahead of my own Phys. Rev. A paper on the same topic.
We both built on important, early work by Vedral, Barenco and Ekert (VBE) and by Beckman, Chari, Devabhaktuni and Preskill (BCDP).
If you are looking to broaden your reading on implementations of Shor’s algorithm, the following are useful:
Pavlidis and Gizopoulous found an efficient division algorithm, accelerating the math.
Roetteler, Steinwandt focused on the applicability of Shor's algorithm to elliptic curve. I like the paper, except I think their survey of related research could have been better.
and Roetteler, Naehrig, Svore, Lauter:
Gidney and Ekera submitted to the arXiv a paper on factoring a 2048-bit number using 20 million noisy quibits. In this paper, one of their techniques is arithmetic "windowing" which is essentially identical to one of the techniques I proposed in my 2005 Phys. Rev. A paper. https://arxiv.org/abs/1905.09749
May and Schliper also recently uploaded a paper on period finding with a single qubit.
Ekeraa and Hastad also proposed a new period-finding algorithm variant, in 2017.
Smolin, Smith, Vargo wrote something of a warning about inferring too much from very simple demonstrations on a few qubits.
Here is one early paper on how to assess errors in Shor’s algorithm, by Miquel, Paz and Perazzo:
Chuang et al., also published an early examination of decoherence in factoring.
Among random things, there is Dridi and Alghassi, factoring on D-Wave; I don’t think this paper tells us very much about factoring at scale.
That's more than enough for now, since it isn't really the focus of what we're after here, anyway.
No comments:
Post a Comment