Back of the Envelope

I've been bouncing around an idea in my head of starting up a second blog, a group blog devoted entirely to Quantum Computation. The idea would be to despin the quantum news in order to help the layman understand the true state of progress without trying to convince people that every incremental step is the next revolution in computing. It would also help readers keep up withthe real news in quantum computation, looking at important advances which appear in the scientific journals but which lack the proper PR department to impress the MSM.

The problem is, aside from my lack of time to take on yet another project, the fact that I lack the expertise to effectively do this. I am, as I have said in the past, not a physicist, theoretical or otherwise, but an engineer who has done experimental physics, and I'm not even in the field of quantum computation anymore. Thus the need for this to be a group blog, where my role would primarily be Token Engineer and Substitute Layman, trying to get the real experts to explain it in terms the rest of us can understand. Of course, to really do this, I would need to recruit real Quantum Computation experts, of whom I know a couple. I'm not sure they'd be interested--some of them are bloggers, but they may rather write their own blogs than participate in a group one. If one of them were doing the job, I could just link to them and not worry about it, but some prefer to use their blogs for non-technical things, while others are way too technical, and most of them are not very regular bloggers. We'll see.

I'm thinking of getting some business cards. Not for work, but for blogging. Of course, by "get," I mean design them with Microsoft Publisher and buy some business card stock and print them out on my color inkjet at home. That's really all that's needed to get business cards these days. In any case, here are a couple of designs I came up with.

First design:


Second design:

