1. The Power of Unentanglement
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor
http://arxiv.org/abs/0804.0802
The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Does QMA(k)=QMA(2) for k>=2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. First, we give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given ~O(sqrt(n)) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on the existence of very short PCPs. Second, we show that assuming a weak version of the Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all k>=2. Third, we prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.
2. Quantum Simulations of Classical Annealing Processes
R. D. Somma, S. Boixo, H. Barnum, E. Knill
Phys. Rev. Lett. 101, 130504 (2008)
http://arxiv.org/abs/0804.1571
We describe a quantum algorithm that solves combinatorial optimization problems by quantum simulation of a classical simulated annealing process. Our algorithm exploits quantum walks and the quantum Zeno effect induced by evolution randomization. It requires order $1/\sqrt{\delta}$ steps to find an optimal solution with bounded error probability, where $\delta$ is the minimum spectral gap of the stochastic matrices used in the classical annealing process. This is a quadratic improvement over the order $1/\delta$ steps required by the latter.
3. The Limiting Distribution of Decoherent Quantum Random Walks
Kai Zhang
http://arxiv.org/abs/0804.4311
The behaviors of one-dimensional quantum random walks are strikingly different from those of classical ones. However, when decoherence is involved, the limiting distributions take on many classical features over time. In this paper, we study the decoherence on both position and ``coin'' spaces of the particle. We propose a new analytical approach to investigate these phenomena and obtain the generating functions which encode all the features of these walks. Specifically, from these generating functions, we find exact analytic expressions of several moments for the time and noise dependence of position. Moreover, the limiting position distributions of decoherent quantum random walks are shown to be Gaussian in an analytical manner. These results explicitly describe the relationship between the system and the level of decoherence.
4. Quantum effects in classical systems having complex energy
Carl M. Bender, Dorje C. Brody, Daniel W. Hook
J.Phys.A41:352003,2008
http://arxiv.org/abs/0804.4169
On the basis of extensive numerical studies it is argued that there are strong analogies between the probabilistic behavior of quantum systems defined by Hermitian Hamiltonians and the deterministic behavior of classical mechanical systems extended into the complex domain. Three models are examined: the quartic double-well potential $V(x)=x^4-5x^2$, the cubic potential $V(x)=frac{1}{2}x^2-gx^3$, and the periodic potential $V(x)=-\cos x$. For the quartic potential a wave packet that is initially localized in one side of the double-well can tunnel to the other side. Complex solutions to the classical equations of motion exhibit a remarkably analogous behavior. Furthermore, classical solutions come in two varieties, which resemble the even-parity and odd-parity quantum-mechanical bound states. For the cubic potential, a quantum wave packet that is initially in the quadratic portion of the potential near the origin will tunnel through the barrier and give rise to a probability current that flows out to infinity. The complex solutions to the corresponding classical equations of motion exhibit strongly analogous behavior. For the periodic potential a quantum particle whose energy lies between -1 and 1 can tunnel repeatedly between adjacent classically allowed regions and thus execute a localized random walk as it hops from region to region. Furthermore, if the energy of the quantum particle lies in a conduction band, then the particle delocalizes and drifts freely through the periodic potential. A classical particle having complex energy executes a qualitatively analogous local random walk, and there exists a narrow energy band for which the classical particle becomes delocalized and moves freely through the potential.