1. Quantum Diffusions and Appell Systems
Demosthenes Ellinas
http://arxiv.org/abs/quant-ph/0001047
Within the algebraic framework of Hopf algebras, random walks and associated diffusion equations (master equations) are constructed and studied for two basic operator algebras of Quantum Mechanics i.e the Heisenberg-Weyl algebra (hw) and its q-deformed version hw_q. This is done by means of functionals determined by the associated coherent state density operators. The ensuing master equations admit solutions given by hw and hw_q-valued Appell systems.
2. Query Complexity: Worst-Case Quantum Versus Average-Case Classical
Scott Aaronson
http://arxiv.org/abs/cs/0001013
In this note we investigate the relationship between worst-case quantum query complexity and average-case classical query complexity. Specifically, we show that if a quantum computer can evaluate a total Boolean function f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^5) queries in the average case, under a uniform distribution of inputs. If f is monotone, we show furthermore that only O(T^3) queries are needed. Previously, Beals et al. (1998) showed that if a quantum computer can evaluate f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^6) queries in the worst case, or O(T^4) if f is monotone. The optimal bound is conjectured to be O(T^2), but improving on O(T^6) remains an open problem. Relating worst-case quantum complexity to average-case classical complexity may suggest new ways to reduce the polynomial gap in the ordinary worst-case versus worst-case setting.