1. Two-particle fermionic quantum walks on a cycle graph
Alexey A. Melnikov, Leonid E. Fedichkin
http://arxiv.org/abs/1310.0420
In this paper we study quantum walks of electrons on a graph. This graph is composed of Si quantum dots arranged in a circle. Electrons can tunnel between neighbouring dots and interact via Coulomb interaction. We show that this mutual repulsion leads to entanglement. Fermionic entanglement dynamics is evaluated by several measures. Current detectors are considered in the paper as a noisy environment. We show that depending on the noise parameters fermionic entanglement can be annihilated, preserved, created for a certain time or re-created after annihilation.
2. Finding structural anomalies in star graphs: A general approach
Seth Cottrell, Mark Hillery
Phys. Rev. Lett. 112, 030501 (2014)
http://arxiv.org/abs/1310.3147
We develop a general theory for a quantum-walk search on a star graph. A star graph has N edges each of which is attached to a central vertex. A graph G is attached to one of these edges, and we would like to find out to which edge it is attached. This is done by means of a quantum walk, a quantum version of a random walk. This walk contains O(\sqrt{N}) steps, which represents a speedup over a classical search, which would require O(N) steps. The overall graph, star plus G, is divided into two parts, and we find that for a quantum speedup to occur, the eigenvalues associated with these two parts in the N goes to infinity limit must be the same. Our theory tells us how the initial state of the walk should be chosen, and how many steps the walk must make in order to find G.
3. Universal State Transfer on Graphs
Stephen Cameron, Shannon Fehrenbach, Leah Granger, Oliver Hennigh, Sunrose Shrestha, Christino Tamon
Linear Algebra and Its Applications 455:115-142, 2014
http://arxiv.org/abs/1310.3885
A continuous-time quantum walk on a graph $G$ is given by the unitary matrix $U(t) = \exp(-itA)$, where $A$ is the Hermitian adjacency matrix of $G$. We say $G$ has pretty good state transfer between vertices $a$ and $b$ if for any $\epsilon > 0$, there is a time $t$, where the $(a,b)$-entry of $U(t)$ satisfies $|U(t)_{a,b}| \ge 1-\epsilon$. This notion was introduced by Godsil (2011). The state transfer is perfect if the above holds for $\epsilon = 0$. In this work, we study a natural extension of this notion called universal state transfer. Here, state transfer exists between every pair of vertices of the graph. We prove the following results about graphs with this stronger property: (1) Graphs with universal state transfer have distinct eigenvalues and flat eigenbasis (where each eigenvector has entries which are equal in magnitude). (2) The switching automorphism group of a graph with universal state transfer is abelian and its order divides the size of the graph. Moreover, if the state transfer is perfect, then the switching automorphism group is cyclic. (3) There is a family of prime-length cycles with complex weights which has universal pretty good state transfer. This provides a concrete example of an infinite family of graphs with the universal property. (4) There exists a class of graphs with real symmetric adjacency matrices which has universal pretty good state transfer. In contrast, Kay (2011) proved that no graph with real-valued adjacency matrix can have universal perfect state transfer. We also provide a spectral characterization of universal perfect state transfer graphs that are switching equivalent to circulants.
4. Quantum Algorithms for Finding Constant-sized Sub-hypergraphs
Fran?ois Le Gall, Harumichi Nishimura, Seiichiro Tani
http://arxiv.org/abs/1310.4127
We develop a general framework to construct quantum algorithms that detect if a $3$-uniform hypergraph given as input contains a sub-hypergraph isomorphic to a prespecified constant-sized hypergraph. This framework is based on the concept of nested quantum walks recently proposed by Jeffery, Kothari and Magniez [SODA'13], and extends the methodology designed by Lee, Magniez and Santha [SODA'13] for similar problems over graphs. As applications, we obtain a quantum algorithm for finding a $4$-clique in a $3$-uniform hypergraph on $n$ vertices with query complexity $O(n^{1.883})$, and a quantum algorithm for determining if a ternary operator over a set of size $n$ is associative with query complexity $O(n^{2.113})$.
5. Quantum computation of discrete logarithms in semigroups
Andrew M. Childs, G��bor Ivanyos
Journal of Mathematical Cryptology 8, no. 4, 405-416 (2014)
http://arxiv.org/abs/1310.6238
We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor's algorithms for period finding and discrete log as subroutines. Thus proposed cryptosystems based on the presumed hardness of discrete logarithms in semigroups are insecure against quantum attacks. In contrast, we show that some generalizations of the discrete log problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete log problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to $k \ge 2$ generators in a black-box abelian semigroup of order $N$ requires $\tilde \Theta(N^{\frac{1}{2}-\frac{1}{2k}})$ quantum queries.
6. Generation of Universal Linear Optics by Any Beamsplitter
Adam Bouland, Scott Aaronson
Phys. Rev. A 89, 062316 (2014)
http://arxiv.org/abs/1310.6718
In 1994, Reck et al. showed how to realize any unitary transformation on a single photon using a product of beamsplitters and phaseshifters. Here we show that any single beamsplitter that nontrivially mixes two modes, also densely generates the set of unitary transformations (or orthogonal transformations, in the real case) on the single-photon subspace with m>=3 modes. (We prove the same result for any two-mode real optical gate, and for any two-mode optical gate combined with a generic phaseshifter.) Experimentally, this means that one does not need tunable beamsplitters or phaseshifters for universality: any nontrivial beamsplitter is universal for linear optics. Theoretically, it means that one cannot produce "intermediate" models of linear optical computation (analogous to the Clifford group for qubits) by restricting the allowed beamsplitters and phaseshifters: there is a dichotomy; one either gets a trivial set or else a universal set. No similar classification theorem for gates acting on qubits is currently known. We leave open the problem of classifying optical gates that act on three or more modes.
7. Quantum walk with a general coin: Exact solution and asymptotic properties
Miquel Montero
Quantum Information Processing, March 2015, Volume 14, Issue 3, pp 839-866
http://arxiv.org/abs/1310.7486
In this paper we present closed-form expressions for the wave function that governs the evolution of the discrete-time quantum walk on a line when the coin operator is arbitrary. The formulas were derived assuming that the walker can either remain put in the place or proceed in a fixed direction but never move backward, although they can be easily modified to describe the case in which the particle can travel in both directions. We use these expressions to explore the properties of magnitudes associated to the process, as the probability mass function or the probability current, even though we also consider the asymptotic behavior of the exact solution. Within this approximation, we will estimate upper and lower bounds, consider the origins of an emerging approximate symmetry, and deduce the general form of the stationary probability density of the relative location of the walker.
8. Quantum random walks on congested lattices
Keith R. Motes, Alexei Gilchrist, Peter P. Rohde
http://arxiv.org/abs/1310.8161
We consider quantum random walks on congested lattices and contrast them to classical random walks. Congestion is modelled with lattices that contain static defects which reverse the walker's direction. We implement a dephasing process after each step which allows us to smoothly interpolate between classical and quantum random walkers as well as study the effect of dephasing on the quantum walk. Our key results show that a quantum walker escapes a finite boundary dramatically faster than a classical walker and that this advantage remains in the presence of heavily congested lattices. Also, we observe that a quantum walker is extremely sensitive to our model of dephasing.