1. Spectra of Quantized Walks and a $\sqrt{�Ħ�}$ rule
Mario Szegedy
http://arxiv.org/abs/quant-ph/0401053
We introduce quantized bipartite walks, compute their spectra, generalize the algorithms of Grover \cite{g} and Ambainis \cite{amb03} and interpret them as quantum walks with memory. We compare the performance of walk based classical and quantum algorithms and show that the latter run much quicker in general. Let $P$ be a symmetric Markov chain with transition probabilities $P[i,j]$, $(i ,j\in [n])$. Some elements of the state space are marked. We are promised that the set of marked elements has size either zero or at least $\epsilon n$. The goal is to find out with great certainty which of the above two cases holds. Our model is a black box that can answer certain yes/no questions and can generate random elements picked from certain distributions. More specifically, by request the black box can give us a uniformly distributed random element for the cost of $\wp_{0}$. Also, when ``inserting'' an element $i$ into the black box we can obtain a random element $j$, where $j$ is distributed according to $P[i,j]$. The cost of the latter operation is $\wp_{1}$. Finally, we can use the black box to test if an element $i$ is marked, and this costs us $\wp_{2}$. If $\delta$ is the eigenvalue gap of $P$, there is a simple classical algorithm with cost $O(\wp_{0} + (\wp_{1}+\wp_{2})/\delta\epsilon)$ that solves the above promise problem. (The algorithm is efficient if $\wp_{0}$ is much larger than $\wp_{1}+\wp_{2}$.) In contrast,we show that for the ``quantized'' version of the algorithm it costs only $O(\wp_{0} + (\wp_{1}+\wp_{2})/\sqrt{\delta\epsilon})$ to solve the problem. We refer to this as the $\sqrt{\delta\epsilon}$ rule. Among the technical contributions we give a formula for the spectrum of the product of two general reflections.
2. Is Quantum Mechanics An Island In Theoryspace?
Scott Aaronson
http://arxiv.org/abs/quant-ph/0401062
This recreational paper investigates what happens if we change quantum mechanics in several ways. The main results are as follows. First, if we replace the 2-norm by some other p-norm, then there are no nontrivial norm-preserving linear maps. Second, if we relax the demand that norm be preserved, we end up with a theory that allows rapid solution of PP-complete problems (as well as superluminal signalling). And third, if we restrict amplitudes to be real, we run into a difficulty much simpler than the usual one based on parameter-counting of mixed states.
3. Estimating mixing properties of local Hamiltonian dynamics and continuous quantum random walks is PSPACE-hard
Pawel Wocjan
http://arxiv.org/abs/quant-ph/0401184
A major topic of (classical) ergodic theory is to examine qualitatively how the phase space of dynamical systems is penetrated by the orbits of their dynamics. We consider interacting qubit systems with dynamics according to 4-local Hamiltonians and continuous quantum random walks. For these systems one could use the von Neumann entropy of the time-average to characterize the mixing properties of the corresponding orbits, i.e., what portion of the state space and how uniformly it is filled out by the orbits. We show that the problem of estimating this entropy is PSPACE-hard.