1. Suitable bases for quantum walks with Wigner coins
Iva Bezdekova, Martin Stefanak, Igor Jex
Phys. Rev. A 92, 022347 (2015)
http://www.arxiv.org/abs/1509.00960
The analysis of a physical problem simplifies considerably when one uses a suitable coordinate system. We apply this approach to the discrete-time quantum walks with coins given by $2j+1$-dimensional Wigner rotation matrices (Wigner walks), a model which was introduced in T. Miyazaki et al., Phys. Rev. A 76, 012332 (2007). First, we show that from the three parameters of the coin operator only one is physically relevant for the limit density of the Wigner walk. Next, we construct a suitable basis of the coin space in which the limit density of the Wigner walk acquires a much simpler form. This allows us to identify various dynamical regimes which are otherwise hidden in the standard basis description. As an example, we show that it is possible to find an initial state which reduces the number of peaks in the probability distribution from generic $2j+1$ to a single one. Moreover, the models with integer $j$ lead to the trapping effect. The derived formula for the trapping probability reveals that it can be highly asymmetric and it deviates from purely exponential decay. Explicit results are given up to the dimension five.
2. Quantum walk speedup of backtracking algorithms
Ashley Montanaro
http://www.arxiv.org/abs/1509.02374
We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on n variables, or outputs that none exists, and whose corresponding tree contains T vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using O(sqrt(T) n^(3/2) log n) tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree. We also discuss how, for certain distributions on the inputs, the algorithm can lead to an average-case exponential speedup.
3. The Localization in Quantum Walks on a Honeycomb Network
Changyuan Lyu, Luyan Yu, Shengjun Wu
http://www.arxiv.org/abs/1509.03919
We systematically study the localization effect in discrete-time quantum walks on a honeycomb network and establish the mathematical framework. We focus on the Grover walk first and rigorously derive the limit form of the walker's state, showing it has a certain probability to be localized at the starting position. The relationship between localization and the initial coin state is concisely represented by a linear map. We also define and calculate the average probability of localization by generating random initial states. Further, coin operators varying with positions are considered and the sufficient condition for localization is discussed. We also similarly analyze another four-state Grover walk. Theoretical predictions are all in accord with numerical simulation results. Finally, our results are compared with previous works to demonstrate the unusual trapping effect of quantum walks on a honeycomb network, as well as the advantages of our method.
4. Discrete dynamics and non-Markovianity
Kimmo Luoma, Jyrki Piilo
http://www.arxiv.org/abs/1509.04231
We study discrete quantum dynamics where single evolution step consists of unitary system transformation followed by decoherence via coupling to an environment. Often non-Markovian memory effects are attributed to structured environments whereas here we take a more general approach within discrete setting. In addition of controlling the structure of the environment, we are interested in how local unitaries on the open system allow the appearance and control of memory effects. Our first simple qubit model, where local unitary is followed by dephasing, illustrates how memory effects arise despite of having no-structure in the environment the system is coupled with. We then elaborate this observation by constructing a model for open quantum walk where the unitary coin and transfer operation is augmented with dephasing of the coin. The results demonstrate that in the limit of strong dephasing within each evolution step, the combined coin-position open system always displays memory effects and their quantity is independent of the structure of the environment. Our construction makes possible an experimentally realizable open quantum walk with photons exhibiting non-Markovian features.
5. Discrete-time quantum walks as generators of multipartite entanglement
Joshua Lockhart, Mauro Paternostro
http://www.arxiv.org/abs/1509.05816
We present an extension of the discrete time quantum walk on a graph to include a qubit at each vertex of the graph, with which the walker interacts at each time step. We show that allowing for a controlled-Z interaction between the walker and the vertex qubits generates multipartite entanglement between the qubits. We demonstrate that for particular coin operators the system generates a highly entangled cluster state, of use in one way quantum computation.
6. Exceptional configurations of quantum walks with Grover’s coin
Nikolajs Nahimovs, Alexander Rivosh
http://www.arxiv.org/abs/1509.06862
We study search by quantum walk on a two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. We show what the most natural coin transformation - Grover's diffusion transformation - has a wide class of exceptional configurations of marked locations, for which the probability of finding any of the marked locations does not grow over time. This extends the class of known exceptional configurations; until now the only known such configuration was the "diagonal construction" by Ambainis and Rivosh [AR08]
7. Quantum Walk on the Line through Potential Barriers
Thomas G. Wong
http://www.arxiv.org/abs/1509.07112
Quantum walks are well-known for their ballistic dispersion, traveling $\Theta(t)$ away in $t$ steps, which is quadratically faster than a classical random walk's diffusive spreading. In physical implementations of the walk, however, the particle may need to tunnel through a potential barrier to hop, and a naive calculation suggests this could eliminate the ballistic transport. We show by explicit calculation, however, that such a loss does not occur. Rather, the $\Theta(t)$ dispersion is retained, with only the coefficient changing, which additionally gives a way to detect and quantify the hopping errors in experiments.
8. Dirac Quantum Cellular Automaton from Split-step Quantum Walk
Arindam Mallick, C. M. Chandrashekar
http://www.arxiv.org/abs/1509.08851
Simulations of one quantum system by an other has an implications in realization of quantum machine that can imitate any quantum systems and solve problems that are not accessible to classical computers. One of the approach to engineer quantum simulations is to discretize the space-time degree of freedom in quantum dynamics and define the quantum cellular automata (QCA), a local unitary update rule on a lattice. Different models of QCA are constructed using different set of conditions which are not uniquely defined. The form of the operators in these model are not always in implementable configuration on an other system. Here, starting from a split-step discrete-time quantum walk (DTQW) which are uniquely defined for experimental implementation, we recover the Dirac quantum cellular automaton (DQCA). This will bridge the connection between Dirac equation(DE)-DQCA-DTQW and eliminate the explicit use of invariance, symmetries and limiting range of parameter to establish the connections. For a combination of parameters defining the split-step DTQW, we will show the recovery of all the fine oscillation of the probability distribution in position observed in DQCA but not in conventional DTQW. We will also present the Zitterbewegung oscillations and quantify the entanglement as a function of that parameters that define split-step DTQW. The unique definition of DTQW along with the parameter tuneability demonstrated in experimental implementation will establish it as an efficient tool to design quantum simulator with access to different physical regime and approach quantum field theory from principles of quantum information theory.
9. Equivalence between Szegedy’s and Coined Quantum Walks
Renato Portugal
http://www.arxiv.org/abs/1509.08852
Coined Quantum Walks (QWs) are being used in many contexts with the goal of understanding quantum systems and building quantum algorithms for quantum computers. Alternative models such as Szegedy's and continuous-time QWs were proposed taking advantage from the fact that quantum theory seems to allow different quantized versions based on the same classical model, in this case, the classical random walk. In this work we show the conditions upon which coined QWs are equivalent to Szegedy's QWs. Those QW models have in common a large class of instances, in the sense that the evolution operators are equal when we convert the graph on which the coined QW takes place into a bipartite graph on which Szegedy's QW takes place and vice versa. We also show that the abstract search algorithm using the coined QW model can be cast into Szegedy's searching framework using bipartite graphs with sinks.
10. Optimal quantum algorithm for polynomial interpolation
Andrew M. Childs, Wim van Dam, Shih-Han Hung, Igor E. Shparlinski
http://www.arxiv.org/abs/1509.09271
We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm's success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability.