Monthly Archives: February 2019

This article was inspired by a very nice article in Quanta magazine (by Natalie Wolchover) about the connection between error-correction codes and space-time. I thought the quantum mechanics concepts were glossed over, so decided to expand on it a little.

Electrical engineers and digital-signal-processing engineers study error correction for a simple reason – the same reason why we study language (both spoken and written) carefully for many years in school.

Ist bcuz wee somtmes rceeve grbled mssgses frm othrs tht we neeed to enderstnd, andd qickyly!

When the first efforts were made with digital computers, engineers realized that the problem of understanding garbled messages was slightly easier in a computer. The “language” is pretty simple – the alphabet is and “words” are of the ASCII variety with a fixed number of “letters”. While the number of “letters” in every word was ( digits) at the start of the system, it now extends to as many as letters. This has been achieved in a backward compatible way, which is why you have never had to “upgrade” your ASCII character set in your PC and can use a 20 year old Windows PC reasonably easily to read a newer Word document apart from a few newer encoded characters.

If I sent you the following -letter word , you might receive it with a one-bit error, as . How could you figure that there has been an error? The simplest solution involves appending a “parity” bit. You append a single digit (a or a ) to the word according to a simple formula. If the original word had an even number of ‘s, you append an extra . If the original word had an odd number of ‘s, you append a . This extra bit, called a “parity” bit, allows the system to automatically catch a single-bit error. Why is that?

In the above example, if the -bit word sent was , but was received as , you immediately know that there is an error in transmission. This would happen even if the one-bit error were to happen for the “check-bit” itself. At this point, you could ask for a new transmission of error-ridden words, or alternatively if you had the same word sent an odd number of times, perform a “majority” poll of the same word without an obvious one-bit error.

The theory of error correction is a mature area of engineering. It involves catching and correcting errors in more than one-bit, doing the same for errors that occur in bursts, so that successive 8-bit sequences have multiple errors each followed by relatively error-free intervals etc. Several interesting types of codes exist – for instance there is an entire family of error-correcting codes called Hamming codes, where a d-bit code can correct upto d-1 bit errors. These techniques are the reason why your phone calls don’t sound totally garbled, even when you call really long-distance over multiple types of transmission media. It is the basis of the wonder of modern communication.

Quantum computers take this theory to a new level. A quantum computer operates on the principle that a quantum system can be in several orthogonal (read “distinct”) states, or propagate along different trajectories, at the same time. This is called a superposition of states. Very roughly, the “state” of a computer is specified by the contents of its registers, its memory elements and the states of its various connections. A computation consists of letting the total state evolve according to a program.

Suppose some of these registers were quantum objects, then you could allow them to be in several states at the same time, each state serving as an input to a  program. If all these states fed the program together, the quantum computer would evolve all the states, producing the final output states, all in one giant superposition. The only problem would now be to extract the proper answer (maybe the shortest path through a maze) from this collection of answers. The extraction of the answer is not a trivial problem and is sometimes as difficult as writing the algorithm itself.

As an example of this superposition, if an electron were aimed at at two slits (slit and slit ) on a wall, to agree with subsequent observations, we have to assume that it is able to go through both the slits at the same time. The state of the electron after it passes the slits is written this way

Electrons possess a property called spin. They could be in an up-spin state or a down-spin state. Electrons are also completely indistinguishable from each other. If an electron is one of a pair of electrons, with total spin of zero (one is up and one is down), then each electron is in a superposition of up- and down-states. The state of each electron can be written as

which we can write as .

A quantum computer would have several such particles (say ). Let’s say they were in a correlated set of states, i.e., . The computation algorithm requires these states to stay uncorrupted, undisturbed, except acted upon by the program. Even if the program weren’t to run in the quantum computer, we might progressively notice changes in these states due to interactions with other particles from the outside, vibrations from a nearby highway etc.  These are errors – we don’t want anything but the actual program to change these states. If we had a one-bit error of the sort we saw before, we’d end up with one of the spins being flipped, so we could end up in any one of the states (first one flipped) , (second one flipped) or (third one flipped). To reliably use the quantum computer, we will need to correct the states to the starting one – and then we are faced with a problem common to quantum systems. If we “measure” the state in order to find which state is flipped, the quantum system “collapses” to one or the other state. Hence, in the first case where the first spin was flipped, we’d end up with either the state or which would be good except that we just disrupted our quantum computer.

We need to find a method to figure out which spin was flipped without actually collapsing the state, so that we can then apply a “quantum-friendly” approach (maybe using an appropriately placed magnetic field to flip a spin) to then bring the state back to its original “state”.

The lore in quantum mechanics (the way Nature really is) is that if you ask a question of a quantum system that allows it to maintain its anonymity, i.e., not require it to “collapse” into one of the states in its superposition, then the state stays in superposition. The way to do this is to “entangle” the state with another particle.

Suppose there were a particle that would end up in the “up” state if the above particles and were in the same state and in the “down” state if not. And let’s suppose there is another particle that would end up in the “up”  state if particles and were in the same state and in the “down” state if not. Let’s run these two “test” particles against the quantum computer’s particles in their pristine state, i.e., . You can quickly check that both the test particles would end up in the up-state as a result of their interaction with the above computer’s particles. Additionally, if you measured the states of the test particles, you cannot figure out the exact spins of the particles in the quantum computer. All you can find out is that particles and particles are in the same states. This allows the quantum computer’s particles to maintain their quantum “anonymity” and their state is undisturbed .

The interesting consequence results when you apply these test particles to the one-bit-error states (first one flipped) , (second one flipped) or (third one flipped).

In the first case, after interacting with the state , the first test particle ends up “down” with the second test particle “down” too.

In the second case, after interacting with the state , the first test particle ends up “down” with the second test particle “up”.

In the second case, after interacting with the state , the first test particle ends up “up” with the second test particle “down”.

These are distinguishable results, don’t affect the quantum state of the quantum computer and now can be used to gently bring  the one-bit error states back to their pristine condition, i.e., , so the quantum computer can continue to operate.

One-bit errors can thus be detected and corrected by this simple procedure, which is however quite ponderous to implement.

These ideas have connections to current theories of black holes that are best described in a future post.