1. Observation of quasiperiodic dynamics in a one-dimensional quantum walk of single photons in space
Peng Xue, Hao Qin, Bao Tang, Barry C. Sanders
New J. Phys. 16 053009 (6 May 2014)
http://arxiv.org/abs/1312.0123
We realize quasi-periodic dynamics of a quantum walker over 2.5 quasi-periods by realizing the walker as a single photon passing through a quantum-walk optical-interferometer network. We introduce fully controllable polarization-independent phase shifters in each optical path to realize arbitrary site-dependent phase shifts, and we employ large clear-aperture beam displacers, while maintaining high-visibility interference, to enable reaching 10 quantum-walk steps. By varying the half-wave-plate setting, we control the quantum-coin bias thereby observing a transition from quasi-periodic dynamics to ballistic diffusion.
2. Spatial Search on Grids with Minimum Memory
Andris Ambainis, Renato Portugal, Nikolay Nahimov
http://arxiv.org/abs/1312.0172
We study quantum algorithms for spatial search on finite dimensional grids. Patel et al. and Falk have proposed algorithms based on a quantum walk without a coin, with different operators applied at even and odd steps. Until now, such algorithms have been studied only using numerical simulations. In this paper, we present the first rigorous analysis for an algorithm of this type, showing that the optimal number of steps is $O(\sqrt{N\log N})$ and the success probability is $O(1/\log N)$, where $N$ is the number of vertices. This matches the performance achieved by algorithms that use other forms of quantum walks.
3. Quantifying quantumness via commutators: an application to quantum walk
Pavan Iyengar, G. N. Chandan, R. Srikanth
http://arxiv.org/abs/1312.1329
The question of witnessing or quantifying nonclassicality of quantum systems has been addressed in various ways. For a given system or theory, we propose identifying it with the incompatibility of admissible states. We quantify the nonclassicality of quantum systems using the Hilbert-Schmidt norm of the commutator of two states. As a particular application of this measure, we study the classicalization of a discrete-time quantum walk with a noisy coin.
4. Exponential improvement in precision for simulating sparse Hamiltonians
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma
Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014), pp. 283-292 (2014)
http://arxiv.org/abs/1312.1414
We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a $d$-sparse Hamiltonian $H$ acting on $n$ qubits can be simulated for time $t$ with precision $\epsilon$ using $O\big(\tau \frac{\log(\tau/\epsilon)}{\log\log(\tau/\epsilon)}\big)$ queries and $O\big(\tau \frac{\log^2(\tau/\epsilon)}{\log\log(\tau/\epsilon)}n\big)$ additional 2-qubit gates, where $\tau = d^2 \|{H}\|_{\max} t$. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.
5. Universally Optimal Noisy Quantum Walks on Complex Networks
Filippo Caruso
New J. Phys. 16, 055015 (2014), Focus on Quantum Efficiency
http://arxiv.org/abs/1312.1832
Transport properties play a crucial role in several fields of science, as biology, chemistry, sociology, information science, and physics. The behavior of many dynamical processes running over complex networks is known to be closely related to the geometry of the underlying topology, but this connection becomes even harder to understand when quantum effects come into play. Here, we exploit the Kossakoski-Lindblad formalism of quantum stochastic walks to investigate the capability to quickly and robustly transmit energy (or information) between two distant points in very large complex structures, remarkably assisted by external noise and quantum features as coherence. An optimal mixing of classical and quantum transport is, very surprisingly, quite universal for a large class of complex networks. This widespread behaviour turns out to be also extremely robust with respect to geometry changes. These results might pave the way for designing optimal bio-inspired geometries of efficient transport nanostructures that can be used for solar energy and also quantum information and communication technologies.
6. On physical problems that are slightly more difficult than QMA
Andris Ambainis
http://arxiv.org/abs/1312.4758
We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).
7. Quantum simulation of bosonic-fermionic non-interacting particles in disordered systems via quantum walk
Francesco De Nicola, Linda Sansoni, Andrea Crespi, Roberta Ramponi, Roberto Osellame, Vittorio Giovannetti, Rosario Fazio, Paolo Mataloni, Fabio Sciarrino
Phys. Rev. A 89, 032322 (2014)
http://arxiv.org/abs/1312.5538
We report on the theoretical analysis of bosonic and fermionic non-interacting systems in a discrete two-particle quantum walk affected by different kinds of disorder. We considered up to 100-step QWs with a spatial, temporal and space-temporal disorder observing how the randomness and the wavefunction symmetry non-trivially affect the final spatial probability distribution, the transport properties and the Shannon entropy of the walkers.
8. Asymmetric random walks in a discrete spacetime as a model for quantum mechanics
Antonio Sciarretta
http://arxiv.org/abs/1312.5977
This paper presents a simple model that mimics quantum mechanics (QM) results in terms of probability fields of free particles subject to self-interference, without using Schr\"{o}dinger equation or wavefunctions. Unlike the standard QM picture, the proposed model only uses integer-valued quantities and arithmetic operations. In particular, it assumes a discrete spacetime under the form of an euclidean lattice. The proposed approach describes individual particle trajectories as random walks. Transition probabilities are simple functions of a few quantities that are either randomly associated to the particles during their preparation, or stored in the lattice sites they visit during the walk. Non-relativistic QM predictions, particularly self-interference, are retrieved as probability distributions of similarly-prepared ensembles of particles. Extension to interacting particles is discussed but not detailed in this paper.
9. Weak Parity
Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian
http://arxiv.org/abs/1312.0036
We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that n randomized queries and n/2 quantum queries are needed to compute parity on all inputs. But surprisingly, we give a randomized algorithm for Weak Parity that makes only O(n/log^0.246(1/eps)) queries, as well as a quantum algorithm that makes only O(n/sqrt(log(1/eps))) queries. We also prove a lower bound of Omega(n/log(1/eps)) in both cases; and using extremal combinatorics, prove lower bounds of Omega(log n) in the randomized case and Omega(sqrt(log n)) in the quantum case for any eps>0. We show that improving our lower bounds is intimately related to two longstanding open problems about Boolean functions: the Sensitivity Conjecture, and the relationships between query complexity and polynomial degree.
10. Localization of discrete time quantum walks on the glued trees
Yusuke Ide, Norio Konno, Etsuo Segawa, Xin-Ping Xu
Entropy 16 (3), 1501-1514, 2014
http://arxiv.org/abs/1312.1149
In this paper, we consider the time averaged distribution of discrete time quantum walks on the glued trees. In order to analyse the walks on the glued trees, we consider a reduction to the walks on path graphs. Using a spectral analysis of the Jacobi matrices defined by the corresponding random walks on the path graphs, we have spectral decomposition of the time evolution operator of the quantum walks. We find significant contributions of the eigenvalues $\pm 1$ of the Jacobi matrices to the time averaged limit distribution of the quantum walks. As a consequence we obtain lower bounds of the time averaged distribution.
11. The Open Quantum Brownian Motion
Michel Bauer, Denis Bernard, Antoine Tilloy
J. Stat. Mech. P09001 (2014)
http://arxiv.org/abs/1312.1600
Using quantum parallelism on random walks as original seed, we introduce new quantum stochastic processes, the open quantum Brownian motions. They describe the behaviors of quantum walkers -- with internal degrees of freedom which serve as random gyroscopes -- interacting with series of probes. These processes may also be viewed as the scaling limit of open quantum random walks and we develop this approach along three different lines: quantum trajectory, quantum dynamical map, and quantum stochastic differential equation. We also present a study of the simplest case, with a two level system as internal gyroscope, illustrating the interplay between ballistic and diffusive behaviors at work in these processes.
12. Complex Obtuse Random Walks and their Continuous-Time Limits
S. Attal, J. Deschamps, C. Pellegrini
http://arxiv.org/abs/1312.3731
We study a particular class of complex-valued random variables and their associated random walks: the complex obtuse random variables. They are the generalization to the complex case of the real-valued obtuse random variables which were introduced in \cite{A-E} in order to understand the structure of normal martingales in $\RR^n$.The extension to the complex case is mainly motivated by considerations from Quantum Statistical Mechanics, in particular for the seek of a characterization of those quantum baths acting as classical noises. The extension of obtuse random variables to the complex case is far from obvious and hides very interesting algebraical structures. We show that complex obtuse random variables are characterized by a 3-tensor which admits certain symmetries which we show to be the exact 3-tensor analogue of the normal character for 2-tensors (i.e. matrices), that is, a necessary and sufficient condition for being diagonalizable in some orthonormal basis. We discuss the passage to the continuous-time limit for these random walks and show that they converge in distribution to normal martingales in $\CC^N$. We show that the 3-tensor associated to these normal martingales encodes their behavior, in particular the diagonalization directions of the 3-tensor indicate the directions of the space where the martingale behaves like a diffusion and those where it behaves like a Poisson process. We finally prove the convergence, in the continuous-time limit, of the corresponding multiplication operators on the canonical Fock space, with an explicit expression in terms of the associated 3-tensor again.