Fact and Fiction

Thoughts about a funny old world, and what is real, and what is not. Comments are welcome, but please keep them on topic.

Sunday, October 30, 2005

Quantum computers can't be backed-up

In this week's New Scientist there is an article entitled Attack of the quantum worms in which the problem of defending a quantum computer against malicious software attack is discussed. Even the leading quantum computer theorist David Deutsch says that he hadn't anticipated this problem. Frankly, I am amazed that he hadn't forseen this possibility; maybe he has never suffered an attack on his computer.

One of the key parts of your defence strategy is backing up your software, so that if something gets corrupted by an attack then it can be repaired afterwards. This is where quantum mechanics is not very helpful to you, because it is fundamentally impossible to make an independent copy of a QM state, so you can't do a safe backup. This is such an important property of QM that it has been elevated to the status of being called the No-cloning theorem.

This sounds crazy! How is it possible that QM should prevent you from making backups?

I have already discussed in an earlier posting Quantum mechanics is not weird the reason why many people think that QM seems to be crazy. It all boils down to people insisting that the everyday intuition that they have built up through exposure to the world through their senses will also work in situations where their senses are blind. One such example is QM, which exercises its effects in places that we don't directly see with our senses.

This problem of everyday intuition being inappropriately applied also gets in the way of understanding why QM prevents backups from being made. It is tempting to imagine that you can just grab the data and make a copy of it to keep somewhere else. The problem here is that in QM the implementation of the words "data", "grab", and "copy" have to be defined precisely. I already did something like this in my earlier posting Spooky action at a distance?, but the situation is much simpler here.

Suppose that a quantum computer contains only one particle (1 qubit), which is represented as A↑ (spin pointing up) or A↓ (spin pointing down). The power of a quantum computer comes from the fact that its state can simultaneously hold A↑ and A↓, so it can do truly parallel computations. In the intuitively comprehensible classical (i.e. non-quantum) computer these states are mutually exclusive possibilities, so classical computers can do only one computation at a time. It is this reality of doing parallel computations in quantum computers that gives them their enormous (a factor of 2N for an N-particle quantum computer) speed advantage over classical computers.

Assume that the backup store is also a single particle, which is part of a QM backup system that denoted as U. The spin-up and spin-down states of the backup particle in U will be denoted as U↑ and U↓, respectively.

  1. The initial state of the quantum computer and backup store is then U (a A↑ + b A↓), where a and b are the amplitudes of the two possible states of the quantum computer.
  2. The state of the quantum computer and backup store after an attempt has been made to do a backup is then a U↑ A↑ + b U↓ A↓. Arrows have now been attached to U because interactions have occurred between A and U that cause the backup particle in U to become correlated with the state of the quantum computer.
OK, so that's it. We have apparently done a backup; A↑ has been copied as U↑, and A↓ has been copied as U↓. However, U is not a safe backup of A, because in QM the A and U particles are still connected to each other. A malicious software attack on A will thus propagate to U, and will thus be an attack on both A and U.

This is exactly the same effect that appeared in Spooky action at a distance?, where separating the particles does not destroy the connection between them. That means that if you start with a U↑ A↑ + b U↓ A↓, and then you separate the A and U particles you get something that can be represented as a U↑ ••• A↑ + b U↓ ••• A↓, where the ••• remind us of the fact that the QM connection between the particles is unchanged by separating them. This means that A and U behave as if they were the same particle, which was what Einstein called "Spooky action at a distance".

It is this sameness that destroys any pretence that U can be a safe backup of A, because effectively U is A, rather than U is a copy of A.

So the No-cloning theorem prevents backups from being made in a quantum computer. The only defence against attacks by malicious software is to ensure that the connection between the quantum computer and the outside world is switched on for only a negligible fraction of the time, and a further countermeasure is to choose the on-times randomly. This slows down the communication between the quantum computer and the outside world by a fixed fraction, but it does not affect the internal speed of quantum computation.

4 Comments:

At 31 October 2005 at 18:30, Anonymous Dave Bacon said...

I haven't read the New Scientist article (subscription required), but it seems to me that the idea that quantum computers are somehow more susceptable to malicious software isn't quite right.

Sure it is true that quantum states cannot be cloned. But quantum states are not the "software" of a quantum computer. The "software" of quantum computer is a completely classical description of the operations which will be applied to the quantum computer. There is nothing "quantum" about the software of a quantum computer. Actually this isn't quite true there are schemes where one uses quantum states to encode the instructions (which are then "teleported" into the circuit.) But as far as I know, these act just like classical data in that they can be cloned.

 
At 31 October 2005 at 19:30, Blogger Steve said...

I agree with your comments about classical software. However, the "backing-up" the New Scientist article and I were talking about is the whole quantum state of the quantum computer (including any associated quantum files). The term "back-up" normally means making a copy of the computer files rather than the state of the computer itself. However, these files can contain both software and data, and for a quantum computer the data could be quantum data, which thus cannot be backed up.

 
At 31 October 2005 at 19:51, Anonymous Dave Bacon said...

Ah, I'll have to find a copy of New Scientist to read the article. I just don't see the connection between not being able to make a copy and malicious software. From the little intro to the bit in New Scientist it makes it sound like quantum computers are more susceptible to worms and such, and I just don't see how the inability to clone the state follows from this statement.

 
At 31 October 2005 at 21:05, Blogger Steve said...

Not being able to make a copy leaves you more open to irrecoverable damage caused by malicious software, not the other way around. This is what I summarised towards the end of my posting by saying "It is this sameness that destroys any pretence that U can be a safe backup of A, because effectively U is A, rather than U is a copy of A.".

 

Post a Comment

<< Home