1. Dynamical moments reveal a topological quantum transition in a photonic quantum walk
Filippo Cardano, Maria Maffei, Francesco Massa, Bruno Piccirillo, Corrado de Lisio, Giulio De Filippis, Vittorio Cataudella, Enrico Santamato, Lorenzo Marrucci
http://www.arxiv.org/abs/1507.01785
Many phenomena in solid-state physics can be understood in terms of their topological properties. Recently, controlled protocols of quantum walks are proving to be effective simulators of such phenomena. Here we report the realization of a photonic quantum walk showing both the trivial and the non-trivial topologies associated with chiral symmetry in one-dimensional periodic systems, as in the Su-Schrieffer-Heeger model of polyacetylene. We find that the probability distribution moments of the walker position after many steps behave differently in the two topological phases and can be used as direct indicators of the quantum transition: while varying a control parameter, these moments exhibit a slope discontinuity at the transition point, and remain constant in the non-trivial phase. Extending this approach to higher dimensions, different topological classes, and other typologies of quantum phases may offer new general instruments for investigating quantum transitions in such complex systems.
2. Doubly infinite separation of quantum information and communication
Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson
http://www.arxiv.org/abs/1507.03546
We prove the existence of (one-way) communication tasks with a vanishing vs. diverging type of asymptotic gap, which we call "doubly infinite", between quantum information and communication complexities. We do so by showing the following: As the size of the task $n$ increases, the quantum communication complexity of a certain regime of the exclusion game, recently introduced by Perry, Jain, and Oppenheim, scales at least logarithmically in $n$, while the information cost of a winning quantum strategy may tend to zero. The logarithmic lower bound on the quantum communication complexity is shown to hold even if we allow a small probability of error, although the $n$-qubit quantum message of the zero-error strategy can then be compressed polynomially. We leave open the problems of whether the quantum communication complexity of the specified regime scales polynomially in $n$, and whether the gap between quantum and classical communication complexities can be superexponential beyond this regime.
3. Quantum walks on two-dimensional grids with multiple marked locations
Nikolajs Nahimovs, Alexander Rivosh
http://www.arxiv.org/abs/1507.03788
The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration of marked locations. While the first dependence have been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. The original paper analyses one and two marked location cases only. We move beyond two marked locations and study the behaviour of the algorithm for an arbitrary configuration of marked locations. In this paper we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of $k$ marked locations for which the number of steps of the algorithm differs by $\Omega(\sqrt{k})$ factor. Second, we present two configurations of $k$ and $\sqrt{k}$ marked locations having the same number of steps and probability to find a marked location.
4. Generation and complete nondestructive analysis of hyperentanglement assisted by nitrogen-vacancy centers in resonators
Qian Liu, Mei Zhang
Phys. Rev. A 91, 062321 (2015)
http://www.arxiv.org/abs/1507.06108
We present two efficient schemes for the deterministic generation and the complete nondestructive analysis of hyperentangled Bell states in both the polarization and spatial-mode degrees of freedom (DOFs) of two-photon systems, assisted by the nitrogen-vacancy (NV) centers in diamonds coupled to microtoroidal resonators as a result of cavity quantum electrodynamics (QED). With the input-output process of photons, two-photon polarization-spatial hyperentangled Bell states can be generated in a deterministic way and their complete nondestructive analysis can be achieved. These schemes can be generalized to generate and analyze hyperentangled Greenberger-Horne-Zeilinger states of multi-photon systems as well. Compared with previous works, these two schemes relax the difficulty of their implementation in experiment as it is not difficult to obtain the $\pi$ phase shift in single-sided NV-cavity systems. Moreover, our schemes do not require that the transmission for the uncoupled cavity is balanceable with the reflectance for the coupled cavity. Our calculations show that these schemes can reach a high fidelity and efficiency with current technology, which may be a benefit to long-distance high-capacity quantum communication with two DOFs of photon systems.
5. Optimal state discrimination and unstructured search in nonlinear quantum mechanics
Andrew M. Childs, Joshua Young
http://www.arxiv.org/abs/1507.06334
Nonlinear variants of quantum mechanics can solve tasks that are impossible in standard quantum theory, such as perfectly distinguishing nonorthogonal states. Here we derive the optimal protocol for distinguishing two states of a qubit using the Gross-Pitaevskii equation, a model of nonlinear quantum mechanics that arises as an effective description of Bose-Einstein condensates. Using this protocol, we present an algorithm for unstructured search in the Gross-Pitaevskii model, obtaining an exponential improvement over a previous algorithm of Meyer and Wong. This result establishes a limitation on the effectiveness of the Gross-Pitaevskii approximation. More generally, we demonstrate similar behavior under a family of related nonlinearities, giving evidence that the ability to quickly discriminate nonorthogonal states and thereby solve unstructured search is a generic feature of nonlinear quantum mechanics.
6. Faster Quantum Walk Search on a Weighted Graph
Thomas G. Wong
Phys. Rev. A 92, 032320 (2015)
http://www.arxiv.org/abs/1507.07590
A randomly walking quantum particle evolving by Schr\"odinger's equation searches for a unique marked vertex on the "simplex of complete graphs" in time $\Theta(N^{3/4})$. In this paper, we give a weighted version of this graph that preserves vertex-transitivity, and we show that the time to search on it can be reduced to nearly $\Theta(\sqrt{N})$. To prove this, we introduce two novel extensions to degenerate perturbation theory: an adjustment that distinguishes the weights of the edges, and a method to determine how precisely the jumping rate of the quantum walk must be chosen.
7. Quantum walks on simplicial complexes
Kaname Matsue, Osamu Ogurisu, Etsuo Segawa
http://www.arxiv.org/abs/1507.01194
We construct a new type of quantum walks on simplicial complexes as a natural extension of the well-known Szegedy walk on graphs. One can numerically observe that our proposing quantum walks possess linear spreading and localization as in the case of the Grover walk on lattices. Moreover, our numerical simulation suggests that localization of our quantum walks reflect not only topological but also geometric structures. On the other hand, our proposing quantum walk contains an intrinsic problem concerning exhibition of nontrivial behavior, which is not seen in typical quantum walks such as Grover walks on graphs.
8. Automata and Quantum Computing
Andris Ambainis, Abuzer Yakaryilmaz
http://www.arxiv.org/abs/1507.01988
Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers.
9. Fast Scramblers, Democratic Walks and Information Fields
Javier M. Magan
http://www.arxiv.org/abs/1507.02477
We study a family of weighted random walks on complete graphs. These `democratic walks' turn out to be explicitly solvable, and we find the hierarchy window for which the characteristic time scale saturates the so-called fast scrambling conjecture. We show that these democratic walks describe well the properties of information spreading in systems in which every degree of freedom interacts with every other degree of freedom, such as Matrix or infinite range models. The argument is based on the analysis of suitably defined `Information fields' ($\mathcal{I}$), which are shown to evolve stochastically towards stationarity due to unitarity of the microscopic model. The model implies that in democratic systems, stabilization of one subsystem is equivalent to global scrambling. We use these results to study scrambling of infalling perturbations in black hole backgrounds, and argue that the near horizon running coupling constants are connected to entanglement evolution of single particle perturbations in democratic systems.
10. Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing
Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf
http://www.arxiv.org/abs/1507.03126
In the $k$-junta testing problem, a tester has to efficiently decide whether a given function $f:\{0,1\}^n\rightarrow \{0,1\}$ is a $k$-junta (i.e., depends on at most $k$ of its input bits) or is $\epsilon$-far from any $k$-junta. Our main result is a quantum algorithm for this problem with query complexity $\tilde O(\sqrt{k/\epsilon})$ and time complexity $\tilde O(n\sqrt{k/\epsilon})$. This quadratically improves over the query complexity of the previous best quantum junta tester, due to At\i c\i\ and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of $\Omega(k^{1/3})$ queries for junta-testing (for constant $\epsilon$).