Physics - Spotlight of Exceptional Research

[Picture taken from the article: Is there a true supersolid phase transition?]

The American Physical Society (APS) is well known for probably the most traditional series of physics journal, but recently (not that much, but more or less) they made available in their website a feature that I have been enjoying a lot, which goes by the name Physics - Spotlight of Exceptional Research.

This webpage is regularly updated with headlines about notable papers published in their Physical Reviews journals. The best thing is that the papers are then commented by a specialist in the area and made available for free download! The accompanying comment is also downloadable in PDF format if you want. This is a fantastic feature specially for those who for any reason don't have access to the paid subscription of the journals. The current for headlines highlighted in the front page are:

• Blurry vision belongs to history, Hans Blom and Jerker Widengren: Making simple modifications to laser-scanning microscopes—like those found in many laboratories—can beat the classical diffraction limit by a factor of 2.
• Ultrafast computing with molecules, Ian Walmsley: Vibrations of the atoms in a molecule are used to implement a Fourier transform orders of magnitude faster than possible with devices based on conventional electronics.
• Is there a true supersolid phase transition?,  Sébastien Balibar: New measurements of the rigidity of solid helium show that the emergence of supersolidity is actually a crossover, rather than a true phase transition.
• The tetrahedral dice are cast … and pack densely, Daan Frenkel: Magnetic resonance images of tetrahedral dice show a density of random close packing, in agreement with recent calculations.

And yesterday I received an email from them about some videos they made available in this webpage as well. They can be watched in here. Currently they show three videos from a metting that happened in the 17th of March:

• Optomechanical Devices, Florian Marquardt: The interplay of light and mechanical motion on the nanoscale has emerged as a very fruitful research topic during the past few years. Optomechanical systems are now explored as ultrasensitive force and displacement sensors. By using light to cool a mechanical system to its quantum ground state, researchers hope to explore the foundations of quantum mechanics in a new regime.
• Spintronics, David Awschalom: The spin-orbit interaction in the solid state offers several versatile all-electrical routes for generating, manipulating, and routing spin-polarized charge currents in semiconductors. Recent experiments have explored several guises of this effect for the nascent field of spintronics. These include new opportunities for making the transition from fundamental studies to a spin-based technology for classical and quantum information processing.
• Iron Age Superconductors, Michael Norman: A new class of high-temperature superconductors has been discovered in layered iron arsenides. In these materials, magnetism and superconductivity appear to be intimately related. Results in this rapidly moving field may shed light on the still unsolved problem of high-temperature cuprate superconductivity.  

I haven't had the time to watch any of the videos yet, but I intend to do that over the weekend. They seem quite interesting. If someone watched them and wants to comment a bit, you will be very welcome.

Jay Walker's Library of Human Imagination

Jay S. Walker is an American internet intrepeneur. This is a video of the library he constructed for his amusement. The items in the library are original. Isn't good being rich? Via Open Culture.

Read more about it here:

• The Walker Library of Human Imagination,  Open Culture
• Browse the Artifacts of Geek History in Jay Walker's Library, Wired
• Jay Walker's library of human imagination, TED
• The Walker Library of Human Imagination, Walker Digital

Statistical Physics and Error-Correcting Codes #1

As I have been working on the statistical physics of error-correcting codes since 2006, I guess it is only fair to write a bit about that. Although it may not seem as appealing as cosmology, strings or the LHC, there is something fundamental and interesting behind it. Besides, since I started to talk about quantum codes I thought I should write something more basics about classical error-correction and information theory as they are the basis for the their quantum versions.

Since I will have to introduce some information theory first, I thought it would be a better idea to break down this post into two or three parts, depending on how it goes. The standard reference for information theory is Thomas and Cover book:

[1] Elements of Information Theory, Thomas and Cover

The basics of error correction theory is very simple. The so-called sender wants to transmit some information, be it a word, a song or a picture, to someone usually called the receiver. However, some part of that information may be lost during the transmission. We say that the information is being transmitted by a noisy channel. To give a non-orthodox example, if you burn a CD (like the one in the figure above) with some songs to give to a friend but accidentally you scratch the surface of the disc, some of the data will not be correctly read by the laser head. What do you do to avoid losing the information?

