1. Data Structures in Classical and Quantum Computing
Maximilian Fillinger
http://arxiv.org/abs/1308.0833
This survey summarizes several results about quantum computing related to (mostly static) data structures. First, we describe classical data structures for the set membership and the predecessor search problems: Perfect Hash tables for set membership by Fredman, Koml\'{o}s and Szemer\'{e}di and a data structure by Beame and Fich for predecessor search. We also prove results about their space complexity (how many bits are required) and time complexity (how many bits have to be read to answer a query). After that, we turn our attention to classical data structures with quantum access. In the quantum access model, data is stored in classical bits, but they can be accessed in a quantum way: We may read several bits in superposition for unit cost. We give proofs for lower bounds in this setting that show that the classical data structures from the first section are, in some sense, asymptotically optimal - even in the quantum model. In fact, these proofs are simpler and give stronger results than previous proofs for the classical model of computation. The lower bound for set membership was proved by Radhakrishnan, Sen and Venkatesh and the result for the predecessor problem by Sen and Venkatesh. Finally, we examine fully quantum data structures. Instead of encoding the data in classical bits, we now encode it in qubits. We allow any unitary operation or measurement in order to answer queries. We describe one data structure by de Wolf for the set membership problem and also a general framework using fully quantum data structures in quantum walks by Jeffery, Kothari and Magniez.
2. The computational power of matchgates and the XY interaction on arbitrary graphs
Daniel J. Brod, Andrew M. Childs
Quantum Information and Computation 14, 901-916 (2014)
http://arxiv.org/abs/1308.1463
Matchgates are a restricted set of two-qubit gates known to be classically simulable when acting on nearest-neighbor qubits on a path, but universal for quantum computation when the qubits are arranged on certain other graphs. Here we characterize the power of matchgates acting on arbitrary graphs. Specifically, we show that they are universal on any connected graph other than a path or a cycle, and that they are classically simulable on a cycle. We also prove the same dichotomy for the XY interaction, a proper subset of matchgates related to some implementations of quantum computing.
3. Quantum walks of correlated photon pairs in two-dimensional waveguide arrays
Konstantinos Poulios, Robert Keil, Daniel Fry, Jasmin D. A. Meinecke, Jonathan C. F. Matthews, Alberto Politi, Mirko Lobino, Markus Gr?fe, Matthias Heinrich, Stefan Nolte, Alexander Szameit, Jeremy L. O’Brien
Phys. Rev. Lett. 112, 143604 (2014)
http://arxiv.org/abs/1308.2554
We demonstrate quantum walks of correlated photons in a 2D network of directly laser written waveguides coupled in a 'swiss cross' arrangement. The correlated detection events show high-visibility quantum interference and unique composite behaviour: strong correlation and independence of the quantum walkers, between and within the planes of the cross. Violations of a classically defined inequality, for photons injected in the same plane and in orthogonal planes, reveal non-classical behaviour in a non-planar structure.