Imagine a world where the most widely-used cryptographic methods turn out to be broken: quantum computers allow encrypted Internet data transactions to become readable by anyone who happened to be listening. No more HTTPS, no more PGP. It sounds a little bit sci-fi, but that’s exactly the scenario that cryptographers interested in post-quantum crypto are working to save us from. And although the (potential) threat of quantum computing to cryptography is already well-known, this summer has seen a flurry of activity in the field, so we felt it was time for a recap.
How Bad Is It?
If you take the development of serious quantum computing power as a given, all of the encryption methods based on factoring primes or doing modular exponentials, most notably RSA, elliptic curve cryptography, and Diffie-Hellman are all in trouble. Specifically, Shor’s algorithm, when applied on a quantum computer, will render the previously difficult math problems that underlie these methods trivially easy almost irrespective of chosen key length. That covers most currently used public-key crypto and the key exchange that’s used in negotiating an SSL connection. That is (or will be) bad news as those are what’s used for nearly every important encrypted transaction that touches your daily life.
Not long after [Hitler] took control of Germany, his party passed laws forbidding any persons of Jewish descent from holding academic positions in German Universities. This had the effect of running many of the world’s smartest people out of the country, including [Albert Einstein]. Einstein settled into his new home in Princeton, and began to seek out bright young mathematicians to work with, for he still had a bone to pick with [Niels Bohr] and his quantum theory. It wasn’t long until he ran into an American, [Nathan Rosen] and a Russian, [Boris Podolsky]. The trio would soon lay before the world a direct challenge that would strike at the very core of quantum theory’s definition of reality. And unlike the previous challenges, this one would not be so easily dismissed by [Bohr].
Need a bit of catching up? You can check out Complimentarity as well as Tunneling and Transistors but that is just some optional background for wrapping your head around Quantum Computing.
The EPR Argument
On May 4th, 1935, the New York Times published an article entitled “Einstein Attacks Quantum Theory”, which gave a non technical summary of the [Einstein-Podolsky-Rosen] paper. We shall do something similar.
While the official title of the 5th Solvay conference was “on Electrons and Photons”, it was abundantly clear amongst the guests that the presentations would center on the new theory of quantum mechanics. [Planck], [Einstein], [Bohr], [de Broglie], [Schrodinger], [Heisenberg] and many other giants of the time would be in attendance. Just a month earlier, [Niels Bohr] had revealed his idea of complementarity to fellow physicists at the Instituto Carducci, which lay just off the shores of Lake Como in Italy.
The theory suggested that subatomic particles and waves are actually two sides of a single ‘quantum’ coin. Whichever properties it would take on, be it wave or particle, would be dependent upon what the curious scientist was looking for. And asking what that “wave/particle” object is while not looking for it is meaningless. Not surprisingly, the theory was greeted with mixed reception by those who were there, but most were distracted by the bigwig who was not there – [Albert Einstein]. He couldn’t make it due to illness, but all were eager to hear his thoughts on [Bohr’s] somewhat radical theory. After all, it was he who introduced the particle nature of light in his 1905 paper on the photoelectric effect, revealing light could be thought of as particles called photons. [Bohr’s] theory reconciled [Einstein’s] photoelectric effect theory with the classical understanding of the wave nature of light. One would think he would be thrilled with it. [Einstein], however, would have no part of [Bohr’s] theory, and would spend the rest of his life trying to disprove it.
Complementarity – Wave , Particle or both?
[Niels Bohr] contemplates one of [Einstein’s] many challenges to quantum theory.For more than a century it was thought that light was a wave. In 1801, [Thomas Young] had discovered interference patterns when shining a light through two very close slits. Interference is a well known property of waves. This combined with [Maxwell’s] equations, which predicted the existence of electromagnetic radiation put little doubt into anyone’s mind that light was nothing more, or less, than a wave. There was a very odd issue, however, that puzzled physicists during the 18th century. When shining light upon a metallic surface, electrons would be ejected from that surface. Increasing the intensity of the light did not translate to an increase in speed of the expelled electrons, like classical mechanics says it should. Increasing the frequency of the light did increase the speed. The explanation of this phenomenon could not be had until 1900, when [Max Planck] realized that physical action could not be continuous, but must be a multiple of some small quantity. This quantity would lead to the “quantum of action”, which is now called [Planck’s] constant and birthed quantum physics. It would have been impossible for him to know that this simple idea, in less than two decades, would lead to a change in understanding of the nature of reality. It only took Einstein, however, a few years to use [Planck’s] quantum of action to explain that mind-boggling issue of electrons releasing from metal via light and not following classical law with the incredibly complex equation:
E = hv
Where E is the energy of the light quanta, h is Planck’s constant and v is the frequency of the light. The most important item to consider here is this light quanta, later to be called a photon. It is treated as a particle. Now, if you’re not scratching your head in confusion right about now, you haven’t been paying attention. How can light be a wave and a particle? Join me after the jump and we’ll travel further down this physics rabbit hole.
