Computational Complexity


Creative Commons License
This work is licensed under a Creative Commons License.

Powered by Blogger™

Wednesday, July 16, 2003


Perhaps the NEC project most valued by computer scientists is Citeseer developed by Steve Lawrence, with help from Lee Giles and Kurt Bollacker and others. Citeseer is a free web-based service that scans the internet for computer science technical reports, parses the citations and cross-links the papers. You can use Citeseer to see, based on citations, which papers are most relevant to a particular topic. You can sort papers or even computer scientists (not necessarily a good thing). Since the papers are cached you also quickly get hold of old versions of many papers.

With the changes at NEC, I often get asked what will happen to Citeseer. Don't worry--Citeseer will soon have a new safe home and will continue to provide computer scientists with an easy way to track down papers.

8:18 AM # Comments []  

Monday, July 14, 2003

Quantum Advice

Another rump session talk by Scott Aaronson showed that BQP/qpoly is contained in EXP/poly. In other words, everything efficiently quantumly computable with a polynomial amount of arbitrarily entangled quantum advice can be simulated in exponential time with a polynomial amount of classical advice.

Let me try to put this in context while avoiding quantum mechanics. Advice is method for encoding a different program for each input length. We define the class P/poly as those languages computable in polynomial time with access to a polynomially-long advice string an where the string an depends only on the length of the input. P/poly is equivalent to those problems having nonuniform polynomial-size circuits.

Quantum advice is a bit more tricky, since it can be in a superposition of regular advice strings. Formally, quantum advice is an exponentially long vector of numbers βa where βa is the amplitude of advice string a. For simplicity let us assume those numbers are real and we'll also have the restriction that the sum of the squares of the amplitudes is one.

You can see there are far more ways to give quantum advice than classical advice. But the quantum machines are limited in how they can use the advice. Harry Buhrman asked whether one can give any limit at all to what one can do with quantum advice. Scott Aaronson gives an answer: No better than classical advice as long as you are allowed (classical) exponential time.

Ideally one would like that efficient quantum algorithms with quantum advice can be simulated with efficient quantum algorithms with classical advice. Still Aaronson's result shows that even with fully entangled advice one cannot get all the information out of it.

4:38 PM # Comments []