Since their conception, quantum computers have presented a fundamentally different way of processing information to that offered by classical computers.  While this opens up a wealth of opportunities for solving problems that are essentially intractable to classical computers, such opportunities can be both constructive and destructive.  This article will consider one of the most consequential of those opportunities – posed by Shor’s Algorithm – its impact on the world as we know it, post-quantum (or quantum-secure) cryptography, and the interaction with intellectual property (IP).

All this is possible because quantum computers use quantum bits, or ‘qubits’ (usually trapped atoms, ions, or molecules) whose state (e.g. energy of an electron) at any given time is uncertain, and hence fundamentally probabilistic.  This allows us to treat the qubit as being in a ‘superposition’ of those possible states, where each state in the superposition is weighted by its corresponding probability.  Then, by applying one operation to the whole system (e.g. by applying a very specific laser pulse), we can do computations on the whole superposition at once, e.g. by taking advantage of the structure of the energy levels available to our electron after the pulse is applied.  Theoretically, this could allow for absurdly efficient computation if used in the right way, as we will see shortly.

Shor’s Algorithm relates to the problem of finding factors of large numbers.  This may sound at first like an esoteric question confined to pure mathematics or theoretical computer science, but the difficulty of this problem for classical computers underpins much of modern cryptography.  In short: to computers, multiplication is glorified addition, which is computationally very easy and efficient; so generating large numbers (at least on the order of a thousand digits) by multiplying two or more smaller numbers together is not difficult.

However, taking the resulting composite number and finding its factors again is currently a problem which takes a prohibitive amount of computing power.  This is because classical computers don’t really have a better way of looking for factors than checking each possible factor in turn, which for large composite numbers is woefully inefficient.  It is important to note that such cryptography still doesn’t guarantee security – a hacker could get lucky or apply so much computing power to the problem that they might more quickly reach an answer – but it makes it sufficiently harder that most information encrypted via this method is functionally secure against classical computers.

Shor’s Algorithm presents the possibility of almost unrecognisably speeding up this process.  It is not fundamentally quantum-mechanical, as we will see, but it is particularly suited to the way quantum computers are able to manipulate superpositions to test many possibilities at once.

The first key observation at the heart of Shor’s Algorithm is that we are looking for a shared factor with our large number (which we will call N), so it is no problem if our guess g is a multiple of a factor of N, i.e. g=ab and N = ac, because such a shared factor is always reducible to a common factor of N (in this case a).

The other key observation is that, for any two coprime numbers g and N (i.e. ones that do not share any factors other than 1), it will always be the case that some power of g will be one more than a multiple of N.  Put mathematically, g^p = mN + 1 , and some simple rearranging gives us (g^p/2 + 1)(g^p/2 − 1) = mN .  Now each of the brackets on the left hand side looks like a factor of either m or N and, while the factors of m are not what we’re looking for, the algorithm still returns factors of N from an arbitrary guess g with a 37.5% success rate!  This means that if we run the algorithm ten times in a row, we are likely to hit a factor of N more than 99% of the time.

Bingo, they cry!  If the odds are so good, why is it not being done already?  The first trivial problem is that, for an odd value of p, we get a non-integer factor, which is not helpful; however, these are relatively easy to discard.  The more pressing problem is that, when N gets large, finding the right value of p such that g^p = mN + 1  is in fact also very computationally intense for classical computers – it’s another case of simply needing to try a large number of values of p to find the right one.

This is where quantum computers come in.  Ordinarily, one of the problems faced by quantum computers is how to encode the computation we want into a laser pulse efficiently and accurately in order to apply it to our system: happily, Shor’s Algorithm applies very neatly to quantum computers.  Without going into the physics of how the computation is actually done, the superposition we set up in our qubits represents a number of possible values of p all at once.  So, we might write the state of the system as the sum of each of those possible p states, i.e. |1>+|2>+|3>…

Then, taking advantage of another neat trick and measuring only the remainder of g^p  above mN and the fact that the remainders are consistent for values of p spaced by a given number x (i.e. g², g¹², g²² , etc. all give the same remainder when dividing mN, being spaced by x = 10), we use the wave-like nature of the superposition to interfere with itself, leaving only the answers we are looking for, i.e. remainders of 1 to give us factors of mN, as described above.

Once again, it looks like we have made it to the top of the hill, and this time we are much closer than before.  However, so far, researchers have not been able to build a quantum computer that is large enough to sustain a big enough superposition (|1>+|2>+|3>…) for long enough to run these computations.  Still, a number of researchers and policy-makers in the field are optimistic (or concerned!) that we may see a quantum computer that is able to run Shor’s Algorithm within the next 5-10 years.

Now, where does IP come into all this?  In general, algorithms themselves are not patentable, because (put simply) one person should not have the exclusive right to a mathematical expression, regardless of how complex it may be; however, computers that are configured to implement them are much more likely to be patentable.  This is codified in that computer-implemented inventions as such are excluded from patentability, but if they are implemented in such a way that the computer itself produces a new technical effect, it is much more likely to be patentable.

In terms of the present case, Shor’s Algorithm itself would not be patentable for that reason, but a new quantum computer able to sustain a large coherent superposition for a comparatively long time would involve a combination of physical components producing that effect that would much more likely be patentable.

It is also easy to overlook the reason that it is advantageous to apply for patent protection for technical advancements in the first place, particularly in rapidly developing fields.  The trade-off brought about by patents is that, on the one hand, the invention must be disclosed to the public sufficiently to teach others in the field a way of putting it into practice, while on the other hand, providing the proprietor with the right to prevent others from practising the invention for up to twenty years.  Publication generally only happens 18 months after filing an application, so while it is sometimes preferable to keep a concept or device secret (see our section on Trade Secrets), the advantage of moving first with that 18-month offset is still significant.  Equally, not doing so risks the idea being leaked and implemented immediately by third parties.  The subsequent benefit to society at large is then that third parties are able to learn from the published technical information, and thereby innovate further, while incentivising this innovation by protecting the rights of the innovators.

Of course, there are a number of other problems which quantum computers could advance to be configured to solve much more efficiently than classical computers, and protecting the intellectual property of those advancements is forming a rapidly burgeoning field.  At Dehns, we have a team of attorneys specialising in quantum work who are experienced in engaging with such emerging technology both on a detailed technical level, and also with respect to the practical and commercial considerations of clients developing such technology.

If you would like to find out more, please contact me (hcoop@dehns.com) or Dr Mark Bell (mbell@dehns.com) and we will be happy to discuss.