Every human language has already the basic required feature for error-correction, something we call redundancy. Can you r**d th*s phr**e withou* some of t*e le**ers? You can because every language has some degree of redundancy, which means, information is encoded with much more symbols than it is really needed. Because of this, if you loose some of the symbols, you still can manage to understand the original message. In the case of a language, redundancy is a very intricate thing for even if there are entire words missing from a document, you can still retrieve them.

Erasing a symbol (or some), like I did above, is not the only way of corrupting a message. Letters can be scrambled, exchanged for others and, unlike the example I gave, they may be corrupted without you even knowing exactly where it happened.

Error-correction is the driving force behind the digital revolution, simply because it is much easier to correct binary messages and then error correction is much better. For digital messages, which are simply composed of 0's and 1's, errors can be reduced to 2 types: erasure, when you simply cannot read which symbol is there, or flipping, when a 0 becomes a 1 and vice-versa.

The simplest, most naive technique of error-correction is called a repetition code. If your message is 1, then you just repeat it many times, like 111. If the amount of errors is small, for instance 1 in each 3 symbols is corrupted in the example above, you can retrieve the original message by looking at the majority of bits. It means that if you receive 110 instead of 111, you know what the correct message is just by looking to which symbol is the majority. If the noise (the amount of errors) is larger, you need to add more redundancy. For example, if the probability of flipping a bit is 2 in three, you need to use at least 5 copies of the symbol to be able to retrieve the original message. The result of the original message plus the redundancy is what we call the codeword.

Of course you have already noticed that to protect against many errors using the repetition code we need to repeat the symbol many times. The ratio R=N/M of the size N of the original message to the size M of the codeword is called code rate. The code rate is always between zero and one and we obviously want to make it as close to one as possible. For example, in our repetition codes the first code rate was 1/3 and the second was 1/5. It is obvious that the higher the redundancy, the lower the code rate. This is the main dichotomy of codes: we want to add as much redundancy as possible but keep the codeword as small as we can.

It's easy to see that repetition codes give too low code rates, their not very efficient. The next level of the game is named linear codes. A codeword in a linear code is simply the result of multiplying the original N-sized (binary) message m by a binary matrix G, of size M×N to get the M-sized codeword t. Mathematically speaking, we have just t=Gm. G is called the generator matrix. Okay, but how does it help? Well, there is another piece missing and that is the star of the play, a matrix A called the parity-check matrix. A is also binary and is chosen in such a way that AG=0. Now, if you apply the parity-check matrix to the codeword, you can easily see that the result is zero.

I need to make an observation here. All the operations with these matrices and vectors are supposed to be on the binary field, a.k.a. the Galois Field of order two or GF(2). I am saying that because things can be more or less generalised to higher order finite fields (another name for a Galois field), but that's too ahead of us now.

The parity-check matrix has this name because it can be seen as a constraint on t that forces some chosen combination of entries in it to add to zero (addition mod 2, for we are still talking about the binary field). A binary sum of this type has only two possible results, 0 or 1. As we can associate it to a number being even or odd, we end up calling this value the parity of this sum and then we say that we need to check that the parity is 0.

Let us now model the noise in the channel, where by channel I just mean the medium through which the information is being transmitted. Look at the simplest possible model which is called the binary symmetric channel, where each bit of your message can be flipped independently with probability p. To flip a binary number you just need to add 1 to it, for in the binary field the addition is defined by 1+1=0, 1+0=1, 0+0=0 and 0+1=1. So, we can model the noise in our transmitted codeword by adding to it a vector of zeros and ones, a binary vector, that we call the noise vector n and where each bit has probability p of being one. Let us now consider the received message that we will call by the letter r. In our notation, we then have

r=t+n, (1)

