1. Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
Andrew M. Childs, Ben W. Reichardt, Robert Spalek, Shengyu Zhang
http://arxiv.org/abs/quant-ph/0703015
For every NAND formula of size N, there is a bounded-error N^{1/2+o(1)}-time quantum algorithm, based on a coined quantum walk, that evaluates this formula on a black-box input. Balanced, or ``approximately balanced,'' NAND formulas can be evaluated in O(sqrt{N}) queries, which is optimal. It follows that the (2-o(1))-th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.
2. Hyperentangled Bell-state analysis
Tzu-Chieh Wei, Julio T. Barreiro, Paul G. Kwiat
Phys. Rev. A 75, 060305(R) (2007)
http://arxiv.org/abs/quant-ph/0703117
It is known that it is impossible to unambiguously distinguish the four Bell states encoded in pairs of photon polarizations using only linear optics. However, hyperentanglement, the simultaneous entanglement in more than one degree of freedom, has been shown to assist the complete Bell analysis of the four Bell states (given a fixed state of the other degrees of freedom). Yet introducing other degrees of freedom also enlarges the total number of Bell-like states. We investigate the limits for unambiguously distinguishing these Bell-like states. In particular, when the additional degree of freedom is qubit-like, we find that the optimal one-shot discrimination schemes are to group the 16 states into 7 distinguishable classes, and that an unambiguous discrimination is possible with two identical copies.
3. The mathematical role of (commutative and noncommutative) infinitesimal random walks over (commutative and noncommutative) riemannian manifolds in Quantum Physics
Gavriel Segre
http://arxiv.org/abs/math-ph/0703011
Anderson's nonstandard construction of brownian motion as an infinitesimal random walk on the euclidean line is generalized to an Hausdorff riemannian manifold. A nonstandard Feynman-Kac formula holding on such an Hausdorff riemannian manifold is derived. Indications are given on how these (radically elementary) results could allow to formulate a nonstandard version of Stochastic Mechanics (avoiding both the explicitly discussed bugs of Internal Set Theory as well as the controversial renormalization of the stochastic action). It is anyway remarked how this would contribute to hide the basic feature of Quantum Mechanics, i.e. the noncommutativity of the observables' algebra, whose structure is naturally captured in the language of Noncommutative Probability and Noncommutative Geometry. With this respect some preliminary consideration concerning the notion of infinitesimal quantum random walk on a noncommutative riemannian manifold, the notion obtained by the Sinha-Goswami's definition of quantum brownian motion on a noncommutative riemannian manifold replacing a continuous time interval with an hyperfinite time interval, is presented.