1. Quantum Versus Classical Proofs and Advice
Scott Aaronson, Greg Kuperberg
http://arxiv.org/abs/quant-ph/0604056
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove three results about this question. First, we give a "quantum oracle separation" between QMA and QCMA. More concretely, we show that any quantum algorithm needs order sqrt(2^n/(m+1)) queries to find an n-qubit "marked state" |psi>, even if given an m-bit classical description of |psi> together with a quantum black box that recognizes |psi>. Second, we give an explicit QCMA protocol that nearly achieves this lower bound. Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.
2. Speed and entropy of an interacting continuous time quantum walk
Diego de Falco, Dario Tamascelli
J. Phys. A: Math. Gen. 39 (2006) 5873-5895
http://arxiv.org/abs/quant-ph/0604067
We present some dynamic and entropic considerations about the evolution of a continuous time quantum walk implementing the clock of an autonomous machine. On a simple model, we study in quite explicit terms the Lindblad evolution of the clocked subsystem, relating the evolution of its entropy to the spreading of the wave packet of the clock. We explore possible ways of reducing the generation of entropy in the clocked subsystem, as it amounts to a deficit in the probability of finding the target state of the computation. We are thus lead to examine the benefits of abandoning some classical prejudice about how a clocking mechanism should operate.
3. Nonlinear optical Galton board
C. Navarrete-Benlloch, A. Perez, Eugenio Roldan
Physical Review A 75, 062333 (2007)
http://arxiv.org/abs/quant-ph/0604084
We generalize the concept of optical Galton board (OGB), first proposed by Bouwmeester et al. {[}Phys. Rev. A \textbf{61}, 013410 (2000)], by introducing the possibility of nonlinear self--phase modulation on the wavefunction during the walker evolution. If the original Galton board illustrates classical diffusion, the OGB, which can be understood as a grid of Landau--Zener crossings, illustrates the influence of interference on diffusion, and is closely connected with the quantum walk. Our nonlinear generalization of the OGB shows new phenomena, the most striking of which is the formation of non-dispersive pulses in the field distribution (soliton--like structures). These exhibit a variety of dynamical behaviors, including ballistic motion, dynamical localization, non--elastic collisions and chaotic behavior, in the sense that the dynamics is very sensitive to the nonlinearity strength.
4. Quantum random walk of two photons in separable and entangled state
P. K. Pathak, G. S. Agarwal
Phys. Rev. A 75, 032351 (2007)
http://arxiv.org/abs/quant-ph/0604138
We discuss quantum random walk of two photons using linear optical elements. We analyze the quantum random walk using photons in a variety of quantum states including entangled states. We find that for photons initially in separable Fock states, the final state is entangled. For polarization entangled photons produced by type II downconverter, we calculate the joint probability of detecting two photons at a given site. We show the remarkable dependence of the two photon detection probability on the quantum nature of the state. In order to understand the quantum random walk, we present exact analytical results for small number of steps like five. We present in details numerical results for a number of cases and supplement the numerical results with asymptotic analytical results.
5. Momentum Dynamics of One Dimensional Quantum Walks
Ian Fuss, Langord B. White, Peter J. Sherman, Sanjeev Naguleswaran
http://arxiv.org/abs/quant-ph/0604197
We derive the momentum space dynamic equations and state functions for one dimensional quantum walks by using linear systems and Lie group theory. The momentum space provides an analytic capability similar to that contributed by the z transform in discrete systems theory. The state functions at each time step are expressed as a simple sum of three Chebyshev polynomials. The functions provide an analytic expression for the development of the walks with time.