1. Optimal measurements for the dihedral hidden subgroup problem
Dave Bacon, Andrew M. Childs, Wim van Dam
Chicago Journal of Theoretical Computer Science (2006), no. 2
http://arxiv.org/abs/quant-ph/0501044
We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.
2. Decoherence in Quantum Walks on the Hypercube
Gorjan Alagic, Alexander Russell
Physical Review A 72, 062304 (2005)
http://arxiv.org/abs/quant-ph/0501169
We study a natural notion of decoherence on quantum random walks over the hypercube. We prove that in this model there is a decoherence threshold beneath which the essential properties of the hypercubic quantum walk, such as linear mixing times, are preserved. Beyond the threshold, we prove that the walks behave like their classical counterparts.
3. Dephasing by a nonstationary classical intermittent noise
Josef Schriefl, Maxime Clusel, David Carpentier, Pascal Degiovanni
http://arxiv.org/abs/cond-mat/0501301
We consider a new phenomenological model for a $1/f^{\mu}$ classical intermittent noise and study its effects on the dephasing of a two-level system. Within this model, the evolution of the relative phase between the $|\pm>$ states is described as a continuous time random walk (CTRW). Using renewal theory, we find exact expressions for the dephasing factor and identify the physically relevant various regimes in terms of the coupling to the noise. In particular, we point out the consequences of the non-stationarity and pronounced non-Gaussian features of this noise, including some new anomalous and aging dephasing scenarii.