1. Generalizing and Derandomizing Gurvits’s Approximation Algorithm for the Permanent
Scott Aaronson, Travis Hance
http://arxiv.org/abs/1212.0025
Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n*n matrix A. The algorithm runs in O(n^2/eps^2) time, and approximates Per(A) to within eps*||A||^n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. This makes it highly relevant to quantum optics, where the permanents of bounded-norm complex matrices play a central role. Indeed, the existence of Gurvits's algorithm is why, in their recent work on the hardness of quantum optics, Aaronson and Arkhipov (AA) had to talk about sampling problems rather than estimation problems. In this paper, we improve Gurvits's algorithm in two ways. First, using an idea from quantum optics, we generalize the algorithm so that it yields a better approximation when the matrix A has either repeated rows or repeated columns. Translating back to quantum optics, this lets us classically estimate the probability of any outcome of an AA-type experiment---even an outcome involving multiple photons "bunched" in the same mode---at least as well as that probability can be estimated by the experiment itself. (This does not, of course, let us solve the AA sampling problem.) It also yields a general upper bound on the probabilities of "bunched" outcomes, which resolves a conjecture of Gurvits and might be of independent physical interest. Second, we use eps-biased sets to derandomize Gurvits's algorithm, in the special case where the matrix A is nonnegative. More interestingly, we generalize the notion of eps-biased sets to the complex numbers, construct "complex eps-biased sets," then use those sets to derandomize even our generalization of Gurvits's algorithm to the multirow/multicolumn case (again for nonnegative A). Whether Gurvits's algorithm can be derandomized for general A remains an outstanding problem.
2. Weak limits for quantum walks on the half-line
Chaobin Liu, Nelson Petulante
Int. J. Quant. Inf., Vol. 11, No. 5 (2013) 1350054
http://arxiv.org/abs/1212.1109
For a discrete two-state quantum walk (QW) on the half-line with a general condition at the boundary, we formulate and prove a weak limit theorem describing the terminal behavior of its transition probabilities. In this context, localization is possible even for a walk predicated on the assumption of homogeneity. For the Hadamard walk on the half-line, the weak limit is shown to be independent of the initial coin state and to exhibit no localization.
3. Demonstration of active feedforward one-way quantum computing with photon-matter hyperentanglement
Xiao-Fan Xu, Xiao-Hui Bao, Jian-Wei Pan
Phys. Rev. A 86, 050304(R) (2012)
http://arxiv.org/abs/1212.1817
We report an optical one-way quantum computing experiment with stationary quantum memory involved. First we create a hybrid four-qubit cluster state with two qubits propagating as photons and the other two stationary and stored in a laser-cooled atomic-ensemble quantum memory, and characterize it with entanglement witness and quantum state tomography. Then, by making use of this cluster state and fast operations of electro-optic modulators, we realize memory-assisted feedforward operations and demonstrate deterministic single-qubit rotation as an example.
4. Photonic Boson Sampling in a Tunable Circuit
Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari, Justin Dove, Scott Aaronson, Timothy Ralph, Andrew G. White
Science 339, 6121 (2013)
http://arxiv.org/abs/1212.2234
Quantum computers are unnecessary for exponentially-efficient computation or simulation if the Extended Church-Turing thesis---a foundational tenet of computer science---is correct. The thesis would be directly contradicted by a physical device that efficiently performs a task believed to be intractable for classical computers. Such a task is BosonSampling: obtaining a distribution of n bosons scattered by some linear-optical unitary process. Here we test the central premise of BosonSampling, experimentally verifying that the amplitudes of 3-photon scattering processes are given by the permanents of submatrices generated from a unitary describing a 6-mode integrated optical circuit. We find the protocol to be robust, working even with the unavoidable effects of photon loss, non-ideal sources, and imperfect detection. Strong evidence against the Extended Church-Turing thesis will come from scaling to large numbers of photons, which is a much simpler task than building a universal quantum computer.
5. Numerical analysis of second law of thermodynamics and irreversibility in exemplary quantum systems
G.B. Lesovik, I.A. Sadovskyy
http://arxiv.org/abs/1212.2576
We test Boltzmann's H-theorem for several models of particle random walk. We study the influence of interaction between the particle and reservoir/detectors on entropy and find entropy increasing in time for some models and behaving non-monotonically for others. The key mechanism affecting the entropy growth is the quantum entanglement between the system and the reservoir. We discuss the details of the system-reservoir interaction, such as presence of the interference in the system and number of interactions with detector parts, and their impact on the monotonicity of entropy.
6. Understanding and controlling N-dimensional quantum walks via dispersion relations. Application to the 2D and 3D Grover walks: Diabolical points and more
Germ��n J. de Valc��rcel, Margarida Hinarejos, Eugenio Rold��n, Armando P��rez, Alejandro Romanelli
New J. Phys. 15 (2013) 073041
http://arxiv.org/abs/1212.3600
The discrete quantum walk in N dimensions is analyzed from the perspective of its dispersion relations. This allows understanding known properties, as well as designing new ones when spatially extended initial conditions are considered. This is done by deriving wave equations in the continuum, which are generically of the Schr\"odinger type, and allow devising interesting behaviors, such as ballistic propagation without deformation, or the generation of almost flat probability distributions, what is corroborated numerically. There are however special points where the energy surfaces display intersections and, near them, the dynamics is entirely different. Applications to the two- and three-dimensional Grover walks are presented.
7. Quantum walks with memory - goldfish, elephants and wise old men
Peter P. Rohde, Gavin K. Brennen, Alexei Gilchrist
Phys. Rev. A, 87, 052302 (2013)
http://arxiv.org/abs/1212.4540
Quantum walks have emerged as an interesting approach to quantum information processing, exhibiting many unique properties compared to the analogous classical random walk. Here we introduce a model for a discrete-time quantum walk with memory by endowing the walker with multiple recycled coins and using a physical memory function via a history dependent coin flip. By numerical simulation we observe several phenomena. First in one dimension, walkers with memory have persistent quantum ballistic speed up over classical walks just as found in previous studies of multi-coined walks with trivial memory function. However, measurement of the multi-coin state can dramatically shift the mean of the spatial distribution. Second, we consider spatial entanglement in a two-dimensional quantum walk with memory and find that memory destroys entanglement between the spatial dimensions, even when entangling coins are employed. Finally, we explore behaviour in the presence of spatial randomness and find that in contrast to single coined walks, multi-coined walks do not localise and in fact a memory function can speed up the walk relative to a fully decohered multi-coin walker with trivial memory. We explicitly show how to construct linear optics circuits implementing the walks, and discuss prospects for classical simulation.
8. Quantum walks as massless Dirac Fermions in curved Space-Time
Di Molfetta Giuseppe, Fabrice Debbasch, Marc E Brachet
http://arxiv.org/abs/1212.5821
A particular family of time- and space-dependent discrete-time quantum walks (QWs) is considered in one dimensional physical space. The continuous limit of these walks is defined through a new procedure and computed in full detail. In this limit, the walks coincide with the propagation of a massless Dirac fermion in an arbitrary gravitational field. A QW mimicking the radial propagation of a fermion outside and inside the event horizon of a Schwarzschild black hole is explicitly constructed and simulated numerically. Finally, the limiting procedure and the main result itself are carefully discussed.
9. Disorder induced localization and enhancement of entanglement in one- and two-dimensional quantum walks
C. M. Chandrashekar
http://arxiv.org/abs/1212.5984
The time evolution of one- and two-dimensional discrete-time quantum walk with increase in disorder is studied. We use spatial, temporal and spatio-temporal broken periodicity of the unitary evolution as disorder to mimic the effect of disordered/random medium in our study. Disorder induces a dramatic change in the interference pattern leading to localization of the quantum walks in one- and two-dimensions. Spatial disorder results in the decreases of the particle and position entanglement in one-dimension and counter intuitively, an enhancement in entanglement with temporal and spatio-temporal disorder is seen. The study signifies that the Anderson localization of quantum state without compromising on the degree of entanglement could be implement in a large variety of physical settings where quantum walks has been realized. The study presented here could make it feasible to explore, theoretically and experimentally the interplay between disorder and entanglement. This also brings up a variety of intriguing questions relating to the negative and positive implications on algorithmic and other applications.