The Quantum Pontiff

In a clear demonstration that Scott Aaronson has spent to much time on the campus of the Institute for Advanced Study, I find that last week he posted cs.cc/0504048:

Oracles Are Subtle But Not Malicious
Scott Aaronson
Theoretical computer scientists have been debating the role of oracles since the 1970’s. This paper illustrates both that oracles can give us nontrivial insights about the barrier problems in circuit complexity, and that they need not prevent us from trying to solve those problems.
First, we give an oracle relative to which PP has linear-sized circuits, by proving a new lower bound for perceptrons and low- degree threshold polynomials. This oracle settles a longstanding open question, and generalizes earlier results due to Beigel and to Buhrman, Fortnow, and Thierauf. More importantly, it implies the first nonrelativizing separation of “traditional” complexity classes, as opposed to interactive proof classes such as MIP and MA-EXP. For Vinodchandran showed, by a nonrelativizing argument, that PP does not have circuits of size n^k for any fixed k. We present an alternative proof of this fact, which shows that PP does not even have quantum circuits of size n^k with quantum advice. To our knowledge, this is the first nontrivial lower bound on quantum circuit size.
Second, we study a beautiful algorithm of Bshouty et al. for learning Boolean circuits in ZPP^NP. We show that the NP queries in this algorithm cannot be parallelized by any relativizing technique, by giving an oracle relative to which ZPP^||NP and even BPP^||NP have linear-size circuits. On the other hand, we also show that the NP queries could be parallelized if P=NP. Thus, classes such as ZPP^||NP inhabit a “twilight zone,” where we need to distinguish between relativizing and black-box techniques. Our results on this subject have implications for computational learning theory as well as for the circuit minimization problem.

In computational complexity, one often considers the power of a complexity class when you are given access to a black box which solve a problem from a different computational complexity class. This is where all the funny raising computational complexity classes to a power comes from. Thus, for example, in Scott’s abstract he talks about ZPP^NP which is the complexity class zero-error probabilistic polynomial time which has access to an oracle which returns answers (at unit cost) to the computational complexity class NP. Whereas philosophers for eons have pondered Gods, computer scientists have rigorously defined their Gods, and found the world a polytheistic conglomeration of computational complexity classes.
With the notion of an oracle, one can begin to ponder whether certain results you prove in computational complexity are robust under the use of oracles. Suppose you have shown some inclusion in computational complexity theory. Then you can consider whether this result is robust when you consider the same inclusion, but now when the computational complexity classes have access to the same oracle. If the result hold for all possible choices of oracles, then we say that the result is relativizing. Why does this matter? Well, one reason is we know that if we are going to prove P does not equal NP, then we know that this must be done by a nonrelativizing method (this follows from the fact that there exists oracles A and B relative to which P^A=NP^A and P^B NP^B.)
What Scott shows in his paper is that there exists an oracle relative to which the computational complexity class PP (or, you know for those of us who love quantum theory, the computational complexity class post-BQP, i.e. bounded-error quantum polynomial time with postselection) has linear sized circuits. Why is this important? Well, because it has been shown that the computational complexity class PP does not have linear sized circuits via a proof constructed by Vinodchandran. This means that the result of Vinodchandran is nonrelativizing! Nonrelativizing proofs in computational complexity are, especially because of their connection to the P/NP question, totally awesome. It’s like you’ve separated a mortal from a God but only when the other Gods aren’t around to help with the battle. Thinking about all this really makes me want to write a comic strip based on computational complexity classes.

When it rains, it pours! Andris points me to another interesting paper, this time by Shengyu Zhang (Princeton), quant-ph/0504085:

