quantum information theory for dummies
Jan. 25th, 2002 02:42 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
eubNifty talk today by Charles Bennett from IBM Watson. (Popular, too, but through some foulup it was held in a 30-person-sized classroom -- there were so many people sitting on the floor that he hardly had room to turn around.) He gave a low-equation talk that still managed to have some technical content, a good job. At least now I know what a qubit is.
My "aha" moment was when he mentioned in passing that for a quantum computer, factoring is no harder than multiplication. And I thought -- look at what he gave as the basic quantum gate, it's a two-qubit gate, (x, y) -> (x, x xor y). It's its own inverse. So if you have an n-by-n-to-2n multiplier, I think you can convert it to a 2n-bit factoring machine by reversing the flow of data. So is that why factoring is no harder?
On second thought I think something must be wrong here, because look for example at the multiplications 2*2 and 1*4. You can't start from the 4 and work backwards; multiplication isn't reversible. So how does it fit into this seemingly-reversible model? I don't know. Maybe a quantum multiplier deliberately throws information away somewhere. But it was a fun "aha", anyway.
Another lovely piece was the Reverse Shannon Theorem. You may know that if you have a channel with noise, you can use it to simulate a noiseless channel of a certain smaller capacity. The reverse theorem is that if you have a noiseless channel, and you and the other end have also a supply of EPR-entangled qubits, then you can simulate a noisy channel of a larger capacity -- the right capacity so that the two theorems mate. This makes the universe better in my eyes.
I should google for a more extensive intro to quantum information. After I finish that pesky graduation thing.
My "aha" moment was when he mentioned in passing that for a quantum computer, factoring is no harder than multiplication. And I thought -- look at what he gave as the basic quantum gate, it's a two-qubit gate, (x, y) -> (x, x xor y). It's its own inverse. So if you have an n-by-n-to-2n multiplier, I think you can convert it to a 2n-bit factoring machine by reversing the flow of data. So is that why factoring is no harder?
On second thought I think something must be wrong here, because look for example at the multiplications 2*2 and 1*4. You can't start from the 4 and work backwards; multiplication isn't reversible. So how does it fit into this seemingly-reversible model? I don't know. Maybe a quantum multiplier deliberately throws information away somewhere. But it was a fun "aha", anyway.
Another lovely piece was the Reverse Shannon Theorem. You may know that if you have a channel with noise, you can use it to simulate a noiseless channel of a certain smaller capacity. The reverse theorem is that if you have a noiseless channel, and you and the other end have also a supply of EPR-entangled qubits, then you can simulate a noisy channel of a larger capacity -- the right capacity so that the two theorems mate. This makes the universe better in my eyes.
I should google for a more extensive intro to quantum information. After I finish that pesky graduation thing.
