Introduction to Quantum Computing

As I have said before, from the very beginning, everyone knew that Quantum Computing was going to be revolutionary. Aside from the technical factors (orders of magnitude speed up, solving impossible problems), the romantic weirdness multiplier is massive. Computing is magical, Quantum Computing is practically mystical!

I, like everyone, and excited and ready for QC. But I don’t understand it.

For this reason, I was eager to read Johnathan Katz’s nice little tutorial, “How quantum mechanics can change computing[2].

The heart of the matter is, of course, the physics of atomic and subatomic particles, which is so different from familiar classical physics. Katz explains that “[t]he smallest unit of information in classical mechanics […] is the bit, which can hold a value of either 0 or 1”. Quantum superposition means that a quantum bit (qubit) can simultaneously hold the value of 0 and 1.

The second important difference is that classical bits are independent of each other, but qubits may be entangled. This is a form of instantaneous parallelism, by which a whole collection of qubits might be set at once. This raises the tantalizing possibility of solving a computation that takes zillions of bit operations, in just one step.

If that ain’t mystical, I’ll eat (and simultaneous have) my hat.

Building a system that physically implements qubits requires “operations and measurements to be done on a atomic scale”. I don’t know what all that means, but it is real, real hard. Current publicly announced Quantum Computers are in the range of a few qubits (your watch has millions of classical bits). Google has announced a 49-qubit computer by January, 2018, which is a the biggest acknowledged system.* (As far as I know, you may be able to rent time on a QC, but you can’t buy one.)

As I have noted, one of the earliest know uses for QC is in the realm of cryptography.  Much of contemporary computational cryptography depends on algorithms that are difficult to compute with conventional computers. The algorithms that secure the internet are secured by computations that are “too hard” to be broken.

But QC can crack those problems nearly instantly.**

In 1994, Peter Shor showed that quantum computers could quickly solve the complicated math problems that underlie all commonly used public-key cryptography systems

In short, the Internet is basically toast on the day that QC is widely available to break public keys.

QC can also be a defensive weapon, in the form of Quantum Key Distribution. Entangled qubits can be used to create an untappable communication channel, which could be used to securely transmit crypto keys. There are new demonstrations of this capability announced every day <<link>>, and I assume that national security services probably have even better systems.

There is a lot of current work developing “quantum safe” cryptography, most of which I don’t really understand. Old fashioned cryptography isn’t very intuitive, so I’m not surprised that QC gets wild.

In the cryptocurrency field, there are a few tentative steps toward “quantum safe” blockchains. To date, these are “non-Nakamotoan” systems, to coin a phrase. They claim to replicated the key properties of Bitcoin, but there are significant differences besides just the cryptography.

As Mark Anderson comments, there are multiple proposals and “not every solution to the quantum singularity is as promising as every other”. And, as I have suggested before, these solutions are not backward compatible to Bitcoin, and many people may not consider them to be a legitimate replacement.

Interesting times.  (Or maybe, the times are simultaneously interesting and not interesting!)


* I assume that major nation states may well have had much larger QCs for years, but these developments would be highly protected secrets.

** This is why national capabilities are likely to be deeply secret.


  1. Mark Anderson, qBitcoin: A Way of Making Bitcoin Quantum-Computer Proof?, in IEEE Spectrum – Tech Talk. 2017. https://spectrum.ieee.org/tech-talk/computing/networks/qbitcoin-making-bitcoin-quantumcomputer-proof
  2. Jonathan Katz How quantum mechanics can change computing. The Conversation.August 23 2017, https://theconversation.com/how-quantum-mechanics-can-change-computing-80995

 

One thought on “Introduction to Quantum Computing”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s