1. Quantum walk based search algorithms
Miklos Santha
5th Theory and Applications of Models of Computation (TAMC08), Xian, April 2008, LNCS 4978, 31-46
http://arxiv.org/abs/0808.0059
In this survey paper we give an intuitive treatment of the discrete time quantization of classical Markov chains. Grover search and the quantum walk based search algorithms of Ambainis, Szegedy and Magniez et al. will be stated as quantum analogues of classical search procedures. We present a rather detailed description of a somewhat simplified version of the MNRS algorithm. Finally, in the query complexity model, we show how quantum walks can be applied to the following search problems: Element Distinctness, Matrix Product Verification, Restricted Range Associativity, Triangle, and Group Commutativity.
2. On the hitting times of quantum versus random walks
Frederic Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha
http://arxiv.org/abs/0808.0084
In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case. Further, we prove that for any reversible ergodic Markov chain $P$, the quantum hitting time of the quantum analogue of $P$ has the same order as the square root of the classical hitting time of $P$. We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. Finally, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem for the 2D grid. Extending his result, we show that for any state-transitive Markov chain with unique marked state, the quantum hitting time is of the same order for both the detection and finding problems.
3. Non-malleable encryption of quantum information
Andris Ambainis, Jan Bouda, Andreas Winter
http://arxiv.org/abs/0808.0353
We introduce the notion of "non-malleability" of a quantum state encryption scheme (in dimension d): in addition to the requirement that an adversary cannot learn information about the state, here we demand that no controlled modification of the encrypted state can be effected. We show that such a scheme is equivalent to a "unitary 2-design" [Dankert et al.], as opposed to normal encryption which is a unitary 1-design. Our other main results include a new proof of the lower bound of (d^2-1)^2+1 on the number of unitaries in a 2-design [Gross et al.], which lends itself to a generalization to approximate 2-design. Furthermore, while in prime power dimension there is a unitary 2-design with =< d^5 elements, we show that there are always approximate 2-designs with O(epsilon^{-2} d^4 log d) elements.
4. Quantum Algorithms
Michele Mosca
http://arxiv.org/abs/0808.0369
This article surveys the state of the art in quantum computer algorithms, including both black-box and non-black-box results. It is infeasible to detail all the known quantum algorithms, so a representative sample is given. This includes a summary of the early quantum algorithms, a description of the Abelian Hidden Subgroup algorithms (including Shor's factoring and discrete logarithm algorithms), quantum searching and amplitude amplification, quantum algorithms for simulating quantum mechanical systems, several non-trivial generalizations of the Abelian Hidden Subgroup Problem (and related techniques), the quantum walk paradigm for quantum algorithms, the paradigm of adiabatic algorithms, a family of ``topological'' algorithms, and algorithms for quantum tasks which cannot be done by a classical computer, followed by a discussion.
5. Mixing of Quantum Walks on Generalized Hypercubes
Ana Best, Markus Kliegl, Shawn Mead-Gluchacki, Christino Tamon
International Journal of Quantum Information 6(6):1135-1148, 2008.
http://arxiv.org/abs/0808.2382
We study continuous-time quantum walks on graphs which generalize the hypercube. The only known family of graphs whose quantum walk instantaneously mixes to uniform is the Hamming graphs with small arities. We show that quantum uniform mixing on the hypercube is robust under the addition of perfect matchings but not much else. Our specific results include: (1) The graph obtained by augmenting the hypercube with an additive matching is instantaneous uniform mixing whenever the parity of the matching is even, but with a slower mixing time. This strictly includes Moore-Russell's result on the hypercube. (2) The class of Hamming graphs is not uniform mixing if and only if its arity is greater than 5. This is a tight characterization of quantum uniform mixing on Hamming graphs; previously, only the status of arity less than 5 was known. (3) The bunkbed graph B(A[f]), defined by a hypercube-circulant matrix A and a Boolean function f, is not uniform mixing if the Fourier transform of f has small support. This explains why the hypercube is uniform mixing and why the join of two hypercubes is not.
6. Closed Timelike Curves Make Quantum and Classical Computing Equivalent
Scott Aaronson, John Watrous
http://arxiv.org/abs/0808.2669
While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas. In this paper we show that if CTCs existed, then quantum computers would be no more powerful than classical computers: both would have the (extremely large) power of the complexity class PSPACE, consisting of all problems solvable by a conventional computer using a polynomial amount of memory. This solves an open problem proposed by one of us in 2005, and gives an essentially complete understanding of computational complexity in the presence of CTCs. Following the work of Deutsch, we treat a CTC as simply a region of spacetime where a "causal consistency" condition is imposed, meaning that Nature has to produce a (probabilistic or quantum) fixed-point of some evolution operator. Our conclusion is then a consequence of the following theorem: given any quantum circuit (not necessarily unitary), a fixed-point of the circuit can be (implicitly) computed in polynomial space. This theorem might have independent applications in quantum information.
7. Reexamination of decoherence in quantum walks on the hypercube
Frederick W. Strauch
http://arxiv.org/abs/0808.3403
The effect of decoherence on the continuous-time quantum walk on the hypercube is revisited. Previously, an exact solution was found for a decoherence model that preserved the effective tensor-product form of the dynamics. Here a new model is presented, inspired by perfect quantum state transfer in qubit networks. A perturbative solution is found for the dynamics of this model which is not of a tensor-product form. In contrast to previous results, the hitting probability has a lower bound that is independent of the hypercube dimension.