(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids
Shengyu Zhang
The Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to many areas in computer science and natural sciences. In this paper, we show that for the Boolean hypercube $B^n$, the randomized query complexity of Local Search is $Theta(2^{n/2}n^{1/2})$ and the quantum query complexity is $Theta(2^{n/3}n^{1/6})$. We also show that for the constant dimensional grid $[N^{1/d}]^d$, the randomized query complexity is $Theta(N^{1/2})$ for $d geq 4$ and the quantum query complexity is $Theta(N^{1/3})$ for $d geq 6$. New lower bounds for lower dimensional grids are also given. These improve the previous results by Aaronson [STOC’04], and Santha and Szegedy [STOC’04]. Finally we show for $[N^{1/2}]^2$ a new upper bound of $O(N^{1/4}(loglog N)^{3/2})$ on the quantum query complexity, which implies that Local Search on grids exhibits different properties at low dimensions.

In the local search problem, one is given a graph and a function on this graph from its vertices to the natural numbers and one seeks to return a vertex such that for all of the neighbors of this vertex the function obtains a greater value on those neighboring vertices. Here, Zhang is able to demonstrate a remarkable number of matching bounds for this problem in both the randomized classical model and the quantum model.
Another interesting paper which appeared today is Michael Nielsen’s (University of Queensland) summary (plus a bit more) about cluster state quantum computing, quant-ph/0504097:

Cluster-state quantum computation
Michael A. Nielsen
This article is a short introduction to and review of the cluster-state model of quantum computation, in which coherent quantum information processing is accomplished via a sequence of single-qubit measurements applied to a fixed quantum state known as a cluster state. We also discuss a few novel properties of the model, including a proof that the cluster state cannot occur as the exact ground state of any naturally occurring physical system, and a proof that measurements on any quantum state which is linearly prepared in one dimension can be efficiently simulated on a classical computer, and thus are not candidates for use as a substrate for quantum computation.

This is a nice review, which contains some interesting bonus(!) results. The first is that the cluster state cannot be the ground state of any two-body Hamiltonian. This is particularly interesting because one way one might imagine realizing the cluster state is by engineering the appropriate Hamiltonian and then cooling the system a ground state which is the cluster state. The other important result in this paper is that certain one dimensional quantum systems aren’t useful for quantum computation. In particular one dimensional quantum systems which are prepare via a linear series of unitary evolutions can be efficiently simulated on a classical computer. Michael shows that this is true for qubit circuits, I wonder how this scales when we replace these qubits by qudits? Also I see there is a note about this later result also being shown by Steve Flammia (University of New Mexico), Bryan Eastin(University of New Mexico), and Andrew Doherty(University of Queensland). (Correction: it seems I can’t parse a sentence. The later result is joint work with Andrew Doherty(University of Queensland) while Steve and Brian are acknowledge for introducing clusters states to the qcircut latex package.)

Another cool paper on the arXiv today, this time by Iordanis Kerenidis(MIT)

Quantum multiparty communication complexity and circuit lower bounds
Iordanis Kerenidis
We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result of our simulation, we show that if the quantum k-party communication complexity of a function f is $Omega(n/2^k)$, then its classical k-party communication is $Omega(n/2^{k/2})$. Finding such an f would allow us to prove strong classical lower bounds for (k>log n) players and hence resolve a main open question about symmetric circuits. Furthermore, we prove that for the Generalized Inner Product (GIP) function, the quantum model is exponentially more efficient than the classical one. This provides the first exponential separation for a total function between any quantum and public coin randomized communication model.

The first part of the abstract refers to one of the grand hopes of the field of communication complexity: to prove that a function cannot be computed with ACC circuits (constant depth, polynomial size, circuits with unbounded fan-in, and mod gates.) It turns out that finding such an f corresponds to proving a superlogarithmlic lower bound for a k-party communication complexity problem. What Iordanis does is show an explicit connection between lower bound between classical multiparty communication complexity results and quantum multiplarty communication complexity. The hope here is then that the proofs in the quantum world will turn out to be simpler than in the classical world, where all attempts to get functions out of ACC have failed. Did we ever imagine there would be a day when the quantum world was considered simpler than the classical world? Yeah for the new generation.
In the second part of the paper, Iordanis shows an exponential separation between classical communication complexity and quantum communication for a total function. A total function is a function which is defined over all of it’s inputs. Previously all the functions for which there was an exponential separation were promise problems or relations. This is quite cool for the world of communication complexity. This follows earlier work by Iordanis and coworkers Ziv Bar-Yossef and T.S. Jayram where they were able to show an exponential quantum-classical separation for a communication complexity problem which used only one way communication. Quite a roll to be on!