More Papers

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.)