1. Impossibility of Succinct Quantum Proofs for Collision-Freeness
Scott Aaronson
http://arxiv.org/abs/1101.0403
We show that any quantum algorithm to decide whether a function f:[n]->[n] is a permutation or far from a permutation must make Omega(n^{1/3}/w) queries to f, even if the algorithm is given a w-qubit quantum witness in support of f being a permutation. This implies that there exists an oracle A such that SZK^A is not contained in QMA^A, answering an eight-year-old open question of the author. Indeed, we show that relative to some oracle, SZK is not in the counting class A0PP defined by Vyalyi. The proof is a fairly simple extension of the quantum lower bound for the collision problem.
2. Disordered Quantum Walks in one lattice dimension
Andre Ahlbrecht, Volkher B. Scholz, Albert H. Werner
J. Math. Phys. 52, 102201 (2011)
http://arxiv.org/abs/1101.2298
We study a spin-1/2-particle moving on a one dimensional lattice subject to disorder induced by a random, space-dependent quantum coin. The discrete time evolution is given by a family of random unitary quantum walk operators, where the shift operation is assumed to be deterministic. Each coin is an independent identically distributed random variable with values in the group of two dimensional unitary matrices. We derive sufficient conditions on the probability distribution of the coins such that the system exhibits dynamical localization. Put differently, the tunneling probability between two lattice sites decays rapidly for almost all choices of random coins and after arbitrary many time steps with increasing distance. Our findings imply that this effect takes place if the coin is chosen at random from the Haar measure, or some measure continuous with respect to it, but also for a class of discrete probability measures which support consists of two coins, one of them being the Hadamard coin.
3. Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
Oliver Muelken, Alexander Blumen
Physics Reports 502, 37-87 (2011)
http://arxiv.org/abs/1101.2572
This paper reviews recent advances in continuous-time quantum walks (CTQW) and their application to transport in various systems. The introduction gives a brief survey of the historical background of CTQW. After a short outline of the theoretical ideas behind CTQW and of its relation to classical continuous-time random walks (CTRW) in Sec.~2, implications for the efficiency of the transport are presented in Sec.~3. The fourth section gives an overview of different types of networks on which CTQW have been studied so far. Extensions of CTQW to systems with long-range interactions and with static disorder are discussed in section V. Systems with traps, i.e., systems in which the walker's probability to remain inside the system is not conserved, are presented in section IV. Relations to similar approaches to the transport are studied in section VII. The paper closes with an outlook on possible future directions.
4. Decoherence and disorder in quantum walks: From ballistic spread to localization
A. Schreiber, K. N. Cassemiro, V. Poto?ek, A. G��bris, I. Jex, Ch. Silberhorn
Phys. Rev. Lett. 106, 180403 (2011)
http://arxiv.org/abs/1101.2638
We investigate the impact of decoherence and static disorder on the dynamics of quantum particles moving in a periodic lattice. Our experiment relies on the photonic implementation of a one-dimensional quantum walk. The pure quantum evolution is characterized by a ballistic spread of a photon's wave packet along 28 steps. By applying controlled time-dependent operations we simulate three different environmental influences on the system, resulting in a fast ballistic spread, a diffusive classical walk and the first Anderson localization in a discrete quantum walk architecture.
5. Advice Coins for Classical and Quantum Computation
Scott Aaronson, Andrew Drucker
http://arxiv.org/abs/1101.5355
We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states can be sensitive to arbitrarily small changes in a coin's bias. This contrasts with classical probabilistic finite automata, whose sensitivity to changes in a coin's bias is bounded by a classic 1970 result of Hellman and Cover. Despite this finding, we are able to bound the power of advice coins for space-bounded classical and quantum computation. We define the classes BPPSPACE/coin and BQPSPACE/coin, of languages decidable by classical and quantum polynomial-space machines with advice coins. Our main theorem is that both classes coincide with PSPACE/poly. Proving this result turns out to require substantial machinery. We use an algorithm due to Neff for finding roots of polynomials in NC; a result from algebraic geometry that lower-bounds the separation of a polynomial's roots; and a result on fixed-points of superoperators due to Aaronson and Watrous, originally proved in the context of quantum computing with closed timelike curves.
6. Bringing order through disorder: Localization of errors in topological quantum memories
James R. Wootton, Jiannis K. Pachos
Phys. Rev. Lett. 107, 030503 (2011)
http://arxiv.org/abs/1101.5900
Anderson localization emerges in quantum systems when randomised parameters cause the exponential suppression of motion. Here we consider this phenomenon in topological models and establish its usefulness for protecting topologically encoded quantum information. For concreteness we employ the toric code. It is known that in the absence of a magnetic field this can tolerate a finite initial density of anyonic errors, but in the presence of a field anyonic quantum walks are induced and the tolerable density becomes zero. However, if the disorder inherent in the code is taken into account, we demonstrate that the induced localization allows the topological quantum memory to regain a finite critical anyon density, and the memory to remain stable for arbitrarily long times. We anticipate that disorder inherent in any physical realisation of topological systems will help to strengthen the fault-tolerance of quantum memories.
7. Variety of c-axis collective excitations in layered multigap superconductors
Yukihiro Ota, Masahiko Machida, Tomio Koyama
Phys. Rev. Lett. 106, 157001 (2010)
http://arxiv.org/abs/1101.0886
We present a dynamical theory for the phase differences along a stacked direction of intrinsic Josephson junctions (IJJ's) in layered multigap superconductors, motivated by the discovery of highly-anisotropic iron-based superconductors with thick perovskite-type blocking layers. The dynamical equations describing AC and DC intrinsic Josephson effects peculiar to multigap IJJ's are derived, and collective Leggett mode excitations in addition to the Josephson plasma established in single-gap IJJ's are predicted. The dispersion relations of their collective modes are explicitly displayed, and the remarkable peculiarity of the Leggett mode is demonstrated.
8. Superiority of exact quantum automata for promise problems
Andris Ambainis, Abuzer Yakaryilmaz
Information Processing Letters, Volume 112, Issue 7, 31 March 2012, Pages 289-291
http://arxiv.org/abs/1101.3837
In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automata operating in realtime mode, whereas the size of the corresponding classical automata grow without bound.