1. A random walk approach to quantum algorithms
Viv Kendon
Phil. Trans. R. Soc. A (2006) 364, 3407-3422
http://arxiv.org/abs/quant-ph/0609035
The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial: pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e., when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk, due to interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point on average than a classical walker, and this forms the basis of a quantum speed up that can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, with even a small quantum computer available, development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.
2. Complete and Deterministic discrimination of polarization Bell state assisted by momentum entanglement
M. Barbieri, G. Vallone, P. Mataloni, F. De Martini
Phys. Rev. A 75, 042317 (2007)
http://arxiv.org/abs/quant-ph/0609080
A complete and deterministic Bell state measurement was realized by a simple linear optics experimental scheme which adopts 2-photon polarization-momentum hyperentanglement. The scheme, which is based on the discrimination among the single photon Bell states of the hyperentangled state, requires the adoption of standard single photon detectors. The four polarization Bell states have been measured with average fidelity $F=0.889\pm0.010$ by using the linear momentum degree of freedom as the ancilla. The feasibility of the scheme has been characterized as a function of the purity of momentum entanglement.
3. Quantum Walks in an array of Quantum Dots
K. Manouchehri, J. B. Wang
http://arxiv.org/abs/quant-ph/0609088
Quantum random walks are shown to have non-intuitive dynamics, which makes them an attractive area of study for devising quantum algorithms for well-known classical problems as well as those arising in the field of quantum computing. In this work we propose a novel scheme for the physical implementation of a discrete-time quantum random walk using laser excitations of the electronic states of an array of quantum dots. These dots represent the discrete nodes of the walk, while transitions between the energy levels inside each dot correspond to the required coin operation and stimulated Raman adiabatic passage (STIRAP) processes are employed to induce the steps of the walk. The quantum dot design is tailored in such a way as to enable selective coupling of the energy levels. Our simulation results show a close agreement with the ideal quantum walk distribution as well as modest robustness towards noise disturbance.
4. Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
Andrew M. Childs, Aram W. Harrow, Pawel Wocjan
Proc. 24th Symposium on Theoretical Aspects of Computer Science (STACS 2007), Lecture Notes in Computer Science 4393, pp. 598-609
http://arxiv.org/abs/quant-ph/0609110
Schur duality decomposes many copies of a quantum state into subspaces labeled by partitions, a decomposition with applications throughout quantum information theory. Here we consider applying Schur duality to the problem of distinguishing coset states in the standard approach to the hidden subgroup problem. We observe that simply measuring the partition (a procedure we call weak Schur sampling) provides very little information about the hidden subgroup. Furthermore, we show that under quite general assumptions, even a combination of weak Fourier sampling and weak Schur sampling fails to identify the hidden subgroup. We also prove tight bounds on how many coset states are required to solve the hidden subgroup problem by weak Schur sampling, and we relate this question to a quantum version of the collision problem.
5. Discrete time quantum walk model for single and entangled particles to retain entanglement in coin space
C.M. Chandrashekar
http://arxiv.org/abs/quant-ph/0609113
In most widely discussed discrete time quantum walk model, after every unitary shift operator, the particle evolves into the superposition of position space and settles down in one of its basis states, loosing entanglement in the coin space in the new position. The Hadamard operation is applied to let the particle to evolve into the superposition in the coin space and the walk is iterated. We present a model with a additional degree of freedom for the unitary shift operator $U^{\prime}$. The unitary operator with additional degree of freedom will evolve the quantum particle into superposition of position space retaining the entanglement in coin space. This eliminates the need for quantum coin toss (Hadamard operation) after every unitary displacement operation as used in most widely studied version of the discrete time quantum walk model. This construction is easily extended to a multiple particle quantum walk and in this article we extend it for a pair of particles in pure state entangled in coin degree of freedom by simultaneously subjecting it to a pair of unitary displacement operators which were constructed for single particle. We point out that unlike for single particle quantum walk, upon measurement of its position after $N$ steps, the entangled particles are found together with 1/2 probability and at different positions with 1/2 probability. This can act as an advantage in applications of the quantum walk. A special case is also treated using a complex physical system such as, inter species two-particle entangled Bose-Einstein condensate, as an example.
6. Distributions of continuous-time quantum walks
Arvid J. Bessen
http://arxiv.org/abs/quant-ph/0609128
We study the distributions of the continuous-time quantum walk on a one-dimensional lattice. In particular we will consider walks on unbounded lattices, walks with one and two boundaries and Dirichlet boundary conditions, and walks with periodic boundary conditions. We will prove that all continuous-time quantum walks can be written as a series of Bessel functions of the first kind and show how to approximate these series.
7. Quantum search with variable times
Andris Ambainis
http://arxiv.org/abs/quant-ph/0609168
Since Grover's seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items and we would like to find a marked item. We consider a new variant of this problem in which evaluating the i-th item may take a different number of time steps for different i. Let t_i be the number of time steps required to evaluate the i-th item. If the numbers t_i are known in advance, we give an algorithm that solves the problem in O(\sqrt{t_1^2+t_2^2+...+t_n^2}) steps. This is optimal, as we also show a matching lower bound. The case, when t_i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.
8. Quantum speedup of classical mixing processes
Peter C. Richter
Phys. Rev. A 76, 042306 (2007)
http://arxiv.org/abs/quant-ph/0609204
Most approximation algorithms for #P-complete problems (e.g., evaluating the permanent of a matrix or the volume of a polytope) work by reduction to the problem of approximate sampling from a distribution $\pi$ over a large set $\S$. This problem is solved using the {\em Markov chain Monte Carlo} method: a sparse, reversible Markov chain $P$ on $\S$ with stationary distribution $\pi$ is run to near equilibrium. The running time of this random walk algorithm, the so-called {\em mixing time} of $P$, is $O(\delta^{-1} \log 1/\pi_*)$ as shown by Aldous, where $\delta$ is the spectral gap of $P$ and $\pi_*$ is the minimum value of $\pi$. A natural question is whether a speedup of this classical method to $O(\sqrt{\delta^{-1}} \log 1/\pi_*)$, the diameter of the graph underlying $P$, is possible using {\em quantum walks}. We provide evidence for this possibility using quantum walks that {\em decohere} under repeated randomized measurements. We show: (a) decoherent quantum walks always mix, just like their classical counterparts, (b) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (c) the mixing time of the decoherent quantum walk on a periodic lattice $\Z_n^d$ is $O(n d \log d)$, which is indeed $O(\sqrt{\delta^{-1}} \log 1/\pi_*)$ and is asymptotically no worse than the diameter of $\Z_n^d$ (the obvious lower bound) up to at most a logarithmic factor.
9. Exploring scalar quantum walks on Cayley graphs
Olga Lopez Acevedo, J��r��mie Roland, Nicolas J. Cerf
Quantum Information & Computation, 8(1&2):68-81, 2008.
http://arxiv.org/abs/quant-ph/0609234
A quantum walk, \emph{i.e.}, the quantum evolution of a particle on a graph, is termed \emph{scalar} if the internal space of the moving particle (often called the coin) has a dimension one. Here, we study the existence of scalar quantum walks on Cayley graphs, which are built from the generators of a group. After deriving a necessary condition on these generators for the existence of a scalar quantum walk, we present a general method to express the evolution operator of the walk, assuming homogeneity of the evolution. We use this necessary condition and the subsequent constructive method to investigate the existence of scalar quantum walks on Cayley graphs of various groups presented with two or three generators. In this restricted framework, we classify all groups -- in terms of relations between their generators -- that admit scalar quantum walks, and we also derive the form of the most general evolution operator. Finally, we point out some interesting special cases, and extend our study to a few examples of Cayley graphs built with more than three generators.