What do you think? You notice that they're both based on the new Back of the Envelope logo I now have on my page (if it looks like the old one to you, hit reload to make sure the new image is used rather than the old one you have in your cache). I decided to update it to a better looking envelope with a more quantum computation-specific equation. <0|+>=1/2^½ is actually a dot product of two vectors (one-dimensional arrays). If |0> and |1> are the two qubit states zero and one in vector form, then <0| and <1| are their conjugate transposes. (That's just what it sounds like--take the conjugate of the complex numbers and transpose the vector.) Using the usual 0 and 1 basis, we define the vector |0>=[1;0] and |1>=[0;1]. (The semicolons indicate that the elements are in separate rows--it's hard to show here.) Thus, <0|=[1 0] and <1|=[0 1]. <0|0>=1 and <1|1>=1, but <0|1>=0 and <1|0>=0. It's an orthonormal basis set, where each vector has a unit length and is orthogonal to the other vectors in that set, and by multiplying them by scalars you can create any vector in that space. Meanwhile, |+>=1/2^½(|0>+|1>) and |->=1/2^½(|0>-|1>), forming a separate orthonormal basis set. I've discussed different bases before. The key idea is that while |0> and |1> are orthonormal to one another, as are |+> and |->, |0> and |1> are not orthonormal to |+> amd |->, giving <0|+>=1/2^½.

Dean Esmay is excited about an article in quantum computation. To quote from the article:

Delsing and colleagues at Chalmers University began by embedding their Cooper-pair transistor in a resonant circuit. Next, they cooled the device down to millikelvin temperatures and measured how the phase of a radio-frequency signal changed when it was reflected from the circuit. Based on these measurements, the team was able to show that the device behaved like a quantum capacitor. Hakonen and co-workers in Helsinki and Moscow group employed a similar technique. Both teams found that the devices behaved as predicted by theory.

The effect could be used to read out quantum bits (qubits) in a reliable way because the quantum capacitance of the excited state of the qubit has the opposite sign to the ground state. These states could be used as the "1s" and "0s" in a quantum computer. Indeed Hakonen and colleagues have already used this approach to read the value of a qubit without changing its value — which is almost always a problem when measuring the quantum state of any system.

As I explained in Dean's comments, this isn't anywhere near as exciting as the article makes it sound. Generally, reading the papers (or at least the abstracts) makes the actual results of the experiments clearer. The two papers mentioned in this article can be found here and here. Reading a qubit without collapsing its wavefunction is, to the best of our knowledge, physically impossible. It's not something you want in a quantum computer either, as the quantum algorithms won't work unless you collapse the wavefunction. This is best understood in the context of entanglement. Suppose that you have a three qubit register which is in an equal superposition of two values, 100 and 010. Both of these values are possible solutions to the problem you are solving, but 110 is not. Because these three qubits are entangled, once you read the first qubit, the others collapse into the appropriate state. So if your highest order qubit is read as 1, the second qubit collapses to 0, and the third is 0 as well. If your highest order qubit is read as 0, the second qubit is 1, and the third is 0. You read either 100 or 010. Now suppose you could read each qubit individually without collapsing the wavefunction. You could tell that the highest order qubit is half one and half zero, the next is half one and half zero, and the third is 0. Knowing only this, you might conclude that the solutions to the problem are 000, 100, 010, and 110. There is no way of telling, with just the above information, that 000 and 110 are not solutions, and that collapsing the superposition will only give you 100 or 010.

Of course, this experiment is impossible, as reading out a value of a qubit does collapse the wavefunction. There is a theory of doing non-destructive measurements, but these reduce down to ways of transferring information from a qubit to another quantum system, which is ultimately just two qubit operations. What is wanted for a non-demolition qubit measurement is something that collapses the wavefunction from a superposition, but does not disturb the probabilistic distribution of the states which results. Schemes using the resonant frequency of weakly coupled systems are one way of doing this, and Hakonen claims to have achieved it in the paper mentioned above. A friend (and former labmate) of mine has done something similar, as her paper shows. Personally, I've always favored very fast, strongly coupled measurements, using RSFQ superconducting electronics for example, instead. This gives you a very quick readout, on a picosecond timescale, collapsing the wavefunction quickly but measuring the result before it has time to change. The speed with which this can be done is part of the advantage.

Every once in a while I'm forcibly reminded that although I have a Ph.D., I am not a theorist, such as when I attempted to make sense out of this article at NewScientist.com:

ATTEMPTS to build quantum computers could run up against a fundamental limit on how long useful information can persist inside them. Exceed the limit and information could just leak away, making computation impossible.

...The entire [Quantum Computer] system is delicate: during a computation the qubits have to be isolated from their environment, because any outside disturbance can cause "decoherence" and spoil the calculations.

Coherence is harder to maintain in larger qubits containing more particles, because there is more potential for interaction with the surroundings. To try and limit this effect, researchers are pursuing ways of making microscopic qubits...

But physicists Jasper van Wezel, Jeroen van den Brink and Jan Zaanen of Leiden University in the Netherlands have shown that efforts to engineer quantum computers around ever-smaller qubits may face significant obstacles. "We have proven that there is a universal decoherence rate for qubits," says van den Brink. This means that quantum information will inevitably be lost after a certain time, even without any external disturbance. Rather than remaining in a superposition of two states, a qubit will spontaneously collapse into one state or another (Physical Review Letters, vol 94, p 230401). "When we discovered this we were stunned," says van den Brink.

Worryingly, the time limit for decoherence seems to grow shorter as systems get smaller. Zaanen says that for some of the most promising qubit technologies the limit would be about 1 second. It's not a problem at the moment, he says, because researchers are fighting to get coherence times up to around a microsecond. "But this fundamental limit is getting within reach."

Not being satisfied with the news report, I read the paper. Upon doing that, I realized that it is very much a theoretical paper, and I'm not sure I feel qualified to comment on it. I did notice a couple of things in the paper that don't really fit with the article, however, which means that either I am misreading the paper (quite possible), the article got it wrong, or the authors of the paper are missing something. Anyway, rather than attempt to Fisk the paper (again, I'm not qualified to do that), I'll just pose the questions I have about it. The paper can be found here, but only if you or your organization has an account with APS. However, there is an older version of it available to everyone here.

1. The calculations in the paper begin with the assumption that the qubit is entangled to the measurement device, and calculates the decoherence time (the time it takes for the qubit to lose its information) from there. However, the measurement schemes which I'm most familiar with do their best not to entangle the measurement device to the qubit until it's time to perform the measurement. As the measurement is performed at the end, after all the calculations are done, I don't see why this would limit the coherence time of the qubit while it's performing the calculations, which is where the coherence time is most critical. If that's the case, then the article is highly misleading. However, it may be that the measurement device represented in the paper is not literally the device performing measurements, but is rather representative of the environment, which is effectively measuring the qubit.


2. The New Scientist article says, "the time limit for decoherence seems to grow shorter as systems get smaller." In the paper, this is because the coherence time is inversely proportional to the N variable, which is the number of atoms. However, this brings me to my second problem, as N is not the number of atoms in the qubit, but in the measurement device. The measurement device can be much, much bigger than the qubit storing the data, so it's not obvious to me that a smaller qubit (an ion in a trap, for instance) should have worse decoherence than a larger one (a superconducting ring), should they use the same measurement device (a SQUID magnetometer, for instance). Of course, this may go back to my first question, and whether the measurement device is really the measurement device or rather the environment seen by the qubit, this being itself. (Yes, the qubit is its own environment, in the sense that the physical system has a lot more quantum states than those purposely used to store data, and losing data into these states is just as bad as losing data to the world at large.)


3. Nowhere in the decoherence equation does a coupling parameter appear. The coupling between the measurement device and the qubit is controllable in most quantum computation schemes, and if they're really talking about a measurement device, it seems to me that this should be taken into account. I think, reading the paper, that the coupling parameter is supposed to cancel out, but I find that hard to believe, and I'm not sure if I'm reading the paper correctly.


4. The paper doesn't address the question of quantum error correction. A fundamental time limit on quantum coherence time doesn't matter if quantum error correction can still be performed (which requires the coherence time to be 10⁴ times as long as the operation time), which can extend the coherence time of the device indefinitely. One second should be plenty of time for most quantum computation schemes to implement error correction. Is there something in this fundamental limit which prevents this?


5. Finally, I want to know whether this fundamental coherence time limit can be applied to NMR. NMR quantum computers, though limited in size, have demonstrated quantum coherence greater than the one second limit at room temperature. Admittedly, there is some question of whether NMR is real quantum computing, but I'd like to see the authors address this and how their analysis applies, or why it does not, in this case.

So there're five questions I don't know the answer to.Maybe I should ask a real theorist, such as Ben Schumacher, what he thinks.

Can you spot what's missing in this article?

Toshiba Research Europe has used the science of quantum cryptography to transmit voice and video over a secure fiber link that is protected by the laws of physics. The demonstration is significant because it shows that the single-photon encryption technology is not only compatible with real Internet Protocol (IP) traffic but also robust enough for deployment on commercial fiber networks.

The system was shown to financial institutions and government representatives in London last week by scientists working at Toshiba’s Cambridge Research Laboratory.

Toshiba’s “Quantum Key Server” can generate up to 100 quantum (single-photon) keys per second, enough to encrypt each video frame with a separate key. In addition, it features an automatic management system that continually monitors and adjusts the system’s optical path length to allow it to operate continuously without any need for user intervention.

If you remember the things I talked about in my previous posts on quantum cryptography and RSA encryption, you should be scratching your head wondering something right now. There's a critical piece of information missing, and it's nowhere to be found in the article that I quoted. Go ahead and follow the link and read the article. I read it three times before I was convinced that they really had left it out.

Nowhere do they state what the length of the key is! Nowhere! How in the world can anyone write an article, where they make a point about how fast this new system can send the quantum information, without telling you the data rate? Talking about sending 100 keys per second is meaningless if they don't say how long the key is!

Okay, let me calm down and explain. Recall that, using quantum key distribution, you can share random bits between two users, and these bits form your key. One user uses his key to encrypt his data, which he then sends over a public channel, and the other user receives the encrypted data and uses his key to decrypt it. Since they have the same key, transmitted securely, they can share encrypted data confident that no one else can decrypt it. The trick here is that quantum key distribution allows you to transmit the key securely, but it's slow. Very slow. For one, you end up losing three-quarters of your data up front, and the more secure you want to make the transmission, the more data you have to toss aside. So some day it may be possible for quantum key distribution to distribute the key at somewhere around one-quarter the speed of the open, unsecured data line. Someday. The technological difficulty of transmitting and detecting one photon at a time, which is necessary for quantum key distribution, makes it even slower. The highest data rates are somewhere around 10 kbps (10,000 bits per second), as I mentioned in a previous post. For complete security, your key has to be as long as your data, meaning it will take longer to send the key than to send the data.

Now, you can use a key shorter than your data length. It won't be as good of an encryption, but you can encrypt data with keys which are much smaller than the data you're encrypting, just using the same key over and over. The problem is with a short key, a hacker who intercepts the encrypted message can just keep trying possible key values over and over until he gets an output that makes sense. For example, you can encrypt a phrase with an 8-bit key, but it will take someone no more than 256 tries to find the right key, and once he finds it, he'll know, since the decrypted phrase will make sense. Now if your key is as long as your data, then no key he tries could differentiate it from any other phrase of the same length.

So let's say you have a quantum key distribution system running in parallel to the data you're sending, but much slower. The best way to use it is to produce a key, say 100 bits in length, and use it to encrypt the next 100,000 bits of data. Then, when you produce another 100 bit key, you use it to encrypt the next 100 kb block of data. This works well when you have a 10 kbps quantum key distribution system and a 10 Mbps open data channel. This is what's being done in this article. They produce a key, encrypt some amount of data, then produce a new key and encrypt then next block of data, and so on. They can do this 100 times a second, enough that if they're transmitting video, each frame can have its own encryption. (This is actually an understatement, as video framerates are typically somewhere between 10 fps and 60 fps.) There's just one tiny problem--they don't tell you what the key length is! Without that information, talking about the number of keys is meaningless. The key could be only 10 bits long, in which case this is an exceedingly slow quantum key distribution system with a 1 kbps key data rate. It could be 100 bits, which means it's about average as quantum key distribution systems go at 10 kbps. Without telling you the length of the key, they aren't telling you the key distribution data rate, which is the number of keys times the length of the key. What's the point in talking about the number of keys if they don't tell you the key length?

I had to do a bit of hunting around the internet until I could find an article which said what the data rate is. A surprising number of articles neglected to say. This one finally shed some light on it (and it still didn't give the information the proper emphasis):

Their system is capable of generating 100 quantum 'keys' every second. This is fast enough for every individual frame of video to be protected by its own encryption. "This makes the system highly secure," says Andrew Shields, who leads the Cambridge team. "It would take an enormous computational resource to crack this frame by frame."
...
The Toshiba system creates keys made of 256 'bits', where each bit is a photon speeding along a fibre-optic cable. A photon represents either one or zero depending on whether it arrives slightly early or late at its destination. By passing a series of messages between the sender and receiver, both can arrive at a secure, mutually agreed key.

So, it's a 256 bit key, transmitted 100 times per second, a distribution rate of approximately 25 kbps, roughly 2.5 times the previous state of the art. Not bad, but do you think they could bother making sure that information is emphasized next time? I know I should blame the reporters for missing that crucial piece of information, and I do, but I think that if Toshiba had emphasized it, they might have picked up on that fact.

A while ago, I explained how quantum key encryption worked. At the time, I said that this form of quantum encryption is in the early stages of commercial application. Well, along comes this article (just a preview--the whole thing isn't free) in Scientific American to prove my point. "Best Kept Secrets" by Gary Stix is in the January 2005 issue. Here's an excerpt:

Today quantum cryptography has come a long way from the jury-rigged project assembled on a table in Bennett's office. The National Security Agency or one of the Federal Reserve banks can now buy a quantum-cryptographic system from two small companies--and more products are on the way. This new method of encryption represents the first major commercial implementation for what has become known as quantum information science, which blends quantum mechanics and information theory. The ultimate technology to emerge from the field may be a quantum computer so powerful that the only way to protect against its prodigious code-breaking capability may be to deploy quantum-cryptographic techniques.

So, what companies are producing these quantum key distribution systems? They would be id Quantique, a company in Geneva which has an optical fiber system which can operate over tens of kilometers, and MagiQ Technologies, located in New York, which can send keys up to 100 km. So how much will one of these systems run you? MagiQ is charging $70,000+ for a system, while I don't have a clue what id Quantique charges (incidentally, Quantique also produces a quantum random number generator, for those who like true randomness, at least according to the accepted theory of quantum mechanics). Of course, as I pointed out in my previous post, quantum key distribution is inefficient, and, as I didn't point out, it's also technologically hard to do, so these products don't have the highest bitrates in the world, somewhere around 10 kbps. Yes, that is slower than any current dial-up modem. You can re-use a 1000 bit key to encrypt 2000 bits of data, just by using it twice in a row, so you don't have to send the key as fast as your data, but this pretty much kills the key's usefulness. I mean, it's still a pretty good key, but it's no longer unbreakable, which was the whole point of spending all this money on a quantum key distribution system in the first place, wasn't it? If the same key is used twice, this gives your eavesdropper (Eve) an avenue of attack. Even if there are 2^1000 variations for Eve to try, when both halves of the data makes sense, then she knows she's found something. It may not be quite the correct key, as you can imagine that several keys will give you sensible messages, but she has more information than before, and the more times you re-use the same key, the closer Eve comes to finding exactly what that key is. Whereas, if the key is as long (or longer) than the message, then any key she comes up with is just a random guess. Sure, you can come up with all sorts of messages that make sense that are 100 letters long or less, but there's no way to tell which one is what was actually sent.

There's an interesting article on a superconducting quantum computation scheme here, in the EE Times. Be forewarned, while I'm not too familiar with this particular project, I have read about some of the experiments and I'm fairly knowledgeable about superconducting quantum computation in general. I saw a lot of things in this article that seemed fishy or flat out wrong. I don't think it's dishonesty on the part of the researchers, aside from the usual hype about their research, so much as the author's limited knowledge about quantum computation and superconductivity in general. I'll let you know more once I have a chance to read the papers. Maybe I'll do a fisking of the EE Times article.

This is part of the series of posts which are going up automatically while I'm in the middle of my move. All these posts were written before August 29th, in some cases by as much as two weeks.

Old Post: My last post on quantum computation, where I discussed entanglement, is especially relevant to this.

When you think of teleportation, you probably think of Star Trek's transporter, or perhaps the teleportation device in The Fly. I'd hate to disappoint you, but quantum teleportation is something quite different. Quantum teleportation transfers a qubit state from one qubit in an unknown state to another qubit using entanglement.

First let me explain how remarkable this is. You cannot make an independent copy of a qubit state. This is called the no-cloning theorem, and it simply means that if you have a qubit in an unknown state, a|0>+b|1>, there is no operation which will copy that unknown state to another qubit without entangling the two qubits, so that you really get the state a|00>+b|11>. If you could clone qubit states, then you could take a single qubit, make a million copies, and perform measurements on each of those copies in order to determine the exact state of the first qubit while leaving it in its original state. It would be a way to measure the exact state of a qubit. But with the no-cloning theorem, each of those qubits are entangled to the original one, and measuring any one will collapse the whole system, including the first qubit, and every qubit will be measured with the same value. Thus you can only get the 0 or 1 measurement out of the million copies that you can get out of the single qubit, with the same probability, |a|² for 0 and |b|² for 1. You gain no new information by building the entangled system. But while you cannot copy a qubit state, you can transfer it. Now if you could measure the qubit state, converting it into classical information, then you could obviously transfer the state through a classical data channel--except that you could never have enough bits. While you can measure only 0 or 1 from a qubit, its state, a|0>+b|1>, can have any complex value of a and b as long as |a|²+|b|²=1. That's an infinite number of possible values, so even if you had some way of reading out the value of the original qubit, how could you possibly transfer it to another qubit with a finite number of classical bits, much less two?

So let's start with our qubit in its unknown quantum state, a|0>+b|1>. We'll call this qubit A. We also have two entangled qubits, B and C, which are in state (|00>+|11>)/2^1/2. Recall that entangled qubits can be any distance apart and still retain their entanglement. In this case, we'll put qubit B in close proximity to qubit A, and keep qubit C a mile away. A is the qubit from which we're transferring the state, and C is the qubit to which we're transferring the state. The total state of the system of A, B, and C is

1/2^1/2[a|0>(|00>+|11>) + b|1>(|00>+|11>)].
While B and C are entangled, A is not entangled with them yet. Next, we perform the operation A CNOT B, where B is inverted if and only if A is |1>. This gives the result

1/2^1/2[a|0>(|00>+|11>) + b|1>(|10>+|01>)].
Next, we perform a Hadamard gate on A. A Hadamard rotation converts |0> to 1/2^1/2(|0>+|1>), and converts |1> to 1/2^1/2(|0>-|1>). This gives a state of
1/2[a(|0>+|1>)(|00>+|11>)+b(|0>-|1>)(|10>+|01>)]
You can rewrite this as

1/2[a(|000>+|011>+|100>+|111>)+b(|010>+|001>-|110>-|101>)]
and then regroup it as

1/2[|00>(a|0>+b|1>)+|01>(a|1>+b|0>)+|10>(a|0>-b|1>)+|11>(a|1>-b|0>)]
Now let's say we measure the first two qubits and collapse the system. The state which the third qubit collapses into is not a 0 or 1 state--it's still a superposition. (This is distinct from the situation we were discussing when talking about the no-cloning theorem, since in that situation, the system was in the a|00..0>+b|11..1> state, and collapsing one of them to 0 or 1 collapsed them all to 0 or 1.) Moreover, we know which superposition it's in based on the output of the measurement on A and B. If we send those two classical bits to the person sitting a mile away holding onto qubit C, he knows the state of qubit C relative to the original, unknown state of qubit A, and he can perform a qubit rotation on C in order to put it in the same state A was originally in. Specifically, he applies an X rotation if B is measured in the 1 state, and a Z rotation if A is measured in the 1 state (both if they're both in the 1 state, and neither if they're both in the 0 state).

And so the state of qubit A has been transferred to qubit C by performing operations on A and B, which is entangled to C, then sending two bits of classical information to the person holding qubit C. A and B, meanwhile, have been collapsed to the 0 and 1 states.

NOTE: In writing this post, I used Nielsen and Chuang's Quantum Computation and Quantum Information as a reference. This is a very useful book, if a bit dense in places. And I never found it to be very useful while trying to understand Shor's algorithm.

Old Posts: In my previous posts on quantum computation, I explained what a qubit was and how you could use them for Quantum key distribution.

Entanglement is one of the keys to the power of quantum computation, and it is a very difficult concept to wrap your mind around. But I'll do my best to explain it in layman's terms.

Imagine you have a qubit that you put in the state a|0>+b|1>. Recall that a qubit can be in both the |0> and |1> state at the same time, but if measured, it will collapse to one state or the other, with a probability of |a|² that it will be measured in the 0 state and |b|² that it will be measured in the 1 state. Recall that both a and b are complex numbers, such that |a|²+|b|²=1. Now, let's say that we have another qubit, which is also in the a|0>+b|1> state, and we place them in a 2-bit register which can hold the values 00, 01, 10, or 11, where the first, higher-order bit is the value of the first qubit, and the second, lower-order bit is the value of the second qubit. Because both the bits in the register are really qubits, the register can hold all four values simultaneously, but when we measure it, we only get one value out. Which value? Well, it's a simple probability problem, where the probability of outcome A and outcome B equals the probability of A times the probability of B. The probability of the first qubit being measured as 0 is |a|², and the probability of the second qubit being measured as 0 is |a|², so the probability of measuring 00 is |a|²|a|². Then the probability of 01 is |a|²|b|², of 10 is |b|²|a|², and of 11 is |b|²|b|². This is the case as long as the two qubits are independent--they're not entangled.

Now let's do this a little differently. We'll start with the first qubit in a|0>+b|1>, and the second qubit in |0>. Then we'll apply an operation called CNOT. In classical language, CNOT, the controlled-not gate, inverts a target bit if and only if the control bit is in the 1 state. In quantum language, it's a bit more complicated, since the control qubit can be partially in the 1 state. So, it partially inverts the target qubit, right? Well, sort of. What it does is merge the two independent quantum systems into a single quantum system--what's called entangling the qubits. So let's consider our register again, and use the higher-order bit, which is in the a|0>+b|1> state, as the control qubit, and the lower-order bit, which is in the |0> state, as the target qubit, so the register begins in the state a|00>+b|10>. When we apply the CNOT, the state of the register becomes a|00>+b|11>. Measured independently, each qubit is in the state a|0>+b|1>. However, once you've measured one qubit, you've determined the state of the other, because the register is now one quantum system rather than two, so measuring a single qubit collapses the entire system. So your probability of measuring 00 is |a|², your probability of measuring 11 is |b|², and your probability of measuring 01 or 10 is 0. This is entanglement, and it should be obvious why it is useful. Without entanglement, you can create a superposition of one qubit, so it can be in both 0 and 1, but when it comes to two qubits, you're out of luck. You can place both of them in superpositions, but there's no way to have a superposition of 00 and 11 without also having a superposition of 01 and 10.

Entanglement gives rise to all sorts of interesting quantum behaviors, including what's called "spooky action-at-a-distance," which completely freaked Einstein out. Let's say that you have two entangled qubits, and you separate them by a distance of miles--heck, let's separate them by lightyears. Now you measure one, and at the same instance you make your measurement, you collapse the state of the other one as well, because they are still one quantum system. "Hey, wait a minute!" you say. "Einstein's theory of relativity won't let any effect take place faster than the speed of light." Funny, that's just what Einstein said. He came up with this theory, called EPR (Einstein-Podolsky-Rosen), precisely to show that quantum mechanics conflicted with special relativity and thus had to be wrong. He was the one who was wrong in this case, since it turns out that EPR works and can be tested in the laboratory. Fortunately, it turns out that EPR doesn't conflict with special relativity. Here's how you can do the experiment: In this case, our qubits are photons, whose states are represented by different linear polarizations. When you measure the state of one, you determine the state of the other as well, which collapses to a state orthogonal to the original. (Why orthogonal? It turns out that certain atoms, when they decay from a high energy state, naturally emit two photons in opposite directions with orthogonal polarizations.) Now, if you measure the two qubits at a reasonable distance apart, you can have electronics good enough to measure them more or less simultaneously (such that the time between the measurement of each qubit is less than the time it takes light to travel between the two experimental apparati), and then compare your answers, and determine that they are indeed orthogonal every time. Now at this point, you may be wondering whether you can be sure that you are indeed collapsing qubit states rather than just measuring some classical polarizations which just happen to be orthogonal every time. This is the "hidden variable" interpretation. The answer is you can be sure that the "hidden variable" interpretation doesn't work if your measurement apparati are set to measure not quite orthogonal states, so that your collapsed state is a superposition of two other states, and then you compare your statistical measurements with rules known as Bell's inequalities, but frankly, it's rather complicated and I'd have to look it up to make sure I've explained it right, and I'd rather not. So I'll just say that we do know we're collapsing superpositions.

So if this effect travels faster than light, how can it not conflict with special relativity? Well, when it comes right down to it, "effect" is probably the wrong word. When you measure one photon, there's really no way to tell whether the other photon has collapsed already, or whether you're just now causing it to collapse. All you know is that you measure it in a certain state which you knew there was some probability you'd measure it in anyway. Go back to our original CNOT operation and our a|00>+b|11> register. When you measure one, you get 0 with probability |a|² and 1 with probability |b|², the same as if they weren't entangled. You don't get any new information out due to their entanglement until you can compare them, and you can only compare them at the speed of light. And thus Einstein's special relativity remains intact, because there's no cause and effect taking place faster than the speed of light.

If this justification leaves you queasy, you're not the only one. I've been thinking about this for years and wondering whether there's some clever way to use this to communicate faster than the speed of light. It shouldn't be possible, not if special relativity remains intact, and lots of physicists smarter and more experienced than I have told me that again and again, but I can't help feeling that there's a violation going on someplace. I'll leave it as an exercise to the reader to prove either Einstein or quantum physics wrong.

Old Post: Since I posed the ethical problems of quantum computation below, I'm talking about the solution now.

Doc Rampage has this to say about one-time pads:

The problem with one-time pads is that the pad contains as much information as the message and it requires a fully secure channel because if anyone can intercept the pad, he can easily decrypt the message. If you have a fully secure channel with enough bandwidth for the pad, why not use it to send the message? One-time pads are really only useful when you have two channels, one secure and one insecure, and you don't always have the secure channel available. Usually the non-secure channel is a wide-area network and the secure channel is some guy on a plane carrying a CD. In these cases, you can use the secure channel to send the pads whenever you can and you use the non-secure but faster, more reliable, or more widely available channel to send the messages.

This seems like the perfect time to talk about quantum cryptography, or as it's more accurately known, quantum key distribution, which proves once again that there's an exception to every rule, and it's quantum mechanics. The idea is to distribute some amount of data which will be used as the key to encrypt the message you want to send. So this data you exchange, the key, is the equivalent of a one-time pad, distributed securely. Why not just send the message this way? Well, as we'll see, QKD is very inefficient, and only a quarter of the data gets through, which would be pretty useless if you were sending message data. It's also vulnerable to eavesdropping; the trick is that you can tell when it's being eavesdropped.

Let's say you have a public channel, which can be eavesdropped. One party, Alice, wants to send a message to another party, Bob, but is worried that it could be eavesdropped by a third party, Eve. (These are the standard names used in the quantum key distribution literature.) However, this channel is capable of carrying not just regular bits, but also qubits. This is simple enough to imagine, since sending individual photons in essence sends qubits down the channel. Photons also make it easier to explain how the process works, so we'll stick with that. Alice's photons are linearly polarized, in 4 different directions, 0 degrees, 90 degrees, 45 degrees, and 135 degrees. If you use a polarizing filter, then orthogonal light can't get through the filter. If your filter is at 0 degrees, then the photon doesn't get through if it's at 90 degrees. However, due to the magic of quantum mechanics, a photon polarized at 45 or 135 degrees has a fifty percent change of getting through since you can decompose it into a 0 degree and a 90 degree component. Similarly, a 45 degree filter will block 135 degree polarized photons, but pass 50% of the 0 and 90 degree photons. There's no way to tell what the original polarization was. If you have a 0 degree polarizing filter, and a photon gets through to your detector on the other side, then it may have been polarized at 0 degrees, or it could have been polarized at 45 or 135. If the photon is blocked, then it may have been polarized at 90 degrees, or at 45 or 135. So we have two sets of two polarizations which are orthogonal to one another (0-90 and 45-135) but not orthogonal to the other set.

Alice takes a string of random bits, a, and decides on the polarization from a equal-length string of random bits b. For the kth bit in each string, if a(k)b(k) is 00, then she sends a photon polarized at 90 degrees. If a(k)b(k)=10, she sends a photon polarized at 0 degrees. Using a 0 degree polarizing filter with a photodetector on the other side, measuring a photon indicates that a(k) is 1 and measuring no photon indicates that a(k) is 0. If a(k)b(k) is 01, the photon Alice sends is at 135 degrees, and if a(k)b(k) is 11, the photon is at 45 degrees. So if b(k) is 0, the photon should be measured with the 0 degree filter, if b(k) is 1, it should be measured with the 45 degree filter. However, neither Bob nor Eve have any way of knowing this. Instead, Bob randomly chooses the filter with which to measure, using random string b'. The results of the measurement gives a string of a'. If there's an eavesdropper, Eve, she can also try to measure it, but there's no way to measure a photon and then send it to Bob. It's also not possible to copy a photon exactly and measure the copy. Eve could try measuring the photon by guessing at the correct polarization, then send a new photon to Bob based on her guess. If she guessed that the photon would be either 0 or 90 degrees and used a 0 degree filter, she could send Bob a new photon at either 0 or 90 degrees based on her measurement, and if she had guessed correctly, the photon would be at the correct angle. However, if she guessed incorrectly, it would be at the wrong angle. If Bob also measures with the 0 degree filter, it won't make much difference, so if Alice, Bob, and Eve all used the same polarization (a 1 in 4 chance), Eve would have successfully eavesdropped. If Bob measures with a 45 degree filter and the original photon was in the 45-135 set, while Eve measured and resent at 0 degrees, then there's only a 50% chance he'll get the correct value.

Once Bob tells Alice he's gotten the message, the two compare their b and b' strings. This is done publically, so Eve can hear what's being said. They then toss out all the bits where b and b' disagree, where Bob measured at a different polarization than Alice sent, since for each of those bits a(j)=a'(j) only 50% of the time. All the remaining bits should agree. So next they randomly choose about half the remaining bits to compare. There'll probably be some errors just due to the difficulty of sending single photons over long distances, but if the error rate exceeds a certain threshold, then they can know that someone's been eavesdropping on their communication. In that case, they can scratch the attempt and try again. (However, if Eve was smart, she may have eavesdropped only a small number bits, thus settling for a partial key while keeping below the threshold error rate.) If they decide they weren't eavesdropped, they need to correct for errors in the transmission by information reconciliation. Information reconciliation is a form of error correction, doing parity checking on random subsets of the shared string (a and a'), discarding the last bit each time so that Eve gains no new information (a parity check of a set of bits sums all the 1s and determines whether the result is odd or even; any single bit in a set can change its parity, so if you discard a bit without disclosing its value, you reveal no new information by revealing a set's parity). The subsets are chosen to be small enough so that each is unlikely to contain more than one error, and if an error is found, the subset is bissected and the parities checked again until the error is located. This is done repeatedly, with different, randomly chosen subsets, to negate mistakes caused by selecting subsets where an even number of errors may have given a false parity check. Let's say this is done, but Eve still has some information about the key--not a lot, else they would have detected her. Information reconciliation neither increases nor decreases the amount of information Eve has, since if you discard a bit she knew, she then learns what the parity of the remainder of the subset is. Privacy amplification reduces the information available to Eve, even if she's intercepted some information, while reducing the total number of bits in the key. One way of doing this would be to publically select a permutation of the remaining bits in a=a' (without sharing any of the values), then divide it into blocks of a certain size, and using the parity of each block to form the new key. This is a pretty inefficient way of doing it, where the total number of bits in the new key, r, equals the original number of bits divided by the block size. However, it drastically reduces the amount of information that Eve has, since Eve only knows the parity of a block when she has all the bits in it. There are more efficient functions, but the smaller the final key is compared to its original length, the less information available to Eve, even if she managed to get some information from eavesdropping.

The remaining bits form the key, which can then be used to encrypt the message Alice wants to send. Depending on degree of privacy amplification (how much you're willing to reduce the key size) and the error threshold (how many errors you'll accept before concluding that someone's eavesdropping), the distributed key can be made arbitrarily secure.

One thing you'll notice right away is that QKD is very inefficient. Even before information reconciliation and privacy amplification, you're down to about one-fourth the number of bits you started with. However, you can't expect any provably secure communication over a public channel to be efficient. This form of quantum cryptography (there are others, different in details but similar in concept) has been demonstrated in a lab environment, and at distances of up to 100 km. This particular application of quantum information is in the early stages of commercial application.

I didn't write all of this from memory, although I have studied it before. I needed to look up the details, so I used Nielsen and Chuang's Quantum Computation and Quantum Information, and this useful website.

Update: Doc Rampage gives a... uh, simpler explanation. Also, I edited for clarity.

New Post: I talk about entanglement, which is used in some quantum cryptography schemes, above.

Old Post: An introduction to quantum computation is here, while an explanation of a qubit is here.

I was going to comment on President Bush's Bioethics Council, but then I thought I should start closer to home.

I have a Ph.D. in Electrical Engineering, which generally means that I am either a professor or a researcher. In my case, I am a researcher who runs experiments and analyzes the data. My area of research is quantum computation, as you may have figured out from other things I've said around here. Quantum computation has its own ethical dilemma. To date, we've discovered that it's very good at two useful applications, performing unordered searches and factoring large numbers. The first may be useful, while the second is definitely useful. It's much easier to find a prime number and multiply it by another large prime number than to factor a large product of primes. When I say much easier, I'm talking about it taking the same computer a few seconds to do the finding and multiplying, versus a few million years to do the factoring. This sort of one-way problem forms the basis for public key encryption (although it is of course more complicated than that), such as that used in RSA, the encryption protocol used to transmit information on the Internet. For more information on RSA, check this FAQ from the sci.crypt newsgroup. A quantum computer with a sufficient number of qubits could factor a large product of primes faster than a classical computer create it in the first place. If someone were to produce such a computer today, all Internet transactions would suddenly be vulnerable.

You can tell what use people are planning for a quantum computer by looking at where the funding is coming from. Right now, the people giving out the funds are the Army Research Office, the Defense Department, and, oh yes, the NSA. It's clear that the main objective is decryption (or, perhaps, to prove that a quantum computer is so far from realizable that public key encryption is secure).

In my experience, very few scientists working on quantum computation projects think about the ethical implications at all. For the most part, they console themselves with the fact that a quantum computer capable of factoring a decent sized key is so far in the future that by the time it gets here (~25 years or so), we'll have better encryption (hopefully, quantum encryption). That may or may not be the case. I've heard that the federal government may be pushing for a five-year program to develop a quantum computer that can factor 128-bit encryption. (I've been looking for confirmation but I haven't found it yet.) This is wildly ambitious--I don't think it will happen--but how many scientists, who previously considered quantum computation safe because it was decades away, would jump at the chance to partake of this funding?

For the record, I have thought a bit more in-depth about quantum computation, partially because I took part in a discussion group with MIT's Graduate Christian Fellowship based on the book Responsible Technology. To a large degree, the questions about developing a quantum computer revolve around who would get it. Quantum computers aren't going to be available on the open market anytime soon, and they'll probably be as regulated as nuclear power. So, assuming I helped create a quantum computer, would I trust the NSA to use it wisely? I certainly don't mind them cracking a terrorist's e-mail, but I wouldn't want them reading mine. So, I don't think that the technology itself is wrong, but I am concerned over how it would be used.

New Post: I explain quantum cryptography above.

Old Post: I first discussed quantum computation in this blog here.

I'd like to take a moment to expand on the subject of quantum computation, and that means starting with the term "qubit." A qubit is a quantum bit, and it refers to any quantum system that has two states which can serve as zero and one. Examples include spin states of nuclei in a molecule, an electron's orbital states in an atom, photon polarization, or, in a system such as superconductors which exhibit macroscopic quantum coherence, current circulating in a loop. If it's quantum, it's been proposed as a qubit.

Not every quantum system makes a good qubit, however. The criteria necessary for a quantum system which can be used in a quantum computer were formalized by DiVincenzo. The requirements are the following:

First the two states, called the |0> and |1> states, must be measurable. It must be possible to tell the difference between them. This may seem trivial, but quite a few quantum states are difficult to differentiate.

Second, the states must be controllable. This means that one can first place the system in the |0> state accurately. Then, one must be able to rotate the qubit in order to achieve every possible state. The possible states are not just |0> and |1>. If a and b are complex numbers, such that |a|^2+|b|^2=1, a|0>+b|1> describes all the possible states of the qubit. Thus it is possible for the qubit to be in state |0> and |1> at the same time (called a superposition), as long as the proportions add up to 1. Since a and b are complex, it's not simply a matter of achieving the right proportions, but also the correct phase--the correct complex values.

Third, the qubit must be addressable. One needs to be able to decide which qubit to control and measure. If there's a solution filled with millions of identical molecules, and there's a way to rotate the oxygen atom nucleus in all the molecules at the same time, that's still only one useful qubit (more precisely, it's an ensemble of that qubit). Now if it's possible to address the two carbon atom nuclei and the oxygen atom nucleus on each molecule separately, that's three qubits, and an ensemble of those three qubits. This is what is done in nuclear magnetic resonance (NMR) quantum computing.

Fourth, one needs to be able to couple qubits together so that they affect one another. Thus one qubit will rotate only if another qubit is in a certain state. This is how one makes quantum gates.

Finally, one needs to be able to isolate the qubits from the environment. The environment, which means everything other than the qubits themselves, causes the qubits to decohere. Information is lost as the qubits dephase, drift from the intended phase, and relax, fall to the lowest energy states. If one waits long enough, qubits in just about any system eventually fall to |0>. Only if they remain in the desired states long enough to perform a useful calculation can you make a quantum computer.

And that's the second episode of quantum computation for the layman. Tune in next time as I tell you how you can build your very own quantum computer (with a $1 million grant and a Ph.D., of course).

New Post: More on quantum computation above. First, ethical considerations, then quantum cryptography.

Well, I haven't said anything about quantum computation yet. Honest, if I had noticed anything in the news, I'd comment on it. Right now, there's plenty of buzz in the physics world, but there's just not much that would be very interesting to a layman. Here, in any case, is a quick explanation of what quantum computation is, so that my blog isn't completely devoid of anything about it:

In classical computers, information is stored in the form of bits which hold a value of either 1 or 0. Quantum computers have qubits which can be both 1 and 0 at the same time, in differing proportions: half 1 and half 0, or two-thirds 1 and one-third 0, etc. A classical computer can store any number between 0 and 255 in a single byte, which consists of 8 bits. A quantum computer can store all the numbers between 0 and 255 at the same time on a byte of 8 qubits. Whereas a classical computer performs a calculation on its byte and produces a single answer for the single number on that byte, a quantum computer can perform one calculation and get all the answers for all the numbers on the byte at the same time. This gives you massive parallelism. Of course, it's not as easy as that--getting information out of a quantum computer is a lot harder than putting it in. Thus it's only really good at answering questions that have sharply "peaked" answers, meaning questions where you put in a lot of inputs while lookng for only one answer, such as an unordered search.

(Adapted from The Donald S. Crankshaw Newsletter, Vol. 24, Iss. 1.)

Meanwhile, I have a couple of publications on my specific work, which is on a superconducting qubit, called the persistent current qubit. If you're interested, you can find preprints of the papers online:

Impact of time-ordered measurements of the two states in a niobium superconducting qubit structure
K. Segall, D. Crankshaw, D. Nakada, T.P. Orlando, L.S. Levitov, S. Lloyd, N. Markovic, S.O. Valenzuela, M. Tinkham, K.K. Berggren
Published in Physical Review B, 67, 220506, 2003.

DC measurements of macroscopic quantum levels in a superconducting qubit structure with a time-ordered meter
D.S. Crankshaw, K. Segall, D. Nakada, T.P. Orlando, L.S. Levitov, S. Lloyd, S.O. Valenzuela, N. Markovic, M. Tinkham, K.K. Berggren
Accepted for publication in Physical Review B

Energy Relaxation Time between Macroscopic Quantum Levels in a Superconducting Persistent Current Qubit
Yang Yu, D. Nakada, Janice C. Lee, Bhuwan Singh, D. S. Crankshaw, T. P. Orlando, William D. Oliver, Karl K. Berggren
Accepted for publication in Physical Review Letters

These articles describe a series of experiments done on a persistent current qubit fabricated in niobium (which goes superconducting at 9 K), demonstrating a high Q and, by all indications, a long coherence time. Ask me sometime and I'll explain what that means, but for now, just trust me that these are good things.

Update: Now that Doc Rampage has linked to me, I figured that I needed to clean up the post a bit for clarity.

New Post: So what is a qubit, anyway? I go into more detail here.