This work is licensed under a
Creative Commons License.
|
Saturday, September 28, 2002
The Quantum Algorithms and Complexity workshop clearly showed a field matured. From at least a computer science point of view, researchers have created a strong set of techniques and questions that are leading to several new and exciting results. Let me give you an example of some of the results presented at the workshop.There were new quantum algorithms. Sean Halgreen showed how to solve Pell equations, i.e. given x and y, find a value D such that x2-Dy2=1. Wim van Dam showed how to estimate Gauss sums, which I won't define.
Some new and interesting limitations on quantum computing. Ambainis presented Razborov's newest result giving a n0.5 lower bound on the communication complexity of set disjointness: Given two parties with two n-bit strings, they need to transmit even n0.5 quantum bits to determine if there is an i such that both strings have a 1 in the ith bit.
The most fascinating result was due to Ronald de Wolf who gave lower bounds on two-query locally decodable codes in the classical model using quantum techniques. He first showed how to simulate two classical queries with one quantum query and then gave a lower bound on the one quantum query model.
If you would like to learn more about quantum computing I suggest the textbook, Quantum Computation and Quantum Information by Nielsen and Chuang. Nearly all quantum computation papers can be found at the quant-ph web site.
On quant-ph you can find David Mermin's From Cbits to Qbits: Teaching computer scientists quantum mechanics which I mention just because I am the "newly enlightened computer scientist" quoted on the first page. Feel free to read my paper One complexity theorist's view of quantum computing based on my AQIP talk for another point of view.
9:09 PM # Comments []
Tuesday, September 24, 2002
Howdy from Canada. I have limited internet access here in Banff so there won't be many posts this week.I've heard lots of interesting results about quantum computing here. John Watrous has the following nifty theorem about quantum interactive proofs:
Every language with a quantum interactive proof (and in particular all of PSPACE) has a proof system that works as follows: Merlin sends some qbits to Arthur. Arthur flips a single classical coin and sends it to Merlin. Merlin then sends over more qbits and Arthur performs some quantum operations and accepts or rejects. Even though Arthur's only communication is a single random coin, this protocol has perfect completeness and soundness near one-half.11:23 PM # Comments []
Sunday, September 22, 2002
I'm off to beautiful Banff, Canada for the MSRI Workshop on Quantum Algorithms and Complexity. So no regular features this week but I hope to bring you the latest in quantum computation.6:13 AM # Comments []