One thing that you should notice is that if we add the noise vector to the received vector, we get back the transmitted codeword, clean and uncorrupted. Why? Because of the addition rule I gave above. Note that any number added to itself result in zero. That means that n+n=0 and r+n=t+n+n=t. That means that if we can discover n we can recover our codeword. Now, you probably already noticed that this does not help because I am just restating the problem in a different way. Just that. We still have nothing from which we can recover the message. But now, apply A to both sides of equation (1). Then we end up with what we call the error syndrome:

z=Ar=An. (2)

You may or may not have noticed already, but now we are talking! The parity check matrix is something that both sender and receiver know. The received message is what the receiver has after all. Therefore the receiver can do the above operation and calculate the syndrome. With that, equation (2) gives you a set of linear equations that can in principle be solved to find n and therefore the original codeword t. Of course there are many subtleties, I will talk about them a little in the next posts. The bottom line however is that parity-check codes are much more efficient than repetition codes. Actually, they seem to be at the moment one of the most efficient, if not the most, error-correcting codes.

What is the relationship with physics? We are not ready to appreciate it yet, but just notice that we have here a system where each variable can have two values, more or less like an electron spin, and they must obey a constraint. The constraint relates one variable to the other, or you may say that these variables "interact" is some sense. I will leave you to think a bit about that before spoiling the surprise completely.

Errors as Anyons

[Picture taken from: songshuhui.net]

As promised, I will explain here how anyons are related to the errors in the toric code. I will rely heavily on what is in chapter 9 of Preskill's online lecture notes on quantum computation that can be found here:

[1] Chapter 9 - Topological Quantum Computation, Preskill, J.


Actually, I found that the introduction to anyons in Preskill's lectures is much more pedagogical than in the previous paper from Rao that I linked to. If you do not remember what the heck I am talking about, I suggest you to go back to the posts Kitaev's Toric Code and Anyons to refresh your mind. In the first of these posts, I explained that the toric code was defined by a set of stabilizers defined as plaquette and star operators on a square lattice in the surface of a torus. The spins, each one being just the mental image of a two-level quantum system, live on the edges of the lattice and are responsible for storing the quantum state we want to preserve.

Due to the characteristics of the set of stabilizers, we saw that the whole torus can only store 2 qubits, no matter what size it is. These 2 qubits correspond to the 2 non-trivial topological cycles of the torus, i.e., closed loops that cannot be continuously shrunk to points.

Actually, the way I described it, our torus is what is called a quantum memory. Its aim is to keep the two qubits stored for as long as we want, as if it was a quantum hard disc. It turns out that errors in the encoded message occur when the spins are changed from their original configuration. As the encoded message is defined as the ground state of the Hamiltonian, which itself is defined as minus the sum of all star and plaquette operators, when one qubit suffers an error the energy is increased by two for each operator that changes its measured value. This is because being products of the spins, the operators have only two possible eigenvalues, which are also the possible measured values, +1 and -1.

When an error occur, be it a Z or X error, the measured value of the two operators of the relevant kind (A or B) that contain that edge becomes -1 and the energy increases by 2×{-[(-1)-(+1)]}=4. Well, many times the Hamiltonian is rescaled such that the energy difference has a specific value, but that is not important now.

Before I continue there is one more piece of physics that I need to talk about. It's the Aharonov-Bohm effect. This is a quantum effect where a charged particle's wavefunction gains a phase when the particles goes around an infinite solenoid where an electric current is flowing. This infinite solenoid is just the physical way of constructing what is called a flux tube, which means that inside the solenoid there is a magnetic field that never goes outside. It has an effect on the particle because nowadays we know that the vector potential, which is the spatial part of the gauge field associated with electromagnetism, is more fundamental than the electromagnetic field and the vector potential exists outside the flux tube.

