1. Lower Bounds for Local Search by Quantum Arguments
Scott Aaronson
http://arxiv.org/abs/quant-ph/0307149
The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hypercube {0,1}^n, we show a lower bound of Omega(2^{n/4}/n) on the number of queries needed by a quantum computer to solve this problem. More surprisingly, our approach, based on Ambainis' quantum adversary method, also yields a lower bound of Omega(2^{n/2}/n^2) on the problem's classical randomized query complexity. This improves and simplifies a 1983 result of Aldous. Finally, in both the randomized and quantum cases, we give the first nontrivial lower bounds for finding local minima on grids of constant dimension greater than 2.
2. Lower bounds on the complexity of simulating quantum gates
Andrew M. Childs, Henry L. Haselgrove, Michael A. Nielsen
Phys. Rev. A 68, 052311 (2003)
http://arxiv.org/abs/quant-ph/0307190
We give a simple proof of a formula for the minimal time required to simulate a two-qubit unitary operation using a fixed two-qubit Hamiltonian together with fast local unitaries. We also note that a related lower bound holds for arbitrary n-qubit gates.
3. Hyperentanglement-assisted Bell-state analysis
S. P. Walborn, S. P��dua, C. H. Monken
http://arxiv.org/abs/quant-ph/0307212
We propose a simple scheme for complete Bell-state measurement of photons using hyperentangled states - entangled in multiple degrees of freedom. In addition to hyperentanglement, our scheme requires only linear optics and single photon detectors, and is realizable with current technology. At the cost of additional classical communication, our Bell-state measurement can be implemented non-locally. We discuss the possible application of these results to quantum dense coding and quantum teleportation.