1. Quantum Lattice Boltzmann is a quantum walk
Sauro Succi, Francois Fillion-Gourdeau, Silvia Palpacelli
http://www.arxiv.org/abs/1504.03158
Numerical methods for the 1-D Dirac equation based on operator splitting and on the quantum lattice Boltzmann (QLB) schemes are reviewed. It is shown that these discretizations fall within the class of quantum walks, i.e. discrete maps for complex fields, whose continuum limit delivers Dirac-like relativistic quantum wave equations. The correspondence between the quantum walk dynamics and these numerical schemes is given explicitly, allowing a connection between quantum computations, numerical analysis and lattice Boltzmann methods. The QLB method is then extended to the Dirac equation in curved spaces and it is demonstrated that the quantum walk structure is preserved. Finally, it is argued that the existence of this link between the discretized Dirac equation and quantum walks may be employed to simulate relativistic quantum dynamics on quantum computers.
2. Control of two-photon quantum walk in a complex multimode system by wavefront shaping
Hugo Defienne, Marco Barbieri, Ian A. Walmsley, Brian J. Smith, Sylvain Gigan
http://www.arxiv.org/abs/1504.03178
Multi-photon interferences in complex multimode structures - quantum walks - are of both funda- mental and technological interest. They rely on the ability to design the complex network where the walk occurs. Here, we demonstrate the control of quantum walks of two indistinguishable photons in a complex linear system - a highly multimode fiber - by means of wavefront shaping techniques. Using the measured transmission matrix of the fiber, we demonstrate the ability to address arbitrary output modes of the two-photon speckle pattern, and simultaneous control of the quantum inter- ferences. This work provides a reconfigurable platform for multi-photon, multimode interference experiments and a route to high-dimensional quantum systems.
3. Continuous decomposition of quantum measurements via Hamiltonian feedback
Jan Florjanczyk, Todd A. Brun
http://www.arxiv.org/abs/1504.03772
We characterize the set of generalized quantum measurements that can be decomposed into a continuous measurement process using a stream of probe qubits and a tunable interaction Hamilto- nian. Each probe in the stream interacts weakly with the target quantum system, then is measured projectively in a standard basis. This measurement result is used in a closed feedback loop to tune the interaction Hamiltonian for the next probe. The resulting evolution is a stochastic process with the structure of a one-dimensional random walk. To maintain this structure, and require that at long times the measurement outcomes be independent of the path, the allowed interaction Hamil- tonians must lie in a restricted set, such that the Hamiltonian terms on the target system form a finite dimensional Jordan algebra. This algebraic structure of the interaction Hamiltonians yields a large class of generalized measurements that can be continuously performed by our scheme, and we fully describe this set.
4. The Classification of Reversible Bit Operations
Scott Aaronson, Daniel Grier, Luke Schaeffer
http://www.arxiv.org/abs/1504.05155
We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical logic from the 1940s. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits. Our theorem implies a linear-time algorithm (which we have implemented), that takes as input the truth tables of reversible gates G and H, and that decides whether G generates H. Previously, this problem was not even known to be decidable. The theorem also implies that any n-bit reversible circuit can be "compressed" to an equivalent circuit, over the same gates, that uses at most 2^n*poly(n) gates and O(1) ancilla bits; these are the first upper bounds on these quantities known, and are close to optimal. Finally, the theorem implies that every non-degenerate reversible gate can implement either every reversible transformation, or every affine transformation, when restricted to an "encoded subspace." Briefly, the theorem says that every set of reversible gates generates either all reversible transformations on n-bit strings (as the Toffoli gate does); no transformations; all transformations that preserve Hamming weight (as the Fredkin gate does); all transformations that preserve Hamming weight mod k for some k; all affine transformations (as the Controlled-NOT gate does); all affine transformations that preserve Hamming weight mod 2 or mod 4, inner products mod 2, or a combination thereof; or a previous class augmented by a NOT or NOTNOT gate. Ruling out the possibility of additional classes, not in the list, requires some arguments about polynomials, lattices, and Diophantine equations.
5. The effect of noise correlations on randomized benchmarking
Harrison Ball, Thomas M. Stace, Steven T. Flammia, Michael J. Biercuk
http://www.arxiv.org/abs/1504.05307
Randomized benchmarking is an important statistical tool for characterising the performance of high-fidelity quantum gates. Here we study randomized benchmarking in the presence of quasi-static (i.e. low-frequency) errors. We contrast the resulting fidelity with that under the conventional assumption of Markovian errors. We treat these limiting cases analytically by mapping the averaging process to a random walk in "Pauli space". In the quasi-static case, we find a broad, highly skewed distribution of fidelities, while Markovian errors produce a narrow, approximately Gaussian distribution of fidelities. We use the filter-transfer function formalism to reveal the underlying reason for these differences in terms of effective coherent averaging of correlated errors in certain random sequences. Large skew in the distribution towards high-fidelity outcomes -- consistent with existing experimental data -- highlights potential finite-sampling pitfalls when deploying randomized benchmarking. Moreover, these results demonstrate general challenges in extracting useful single-gate fidelities from randomized benchmarking measurements with correlated errors.
6. Nonhomogeneous quantum Markov chains and a notion of ergodicity
Carlos F. Lardizabal, Rafael R. Souza
http://www.arxiv.org/abs/1504.05398
Motivated by a model presented by S. Gudder, we study a quantum generalization of Markov chains and discuss the relation between these maps and open quantum random walks, a class of quantum channels described by S. Attal et al. We consider processes which are nonhomogeneous in time, i.e., at each time step, a possibly distinct evolution kernel. Inspired by a spectral technique described by L. Saloff-Coste and J. Z\'u\~niga, we define a notion of ergodicity for nonhomogeneous quantum Markov chains and describe a criterion for ergodicity of such objects in terms of singular values. As a consequence we obtain a quantum version of the classical probability result concerning the behavior of the columns (or rows) of the iterates of a stochastic matrix induced by a finite, irreducible, aperiodic Markov chain. We are also able to relate the ergodic property presented here with the notions of weak and uniform ergodicity known in the literature of noncommutative $L^1$-spaces.
7. Bosonic interference as a complementary resource for implementation of quantum walks
Magdalena Stobi��ska, Peter P. Rohde, Pawe? Kurzy��ski
http://www.arxiv.org/abs/1504.05480
Quantum walks are interesting simple models for describing various fundamental processes in nature ranging from chaos or photosynthesis to universal quantum computation. Their implementation usually comprises a single particle and $O(n^2)$ optical elements, where $n$ is the size of the quantum walk space. The question arises if this can be achieved with fewer or complementary resources. Here we show that this can be done using a multi-particle Hong--Ou--Mandel interference. It employs $O(n)$ indistinguishable bosons and a single beam splitter to achieve a similar quantum walk. In addition we show that a quantum-to-classical transition takes place if the particles become distinguishable. This approach establishes a link between the fundamental indistinguishability of quantum particles and the wavelike coherent nature of the walk.
8. Periodicity for the Hadamard walk on cycles
Norio Konno, Yuki Shimizu, Masato Takei
http://www.arxiv.org/abs/1504.06396
The present paper treats the period T_N of the Hadamard walk on a cycle C_N with N vertices. Dukes (2014) considered the periodicity of more general quantum walks on C_N and showed T_2 =2, T_4=8, T_8=24 for the Hadamard walk case. We prove that the Hadamard walk does not have any period except for his case, i.e., N=2, 4, 8. Our method is based on a path counting and cyclotomic polynomials which is different from his approach based on the property of eigenvalues for unitary matrix that determines the evolution of the walk.
9. Quantum speedup of Monte Carlo methods
Ashley Montanaro
http://www.arxiv.org/abs/1504.06987
Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomised or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.
10. Quantum Walk Search with Time-Reversal Symmetry Breaking
Thomas G. Wong
http://www.arxiv.org/abs/1504.07375
We formulate Grover's unstructured search algorithm as a chiral quantum walk, where transitioning in one direction has a phase conjugate to transitioning in the opposite direction. For small phases, this breaking of time-reversal symmetry is too small to significantly affect the evolution: the system still approximately evolves in its ground and first excited states, rotating to the marked vertex in time $\pi \sqrt{N} / 2$. Increasing the phase does not change the runtime, but rather changes the support for the 2D subspace, so the system evolves in its first and second excited states, or its second and third excited states, and so forth. Apart from the critical phases corresponding to these transitions in the support, which become more frequent as the phase grows, this reveals that our model of quantum search is robust against time-reversal symmetry breaking.
11. Asymptotic properties of the Dirac quantum cellular automaton
A. P��rez
http://www.arxiv.org/abs/1504.07418
We show that the Dirac quantum cellular automaton [Ann. Phys. 354 (2015) 244] shares many properties in common with the discrete-time quantum walk. These similarities can be exploited to redefine the automaton as a unitary process that takes place at regular time steps on a one-dimensional lattice with an arbitrary lattice spacing. In this way, it becomes an alternative to the quantum walk, with a dispersion relation that can be controlled by a mass parameter, playing a similar role to the coin angle in the quantum walk. Moreover, the Dirac Hamiltonian is recovered under a suitable limit. We also provide two independent analytical approximations to the long term probability distribution. It is shown that, starting from localized conditions, the asymptotic value of the entropy of entanglement between internal and motional degrees of freedom overcomes the known limit that is approached by the quantum walk for the same initial conditions, and are similar to the ones achieved by highly localized states of the Dirac equation.