Back to the toric code, the beautiful thing is that whenever a Z-error occurs, which means that the |0> in the quantum state of the qubit becomes |1> and the |1> becomes |0>, this can be seen as a pair of "charged" particles being created in the two vertices connected by the link. Similarly, when an X-error occurs, which changes the sign of the relative phase between |0> and |1>, we can see this as the creation of flux tubes in the plaquettes which have this link as a common boundary. Flux tubes and charges are not anyons if considered isolated, but as in the Aharonov-Bohm effect, when a charge goes around a flux tube in a closed path, a loop, it turns out that its wave function is multiplied by -1. Bosons' and fermions' wavefunctions should not gain a phase if we move the particle in a closed loop taking it back to the initial place. Conclusion: the errors are actually anyons (when one kind is compared to the other).

Of course I am cheating a lot because I am not explaining the details, but for those who want to follow them, Preskill's notes and Kitaev's original paper are the recommended readings.

But the story does not end here. What about error-correction? That is the central aim, right? How does it work?

Error-correction is accomplished in the toric code by bringing two anyons together. What happens is that when they encounter each other, they annihilate and depending how this is done, the error is corrected. The important thing here is that anyons need to be annihilated in such a way that the path traced by them is a trivial cycle on the torus. If they annihilate after going around a non-trivial cycle, then the error remains! You can even annihilate anyons from different initial pairs as long as their total paths do not involve non-trivial loops.

You may quickly perceive that the solution to control errors in our code is: do not let the anyons go to far away from each other once they are formed! This way, they will not have gone around dangerous cycles on the torus and everything will be alright. So, you only need to increase the size of the torus, right? Then the anyons would take too long to travel through a non-trivial loop.

It turns out that it's not so simple (in quantum mechanics, it never is...).  In the following very nice (but articleless) paper

[2] Can one build a quantum hard drive? A no-go theorem for storing quantum information in equilibrium systems, Alicki and Horodecki [arXiv:quant-ph/0603260v1]

the authors argue that at a non-zero temperature it does not matter the size of your system, you will not be able to get rid of the errors. They give many arguments, in particular they say that if this was possible, the system would violate the second law of thermodynamics. In essence, the only states that could store some information would be classical states, which cannot store quantum superpositions.

Their conclusion is that you cannot have a quantum hard drive, store information in it and leave it there. The information will always leak unless you spend energy to keep it that way. This is dismaying as it shatters the dream of quantum information storage. However, we know that being mortals we only need to store information for a reasonable amount of time. For instance, I am pretty sure I don't care about what is gonna happen to my files after the next 300 years. So the idea is to try to increase the storage time reasonably. I've been talking to the quantum information group in Leeds about the subject and we had some nice ideas, but that is something I will write about in another opportunity. 

Condensed Matter Blogs

[Picture taken from the San Diego State University Website]

If you follow physics blogs in the internet you probably read Cosmic Variance, Backreaction, Not Even Wrong The Reference Frame etc. That's okay, I read them too. They are basically Cosmology and High Energy Physics blogs though and there is a part of physics that is not probably well represented there: Condensed Matter Physics.

For those to whom this word may seem unfamiliar, condensed matter is that part of physics that deal with how matter behaves when you have a lot of it. Superconductivity, superfluids, metals, crystals... they are all subjects of condensed matter. These are thrilling topics as well and there are many wonderful things in this area that does not appear in those above cited (and side listed) blogs. That's why I am listing two very interesting blogs about the subject below and I myself will try to write more articles in this area. The two blogs are:

1. Nanoscale Views (http://nanoscale.blogspot.com/), by Douglas Natelson
2. Condensed Concepts (http://condensedconcepts.blogspot.com/), by Ross H. Mackenzie

Take a look at them. Browsing around these blogs you will understand how exciting condensed matter can be. Many important concepts in physics have their origins in condensed matter, like symmetry breaking for example, and the field is full of unsolved and intriguing problems. I will finish this flash post with a list of subjects that have been around for some time but are still hot today and that you will probably see them in those blogs and in mine as well:

• Supersolidity
• High Temperature Superconductors
• Spin Glasses
• Graphene
• Topological Order
• Quantum Phase Transitions
• Optical Lattices
• Fractional Quantum Hall Effect
• Anderson Localisation

Look around and have fun!

Symphony of Science

The above video, which I found reading the Portuguese blog BioTerra, is one of a series from a website named Symphony of Science which according to their own description

is a musical project headed by John Boswell designed to deliver scientific knowledge and philosophy in musical form. Here you can watch music videos, download songs, read lyrics and find links relating to the messages conveyed by the music.

The project owes its existence in large measure to the wonderful work of Carl Sagan, Ann Druyan, and Steve Soter, of Druyan-Sagan Associates, and their production of the classic PBS Series Cosmos, as well as all the other featured figures and visuals.

Enjoy.

50 Years of Laser

1960, exactly 50 years ago, is officially the year when the laser was born. At that year, Theodore Harold Maiman constructed the first working ruby laser at Hughes Research Laboratories in the USA. Although the historical paper

[1] Maiman, T.H., "Stimulated Optical Radiation in Rubi", Nature 187, 493-494 (1960)

published on the 6th of August has only one author, I would think that he probably had a team to construct it and did not do everything alone. About the paper, you can find a nice excerpt written by the other laser pioneer Charles H. Townes, which actually won a Nobel Prize for it, named The First Laser.

In Towner's excerpt, you can read the famous quote about the laser as being a "solution looking for a problem". The meaning is not that nobody was thinking about possible applications, but that the applications were not the objective of the research. This idea seems heretical today, researching without practical objective?, but that is only a consequence of the New Dark Age mentality that is becoming stronger each day. I will write a future post about that soon, but just look around today and see how your life would be without the laser before criticising pure research, although I know that this advice will unfortunately be just ignored by most people...

Back to good things, the festivities include Physics World giving a sample copy of its commemorative issue on the 50 years of the laser on their webpage: Physics World magazine: May 2010 special issue and New Scientist publishing a cool picture gallery about the subject with the first photo being the one I put above, which is from the first laser taken by Kathleen Maiman (which surely must be a realtive of  Theodore, but I am not sure at what level). The Nobel Prize foundation also has special pages about the laser called Laser Facts. And finally, there is also an editorial in Nature about the laser: Laser-guided impact.

Albert Fert Answers

The above YouTube video is one of the series of videos uploaded by the Nobel Prize Foundation into their YouTube channel where Albert Fert answers questions made by many different persons (I have even seen one Second Life avatar asking one in one of the videos). The series can be watched: Answers from Alber Fert.

Albert Fert won the Nobel Prize of Physics in 2007, together with Peter Gruenberg, for the discovery og the Giant Magnetoresitance (GMR) effect in 1988, which he explains in a very simplified way in the above embedded video. The Nobel Prize website is quite good and you can find not only a lot of information about him in the 2007 Physics Prize page but also a downloadable video with his Nobel Prize Lecture.

GMR is the effect of decreasing of the electric resistance of a material in the presence of a magnetic field. It's giant because the resistivity can drop up to 80%. The effect is very well explained in the Wikipedia article linked above and by Albert Fert itself in the videos (in particular the one I put in this post). It is used comercially in read heads of hard disk drives, this being actually the application that made this discovery so important.

Anyons

I started to talk about the toric code some time ago (see Kitaev's Toric Code) and finished writing that errors in the codeword, which if you remember was constructed using spins on the surface of a torus, can be interpreted as pair of quasiparticles which behave like anyons. Although every physicist reading this knows what a quasiparticle is since their first Ashcroft and Mermin reading (the book linked to at the left, which I like a lot), I believe that for a broader audience this term is not entirely familiar.
 

So let me try to explain it before going to anyons. A quasiparticle is not supposed to be a "real" particle, at least in the sense that it is not an elementary particle or a bound state of elementary particles, although I know that the philosophers out there will pick on me because of this statement.

At the most fundamental level, nature is described by a quantum theory of fields, QFT for short. In this model of reality, the world is composed of fields and the elementary particles is what we detect when those fields are not in their ground state, which means, they have energy above their minimum energy levels. These excited states are described by the action of operators, mathematical functions acting on vectors, that create and anihilate a certain number of particles in the system when acting on a vector representing the lower energy state |0>, which we call "the vacuum" for obvious reasons (there are no particles).

The mathematical entity that embodies the features of the system is called the Lagrangean and can be written in a certain specific way using the creation and annihilation operators. In some situations, specially more complicated systems like condensed matter ones, there is a way to write the Lagrangean in a mathematical analogous form in terms of some sort of creation/annihilation operators. Although they don't appear because of "real" particles in the system, they have all the mathematical structure the real ones have. These operators create excited levels that are analogous to the particle states and that is how they end up being considered as (quasi-)particles. The term seems to have been coined by Lev Landau, one of the greatest physicists of the last century whose name didn't make its way to the world media.

I know what you must be thinking now... How do we know that our elementary particles are not quasiparticles in some medium, say, the aether. Well, some people have proposed that and there is an entire book written by a a very competent physicist (although I am not trying to make use of an authority fallacy here...) about the subject:

[1] The Universe in a Helium Droplet, G. Volovik

But let's not loose the focus here. Now it became clear why we call our errors quasiparticles. They are obviously not any kind of elementary particle travelling around in our system, but can be mathematically described as such. Let's move on to anyons. Now, think about the following process. Imagine two elementary particles, let's say, two electrons. Move one electron very slowly around the other until the former gets back to the initial position. If we do it very slowly indeed , adiabatically for quantum physicists or quasi-staticallyfor classical ones, in the end of the process the description of the system should simply comes back to the initial one (assuming that nothing else in the neighbouring universe has changed...). I am going to jump over a lot of things now. For those of you who will be annoyed by that, a more rigorous exposition can be found here:

[2] An Anyon Primer, S. Rao [arXiv:hep-th/9209066v3]

The main point is that it was understood some time ago that this result (nothing changing) is a consequence of a very beautiful geometrical property of three-dimensional space. If you visualise the path of the moving electron as a rubber band, you see that in 3D you can continuously shrink the band to a point without any impediment. But you would not be able to shrink the band if both electrons lived in a 2D plane. If you try, the band will always find the second electrons in its way and could not shrink. Because of this, in this case things may not be exactly as before.

For those particles for which winding around would not change the system, there are two possible kinds of behaviour defined for the statistics they obey: fermions, obeying Fermi-Dirac statistics, and bosons, obeying Bose-Einstein statistics. But those that do change do not need to obey only these two statistics, they can obey ANY statistics and then they are called anyons.

You see, the toric code is defined on a 2D surface, the ideal place for the appearing of anyons, and that's exactly how the error can be described mathematically. In the next post about this subject I will explain it in more details. Actually, I am stopping now because I am also learning this subject and I need to understand it better before writing it here. As such, if anyone can pick something wrong here, please correct me. And also, if you have anything to add or any question, please post it in the comments and we can learn it together.

Finally, let me link to some other Wikipedia articles that may be of relevance here:

• Anyons
• Quasiparticles

Did you think you knew π?

The document is the kind of thing you receive regularly when you are a scientist. I guess I commented briefly a long time ago about similar papers proving that relativity was wrong and that the author would have a better theory which unfortunately he/she could not express mathematically yet...

I obviously cut the name of the author of the paper at your left as I am a nice person.

Actually, I was very surprised about the paper. I knew that a lot of people have personal problems with relativity and quantum mechanics, many even with evolution, but I have never thought that people were thinking about π as a problem to be solved. The interesting conclusion of the author is that his "exact value" for Pi is finite. What exactly he means by finite I have no idea whatsoever. Well, he said it is not transcendental but I cannot understand the unhappiness of the author with transcendental numbers as their only fault is not to be the solution of any polynomial equation with rational coefficients, which is not such a general structure after all. Actually, you can find even in the Wikipedia article I linked to that the proof of π's transcendentality is given by a corollary of the Lindemann-Weierstrass Theorem, which shows that the guy did not even bother, during his 36 years of work on π, to look at the Internet to check his arguments.


Did you have already a similar paper in your hands?

Statphys 24

For those who are interested in, there is still time to register to Statphys 24. Statphys is considered the most important international conference of Statistical Physics and this year it is going to take place on Cairns, Australia, from 19 to 23 of July. This is the official website: 

http://www.statphys.org.au/

Every conference, the Boltzmann medal is awarded to scientists with outstanding contributions to statistical physics. This year's award is going to two persons that do not need many introductions: John Cardy and Bernard Derrida. Although their entries in the Wikipedia are small, their contributions are not and those who don't know them can do a quick search of their names in the internet to see the extension of their work.

Although there is still time to participate in the conference, abstract submission closes tomorrow (30/Apr) and so those who are still thinking about submitting their work should rush. Many outstanding scientist will give talks, for instance, R. Baxter, S. Sachdev and C. N. Yang (!!!). The complete list of plenary talks with brief bios of the speakers is here:

Statphys 24 - Plenary Talks

In addition, many other related satellite meetings will be happening in the far east. This page has a list of them:

Statphys 24 - Satellite Meetings

If you have the time, the interest and the funding to go, that should not be missed.

Error-Correcting Bug

When you start to work with something, you soon begin to see that thing everywhere. In 2006 I started to work with statistical mechanics of error-correcting codes in the NCRG at Aston University and suddenly I noticed things I haven't before.

I always liked extremophiles. They are really interesting organisms. I guess that what fascinates me is how many extraordinary solutions to the survival problem they present. The guy in the picture above mix my interest in extremophiles with my present work. It is called Deinococcus radiodurans. It is probably the organism with the highest error-correcting ability in nature, and I believe that the exact mechanism is still unclear. Any biologist around please clarify if it is true.

This bacterium can stand radiation levels 500 times larger than a human being can survive to with no effort and even get to 3000 times sometimes. The way it does that is ingenuous. It blends hardware error-correction with software error-correction.

The first part is a pure hardware correction. Its DNA is arranged in a torus that is very tightly packed. As the main effect of radiation is to cut the DNA in parts, this configuration guarantees that most of the parts do not flow away in the cell, staying almost in the same place, which facilitate the correction by the relevant proteins. 

Now, if you look at the picture above, you will see that our star is formed by 4 compartments. In the Wikipedia article [1] I am linking below it is said that each part is a different bacterium, although in a second article [2] it is said that these compartments are of the same bacterium, and then of the same cell I suppose as, as far as I know, bacteria are unicellular organisms. In any case, I think that [2] is probably more correct as the next part of the correction uses DNA from all compartments.

It works actually as the simplest error-correction code of all, a repetition code. Repetition codes are simply codes where symbols are repeated a number of times so that if the number of errors are not that big, you can correct them by just following what the majority of the symbols in the neighborhood are. In the case of our guy, it has one copy in each compartment and (that's fantastic!) after the first hardware error-correction the DNA in one compartment unfolds, migrates to another and melds with the other one to correct its errors! Well, it is not exactly a conventional repetition code in the sense that there seems to be no global comparison between all four copies to decide on the correction based on the majority rule. However, it is still kind of.

I could not find the details of the process. For example, does it migrate and then come back to the original compartment? Does it do it in some specific order? Which is the first DNA to migrate? Again, if there is a biologist that can clarify those questions, please feel free.

Isn't that cool? I must confess that the first time I heard about it I was expecting some very smart kind of error-correcting code embedded in the DNA construction. I was a little disappointed when I learned that from the software point of view, it is as simple as it can get. However, the whole process is quite interesting and not less ingenious because of that.

[1] Wikipedia Article

[2] The Internet Encyclopedia of Science

Solving Rubik's Cube

I am experimenting with a platform to write small one-page websites called Squidoo. It seems very interesting and very elegant as it is somewhere between a blog post and a website. As my first tentative, I wrote a lens (which is how they call it) with a method to solve Rubik's Cube I have learned a long time ago:

Solving Rubik's Cube

The method is explained in details with pictures (made by myself) for every move, although I haven't reached the point of making a video yet. Maybe in the future. 

I also write en passant about the relationship between the cube and group theory, as I learned the solution when I was actually preparing a coursework for a Group Theory class. Check it out and leave a comment.

[The photo above is from Erno Rubik, the creator of the cube. I don't have the credits for it, but I will be happy to put it here if someone can provide it.]

LEGO Turing Machine

And here for those who prefer 1000 words (more actually): Turing Machine on Wikipedia

Kitaev's Toric Code

After 3 years, here I am again. Hard times, but I will neither complain nor explain. Let me go straight to what matters, for time is still short.

I have just come back from the 10th Topological Quantum Computation Symposium in Leeds. I was invited to talk about my present work on statistical physics of classical error-correcting codes and our tentatives to extend it to quantum codes. It was a bit off topic I thought after watching all those talks about anyons, but they insisted to me it was useful anyway. I am not so sure, but I would like to believe so.

I am becoming very interested in TQC, probably because I miss quantum mechanics. Let me explain more or less how it works, or how I understood it. Following John Baez's philosophy, I may be able to clarify my thoughts by doing that.

Topological Quantum Computation is a spinoff of Topological Quantum Codes, which seem to have been first proposed by A. Kitaev in the by now classic paper:

[1] Fault tolerant quantum computation by Anyons, A. Y. Kitaev

Kitaev's model became known as the Toric Code, because it is designed to correct errors in a quantum system which is constructed in the surface of a torus. The Toric Code belongs to a class of quantum error-correcting codes called Stabilizer Codes. In this kind of code the codewords t correspond to eigenstates |t> with eigenvalue 1 of an Abelian group of operators S called the Stabilizer Group for that particular code such that

S|t> = |t>.

For obvious reasons, |t> is said to be stabilized by the code. A more detailed explanation can be found on Nielsen and Chuang's book:

[2] Quantum Computation and Quantum Information, Nielsen & Chuang

In the toric code, the codewords are states of a system composed by a square N x N lattice with qubits (two-level quantum systems) placed on the edges, not on the vertices. Opposite boudaries of the square lattice are identified, i.e., periodic boundary conditions are assumed resulting in the surface of a torus, which gives the model its name. The total amount of qubits is 2k^2.

The toric code is then defined by a set of star operators A and plaquette operators B. Each star operator A_s is associated with the s-th vertex of the lattice and is composed by the tensor product of the four X operators (2 x 2 Pauli matrix corresponding to the spin in the x direction) acting on the four edges meeting at that vertex. One plaquette operator B_p is associated to each square on the lattice and composed by the tensor product of the four Z operators (spin in the z direction) acting on the edges of the corresponding square. As X and Z commute for different vertices and anticommute for the same vertex and as each star operator and each plaquette operator has only zero or two edges in common, all A_s's commute with all B_p's. Then we call the toric code the set of states stabilized by all A_s and B_p simultaneously.

However, the A's and B's are not completely independent and multiplying all operators of one kind together must give the identity. Therefore, the stabilizer group contains 2k^2-2 independent generators. Now, the handwaving argument is that each stabilizer condition halves the stabilized vector space for each stabilizer has half of the eigenvalues -1 and the other half +1. The rigorous proof can be found in Nielsen & Chuang's book above. This implies that the stabilized vector space has dimension 2^2, which means that it encodes 2 qubits.

Any Pauli operator that commutes with all the stabilizers sends a codeword to another codeword. These operators can be represented by the product of two other Pauli operators containing respectively only I's and X's and only I's and Z's. These can be represented graphically by chains, which are structures composed by the edges in which the Z's act and the edges of the dual lattice that cut the edges of the direct lattice where the X's act. The picture at the side give examples of these chains. It was taken from Kitaev's paper [1]. 

It turns out that topologically trivial loops, those that can be contracted to a point, correspond to stabilizers, while non-trivial ones do not and therefore change one codeword into another.

This basically defines the toric code. In the next post I will explain how errors can be graphically represented and how they correspond to quasiparticles of a specific Hamiltonian that posses fractional spin, which means, they are anyons.