Quantum interface between an electrical circuit and a single atom - D. Kielpinski; D. Kafri; M. J. Woolley; G. J. Milburn; J. M. Taylor (Physical Review Letters, 2012)
We show how to bridge the divide between atomic systems and electronic devices by engineering a coupling between the motion of a single ion and the quantized electric field of a resonant circuit. Our method can be used to couple the internal state of an ion to the quantized circuit with the same speed as the internal-state coupling between two ions. All the well-known quantum information protocols linking ion internal and motional states can be converted to protocols between circuit photons and ion internal states. Our results enable quantum interfaces between solid state qubits, atomic qubits, and light, and lay the groundwork for a direct quantum connection between electrical and atomic metrology standards.

Quantum nonlinear optics with single photons enabled by strongly interacting atoms - Peyronel, Thibault; Firstenberg, Ofer; Liang, Qi-Yu; Hofferberth, Sebastian; Alexey V. Gorshkov; Pohl, Thomas; Lukin, Mikhail D.; Vuletic, Vladan (Nature (London), 2012)

The quantum query complexity of read-many formulas - Andrew M. Childs; Shelby Kimmel; Robin Kothari (Lecture Notes in Computer Science, 2012)
The quantum query complexity of evaluating any read-once formula with n black-box input bits is Theta(sqrt(n)). However, the corresponding problem for read-many formulas (i.e., formulas in which the inputs have fanout) is not well understood. Although the optimal read-once formula evaluation algorithm can be applied to any formula, it can be suboptimal if the inputs have large fanout. We give an algorithm for evaluating any formula with n inputs, size S, and G gates using O(min{n, sqrtS, n^{1/2} G^{1/4}}) quantum queries. Furthermore, we show that this algorithm is optimal, since for any n,S,G there exists a formula with n inputs, size at most S, and at most G gates that requires Omega(min{n, sqrtS, n^{1/2} G^{1/4}}) queries. We also show that the algorithm remains nearly optimal for circuits of any particular depth k >= 3, and we give a linear-size circuit of depth 2 that requires Omega (n^{5/9}) queries. Applications of these results include a Omega (n^{19/18}) lower bound for Boolean matrix product verification, a nearly tight characterization of the quantum query complexity of evaluating constant-depth circuits with bounded fanout, new formula gate count lower bounds for several functions including PARITY, and a construction of an AC^0 circuit of linear size that can only be evaluated by a formula with Omega(n^{2-epsilon}) gates.

Quantum Simulation of Spin Models on an Arbitrary Lattice with Trapped Ions - Simcha Korenblit; Dvir Kafri; Wess C. Campbell; Rajibul Islam; Emily E. Edwards; Zhe-Xuan Gong; Guin-Dar Lin; Luming Duan; Jungsang Kim; Kihwan Kim; Christopher Monroe (New Journal of Physics, 2012)
A collection of trapped atomic ions represents one of the most attractive platforms for the quantum simulation of interacting spin networks and quantum magnetism. Spin-dependent optical dipole forces applied to an ion crystal create long-range effective spin-spin interactions and allow the simulation of spin Hamiltonians that possess nontrivial phases and dynamics. Here we show how appropriate design of laser fields can provide for arbitrary multidimensional spin-spin interaction graphs even for the case of a linear spatial array of ions. This scheme uses currently existing trap technology and is scalable to levels where classical methods of simulation are intractable.

Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators - Steven T. Flammia; David Gross; Yi-Kai Liu; Jens Eisert (New Journal of Physics, 2012)
Intuitively, if a density operator has small rank, then it should be easier to estimate from experimental data, since in this case only a few eigenvectors need to be learned. We prove two complementary results that confirm this intuition. First, we show that a low-rank density matrix can be estimated using fewer copies of the state, i.e., the sample complexity of tomography decreases with the rank. Second, we show that unknown low-rank states can be reconstructed from an incomplete set of measurements, using techniques from compressed sensing and matrix completion. These techniques use simple Pauli measurements, and their output can be certified without making any assumptions about the unknown state. We give a new theoretical analysis of compressed tomography, based on the restricted isometry property (RIP) for low-rank matrices. Using these tools, we obtain near-optimal error bounds, for the realistic situation where the data contains noise due to finite statistics, and the density matrix is full-rank with decaying eigenvalues. We also obtain upper-bounds on the sample complexity of compressed tomography, and almost-matching lower bounds on the sample complexity of any procedure using adaptive sequences of Pauli measurements. Using numerical simulations, we compare the performance of two compressed sensing estimators with standard maximum-likelihood estimation (MLE). We find that, given comparable experimental resources, the compressed sensing estimators consistently produce higher-fidelity state reconstructions than MLE. In addition, the use of an incomplete set of measurements leads to faster classical processing with no loss of accuracy. Finally, we show how to certify the accuracy of a low rank estimate using direct fidelity estimation and we describe a method for compressed quantum process tomography that works for processes with small Kraus rank.

Rank Reduction for the Local Consistency Problem - Jianxin Chen; Zhengfeng Ji; Alexander Klyachko; David W. Kribs; Bei Zeng (Journal of Mathematical Physics, 2012)
We address the problem of how simple a solution can be for a given quantum local consistency instance. More specifically, we investigate how small the rank of the global density operator can be if the local constraints are known to be compatible. We prove that any compatible local density operators can be satisfied by a low rank global density operator. Then we study both fermionic and bosonic versions of the N-representability problem as applications. After applying the channel-state duality, we prove that any compatible local channels can be obtained through a global quantum channel with small Kraus rank.

Reply to Comment on "Space-Time Crystals of Trapped Ions - Tongcang Li; Zhe-Xuan Gong; Zhang-qi Yin; H. T. Quan; Xiaobo Yin; Peng Zhang; L. -M. Duan; Xiang Zhang (2012)
This is a reply to the comment from Patrick Bruno (arXiv:1211.4792) on our paper (Phys. Rev. Lett. 109, 163001 (2012)).

Resonant control of polar molecules in an optical lattice - Thomas M. Hanna; Eite Tiesinga; William F. Mitchell; Paul S. Julienne (Physical Review A, 2012)
We study the resonant control of two nonreactive polar molecules in an optical lattice site, focussing on the example of RbCs. Collisional control can be achieved by tuning bound states of the intermolecular dipolar potential, by varying the applied electric field or trap frequency. We consider a wide range of electric fields and trapping geometries, showing that a three-dimensional optical lattice allows for significantly wider avoided crossings than free space or quasi-two dimensional geometries. Furthermore, we find that dipolar confinement induced resonances can be created with reasonable trapping frequencies and electric fields, and have widths that will enable useful control in forthcoming experiments.

Scalable Architecture for a Room Temperature Solid-State Quantum Information Processor - Norman Y. Yao; Liang Jiang; Alexey V. Gorshkov; Peter C. Maurer; Geza Giedke; J. Ignacio Cirac; Mikhail D. Lukin (Nature Communications, 2012)
The realization of a scalable quantum information processor has emerged over the past decade as one of the central challenges at the interface of fundamental science and engineering. Much progress has been made towards this goal. Indeed, quantum operations have been demonstrated on several trapped ion qubits, and other solid-state systems are approaching similar levels of control. Extending these techniques to achieve fault-tolerant operations in larger systems with more qubits remains an extremely challenging goal, in part, due to the substantial technical complexity of current implementations. Here, we propose and analyze an architecture for a scalable, solid-state quantum information processor capable of operating at or near room temperature. The architecture is applicable to realistic conditions, which include disorder and relevant decoherence mechanisms, and includes a hierarchy of control at successive length scales. Our approach is based upon recent experimental advances involving Nitrogen-Vacancy color centers in diamond and will provide fundamental insights into the physics of non-equilibrium many-body quantum systems. Additionally, the proposed architecture may greatly alleviate the stringent constraints, currently limiting the realization of scalable quantum processors.

Space-Time Crystals of Trapped Ions - Tongcang Li; Gong, Zhe-Xuan; Yin, Zhang-Qi; Quan, H. T.; Yin, Xiaobo; Zhang, Peng; Duan, L.-M.; Zhang, Xiang (Physical Review Letters, 2012)
Spontaneous symmetry breaking can lead to the formation of time crystals, as well as spatial crystals. Here we propose a space-time crystal of trapped ions and a method to realize it experimentally by confining ions in a ring-shaped trapping potential with a static magnetic field. The ions spontaneously form a spatial ring crystal due to Coulomb repulsion. This ion crystal can rotate persistently at the lowest quantum energy state in magnetic fields with fractional fluxes. The persistent rotation of trapped ions produces the temporal order, leading to the formation of a space-time crystal. We show that these space-time crystals are robust for direct experimental observation. We also study the effects of finite temperatures on the persistent rotation. The proposed space-time crystals of trapped ions provide a new dimension for exploring many-body physics and emerging properties of matter.

A Spectral Algorithm for Latent Dirichlet Allocation - Animashree Anandkumar; Dean P. Foster; Daniel Hsu; Sham M. Kakade; Yi-Kai Liu (Algorithmica, 2012)
The problem of topic modeling can be seen as a generalization of the clustering problem, in that it posits that observations are generated due to multiple latent factors (e.g., the words in each document are generated as a mixture of several active topics, as opposed to just one). This increased representational power comes at the cost of a more challenging unsupervised learning problem of estimating the topic probability vectors (the distributions over words for each topic), when only the words are observed and the corresponding topics are hidden. We provide a simple and efficient learning procedure that is guaranteed to recover the parameters for a wide class of mixture models, including the popular latent Dirichlet allocation (LDA) model. For LDA, the procedure correctly recovers both the topic probability vectors and the prior over the topics, using only trigram statistics (i.e., third order moments, which may be estimated with documents containing just three words). The method, termed Excess Correlation Analysis (ECA), is based on a spectral decomposition of low order moments (third and fourth order) via two singular value decompositions (SVDs). Moreover, the algorithm is scalable since the SVD operations are carried out on $k× k$ matrices, where $k$ is the number of latent factors (e.g. the number of topics), rather than in the $d$-dimensional observed space (typically $d \gg k$).

Spontaneous emission by rotating objects: A scattering approach - Mohammad F. Maghrebi; Robert L. Jaffe; Mehran Kardar (Physical Review Letters, 2012)
We study the quantum electrodynamics (QED) vacuum in the presence of a body rotating along its axis of symmetry and show that the object spontaneously emits energy if it is lossy. The radiated power is expressed as a general trace formula solely in terms of the scattering matrix, making an explicit connection to the conjecture of Zel'dovich [JETP Lett. 14, 180 (1971)] on rotating objects. We further show that a rotating body drags along nearby objects while making them spin parallel to its own rotation axis.

Steady-state many-body entanglement of hot reactive fermions - Michael Foss-Feig; Andrew J. Daley; James K. Thompson; Ana Maria Rey (Physical Review Letters, 2012)
Entanglement is typically created via systematic intervention in the time evolution of an initially unentangled state, which can be achieved by coherent control, carefully tailored non-demolition measurements, or dissipation in the presence of properly engineered reservoirs. In this paper we show that two-component Fermi gases at ~μ K temperatures naturally evolve, in the presence of reactive two-body collisions, into states with highly entangled (Dicke-type) spin wavefunctions. The entanglement is a steady-state property that emerges---without any intervention---from uncorrelated initial states, and could be used to improve the accuracy of spectroscopy in experiments with fermionic alkaline earth atoms or fermionic groundstate molecules.

Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure - Bohua Zhan; Shelby Kimmel; Avinatan Hassidim (ITCS '12 Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, 2012)
We give a quantum algorithm for evaluating a class of boolean formulas (such as NAND trees and 3-majority trees) on a restricted set of inputs. Due to the structure of the allowed inputs, our algorithm can evaluate a depth $n$ tree using $O(n^{2+\logω})$ queries, where $ω$ is independent of $n$ and depends only on the type of subformulas within the tree. We also prove a classical lower bound of $n^{Ω(\log\log n)}$ queries, thus showing a (small) super-polynomial speed-up.

Topological Flat Bands from Dipolar Spin Systems - Norman Y. Yao; Chris R. Laumann; Alexey V. Gorshkov; Steven D. Bennett; Eugene Demler; Peter Zoller; Mikhail D. Lukin (Physical Review Letters, 2012)
We propose and analyze a physical system that naturally admits two-dimensional topological nearly flat bands. Our approach utilizes an array of three-level dipoles (effective S = 1 spins) driven by inhomogeneous electromagnetic fields. The dipolar interactions produce arbitrary uniform background gauge fields for an effective collection of conserved hardcore bosons, namely, the dressed spin-flips. These gauge fields result in topological band structures, whose bandgap can be larger than the corresponding bandwidth. Exact diagonalization of the full interacting Hamiltonian at half-filling reveals the existence of superfluid, crystalline, and supersolid phases. An experimental realization using either ultra-cold polar molecules or spins in the solid state is considered.

Why the Tsirelson bound? - Jeffrey Bub (The Probable and the Improbable: The Meaning and Role of Probability in Physics, 2012)
Wheeler's question 'why the quantum' has two aspects: why is the world quantum and not classical, and why is it quantum rather than superquantum, i.e., why the Tsirelson bound for quantum correlations? I discuss a remarkable answer to this question proposed by Pawlowski et al (2009), who provide an information-theoretic derivation of the Tsirelson bound from a principle they call 'information causality.'

Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit - Stephen P. Jordan; Gorjan Alagic (In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC11), 2011)
The Turaev-Viro invariants are scalar topological invariants of three-dimensional manifolds. Here we show that the problem of estimating the Fibonacci version of the Turaev-Viro invariant of a mapping torus is a complete problem for the one clean qubit complexity class (DQC1). This complements a previous result showing that estimating the Turaev-Viro invariant for arbitrary manifolds presented as Heegaard splittings is a complete problem for the standard quantum computation model (BQP). We also discuss a beautiful analogy between these results and previously known results on the computational complexity of approximating the Jones polynomial.

Casimir force between sharp-shaped conductors - Mohammad F. Maghrebi; Sahand Jamal Rahi; Thorsten Emig; Noah Graham; Robert L. Jaffe; Mehran Kardar (Proceedings of the National Academy of Sciences, 2011)
Casimir forces between conductors at the sub-micron scale cannot be ignored in the design and operation of micro-electromechanical (MEM) devices. However, these forces depend non-trivially on geometry, and existing formulae and approximations cannot deal with realistic micro-machinery components with sharp edges and tips. Here, we employ a novel approach to electromagnetic scattering, appropriate to perfect conductors with sharp edges and tips, specifically to wedges and cones. The interaction of these objects with a metal plate (and among themselves) is then computed systematically by a multiple-scattering series. For the wedge, we obtain analytical expressions for the interaction with a plate, as functions of opening angle and tilt, which should provide a particularly useful tool for the design of MEMs. Our result for the Casimir interactions between conducting cones and plates applies directly to the force on the tip of a scanning tunneling probe; the unexpectedly large temperature dependence of the force in these configurations should attract immediate experimental interest.

Chern numbers hiding in time-of-flight images - Erhai Zhao; Noah Bray-Ali; Carl J. Williams; I. B. Spielman; Indubala I. Satija (Physical Review A, 2011)
We present a technique for detecting topological invariants -- Chern numbers -- from time-of-flight images of ultra-cold atoms. We show that the Chern numbers of integer quantum Hall states of lattice fermions leave their fingerprints in the atoms' momentum distribution. We analytically demonstrate that the number of local maxima in the momentum distribution is equal to the Chern number in two limiting cases, for large hopping anisotropy and in the continuum limit. In addition, our numerical simulations beyond these two limits show that these local maxima persist for a range of parameters. Thus, an everyday observable in cold atom experiments can serve as a useful tool to characterize and visualize quantum states with non-trivial topology.

Comment on "Foundation of Statistical Mechanics under Experimentally Realistic Conditions" - Zhe-Xuan Gong; L. -M. Duan (2011)
Reimann [Phys. Rev. Lett. 101, 190403 (2008)] claimed that generic isolated macroscopic quantum system will equilibrate under experimentally realistic conditions by proving a theorem. We here show that the proof is invalid for most many-body systems and is unable to demonstrate equilibration in realistic experiment.

Continuous-variable quantum compressed sensing - Matthias Ohliger; Vincent Nesme; David Gross; Yi-Kai Liu; Jens Eisert (2011)
We significantly extend recently developed methods to faithfully reconstruct unknown quantum states that are approximately low-rank, using only a few measurement settings. Our new method is general enough to allow for measurements from a continuous family, and is also applicable to continuous-variable states. As a technical result, this work generalizes quantum compressed sensing to the situation where the measured observables are taken from a so-called tight frame (rather than an orthonormal basis) --- hence covering most realistic measurement scenarios. As an application, we discuss the reconstruction of quantum states of light from homodyne detection and other types of measurements, and we present simulations that show the advantage of the proposed compressed sensing technique over present methods. Finally, we introduce a method to construct a certificate which guarantees the success of the reconstruction with no assumption on the state, and we show how slightly more measurements give rise to "universal" state reconstruction that is highly robust to noise.

Deciding Unitary Equivalence Between Matrix Polynomials and Sets of Bipartite Quantum States - Chitambar, Eric; Carl Miller; Shi, Yaoyun (Quantum Information and Computation, 2011)
In this brief report, we consider the equivalence between two sets of m + 1 bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree m matrix polynomials are unitarily equivalent; i.e. UAiV† = Bi for 0 ≤ i ≤ m where U and V are unitary and (Ai, Bi) are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices U and V.
Keywords: matrix polynomials; Schwartz-Zippel lemma; unitary transformations

Detecting paired and counterflow superfluidity via dipole oscillations - Anzi Hu; L. Mathey; Eite Tiesinga; Ippei Danshita; Carl J. Williams; Charles W. Clark (Physical Review A, 2011)
We suggest an experimentally feasible procedure to observe paired and counterflow superfluidity in ultra-cold atom systems. We study the time evolution of one-dimensional mixtures of bosonic atoms in an optical lattice following an abrupt displacement of an additional weak confining potential. We find that the dynamic responses of the paired superfluid phase for attractive inter-species interactions and the counterflow superfluid phase for repulsive interactions are qualitatively distinct and reflect the quasi long-range order that characterizes these states. These findings suggest a clear experimental procedure to detect these phases, and give an intuitive insight into their dynamics.

A diagrammatic expansion of the Casimir energy in multiple reflections: theory and applications - Mohammad F. Maghrebi (Physical Review D, 2011)
We develop a diagrammatic representation of the Casimir energy of a multibody configuration. The diagrams represent multiple reflections between the objects and can be organized by a few simple rules. The lowest-order diagrams (or reflections) give the main contribution to the Casimir interaction which proves the usefulness of this expansion. Among some applications of this, we find analytical formulae describing the interaction between "edges", i.e. semi-infinite plates, where we also give a first example of blocking in the context of the Casimir energy. We also find the interaction of edges with a needle and describe analytically a recent model of the repulsion due to the Casimir interaction.

Direct Fidelity Estimation from Few Pauli Measurements - Steven T. Flammia; Yi-Kai Liu (Physical Review Letters, 2011)
We describe a simple method for certifying that an experimental device prepares a desired quantum state rho. Our method is applicable to any pure state rho, and it provides an estimate of the fidelity between rho and the actual (arbitrary) state in the lab, up to a constant additive error. The method requires measuring only a constant number of Pauli expectation values, selected at random according to an importance-weighting rule. Our method is faster than full tomography by a factor of d, the dimension of the state space, and extends easily and naturally to quantum channels.

d-Wave Superfluidity in Optical Lattices of Ultracold Polar Molecules - Kevin A. Kuns; Ana Maria Rey; Alexey V. Gorshkov (Physical Review A, 2011)
Recent work on ultracold polar molecules, governed by a generalization of the t-J Hamiltonian, suggests that molecules may be better suited than atoms for studying d-wave superfluidity due to stronger interactions and larger tunability of the system. We compute the phase diagram for polar molecules in a checkerboard lattice consisting of weakly coupled square plaquettes. In the simplest experimentally realizable case where there is only tunneling and an XX-type spin-spin interaction, we identify the parameter regime where d-wave superfluidity occurs. We also find that the inclusion of a density-density interaction destroys the superfluid phase and that the inclusion of a spin-density or an Ising-type spin-spin interaction can enhance the superfluid phase. We also propose schemes for experimentally realizing the perturbative calculations exhibiting enhanced d-wave superfluidity.

Dynamics of Overhauser Field under nuclear spin diffusion in a quantum dot - Zhe-Xuan Gong; Zhang-qi Yin; L. -M. Duan (New Journal of Physics, 2011)
The coherence of electron spin can be significantly enhanced by locking the Overhauser field from nuclear spins using the nuclear spin preparation. We propose a theoretical model to calculate the long time dynamics of the Overhauser field under intrinsic nuclear spin diffusion in a quantum dot. We obtain a simplified diffusion equation that can be numerically solved and show quantitatively how the Knight shift and the electron-mediated nuclear spin flip-flop affect the nuclear spin diffusion. The results explain several recent experimental observations, where the decay time of Overhauser field is measured under different configurations, including variation of the external magnetic field, the electron spin configuration in a double dot, and the initial nuclear spin polarization rate.

Electromagnetic Casimir Energies of Semi-Infinite Planes - Mohammad F. Maghrebi; Noah Graham (EPL (Europhysics Letters), 2011)
Using recently developed techniques based on scattering theory, we find the electromagnetic Casimir energy for geometries involving semi-infinite planes, a case that is of particular interest in the design of microelectromechanical devices. We obtain both approximate analytic formulae and exact results requiring only modest numerical computation. Using these results, we analyze the effects of edges and orientation on the Casimir energy. We also demonstrate the accuracy, simplicity, and utility of our approximation scheme, which is based on a multiple reflection expansion.

Entanglement can completely defeat quantum noise - Jianxin Chen; Toby S. Cubitt; Aram W. Harrow; Graeme Smith (Physical Review Letters, 2011)
We describe two quantum channels that individually cannot send any information, even classical, without some chance of decoding error. But together a single use of each channel can send quantum information perfectly reliably. This proves that the zero-error classical capacity exhibits superactivation, the extreme form of the superadditivity phenomenon in which entangled inputs allow communication over zero capacity channels. But our result is stronger still, as it even allows zero-error quantum communication when the two channels are combined. Thus our result shows a new remarkable way in which entanglement across two systems can be used to resist noise, in this case perfectly. We also show a new form of superactivation by entanglement shared between sender and receiver.

Entropic force of polymers on a cone tip - Mohammad F. Maghrebi; Yacov Kantor; Mehran Kardar (EPL (Europhysics Letters), 2011)
We consider polymers attached to the tip of a cone, and the resulting force due to entropy loss on approaching a plate (or another cone). At separations shorter than the polymer radius of gyration R_g, the only relevant length scale is the tip-plate (or tip-tip) separation h, and the entropic force is given by F=A kT/h. The universal amplitude A can be related to (geometry dependent) correlation exponents of long polymers. We compute A for phantom polymers, and for self-avoiding (including star) polymers by epsilon-expansion, as well as by numerical simulations in 3 dimensions.

Fast and robust quantum computation with ionic Wigner crystals - J. D. Baltrusch; A. Negretti; J. M. Taylor; T. Calarco (Physical Review A, 2011)
We present a detailed analysis of the modulated-carrier quantum phase gate implemented with Wigner crystals of ions confined in Penning traps. We elaborate on a recent scheme, proposed by two of the authors, to engineer two-body interactions between ions in such crystals. We analyze for the first time the situation in which the cyclotron (w_c) and the crystal rotation (w_r) frequencies do not fulfill the condition w_c=2w_r. It is shown that even in the presence of the magnetic field in the rotating frame the many-body (classical) Hamiltonian describing small oscillations from the ion equilibrium positions can be recast in canonical form. As a consequence, we are able to demonstrate that fast and robust two-qubit gates are achievable within the current experimental limitations. Moreover, we describe a realization of the state-dependent sign-changing dipole forces needed to realize the investigated quantum computing scheme.

Implications of the Babinet Principle for Casimir Interactions - Mohammad F. Maghrebi; Ronen Abravanel; Robert L. Jaffe (Physical Review D, 2011)
We formulate the Babinet Principle (BP) as a relation between the scattering amplitudes for electromagnetic waves, and combine it with multiple scattering techniques to derive new properties of Casimir forces. We show that the Casimir force exerted by a planar conductor or dielectric on a self- complementary perforated planar mirror is approximately half that on a uniform mirror independent of the distance between them. The BP suggests that Casimir edge effects are anomalously small, supporting results obtained earlier in special cases. Finally, we illustrate how the BP can be used to estimate Casimir forces between perforated planar mirrors.

Interferometry with Synthetic Gauge Fields - Brandon M. Anderson; J. M. Taylor; Victor M. Galitski (Physical Review A, 2011)
We propose a compact atom interferometry scheme for measuring weak, time-dependent accelerations. Our proposal uses an ensemble of dilute trapped bosons with two internal states that couple to a synthetic gauge field with opposite charges. The trapped gauge field couples spin to momentum to allow time dependent accelerations to be continuously imparted on the internal states. We generalize this system to reduce noise and estimate the sensitivity of such a system to be S~10^-7 m / s^2 / Hz^1/2.

Laser cooling and optical detection of excitations in a LC electrical circuit - J. M. Taylor; A. S. Sørensen; C. M. Marcus; E. S. Polzik (Physical Review Letters, 2011)
We explore a method for laser cooling and optical detection of excitations in a LC electrical circuit. Our approach uses a nanomechanical oscillator as a transducer between optical and electronic excitations. An experimentally feasible system with the oscillator capacitively coupled to the LC and at the same time interacting with light via an optomechanical force is shown to provide strong electro-mechanical coupling. Conditions for improved sensitivity and quantum limited readout of electrical signals with such an "optical loud speaker" are outlined.

Levinson's theorem for graphs - Andrew M. Childs; DJ Strouse (Journal of Mathematical Physics, 2011)
We prove an analog of Levinson's theorem for scattering on a weighted (m+1)-vertex graph with a semi-infinite path attached to one of its vertices. In particular, we show that the number of bound states in such a scattering problem is equal to m minus half the winding number of the phase of the reflection coefficient (where each so-called half-bound state is counted as half a bound state).

Light storage in an optically thick atomic ensemble under conditions of electromagnetically induced transparency and four-wave mixing - Nathaniel B. Phillips; Alexey V. Gorshkov; Irina Novikova (Physical Review A, 2011)
We study the modification of a traditional electromagnetically induced transparency (EIT) stored light technique that includes both EIT and four-wave mixing (FWM) in an ensemble of hot Rb atoms. The standard treatment of light storage involves the coherent and reversible mapping of one photonic mode onto a collective spin coherence. It has been shown that unwanted, competing processes such as four-wave mixing are enhanced by EIT and can significantly modify the signal optical pulse propagation. We present theoretical and experimental evidence to indicate that while a Stokes field is indeed detected upon retrieval of the signal field, any information originally encoded in a seeded Stokes field is not independently preserved during the storage process. We present a simple model that describes the propagation dynamics of the fields and the impact of FWM on the spin wave.

No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems - Jianxin Chen; Xie Chen; Runyao Duan; Zhengfeng Ji; Bei Zeng (Physical Review A, 2011)
One-way quantum computing achieves the full power of quantum computation by performing single particle measurements on some many-body entangled state, known as the resource state. As single particle measurements are relatively easy to implement, the preparation of the resource state becomes a crucial task. An appealing approach is simply to cool a strongly correlated quantum many-body system to its ground state. In addition to requiring the ground state of the system to be universal for one-way quantum computing, we also want the Hamiltonian to have non-degenerate ground state protected by a fixed energy gap, to involve only two-body interactions, and to be frustration-free so that measurements in the course of the computation leave the remaining particles in the ground space. Recently, significant efforts have been made to the search of resource states that appear naturally as ground states in spin lattice systems. The approach is proved to be successful in spin-5/2 and spin-3/2 systems. Yet, it remains an open question whether there could be such a natural resource state in a spin-1/2, i.e., qubit system. Here, we give a negative answer to this question by proving that it is impossible for a genuinely entangled qubit states to be a non-degenerate ground state of any two-body frustration-free Hamiltonian. What is more, we prove that every spin-1/2 frustration-free Hamiltonian with two-body interaction always has a ground state that is a product of single- or two-qubit states, a stronger result that is interesting independent of the context of one-way quantum computing.

Phase diagram of the Bose Kondo-Hubbard model - Michael Foss-Feig; Ana Maria Rey (Physical Review A, 2011)
We study a bosonic version of the Kondo lattice model with an on-site repulsion in the conduction band, implemented with alkali atoms in two bands of an optical lattice. Using both weak and strong-coupling perturbation theory, we find that at unit filling of the conduction bosons the superfluid to Mott insulator transition should be accompanied by a magnetic transition from a ferromagnet (in the superfluid) to a paramagnet (in the Mott insulator). Furthermore, an analytic treatment of Gutzwiller mean-field theory reveals that quantum spin fluctuations induced by the Kondo exchange cause the otherwise continuous superfluid to Mott-insulator phase transition to be first order. We show that lattice separability imposes a serious constraint on proposals to exploit excited bands for quantum simulations, and discuss a way to overcome this constraint in the context of our model by using an experimentally realized non-separable lattice. A method to probe the first-order nature of the transition based on collapses and revivals of the matter-wave field is also discussed.

Photon-Photon Interactions via Rydberg Blockade - Alexey V. Gorshkov; Johannes Otterbach; Michael Fleischhauer; Thomas Pohl; Mikhail D. Lukin (Physical Review Letters, 2011)
We develop the theory of light propagation under the conditions of electromagnetically induced transparency (EIT) in systems involving strongly interacting Rydberg states. Taking into account the quantum nature and the spatial propagation of light, we analyze interactions involving few-photon pulses. We demonstrate that this system can be used for the generation of nonclassical states of light including trains of single photons with an avoided volume between them, for implementing photon-photon quantum gates, as well as for studying many-body phenomena with strongly correlated photons.

Quantum Magnetism with Polar Alkali Dimers - Alexey V. Gorshkov; Salvatore R. Manmana; Gang Chen; Eugene Demler; Mikhail D. Lukin; Ana Maria Rey (Physical Review A, 2011)
We show that dipolar interactions between ultracold polar alkali dimers in optical lattices can be used to realize a highly tunable generalization of the t-J model, which we refer to as the t-J-V-W model. The model features long-range spin-spin interactions J_z and J_perp of XXZ type, long-range density-density interaction V, and long-range density-spin interaction W, all of which can be controlled in both magnitude and sign independently of each other and of the tunneling t. The "spin" is encoded in the rotational degree of freedom of the molecules, while the interactions are controlled by applied static electric and continuous-wave microwave fields. Furthermore, we show that nuclear spins of the molecules can be used to implement an additional (orbital) degree of freedom that is coupled to the original rotational degree of freedom in a tunable way. The presented system is expected to exhibit exotic physics and to provide insights into strongly correlated phenomena in condensed matter systems. Realistic experimental imperfections are discussed.

Quantum magnetism with polar alkali-metal dimers - Alexey V. Gorshkov; Manmana, S R; Chen, G; Demler, E; Lukin, M D; Rey, A M (Phys. Rev. A, 2011)

Quantum query complexity of minor-closed graph properties - Andrew M. Childs; Robin Kothari (Proc. 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011), Leibniz International Proceedings in Informatics, 2011)
We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether an $n$-vertex graph is planar, is a forest, or does not contain a path of a given length. We show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Θ(n^{3/2}). To establish this, we prove an adversary lower bound using a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. On the other hand, we show that minor-closed properties (and more generally, sparse graph properties) that can be characterized by finitely many forbidden subgraphs can be solved strictly faster, in o(n^{3/2}) queries. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.

Resolved atomic interaction sidebands in an optical clock transition - Michael Bishof; Yige Lin; Matthew D. Swallows; Alexey V. Gorshkov; Jun Ye; Ana Maria Rey (Physical Review Letters, 2011)
We report the observation of resolved atomic interaction sidebands (ISB) in the ${}^{87}$Sr optical clock transition when atoms at microkelvin temperatures are confined in a two-dimensional (2D) optical lattice. The ISB are a manifestation of the strong interactions that occur between atoms confined in a quasi-one-dimensional geometry and disappear when the confinement is relaxed along one dimension. The emergence of ISB is linked to the recently observed suppression of collisional frequency shifts in [1]. At the current temperatures, the ISB can be resolved but are broad. At lower temperatures, ISB are predicted to be substantially narrower and usable as powerful spectroscopic tools in strongly interacting alkaline-earth gases.

Robust Quantum State Transfer in Random Unpolarized Spin Chains - Norman Y. Yao; Liang Jiang; Alexey V. Gorshkov; Zhe-Xuan Gong; Alex Zhai; L. -M. Duan; Mikhail D. Lukin (Physical Review Letters, 2011)
We propose and analyze a new approach for quantum state transfer between remote spin qubits. Specifically, we demonstrate that coherent quantum coupling between remote qubits can be achieved via certain classes of random, unpolarized (infinite temperature) spin chains. Our method is robust to coupling strength disorder and does not require manipulation or control over individual spins. In principle, it can be used to attain perfect state transfer over arbitrarily long range via purely Hamiltonian evolution and may be particularly applicable in a solid-state quantum information processor. As an example, we demonstrate that it can be used to attain strong coherent coupling between Nitrogen-Vacancy centers separated by micrometer distances at room temperature. Realistic imperfections and decoherence effects are analyzed.

Spatial separation in a thermal mixture of ultracold $^174$Yb and $^87$Rb atoms - Florian Baumer; Frank Münchow; Axel Görlitz; Stephen E. Maxwell; Paul S. Julienne; Eite Tiesinga (Physical Review A, 2011)
We report on the observation of unusually strong interactions in a thermal mixture of ultracold atoms which cause a significant modification of the spatial distribution. A mixture of $^{87}$Rb and $^{174}$Yb with a temperature of a few $μ$K is prepared in a hybrid trap consisting of a bichromatic optical potential superimposed on a magnetic trap. For suitable trap parameters and temperatures, a spatial separation of the two species is observed. We infer that the separation is driven by a large interaction strength between $^{174}$Yb and $^{87}$Rb accompanied by a large three-body recombination rate. Based on this assumption we have developed a diffusion model which reproduces our observations.

Spectral Concentration of Positive Functions on Compact Groups - Gorjan Alagic; Alexander Russell (Journal of Fourier Analysis and Applications, 2011)
The problem of understanding the Fourier-analytic structure of the cone of positive functions on a group has a long history. In this article, we develop the first quantitative spectral concentration results for such functions over arbitrary compact groups. Specifically, we describe a family of finite, positive quadrature rules for the Fourier coefficients of band-limited functions on compact groups. We apply these quadrature rules to establish a spectral concentration result for positive functions: given appropriately nested band limits A ⊂ B ⊂ G, we prove a lower bound on the fraction of L2-mass that any B-band-limited positive function has in A. Our bounds are explicit and depend only on elementary properties of A and B; they are the first such bounds that apply to arbitrary compact groups. They apply to finite groups as a special case, where the quadrature rule is given by the Fourier transform on the smallest quotient whose dual contains the Fourier support of the function.

Spectroscopy of dipolar fermions in 2D pancakes and 3D lattices - Kaden R. A. Hazzard; Alexey V. Gorshkov; Ana Maria Rey (Physical Review A, 2011)
Motivated by ongoing measurements at JILA, we calculate the recoil-free spectra of dipolar interacting fermions, for example ultracold heteronuclear molecules, in a one-dimensional lattice of two-dimensional pancakes, spectroscopically probing transitions between different internal (e.g., rotational) states. We additionally incorporate p-wave interactions and losses, which are important for reactive molecules such as KRb. Moreover, we consider other sources of spectral broadening: interaction-induced quasiparticle lifetimes and the different polarizabilities of the different rotational states used for the spectroscopy. Although our main focus is molecules, some of the calculations are also useful for optical lattice atomic clocks. For example, understanding the p-wave shifts between identical fermions and small dipolar interactions coming from the excited clock state are necessary to reach future precision goals. Finally, we consider the spectra in a deep 3D lattice and show how they give a great deal of information about static correlation functions, including all the moments of the density correlations between nearby sites. The range of correlations measurable depends on spectroscopic resolution and the dipole moment.

Spectroscopy of dipolar fermions in layered two-dimensional and three-dimensional lattices - Hazzard, K R A; Alexey V. Gorshkov; Rey, A M (Phys. Rev. A, 2011)

Superactivation of the Asymptotic Zero-Error Classical Capacity of a Quantum Channel - Toby S. Cubitt; Jianxin Chen; Aram W. Harrow (IEEE Transactions on Information Theory, 2011)
The zero-error classical capacity of a quantum channel is the asymptotic rate at which it can be used to send classical bits perfectly, so that they can be decoded with zero probability of error. We show that there exist pairs of quantum channels, neither of which individually have any zero-error capacity whatsoever (even if arbitrarily many uses of the channels are available), but such that access to even a single copy of both channels allows classical information to be sent perfectly reliably. In other words, we prove that the zero-error classical capacity can be superactivated. This result is the first example of superactivation of a classical capacity of a quantum channel.

Superradiance of cold atoms coupled to a superconducting circuit - Daniel Braun; Jonathan Hoffman; Eite Tiesinga (Physical Review A, 2011)
We investigate superradiance of an ensemble of atoms coupled to an integrated superconducting LC-circuit. Particular attention is paid to the effect of inhomogeneous coupling constants. Combining perturbation theory in the inhomogeneity and numerical simulations we show that inhomogeneous coupling constants can significantly affect the superradiant relaxation process. Incomplete relaxation terminating in "dark states" can occur, from which the only escape is through individual spontaneous emission on a much longer time scale. The relaxation dynamics can be significantly accelerated or retarded, depending on the distribution of the coupling constants. On the technical side, we also generalize the previously known propagator of superradiance for identical couplings in the completely symmetric sector to the full exponentially large Hilbert space.

Tunable Superfluidity and Quantum Magnetism with Ultracold Polar Molecules - Alexey V. Gorshkov; Salvatore R. Manmana; Gang Chen; Jun Ye; Eugene Demler; Mikhail D. Lukin; Ana Maria Rey (Physical Review Letters, 2011)
By selecting two dressed rotational states of ultracold polar molecules in an optical lattice, we obtain a highly tunable generalization of the t-J model, which we refer to as the t-J-V-W model. In addition to XXZ spin exchange, the model features density-density interactions and novel density-spin interactions; all interactions are dipolar. We show that full control of all interaction parameters in both magnitude and sign can be achieved independently of each other and of the tunneling. As a first step towards demonstrating the potential of the system, we apply the density matrix renormalization group method (DMRG) to obtain the 1D phase diagram of the simplest experimentally realizable case. Specifically, we show that the tunability and the long-range nature of the interactions in the t-J-V-W model enable enhanced superfluidity. Finally, we show that Bloch oscillations in a tilted lattice can be used to probe the phase diagram experimentally.

Unified approach to topological quantum computation with anyons: From qubit encoding to Toffoli gate - Haitan Xu; J. M. Taylor (Physical Review A, 2011)
Topological quantum computation may provide a robust approach for encoding and manipulating information utilizing the topological properties of anyonic quasi-particle excitations. We develop an efficient means to map between dense and sparse representations of quantum information (qubits) and a simple construction of multi-qubit gates, for all anyon models from Chern-Simons-Witten SU(2)$_k$ theory that support universal quantum computation by braiding ($k≥ 3,\ k ≠ 4$). In the process, we show how the constructions of topological quantum memory and gates for $k=2,4$ connect naturally to those for $k≥ 3,\ k ≠ 4$, unifying these concepts in a simple framework. Furthermore, we illustrate potential extensions of these ideas to other anyon models outside of Chern-Simons-Witten field theory.

Universal low-rank matrix recovery from Pauli measurements - Yi-Kai Liu (Advances in Neural Information Processing Systems (NIPS), 2011)
We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing: recovering a sparse vector from a few of its Fourier coefficients. We show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP). This implies that M can be recovered from a fixed ("universal") set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error. A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm. Our proof uses Dudley's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.

Adiabatic preparation of many-body states in optical lattices - Anders S. Sorensen; Ehud Altman; Michael Gullans; J. V. Porto; Mikhail D. Lukin; Eugene Demler (Physical Review A, 2010)
We analyze a technique for the preparation of low entropy many body states of atoms in optical lattices based on adiabatic passage. In particular, we show that this method allows preparation of strongly correlated states as stable highest energy states of Hamiltonians that have trivial ground states. As an example, we analyze the generation of antiferromagnetically ordered states by adiabatic change of a staggered field acting on the spins of bosonic atoms with ferromagnetic interactions.

Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation - Gorjan Alagic; Stephen P. Jordan; Robert Koenig; Ben W. Reichardt (Physical Review A, 2010)
The Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and (2+1)-D topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a novel relation between the task of distinguishing non-homeomorphic 3-manifolds and the power of a general quantum computer.

Characterization of universal two-qubit Hamiltonians - Andrew M. Childs; Debbie Leung; Laura Mancinska; Maris Ozols (2010)
Suppose we can apply a given 2-qubit Hamiltonian H to any (ordered) pair of qubits. We say H is n-universal if it can be used to approximate any unitary operation on n qubits. While it is well known that almost any 2-qubit Hamiltonian is 2-universal (Deutsch, Barenco, Ekert 1995; Lloyd 1995), an explicit characterization of the set of non-universal 2-qubit Hamiltonians has been elusive. Our main result is a complete characterization of 2-non-universal 2-qubit Hamiltonians. In particular, there are three ways that a 2-qubit Hamiltonian H can fail to be universal: (1) H shares an eigenvector with the gate that swaps two qubits, (2) H acts on the two qubits independently (in any of a certain family of bases), or (3) H has zero trace. A 2-non-universal 2-qubit Hamiltonian can still be n-universal for some n >= 3. We give some partial results on 3-universality. Finally, we also show how our characterization of 2-universal Hamiltonians implies the well-known result that almost any 2-qubit unitary is universal.

Contextuality in Quantum Mechanics: Testing the Klyachko Inequality - Jeffrey Bub; Allen Stairs (2010)
The Klyachko inequality is an inequality for the probabiities of the values of five observables of a spin-1 particle, which is satisfied by any noncontextual assignment of values to this set of observables, but is violated by the probabilities defined by a certain quantum state. We describe an experiment between two entangled spin-1 particles to test contextuality via a related inequality. We point out that a test of contextuality by measurements on a single particle to confirm the Klyachko inequality requires an assumption of non-disturbance by the measuring instrument, which is avoided in the two-particle experiment.

Creation and manipulation of Feshbach resonances with radio-frequency radiation - Thomas M. Hanna; Eite Tiesinga; Paul S. Julienne (New Journal of Physics, 2010)
We present a simple technique for studying collisions of ultracold atoms in the presence of a magnetic field and radio-frequency radiation (rf). Resonant control of scattering properties can be achieved by using rf to couple a colliding pair of atoms to a bound state. We show, using the example of 6Li, that in some ranges of rf frequency and magnetic field this can be done without giving rise to losses. We also show that halo molecules of large spatial extent require much less rf power than deeply bound states. Another way to exert resonant control is with a set of rf-coupled bound states, linked to the colliding pair through the molecular interactions that give rise to magnetically tunable Feshbach resonances. This was recently demonstrated for 87Rb [Kaufman et al., Phys. Rev. A 80:050701(R), 2009]. We examine the underlying atomic and molecular physics which made this possible. Lastly, we consider the control that may be exerted over atomic collisions by placing atoms in superpositions of Zeeman states, and suggest that it could be useful where small changes in scattering length are required. We suggest other species for which rf and magnetic field control could together provide a useful tuning mechanism.

On the degeneracy of SU(3)k topological phases - Stephen P. Jordan; Toufik Mansour; Simone Severini (2010)
The ground state degeneracy of an $SU(N)_k$ topological phase with $n$ quasiparticle excitations is relevant quantity for quantum computation, condensed matter physics, and knot theory. It is an open question to find a closed formula for this degeneracy for any $N > 2$. Here we present the problem in an explicit combinatorial way and analyze the case N=3. While not finding a complete closed-form solution, we obtain generating functions and solve some special cases.

Dynamic Nuclear Polarization in Double Quantum Dots - Michael Gullans; J. J. Krich; J. M. Taylor; H. Bluhm; B. I. Halperin; C. M. Marcus; M. Stopa; A. Yacoby; M. D. Lukin (Physical Review Letters, 2010)
We theoretically investigate the controlled dynamic polarization of lattice nuclear spins in GaAs double quantum dots containing two electrons. Three regimes of long-term dynamics are identified, including the build up of a large difference in the Overhauser fields across the dots, the saturation of the nuclear polarization process associated with formation of so-called "dark states," and the elimination of the difference field. We show that in the case of unequal dots, build up of difference fields generally accompanies the nuclear polarization process, whereas for nearly identical dots, build up of difference fields competes with polarization saturation in dark states. The elimination of the difference field does not, in general, correspond to a stable steady state of the polarization process.

Efficient Direct Tomography for Matrix Product States - Olivier Landon-Cardinal; Yi-Kai Liu; David Poulin (2010)
In this note, we describe a method for reconstructing matrix product states from a small number of efficiently-implementable measurements. Our method is exponentially faster than standard tomography, and it can also be used to certify that the unknown state is an MPS. The basic idea is to use local unitary operations to measure in the Schmidt basis, giving direct access to the MPS representation. This compares favorably with recently and independently proposed methods that recover the MPS tensors by performing a variational minimization, which is computationally intractable in certain cases. Our method also has the advantage of recovering any MPS, while other approaches were limited to special classes of states that exclude important examples such as GHZ and W states.

Efficient quantum state tomography - Marcus Cramer; Martin B. Plenio; Steven T. Flammia; David Gross; Stephen D. Bartlett; Rolando Somma; Olivier Landon-Cardinal; Yi-Kai Liu; David Poulin (Nature Communications, 2010)
Quantum state tomography, the ability to deduce the state of a quantum system from measured data, is the gold standard for verification and benchmarking of quantum devices. It has been realized in systems with few components, but for larger systems it becomes infeasible because the number of quantum measurements and the amount of computation required to process them grows exponentially in the system size. Here we show that we can do exponentially better than direct state tomography for a wide range of quantum states, in particular those that are well approximated by a matrix product state ansatz. We present two schemes for tomography in 1-D quantum systems and touch on generalizations. One scheme requires unitary operations on a constant number of subsystems, while the other requires only local measurements together with more elaborate post-processing. Both schemes rely only on a linear number of experimental operations and classical postprocessing that is polynomial in the system size. A further strength of the methods is that the accuracy of the reconstructed states can be rigorously certified without any a priori assumptions.

An Euler–Poincaré bound for equicharacteristic étale sheaves - Carl Miller (Algebra & Number Theory, 2010)
<p class="noindent" style="font-stretch: normal; font-size: 9pt; font-family: Verdana, Arial, Helvetica, "sans serif"; line-height: 1.3em; margin: 0.2em 0.2em 0.5em 0em; border-width: initial; border-style: none; text-align: justify; vertical-align: middle;">The Grothendieck–Ogg–Shafarevich formula expresses the Euler characteristic of an étale sheaf on a characteristic-<span class="MathJax" data-mathml="p" id="MathJax-Element-1-Frame" role="presentation" style="display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative;" tabindex="0">p<span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px 1px 1px 1px); -webkit-user-select: none; position: static; display: inline; transition: none; vertical-align: 0px; line-height: normal; height: 1px !important; width: 1px !important; overflow: hidden !important;">p curve in terms of local data. The purpose of this paper is to prove an equicharacteristic version of this formula (a bound, rather than an equality). This follows work of R. Pink. <p class="indent" style="font-stretch: normal; font-size: 9pt; font-family: Verdana, Arial, Helvetica, "sans serif"; line-height: 1.3em; margin-right: 0.2em; margin-bottom: 0.5em; margin-left: 0em; border-width: initial; border-style: none; text-align: justify; vertical-align: middle;">The basis for the proof of this result is the characteristic-<span class="MathJax" data-mathml="p" id="MathJax-Element-2-Frame" role="presentation" style="display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative;" tabindex="0">p<span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px 1px 1px 1px); -webkit-user-select: none; position: static; display: inline; transition: none; vertical-align: 0px; line-height: normal; height: 1px !important; width: 1px !important; overflow: hidden !important;">p Riemann–Hilbert correspondence, which is a functorial relationship between two different types of sheaves on a characteristic-<span class="MathJax" data-mathml="p" id="MathJax-Element-3-Frame" role="presentation" style="display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative;" tabindex="0">p<span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px 1px 1px 1px); -webkit-user-select: none; position: static; display: inline; transition: none; vertical-align: 0px; line-height: normal; height: 1px !important; width: 1px !important; overflow: hidden !important;">p scheme. In the paper we prove a one-dimensional version of this correspondence, considering both local and global settings.

Far-field optical imaging and manipulation of individual spins with nanoscale resolution - Maurer, P C; Maze, J R; Stanwix, P L; Jiang, L; Alexey V. Gorshkov; Zibrov, A A; Harke, B; Hodges, J S; Zibrov, A S; Yacoby, A; Twitchen, D; Hell, S W; et al. (Nature Phys., 2010)

Fast Entanglement Distribution with Atomic Ensembles and Fluorescent Detection - Jonatan B. Brask; Liang Jiang; Alexey V. Gorshkov; Vladan Vuletic; Anders S. Sorensen; Mikhail D. Lukin (Physical Review A, 2010)
Quantum repeaters based on atomic ensemble quantum memories are promising candidates for achieving scalable distribution of entanglement over long distances. Recently, important experimental progress has been made towards their implementation. However, the entanglement rates and scalability of current approaches are limited by relatively low retrieval and single-photon detector efficiencies. We propose a scheme, which makes use of fluorescent detection of stored excitations to significantly increase the efficiency of connection and hence the rate. Practical performance and possible experimental realizations of the new protocol are discussed.

Feshbach Resonances in Ultracold Gases - Cheng Chin; Rudolf Grimm; Paul Julienne; Eite Tiesinga (Reviews of Modern Physics, 2010)
Feshbach resonances are the essential tool to control the interaction between atoms in ultracold quantum gases. They have found numerous experimental applications, opening up the way to important breakthroughs. This Review broadly covers the phenomenon of Feshbach resonances in ultracold gases and their main applications. This includes the theoretical background and models for the description of Feshbach resonances, the experimental methods to find and characterize the resonances, a discussion of the main properties of resonances in various atomic species and mixed atomic species systems, and an overview of key experiments with atomic Bose-Einstein condensates, degenerate Fermi gases, and ultracold molecules.

Heavy fermions in an optical lattice - Michael Foss-Feig; Michael Hermele; Victor Gurarie; Ana Maria Rey (Physical Review A, 2010)
We employ a mean-field theory to study ground-state properties and transport of a two-dimensional gas of ultracold alklaline-earth metal atoms governed by the Kondo Lattice Hamiltonian plus a parabolic confining potential. In a homogenous system this mean-field theory is believed to give a qualitatively correct description of heavy fermion metals and Kondo insulators: it reproduces the Kondo-like scaling of the quasiparticle mass in the former, and the same scaling of the excitation gap in the latter. In order to understand ground-state properties in a trap we extend this mean-field theory via local-density approximation. We find that the Kondo insulator gap manifests as a shell structure in the trapped density profile. In addition, a strong signature of the large Fermi surface expected for heavy fermion systems survives the confinement, and could be probed in time-of-flight experiments. From a full self-consistent diagonalization of the mean-field theory we are able to study dynamics in the trap. We find that the mass enhancement of quasiparticle excitations in the heavy Fermi liquid phase manifests as slowing of the dipole oscillations that result from a sudden displacement of the trap center.

Matrix pencils and entanglement classification - Chitambar, Eric; Carl Miller; Shi, Yaoyun (Journal of Mathematical Physics, 2010)
Quantum entanglement plays a central role in quantum information processing. A main objective of the theory is to classify different types of entanglement according to their interconvertibility through manipulations that do not require additional entanglement to perform. While bipartite entanglement is well understood in this framework, the classification of entanglements among three or more subsystems is inherently much more difficult. In this paper, we study pure state entanglement in systems of dimension <span class="mn" id="MathJax-Span-104" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">2<span class="mo" id="MathJax-Span-105" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">⊗<span class="mi" id="MathJax-Span-106" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">m<span class="mo" id="MathJax-Span-107" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">⊗<span class="mi" id="MathJax-Span-108" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">n. Two states are considered equivalent if they can be reversibly converted from one to the other with a nonzero probability using only local quantum resources and classical communication (SLOCC). We introduce a connection between entanglement manipulations in these systems and the well-studied theory of matrix pencils. All previous attempts to study general SLOCC equivalence in such systems have relied on somewhat contrived techniques which fail to reveal the elegant structure of the problem that can be seen from the matrix pencil approach. Based on this method, we report the first polynomial-time algorithm for deciding when two<span class="mn" id="MathJax-Span-112" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">2<span class="mo" id="MathJax-Span-113" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">⊗<span class="mi" id="MathJax-Span-114" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">m<span class="mo" id="MathJax-Span-115" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">⊗<span class="mi" id="MathJax-Span-116" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">n states are SLOCC equivalent. We then proceed to present a canonical form for all <span class="mn" id="MathJax-Span-120" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">2<span class="mo" id="MathJax-Span-121" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">⊗<span class="mi" id="MathJax-Span-122" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">m<span class="mo" id="MathJax-Span-123" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">⊗<span class="mi" id="MathJax-Span-124" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">n states based on the matrix pencil construction such that two states are equivalent if and only if they have the same canonical form. Besides recovering the previously known 26 distinct SLOCC equivalence classes in <span class="mn" id="MathJax-Span-128" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">2<span class="mo" id="MathJax-Span-129" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">⊗<span class="mn" id="MathJax-Span-130" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">3<span class="mo" id="MathJax-Span-131" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">⊗<span class="mi" id="MathJax-Span-132" style="font-size: 16.8px; white-space: nowrap; color: rgb(51, 51, 51); box-sizing: border-box; transition: none; display: inline; position: static; padding-left: 0.241em; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">n systems, we also determine the hierarchy between these classes.

Noise correlations of one-dimensional Bose mixtures in optical lattices - Anzi Hu; L. Mathey; Carl J. Williams; Charles W. Clark (Physical Review A, 2010)
We study the noise correlations of one-dimensional binary Bose mixtures, as a probe of their quantum phases. In previous work, we found a rich structure of many-body phases in such mixtures, such as paired and counterflow superfluidity. Here we investigate the signature of these phases in the noise correlations of the atomic cloud after time-of-flight expansion, using both Luttinger liquid theory and the time-evolving block decimation (TEBD) method. We find that paired and counterflow superfluidity exhibit distinctive features in the noise spectra. We treat both extended and inhomogeneous systems, and our numerical work shows that the essential physics of the extended systems is present in the trapped-atom systems of current experimental interest. For paired and counterflow superfluid phases, we suggest methods for extracting Luttinger parameters from noise correlation spectroscopy.

Optimal Perfect Distinguishability between Unitaries and Quantum Operations - Cheng Lu; Jianxin Chen; Runyao Duan (2010)
We study optimal perfect distinguishability between a unitary and a general quantum operation. In 2-dimensional case we provide a simple sufficient and necessary condition for sequential perfect distinguishability and an analytical formula of optimal query time. We extend the sequential condition to general d-dimensional case. Meanwhile, we provide an upper bound and a lower bound for optimal sequential query time. In the process a new iterative method is given, the most notable innovation of which is its independence to auxiliary systems or entanglement. Following the idea, we further obtain an upper bound and a lower bound of (entanglement-assisted) q-maximal fidelities between a unitary and a quantum operation. Thus by the recursion in [1] an upper bound and a lower bound for optimal general perfect discrimination are achieved. Finally our lower bound result can be extended to the case of arbitrary two quantum operations.

Permutational Quantum Computing - Stephen P. Jordan (Quantum Information & Computation, 2010)
In topological quantum computation the geometric details of a particle trajectory are irrelevant; only the topology matters. Taking this one step further, we consider a model of computation that disregards even the topology of the particle trajectory, and computes by permuting particles. Whereas topological quantum computation requires anyons, permutational quantum computation can be performed with ordinary spin-1/2 particles, using a variant of the spin-network scheme of Marzuoli and Rasetti. We do not know whether permutational computation is universal. It may represent a new complexity class within BQP. Nevertheless, permutational quantum computers can in polynomial time approximate matrix elements of certain irreducible representations of the symmetric group and simulate certain processes in the Ponzano-Regge spin foam model of quantum gravity. No polynomial time classical algorithms for these problems are known.

Photonic Phase Gate via an Exchange of Fermionic Spin Waves in a Spin Chain - Alexey V. Gorshkov; Johannes Otterbach; Eugene Demler; Michael Fleischhauer; Mikhail D. Lukin (Physical Review Letters, 2010)
We propose a new protocol for implementing the two-qubit photonic phase gate. In our approach, the pi phase is acquired by mapping two single photons into atomic excitations with fermionic character and exchanging their positions. The fermionic excitations are realized as spin waves in a spin chain, while photon storage techniques provide the interface between the photons and the spin waves. Possible imperfections and experimental systems suitable for implementing the gate are discussed.

Principle of Maximum Entropy and Ground Spaces of Local Hamiltonians - Jianxin Chen; Zhengfeng Ji; Mary Beth Ruskai; Bei Zeng; Duanlu Zhou (2010)
The structure of the ground spaces of quantum systems consisting of local interactions is of fundamental importance to different areas of physics. In this Letter, we present a necessary and sufficient condition for a subspace to be the ground space of a k-local Hamiltonian. Our analysis are motivated by the concept of irreducible correlations studied by [Linden et al., PRL 89, 277906] and [Zhou, PRL 101, 180505], which is in turn based on the principle of maximum entropy. It establishes a better understanding of the ground spaces of local Hamiltonians and builds an intimate link of ground spaces to the correlations of quantum states.

Probing the Kondo Lattice Model with Alkaline Earth Atoms - Michael Foss-Feig; Michael Hermele; Ana Maria Rey (Physical Review A, 2010)
We study transport properties of alkaline-earth atoms governed by the Kondo Lattice Hamiltonian plus a harmonic confining potential, and suggest simple dynamical probes of several different regimes of the phase diagram that can be implemented with current experimental techniques. In particular, we show how Kondo physics at strong coupling, low density, and in the heavy fermion phase is manifest in the dipole oscillations of the conduction band upon displacement of the trap center.

Pseudorandom generators and the BQP vs. PH problem - Bill Fefferman; Christopher Umans (2010)
It is a longstanding open problem to devise an oracle relative to which BQP does not lie in the Polynomial-Time Hierarchy (PH). We advance a natural conjecture about the capacity of the Nisan-Wigderson pseudorandom generator [NW94] to fool AC_0, with MAJORITY as its hard function. Our conjecture is essentially that the loss due to the hybrid argument (which is a component of the standard proof from [NW94]) can be avoided in this setting. This is a question that has been asked previously in the pseudorandomness literature [BSW03]. We then make three main contributions: (1) We show that our conjecture implies the existence of an oracle relative to which BQP is not in the PH. This entails giving an explicit construction of unitary matrices, realizable by small quantum circuits, whose row-supports are "nearly-disjoint." (2) We give a simple framework (generalizing the setting of Aaronson [A10]) in which any efficiently quantumly computable unitary gives rise to a distribution that can be distinguished from the uniform distribution by an efficient quantum algorithm. When applied to the unitaries we construct, this framework yields a problem that can be solved quantumly, and which forms the basis for the desired oracle. (3) We prove that Aaronson's "GLN conjecture" [A10] implies our conjecture; our conjecture is thus formally easier to prove. The GLN conjecture was recently proved false for depth greater than 2 [A10a], but it remains open for depth 2. If true, the depth-2 version of either conjecture would imply an oracle relative to which BQP is not in AM, which is itself an outstanding open problem. Taken together, our results have the following interesting interpretation: they give an instantiation of the Nisan-Wigderson generator that can be broken by quantum computers, but not by the relevant modes of classical computation, if our conjecture is true.

QMA-complete problems for stoquastic Hamiltonians and Markov matrices - Stephen P. Jordan; David Gosset; Peter J. Love (Physical Review A, 2010)
We show that finding the lowest eigenvalue of a 3-local symmetric stochastic matrix is QMA-complete. We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation using certain excited states of a stoquastic Hamiltonian is universal. We also show that adiabatic evolution in the ground state of a stochastic frustration free Hamiltonian is universal. Our results give a new QMA-complete problem arising in the classical setting of Markov chains, and new adiabatically universal Hamiltonians that arise in many physical systems.

Quantum algorithms for algebraic problems - Andrew M. Childs; Wim van Dam (Reviews of Modern Physics, 2010)
Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation, and in particular, on problems with an algebraic flavor.

Quantum Algorithms for Simon’s Problem over Nonabelian Groups - Gorjan Alagic; Cristopher Moore; Alexander Russell (ACM Trans. Algorithms, 2010)
Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding “hidden shifts” of Z2n provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. In this article, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution m = (m1,…,mn) ∈ Gn from an oracle f with the property that f(x ⋅ y) = f(x) ⇔ y ∈ {1, m}. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form Gn, where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. Although groups of the form Gn have a simple product structure, they share important representation--theoretic properties with the symmetric groups Sn, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called “standard method” requires highly entangled measurements on the tensor product of many coset states. In this article, we provide quantum algorithms with time complexity 2O(√n) that recover hidden involutions m = (m1,…mn) ∈ Gn where, as in Simon's problem, each mi is either the identity or the conjugate of a known element m which satisfies κ(m) = −κ(1) for some κ ∈ Ĝ. Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the “missing harmonic” approach of Moore and Russell. These are the first nontrivial HSP algorithms for group families that require highly entangled multiregister Fourier sampling.

Quantum computation and pseudo-telepathic games - Jeffrey Bub (Philosophy of Science, 2010)
A quantum algorithm succeeds not because the superposition principle allows 'the computation of all values of a function at once' via 'quantum parallelism,' but rather because the structure of a quantum state space allows new sorts of correlations associated with entanglement, with new possibilities for information-processing transformations between correlations, that are not possible in a classical state space. I illustrate this with an elementary example of a problem for which a quantum algorithm is more efficient than any classical algorithm. I also introduce the notion of 'pseudo-telepathic' games and show how the difference between classical and quantum correlations plays a similar role here for games that can be won by quantum players exploiting entanglement, but not by classical players whose only allowed common resource consists of shared strings of random numbers (common causes of the players' correlated responses in a game).

Quantum Computing - Thaddeus D. Ladd; Fedor Jelezko; Raymond Laflamme; Yasunobu Nakamura; Christopher Monroe; Jeremy L. O'Brien (Nature, 2010)
Quantum mechanics---the theory describing the fundamental workings of nature---is famously counterintuitive: it predicts that a particle can be in two places at the same time, and that two remote particles can be inextricably and instantaneously linked. These predictions have been the topic of intense metaphysical debate ever since the theory's inception early last century. However, supreme predictive power combined with direct experimental observation of some of these unusual phenomena leave little doubt as to its fundamental correctness. In fact, without quantum mechanics we could not explain the workings of a laser, nor indeed how a fridge magnet operates. Over the last several decades quantum information science has emerged to seek answers to the question: can we gain some advantage by storing, transmitting and processing information encoded in systems that exhibit these unique quantum properties? Today it is understood that the answer is yes. Many research groups around the world are working towards one of the most ambitious goals humankind has ever embarked upon: a quantum computer that promises to exponentially improve computational power for particular tasks. A number of physical systems, spanning much of modern physics, are being developed for this task---ranging from single particles of light to superconducting circuits---and it is not yet clear which, if any, will ultimately prove successful. Here we describe the latest developments for each of the leading approaches and explain what the major challenges are for the future.

Quantum probabilities: an information-theoretic interpretation - Jeffrey Bub (2010)
This Chapter develops a realist information-theoretic interpretation of the nonclassical features of quantum probabilities. On this view, what is fundamental in the transition from classical to quantum physics is the recognition that information in the physical sense has new structural features, just as the transition from classical to relativistic physics rests on the recognition that space-time is structurally different than we thought. Hilbert space, the event space of quantum systems, is interpreted as a kinematic (i.e., pre-dynamic) framework for an indeterministic physics, in the sense that the geometric structure of Hilbert space imposes objective probabilistic or information-theoretic constraints on correlations between events, just as the geometric structure of Minkowski space in special relativity imposes spatio-temporal kinematic constraints on events. The interpretation of quantum probabilities is more subjectivist in spirit than other discussions in this book (e.g., the chapter by Timpson), insofar as the quantum state is interpreted as a credence function---a bookkeeping device for keeping track of probabilities---but it is also objective (or intersubjective), insofar as the credences specified by the quantum state are understood as uniquely determined, via Gleason's theorem, by objective correlational constraints on events in the nonclassical quantum event space defined by the subspace structure of Hilbert space.

Quantum property testing for bounded-degree graphs - Andris Ambainis; Andrew M. Childs; Yi-Kai Liu (Proc. RANDOM, 2010)
We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound. For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph structure.

Quantum state tomography via compressed sensing - David Gross; Yi-Kai Liu; Steven T. Flammia; Stephen Becker; Jens Eisert (Physical Review Letters, 2010)
We establish methods for quantum state tomography based on compressed sensing. These methods are specialized for quantum states that are fairly pure, and they offer a significant performance improvement on large quantum systems. In particular, they are able to reconstruct an unknown density matrix of dimension d and rank r using O(rd log^2 d) measurement settings, compared to standard methods that require d^2 settings. Our methods have several features that make them amenable to experimental implementation: they require only simple Pauli measurements, use fast convex optimization, are stable against noise, and can be applied to states that are only approximately low-rank. The acquired data can be used to certify that the state is indeed close to pure, so no a priori assumptions are needed. We present both theoretical bounds and numerical simulations.

On the relationship between continuous- and discrete-time quantum walk - Andrew M. Childs (Communications in Mathematical Physics, 2010)
Quantum walk is one of the main tools for quantum algorithms. Defined by analogy to classical random walk, a quantum walk is a time-homogeneous quantum process on a graph. Both random and quantum walks can be defined either in continuous or discrete time. But whereas a continuous-time random walk can be obtained as the limit of a sequence of discrete-time random walks, the two types of quantum walk appear fundamentally different, owing to the need for extra degrees of freedom in the discrete-time case. In this article, I describe a precise correspondence between continuous- and discrete-time quantum walks on arbitrary graphs. Using this correspondence, I show that continuous-time quantum walk can be obtained as an appropriate limit of discrete-time quantum walks. The correspondence also leads to a new technique for simulating Hamiltonian dynamics, giving efficient simulations even in cases where the Hamiltonian is not sparse. The complexity of the simulation is linear in the total evolution time, an improvement over simulations based on high-order approximations of the Lie product formula. As applications, I describe a continuous-time quantum walk algorithm for element distinctness and show how to optimally simulate continuous-time query algorithms of a certain form in the conventional quantum query model. Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations.

Simulating sparse Hamiltonians with star decompositions - Andrew M. Childs; Robin Kothari (2010)
We present an efficient algorithm for simulating the time evolution due to a sparse Hamiltonian. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian H acts for time t, this algorithm uses (d^2(d+log* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which scales like (d^4(log* N)||Ht||)^{1+o(1)}. To achieve this, we decompose a general sparse Hamiltonian into a small sum of Hamiltonians whose graphs of non-zero entries have the property that every connected component is a star, and efficiently simulate each of these pieces.

Temperature driven structural phase transition for trapped ions and its experimental detection - Zhe-Xuan Gong; G. -D. Lin; L. -M. Duan (Physical Review Letters, 2010)
A Wigner crystal formed with trapped ion can undergo structural phase transition, which is determined only by the mechanical conditions on a classical level. Instead of this classical result, we show that through consideration of quantum and thermal fluctuation, a structural phase transition can be solely driven by change of the system's temperature. We determine a finite-temperature phase diagram for trapped ions using the renormalization group method and the path integral formalism, and propose an experimental scheme to observe the predicted temperature-driven structural phase transition, which is well within the reach of the current ion trap technology.

Thesis: Novel Systems and Methods for Quantum Communication, Quantum Computation, and Quantum Simulation - Alexey V. Gorshkov (Harvard University Physics Department, 2010)

Two-orbital SU(N) magnetism with ultracold alkaline-earth atoms - Alexey V. Gorshkov; Hermele, M; Gurarie, V; Xu, C; Julienne, P S; Ye, J; Zoller, P; Demler, E; Lukin, M D; Rey, A M (Nature Phys., 2010)

Von Neumann's 'No Hidden Variables' Proof: A Re-Appraisal - Jeffrey Bub (Foundations of Physics, 2010)
Since the analysis by John Bell in 1965, the consensus in the literature is that von Neumann's 'no hidden variables' proof fails to exclude any significant class of hidden variables. Bell raised the question whether it could be shown that any hidden variable theory would have to be nonlocal, and in this sense 'like Bohm's theory.' His seminal result provides a positive answer to the question. I argue that Bell's analysis misconstrues von Neumann's argument. What von Neumann proved was the impossibility of recovering the quantum probabilities from a hidden variable theory of dispersion free (deterministic) states in which the quantum observables are represented as the 'beables' of the theory, to use Bell's term. That is, the quantum probabilities could not reflect the distribution of pre-measurement values of beables, but would have to be derived in some other way, e.g., as in Bohm's theory, where the probabilities are an artefact of a dynamical process that is not in fact a measurement of any beable of the system.

Alkaline-Earth-Metal Atoms as Few-Qubit Quantum Registers - Alexey V. Gorshkov; Ana Maria Rey; Andrew J. Daley; Martin M. Boyd; Jun Ye; Peter Zoller; Mikhail D. Lukin (Physical Review Letters, 2009)
We propose and analyze a novel approach to quantum information processing, in which multiple qubits can be encoded and manipulated using electronic and nuclear degrees of freedom associated with individual alkaline-earth atoms trapped in an optical lattice. Specifically, we describe how the qubits within each register can be individually manipulated and measured with sub-wavelength optical resolution. We also show how such few-qubit registers can be coupled to each other in optical superlattices via conditional tunneling to form a scalable quantum network. Finally, potential applications to quantum computation and precision measurements are discussed.

Black-box Hamiltonian simulation and unitary implementation - Dominic W. Berry; Andrew M. Childs (2009)
We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D^4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N x N unitary operation use O(N^2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N^{2/3} (log log N)^{4/3}) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(sqrtN) queries, which is optimal.

Collisional cooling of ultra-cold atom ensembles using Feshbach resonances - L. Mathey; Eite Tiesinga; Paul S. Julienne; Charles W. Clark (Physical Review A, 2009)
We propose a new type of cooling mechanism for ultra-cold fermionic atom ensembles, which capitalizes on the energy dependence of inelastic collisions in the presence of a Feshbach resonance. We first discuss the case of a single magnetic resonance, and find that the final temperature and the cooling rate is limited by the width of the resonance. A concrete example, based on a p-wave resonance of $^{40}$K, is given. We then improve upon this setup by using both a very sharp optical or radio-frequency induced resonance and a very broad magnetic resonance and show that one can improve upon temperatures reached with current technologies.

Contextuality and nonlocality in 'no signaling' theories - Jeffrey Bub; Allen Stairs (Foundations of Physics, 2009)
We define a family of 'no signaling' bipartite boxes with arbitrary inputs and binary outputs, and with a range of marginal probabilities. The defining correlations are motivated by the Klyachko version of the Kochen-Specker theorem, so we call these boxes Kochen-Specker-Klyachko boxes or, briefly, KS-boxes. The marginals cover a variety of cases, from those that can be simulated classically to the superquantum correlations that saturate the Clauser-Horne-Shimony-Holt inequality, when the KS-box is a generalized PR-box (hence a vertex of the `no signaling' polytope). We show that for certain marginal probabilities a KS-box is classical with respect to nonlocality as measured by the Clauser-Horne-Shimony-Holt correlation, i.e., no better than shared randomness as a resource in simulating a PR-box, even though such KS-boxes cannot be perfectly simulated by classical or quantum resources for all inputs. We comment on the significance of these results for contextuality and nonlocality in 'no signaling' theories.

Counterflow and paired superfluidity in one-dimensional Bose mixtures in optical lattices - Anzi Hu; L. Mathey; Ippei Danshita; Eite Tiesinga; Carl J. Williams; Charles W. Clark (Physical Review A, 2009)
We study the quantum phases of mixtures of ultra-cold bosonic atoms held in an optical lattice that confines motion or hopping to one spatial dimension. The phases are found by using Tomonaga-Luttinger liquid theory as well as the numerical method of time evolving block decimation (TEBD). We consider a binary mixture with repulsive intra-species interactions, and either repulsive or attractive inter-species interaction. For a homogeneous system, we find paired- and counterflow-superfluid phases at different filling and hopping energies. We also predict parameter regions in which these types of superfluid order coexist with charge density wave order. We show that the Tomonaga-Luttinger liquid theory and TEBD qualitatively agree on the location of the phase boundary to superfluidity. We then describe how these phases are modified and can be detected when an additional harmonic trap is present. In particular, we show how experimentally measurable quantities, such as time-of-flight images and the structure factor, can be used to distinguish the quantum phases. Finally, we suggest applying a Feshbach ramp to detect the paired superfluid state, and a $π/2$ pulse followed by Bragg spectroscopy to detect the counterflow superfluid phase.

Discrete-query quantum algorithm for NAND trees - Andrew M. Childs; Richard Cleve; Stephen P. Jordan; David Yeung (Theory of Computing, 2009)
Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional quantum query model, for any fixed epsilon > 0.

Efficient quantum circuits for arbitrary sparse unitaries - Stephen P. Jordan; Pawel Wocjan (Physical Review A, 2009)
Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided it has at most polynomially many nonzero entries in any row or column, and these entries are efficiently computable. One can formulate a model of computation based on the composition of sparse unitaries which includes the quantum Turing machine model, the quantum circuit model, anyonic models, permutational quantum computation, and discrete time quantum walks as special cases. Thus we obtain a simple unified proof that these models are all contained in BQP. Furthermore our general method for implementing sparse unitaries simplifies several existing quantum algorithms.

Efficient quantum processing of ideals in finite rings - Pawel M. Wocjan; Stephen P. Jordan; Hamed Ahmadi; Joseph P. Brennan (2009)
Suppose we are given black-box access to a finite ring R, and a list of generators for an ideal I in R. We show how to find an additive basis representation for I in poly(log |R|) time. This generalizes a recent quantum algorithm of Arvind et al. which finds a basis representation for R itself. We then show that our algorithm is a useful primitive allowing quantum computers to rapidly solve a wide variety of problems regarding finite rings. In particular we show how to test whether two ideals are identical, find their intersection, find their quotient, prove whether a given ring element belongs to a given ideal, prove whether a given element is a unit, and if so find its inverse, find the additive and multiplicative identities, compute the order of an ideal, solve linear equations over rings, decide whether an ideal is maximal, find annihilators, and test the injectivity and surjectivity of ring homomorphisms. These problems appear to be hard classically.

Entanglement Cost of Nonlocal Measurements - Somshubhro Bandyopadhyay; Gilles Brassard; Shelby Kimmel; William K. Wootters (Physical Review A, 2009)
For certain joint measurements on a pair of spatially separated particles, we ask how much entanglement is needed to carry out the measurement exactly. For a class of orthogonal measurements on two qubits with partially entangled eigenstates, we present upper and lower bounds on the entanglement cost. The upper bound is based on a recent result by D. Berry [Phys. Rev. A 75, 032349 (2007)]. The lower bound, based on the entanglement production capacity of the measurement, implies that for almost all measurements in the class we consider, the entanglement required to perform the measurement is strictly greater than the average entanglement of its eigenstates. On the other hand, we show that for any complete measurement in d x d dimensions that is invariant under all local Pauli operations, the cost of the measurement is exactly equal to the average entanglement of the states associated with the outcomes.

Estimating Jones and HOMFLY polynomials with One Clean Qubit - Stephen P. Jordan; Pawel Wocjan (Quantum Information and Computation, 2009)
The Jones and HOMFLY polynomials are link invariants with close connections to quantum computing. It was recently shown that finding a certain approximation to the Jones polynomial of the trace closure of a braid at the fifth root of unity is a complete problem for the one clean qubit complexity class. This is the class of problems solvable in polynomial time on a quantum computer acting on an initial state in which one qubit is pure and the rest are maximally mixed. Here we generalize this result by showing that one clean qubit computers can efficiently approximate the Jones and single-variable HOMFLY polynomials of the trace closure of a braid at any root of unity.

Geometric-Phase-Effect Tunnel-Splitting Oscillations in Single-Molecule Magnets with Fourth-Order Anisotropy Induced by Orthorhombic Distortion - Michael Foss-Feig; Jonathan R. Friedman (EPL (Europhysics Letters), 2009)
We analyze the interference between tunneling paths that occurs for a spin system with both fourth-order and second-order transverse anisotropy. Using an instanton approach, we find that as the strength of the second-order transverse anisotropy is increased, the tunnel splitting is modulated, with zeros occurring periodically. This effect results from the interference of four tunneling paths connecting easy-axis spin orientations and occurs in the absence of any magnetic field.

Limitations on the simulation of non-sparse Hamiltonians - Andrew M. Childs; Robin Kothari (2009)
The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse N x N Hamiltonian H for time t can be simulated using O(||Ht||poly(log N)) operations, which is essentially optimal due to a no--fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time o(||Ht||), even though ||H|| is not a unique measure of the size of a dense Hamiltonian $H$. We also present a stronger limitation ruling out the possibility of generic simulations taking time poly(||Ht||,log N), showing that known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonians can be simulated efficiently, such as those with graphs of small arboricity.

Locality Bounds on Hamiltonians for Stabilizer Codes - Stephen S. Bullock; Dianne P. O'Leary (Quantum Information and Computation, 2009)
In this paper, we study the complexity of Hamiltonians whose groundstate is a stabilizer code. We introduce various notions of k-locality of a stabilizer code, inherited from the associated stabilizer group. A choice of generators leads to a Hamiltonian with the code in its groundspace. We establish bounds on the locality of any other Hamiltonian whose groundspace contains such a code, whether or not its Pauli tensor summands commute. Our results provide insight into the cost of creating an energy gap for passive error correction and for adiabatic quantum computing. The results simplify in the cases of XZ-split codes such as Calderbank-Shor-Steane stabilizer codes and topologically-ordered stabilizer codes arising from surface cellulations.

Many-Body Treatment of the Collisional Frequency Shift in Fermionic Atoms - Rey, A M; Alexey V. Gorshkov; Rubbo, C (Phys. Rev. Lett., 2009)

Multi-channel modelling of the formation of vibrationally cold polar KRb molecules - Svetlana Kotochigova; Eite Tiesinga; Paul S. Julienne (New Journal of Physics, 2009)
We describe the theoretical advances that influenced the experimental creation of vibrationally and translationally cold polar $^{40}$K$^{87}$Rb molecules \cite{nphys08,science08}. Cold molecules were created from very-weakly bound molecules formed by magnetic field sweeps near a Feshbach resonance in collisions of ultra-cold $^{40}$K and $^{87}$Rb atoms. Our analysis include the multi-channel bound-state calculations of the hyperfine and Zeeman mixed X$^1Σ^+$ and a$^3Σ^+$ vibrational levels. We find excellent agreement with the hyperfine structure observed in experimental data. In addition, we studied the spin-orbit mixing in the intermediate state of the Raman transition. This allowed us to investigate its effect on the vibrationally-averaged transition dipole moment to the lowest ro-vibrational level of the X$^1Σ^+$ state. Finally, we obtained an estimate of the polarizability of the initial and final ro-vibrational states of the Raman transition near frequencies relevant for optical trapping of the molecules.

Number Fluctuations and Energy Dissipation in Sodium Spinor Condensates - Yingmei Liu; Eduardo Gomez; Stephen E. Maxwell; Lincoln D. Turner; Eite Tiesinga; Paul D. Lett (Physical Review Letters, 2009)
We characterize fluctuations in atom number and spin populations in F=1 sodium spinor condensates. We find that the fluctuations enable a quantitative measure of energy dissipation in the condensate. The time evolution of the population fluctuations shows a maximum. We interpret this as evidence of a dissipation-driven separatrix crossing in phase space. For a given initial state, the critical time to the separatrix crossing is found to depend exponentially on the magnetic field and linearly on condensate density. This crossing is confirmed by tracking the energy of the spinor condensate as well as by Faraday rotation spectroscopy. We also introduce a phenomenological model that describes the observed dissipation with a single coefficient.

Prediction of Feshbach resonances from three input parameters - Thomas M. Hanna; Eite Tiesinga; Paul S. Julienne (Physical Review A, 2009)
We have developed a model of Feshbach resonances in gases of ultracold alkali metal atoms using the ideas of multichannel quantum defect theory. Our model requires just three parameters describing the interactions - the singlet and triplet scattering lengths, and the long range van der Waals coefficient - in addition to known atomic properties. Without using any further details of the interactions, our approach can accurately predict the locations of resonances. It can also be used to find the singlet and triplet scattering lengths from measured resonance data. We apply our technique to $^{6}$Li--$^{40}$K and $^{40}$K--$^{87}$Rb scattering, obtaining good agreement with experimental results, and with the more computationally intensive coupled channels technique.

Protocol for Hybrid Entanglement Between a Trapped Atom and a Semiconductor Quantum Dot - Edo Waks; Christopher Monroe (Physical Review A, 2009)
We propose a quantum optical interface between an atomic and solid state system. We show that quantum states in a single trapped atom can be entangled with the states of a semiconductor quantum dot through their common interaction with a classical laser field. The interference and detection of the resulting scattered photons can then herald the entanglement of the disparate atomic and solid-state quantum bits. We develop a protocol that can succeed despite a significant mismatch in the radiative characteristics of the two matter-based qubits. We study in detail a particular case of this interface applied to a single trapped \Yb ion and a cavity-coupled InGaAs semiconductor quantum dot. Entanglement fidelity and success rates are found to be robust to a broad range of experimental nonideal effects such as dispersion mismatch, atom recoil, and multi-photon scattering. We conclude that it should be possible to produce highly entangled states of these complementary qubit systems under realistic experimental conditions.

Quadratic fermionic interactions yield effective Hamiltonians for adiabatic quantum computing - Michael J. O'Hara; Dianne P. O'Leary (Physical Review A, 2009)
Polynomially-large ground-state energy gaps are rare in many-body quantum systems, but useful for adiabatic quantum computing. We show analytically that the gap is generically polynomially-large for quadratic fermionic Hamiltonians. We then prove that adiabatic quantum computing can realize the ground states of Hamiltonians with certain random interactions, as well as the ground states of one, two, and three-dimensional fermionic interaction lattices, in polynomial time. Finally, we use the Jordan-Wigner transformation and a related transformation for spin-3/2 particles to show that our results can be restated using spin operators in a surprisingly simple manner. A direct consequence is that the one-dimensional cluster state can be found in polynomial time using adiabatic quantum computing.

Quantum Algorithms Using the Curvelet Transform - Yi-Kai Liu (Proc. ACM Symposium on Theory of Computing (STOC), 2009)
The curvelet transform is a directional wavelet transform over R^n, which is used to analyze functions that have singularities along smooth surfaces (Candes and Donoho, 2002). I demonstrate how this can lead to new quantum algorithms. I give an efficient implementation of a quantum curvelet transform, together with two applications: a single-shot measurement procedure for approximately finding the center of a ball in R^n, given a quantum-sample over the ball; and, a quantum algorithm for finding the center of a radial function over R^n, given oracle access to the function. I conjecture that these algorithms succeed with constant probability, using one quantum-sample and O(1) oracle queries, respectively, independent of the dimension n -- this can be interpreted as a quantum speed-up. To support this conjecture, I prove rigorous bounds on the distribution of probability mass for the continuous curvelet transform. This shows that the above algorithms work in an idealized "continuous" model.

Quantum Phase Transitions and Continuous Observation of Spinor Dynamics in an Antiferromagnetic Condensate - Yingmei Liu; Sebastian Jung; Stephen E. Maxwell; Lincoln D. Turner; Eite Tiesinga; Paul. D. Lett (Physical Review Letters, 2009)
Condensates of spin-1 sodium display rich spin dynamics due to the antiferromagnetic nature of the interactions in this system. We use Faraday rotation spectroscopy to make a continuous and minimally destructive measurement of the dynamics over multiple spin oscillations on a single evolving condensate. This method provides a sharp signature to locate a magnetically tuned separatrix in phase space which depends on the net magnetization. We also observe a phase transition from a two- to a three-component condensate at a low but finite temperature using a Stern-Gerlach imaging technique. This transition should be preserved as a zero-temperature quantum phase transition.

The quantum query complexity of certification - Andris Ambainis; Andrew M. Childs; François Le Gall; Seiichiro Tani (2009)
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.

Realization of Coherent Optically Dense Media via Buffer-Gas Cooling - Tao Hong; Alexey V. Gorshkov; David Patterson; Alexander S. Zibrov; John M. Doyle; Mikhail D. Lukin; Mara G. Prentiss (Physical Review A, 2009)
We demonstrate that buffer-gas cooling combined with laser ablation can be used to create coherent optical media with high optical depth and low Doppler broadening that offers metastable states with low collisional and motional decoherence. Demonstration of this generic technique opens pathways to coherent optics with a large variety of atoms and molecules. We use helium buffer gas to cool 87Rb atoms to below 7 K and slow atom diffusion to the walls. Electromagnetically induced transparency (EIT) in this medium allows for 50% transmission in a medium with initial OD >70 and for slow pulse propagation with large delay-bandwidth products. In the high-OD regime, we observe high-contrast spectrum oscillations due to efficient four-wave mixing.

Slow light propagation and amplification via electromagnetically induced transparency and four-wave mixing in an optically dense atomic vapor - Phillips, N B; Alexey V. Gorshkov; Novikova, I (J. Mod. Opt., 2009)

Universal computation by quantum walk - Andrew M. Childs (Physical Review Letters, 2009)
In some of the earliest work on quantum mechanical computers, Feynman showed how to implement universal quantum computation by the dynamics of a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be a sparse matrix with all entries equal to 0 or 1, i.e., the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any desired quantum computation encoded entirely in some underlying graph. The main idea of the construction is to implement quantum gates by scattering processes.

The adiabatic theorem in the presence of noise - Michael J. O'Hara; Dianne P. O'Leary (Physical Review A, 2008)
We provide rigorous bounds for the error of the adiabatic approximation of quantum mechanics under four sources of experimental error: perturbations in the initial condition, systematic time-dependent perturbations in the Hamiltonian, coupling to low-energy quantum systems, and decoherent time-dependent perturbations in the Hamiltonian. For decoherent perturbations, we find both upper and lower bounds on the evolution time to guarantee the adiabatic approximation performs within a prescribed tolerance. Our new results include explicit definitions of constants, and we apply them to the spin-1/2 particle in a rotating magnetic field, and to the superconducting flux qubit. We compare the theoretical bounds on the superconducting flux qubit to simulation results.

Ancilla-Assisted Discrimination of Quantum Gates - Jianxin Chen; Mingsheng Ying (2008)
The intrinsic idea of superdense coding is to find as many gates as possible such that they can be perfectly discriminated. In this paper, we consider a new scheme of discrimination of quantum gates, called ancilla-assisted discrimination, in which a set of quantum gates on a $d-$dimensional system are perfectly discriminated with assistance from an $r-$dimensional ancilla system. The main contribution of the present paper is two-fold: (1) The number of quantum gates that can be discriminated in this scheme is evaluated. We prove that any $rd+1$ quantum gates cannot be perfectly discriminated with assistance from the ancilla, and there exist $rd$ quantum gates which can be perfectly discriminated with assistance from the ancilla. (2) The dimensionality of the minimal ancilla system is estimated. We prove that there exists a constant positive number $c$ such that for any $k≤ cr$ quantum gates, if they are $d$-assisted discriminable, then they are also $r$-assisted discriminable, and there are $c^{′}r(c^{′}>c)$ different quantum gates which can be discriminated with a $d-$dimensional ancilla, but they cannot be discriminated if the ancilla is reduced to an $r-$dimensional system. Thus, the order $O(r)$ of the number of quantum gates that can be discriminated with assistance from an $r-$dimensional ancilla is optimal. The results reported in this paper represent a preliminary step toward understanding the role ancilla system plays in discrimination of quantum gates as well as the power and limit of superdense coding.

Anyonic interferometry and protected memories in atomic spin lattices - Liang Jiang; Gavin K. Brennen; Alexey V. Gorshkov; Klemens Hammerer; Mohammad Hafezi; Eugene Demler; Mikhail D. Lukin; Peter Zoller (Nature Physics, 2008)
Strongly correlated quantum systems can exhibit exotic behavior called topological order which is characterized by non-local correlations that depend on the system topology. Such systems can exhibit remarkable phenomena such as quasi-particles with anyonic statistics and have been proposed as candidates for naturally fault-tolerant quantum computation. Despite these remarkable properties, anyons have never been observed in nature directly. Here we describe how to unambiguously detect and characterize such states in recently proposed spin lattice realizations using ultra-cold atoms or molecules trapped in an optical lattice. We propose an experimentally feasible technique to access non-local degrees of freedom by performing global operations on trapped spins mediated by an optical cavity mode. We show how to reliably read and write topologically protected quantum memory using an atomic or photonic qubit. Furthermore, our technique can be used to probe statistics and dynamics of anyonic excitations.

Avoided crossings between bound states of ultracold Cesium dimers - Jeremy M. Hutson; Eite Tiesinga; Paul S. Julienne (Physical Review A, 2008)
We present an efficient new computational method for calculating the binding energies of the bound states of ultracold alkali-metal dimers in the presence of magnetic fields. The method is based on propagation of coupled differential equations and does not use a basis set for the interatomic distance coordinate. It is much more efficient than the previous method based on a radial basis set and allows many more spin channels to be included. This is particularly important in the vicinity of avoided crossings between bound states. We characterize a number of different avoided crossings in Cs_2 and compare our converged calculations with experimental results. Small but significant discrepancies are observed in both crossing strengths and level positions, especially for levels with l symmetry (rotational angular momentum L=8). The discrepancies should allow the development of improved potential models in the future.

Coherence of an optically illuminated single nuclear spin qubit - Liang Jiang; M. V. Gurudev Dutt; Emre Togan; Lily Childress; Paola Cappellaro; J. M. Taylor; Mikhail D. Lukin (Physical Review Letters, 2008)
We investigate the coherence properties of individual nuclear spin quantum bits in diamond [Dutt et al., Science, 316, 1312 (2007)] when a proximal electronic spin associated with a nitrogen-vacancy (NV) center is being interrogated by optical radiation. The resulting nuclear spin dynamics are governed by time-dependent hyperfine interaction associated with rapid electronic transitions, which can be described by a spin-fluctuator model. We show that due to a process analogous to motional averaging in nuclear magnetic resonance, the nuclear spin coherence can be preserved after a large number of optical excitation cycles. Our theoretical analysis is in good agreement with experimental results. It indicates a novel approach that could potentially isolate the nuclear spin system completely from the electronic environment.

Coherent Quantum Optical Control with Subwavelength Resolution - Alexey V. Gorshkov; Liang Jiang; Markus Greiner; Peter Zoller; Mikhail D. Lukin (Physical Review Letters, 2008)
We suggest a new method for quantum optical control with nanoscale resolution. Our method allows for coherent far-field manipulation of individual quantum systems with spatial selectivity that is not limited by the wavelength of radiation and can, in principle, approach a few nanometers. The selectivity is enabled by the nonlinear atomic response, under the conditions of Electromagnetically Induced Transparency, to a control beam with intensity vanishing at a certain location. Practical performance of this technique and its potential applications to quantum information science with cold atoms, ions, and solid-state qubits are discussed.

Efficient scheme for one-way quantum computing in thermal cavities - Wen-Xing Yang; Zhe-Xuan Gong (International Journal of Theoretical Physics, 2008)
We propose a practical scheme for one-way quantum computing based on efficient generation of 2D cluster state in thermal cavities. We achieve a controlled-phase gate that is neither sensitive to cavity decay nor to thermal field by adding a strong classical field to the two-level atoms. We show that a 2D cluster state can be generated directly by making every two atoms collide in an array of cavities, with numerically calculated parameters and appropriate operation sequence that can be easily achieved in practical Cavity QED experiments. Based on a generated cluster state in Box$^{(4)}$ configuration, we then implement Grover's search algorithm for four database elements in a very simple way as an example of one-way quantum computing.

Estimating Jones polynomials is a complete problem for one clean qubit - Peter W. Shor; Stephen P. Jordan (Quantum Information & Computation, 2008)
It is known that evaluating a certain approximation to the Jones polynomial for the plat closure of a braid is a BQP-complete problem. That is, this problem exactly captures the power of the quantum circuit model. The one clean qubit model is a model of quantum computation in which all but one qubit starts in the maximally mixed state. One clean qubit computers are believed to be strictly weaker than standard quantum computers, but still capable of solving some classically intractable problems. Here we show that evaluating a certain approximation to the Jones polynomial at a fifth root of unity for the trace closure of a braid is a complete problem for the one clean qubit complexity class. That is, a one clean qubit computer can approximate these Jones polynomials in time polynomial in both the number of strands and number of crossings, and the problem of simulating a one clean qubit computer is reducible to approximating the Jones polynomial of the trace closure of a braid.

Existence of Universal Entangler - Jianxin Chen; Runyao Duan; Zhengfeng Ji; Mingsheng Ying; Jun Yu (Journal of Mathematical Physics, 2008)
A gate is called entangler if it transforms some (pure) product states to entangled states. A universal entangler is a gate which transforms all product states to entangled states. In practice, a universal entangler is a very powerful device for generating entanglements, and thus provides important physical resources for accomplishing many tasks in quantum computing and quantum information. This Letter demonstrates that a universal entangler always exists except for a degenerated case. Nevertheless, the problem how to find a universal entangler remains open.

Fast quantum algorithms for approximating some irreducible representations of groups - Stephen P. Jordan (2008)
We consider the quantum complexity of estimating matrix elements of unitary irreducible representations of groups. For several finite groups including the symmetric group, quantum Fourier transforms yield efficient solutions to this problem. Furthermore, quantum Schur transforms yield efficient solutions for certain irreducible representations of the unitary group. Beyond this, we obtain poly(n)-time quantum algorithms for approximating matrix elements from all the irreducible representations of the alternating group A_n, and all the irreducible representations of polynomial highest weight of U(n), SU(n), and SO(n). These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters.

High-sensitivity diamond magnetometer with nanoscale resolution - J. M. Taylor; P. Cappellaro; L. Childress; L. Jiang; D. Budker; P. R. Hemmer; A. Yacoby; R. Walsworth; M. D. Lukin (Nature Physics, 2008)
We present a novel approach to the detection of weak magnetic fields that takes advantage of recently developed techniques for the coherent control of solid-state electron spin quantum bits. Specifically, we investigate a magnetic sensor based on Nitrogen-Vacancy centers in room-temperature diamond. We discuss two important applications of this technique: a nanoscale magnetometer that could potentially detect precession of single nuclear spins and an optical magnetic field imager combining spatial resolution ranging from micrometers to millimeters with a sensitivity approaching few femtotesla/Hz$^{1/2}$.

Multilevel effects in the Rabi oscillations of a Josephson phase qubit - S. K. Dutta; Frederick W. Strauch; R. M. Lewis; Kaushik Mitra; Hanhee Paik; T. A. Palomaki; Eite Tiesinga; J. R. Anderson; Alex J. Dragt; C. J. Lobb; F. C. Wellstood (Physical Review B, 2008)
We present Rabi oscillation measurements of a Nb/AlOx/Nb dc superconducting quantum interference device (SQUID) phase qubit with a 100 um^2 area junction acquired over a range of microwave drive power and frequency detuning. Given the slightly anharmonic level structure of the device, several excited states play an important role in the qubit dynamics, particularly at high power. To investigate the effects of these levels, multiphoton Rabi oscillations were monitored by measuring the tunneling escape rate of the device to the voltage state, which is particularly sensitive to excited state population. We compare the observed oscillation frequencies with a simplified model constructed from the full phase qubit Hamiltonian and also compare time-dependent escape rate measurements with a more complete density-matrix simulation. Good quantitative agreement is found between the data and simulations, allowing us to identify a shift in resonance (analogous to the ac Stark effect), a suppression of the Rabi frequency, and leakage to the higher excited states.

Optimal light storage in atomic vapor - Nathaniel B. Phillips; Alexey V. Gorshkov; Irina Novikova (Physical Review A, 2008)
We study procedures for the optimization of efficiency of light storage and retrieval based on the dynamic form of electromagnetically induced transparency (EIT) in warm Rb vapor. We present a detailed analysis of two recently demonstrated optimization protocols: a time-reversal-based iteration procedure, which finds the optimal input signal pulse shape for any given control field, and a procedure based on the calculation of an optimal control field for any given signal pulse shape. We verify that the two procedures are consistent with each other, and that they both independently achieve the maximum memory efficiency for any given optical depth. We observe good agreement with theoretical predictions for moderate optical depths (<25), while at higher optical depths the experimental efficiency falls below the theoretically predicted values. We identify possible effects responsible for this reduction in memory efficiency.

Optimal light storage with full pulse shape control - Irina Novikova; Nathaniel B. Phillips; Alexey V. Gorshkov (Physical Review A, 2008)
We experimentally demonstrate optimal storage and retrieval of light pulses of arbitrary shape in atomic ensembles. By shaping auxiliary control pulses, we attain efficiencies approaching the fundamental limit and achieve precise retrieval into any predetermined temporal profile. Our techniques, demonstrated in warm Rb vapor, are applicable to a wide range of systems and protocols. As an example, we present their potential application to the creation of optical time-bin qubits and to controlled partial retrieval.

Optimal light storage with full pulse-shape control - Novikova, I; Phillips, N B; Alexey V. Gorshkov (Phys. Rev. A, 2008)

Optimizing Slow and Stored Light for Multidisciplinary Applications - Klein, M; Xiao, Y; Alexey V. Gorshkov; M Hohensee; C D Leung; M R Browning; Phillips, D F; Novikova, I; Walsworth, R L (Proc. SPIE, 2008)

Perturbative Gadgets at Arbitrary Orders - Stephen P. Jordan; Edward Farhi (Physical Review A, 2008)
Adiabatic quantum algorithms are often most easily formulated using many-body interactions. However, experimentally available interactions are generally two-body. In 2004, Kempe, Kitaev, and Regev introduced perturbative gadgets, by which arbitrary three-body effective interactions can be obtained using Hamiltonians consisting only of two-body interactions. These three-body effective interactions arise from the third order in perturbation theory. Since their introduction, perturbative gadgets have become a standard tool in the theory of quantum computation. Here we construct generalized gadgets so that one can directly obtain arbitrary k-body effective interactions from two-body Hamiltonians. These effective interactions arise from the kth order in perturbation theory.

Photon storage in Lambda-type optically dense atomic media. IV. Optimal control using gradient ascent - Alexey V. Gorshkov; Tommaso Calarco; Mikhail D. Lukin; Anders S. Sorensen (Physical Review A, 2008)
We use the numerical gradient ascent method from optimal control theory to extend efficient photon storage in Lambda-type media to previously inaccessible regimes and to provide simple intuitive explanations for our optimization techniques. In particular, by using gradient ascent to shape classical control pulses used to mediate photon storage, we open up the possibility of high efficiency photon storage in the non-adiabatic limit, in which analytical solutions to the equations of motion do not exist. This control shaping technique enables an order-of-magnitude increase in the bandwidth of the memory. We also demonstrate that the often discussed connection between time reversal and optimality in photon storage follows naturally from gradient ascent. Finally, we discuss the optimization of controlled reversible inhomogeneous broadening.

Polynomial-time quantum algorithm for the simulation of chemical dynamics - Ivan Kassal; Stephen P. Jordan; Peter J. Love; Masoud Mohseni; Alán Aspuru-Guzik (Proceedings of the National Academy of Sciences, 2008)
The computational cost of exact methods for quantum simulation using classical computers grows exponentially with system size. As a consequence, these techniques can only be applied to small systems. By contrast, we demonstrate that quantum computers could exactly simulate chemical reactions in polynomial time. Our algorithm uses the split-operator approach and explicitly simulates all electron-nuclear and inter-electronic interactions in quadratic time. Surprisingly, this treatment is not only more accurate than the Born-Oppenheimer approximation, but faster and more efficient as well, for all reactions with more than about four atoms. This is the case even though the entire electronic wavefunction is propagated on a grid with appropriately short timesteps. Although the preparation and measurement of arbitrary states on a quantum computer is inefficient, here we demonstrate how to prepare states of chemical interest efficiently. We also show how to efficiently obtain chemically relevant observables, such as state-to-state transition probabilities and thermal reaction rates. Quantum computers using these techniques could outperform current classical computers with one hundred qubits.

The Power of Unentanglement - Scott Aaronson; Salman Beigi; Andrew Drucker; Bill Fefferman; Peter Shor (2008)
The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Does QMA(k)=QMA(2) for k>=2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. First, we give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given ~O(sqrt(n)) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on the existence of very short PCPs. Second, we show that assuming a weak version of the Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all k>=2. Third, we prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.

Quantum behavior of the dc SQUID phase qubit - Kaushik Mitra; F. W. Strauch; C. J. Lobb; J. R. Anderson; F. C. Wellstood; Eite Tiesinga (Physical Review B, 2008)
We analyze the behavior of a dc Superconducting Quantum Interference Device (SQUID) phase qubit in which one junction acts as a phase qubit and the rest of the device provides isolation from dissipation and noise in the bias leads. Ignoring dissipation, we find the two-dimensional Hamiltonian of the system and use numerical methods and a cubic approximation to solve Schrodinger's equation for the eigenstates, energy levels, tunneling rates, and expectation value of the currents in the junctions. Using these results, we investigate how well this design provides isolation while preserving the characteristics of a phase qubit. In addition, we show that the expectation value of current flowing through the isolation junction depends on the state of the qubit and can be used for non-destructive read out of the qubit state.

Quantum Computation Beyond the Circuit Model - Stephen P. Jordan (2008)
The quantum circuit model is the most widely used model of quantum computation. It provides both a framework for formulating quantum algorithms and an architecture for the physical construction of quantum computers. However, several other models of quantum computation exist which provide useful alternative frameworks for both discovering new quantum algorithms and devising new physical implementations of quantum computers. In this thesis, I first present necessary background material for a general physics audience and discuss existing models of quantum computation. Then, I present three results relating to various models of quantum computation: a scheme for improving the intrinsic fault tolerance of adiabatic quantum computers using quantum error detecting codes, a proof that a certain problem of estimating Jones polynomials is complete for the one clean qubit complexity class, and a generalization of perturbative gadgets which allows k-body interactions to be directly simulated using 2-body interactions. Lastly, I discuss general principles regarding quantum computation that I learned in the course of my research, and using these principles I propose directions for future research.

Suppression of Inelastic Collisions Between Polar Molecules With a Repulsive Shield - Alexey V. Gorshkov; Rabl, P; Pupillo, G; Micheli, A; Zoller, P; Lukin, M D; Büchler, H P (Phys. Rev. Lett., 2008)

Theoretical analysis of perfect quantum state transfer with superconducting qubits - Frederick W. Strauch; Carl J. Williams (Physical Review B, 2008)
Superconducting quantum circuits, fabricated with multiple layers, are proposed to implement perfect quantum state transfer between nodes of a hypercube network. For tunable devices such as the phase qubit, each node can transmit quantum information to any other node at a constant rate independent of the distance between qubits. The physical limits of quantum state transfer in this network are theoretically analyzed, including the effects of disorder, decoherence, and higher-order couplings.

Tunneling phase gate for neutral atoms in a double-well lattice - Frederick W. Strauch; Mark Edwards; Eite Tiesinga; Carl J. Williams; Charles W. Clark (Physical Review A, 2008)
We propose a new two--qubit phase gate for ultra--cold atoms confined in an experimentally realized tilted double--well optical lattice [Sebby--Strabley et al., Phys. Rev. A {\bf 73} 033605 (2006)]. Such a lattice is capable of confining pairs of atoms in a two--dimensional array of double--well potentials where control can be exercised over the barrier height and the energy difference of the minima of the two wells (known as the ``tilt''). The four lowest single--particle motional states consist of two pairs of motional states in which each pair is localized on one side of the central barrier, allowing for two atoms confined in such a lattice to be spatially separated qubits. We present a time--dependent scheme to manipulate the tilt to induce tunneling oscillations which produce a collisional phase gate. Numerical simulations demonstrate that this gate can be performed with high fidelity.

Two-body transients in coupled atomic-molecular BECs - Pascal Naidon; Eite Tiesinga; Paul S. Julienne (Physical Review Letters, 2008)
We discuss the dynamics of an atomic Bose-Einstein condensate when pairs of atoms are converted into molecules by single-color photoassociation. Three main regimes are found and it is shown that they can be understood on the basis of time-dependent two-body theory. In particular, the so-called rogue dissociation regime [Phys. Rev. Lett., 88, 090403 (2002)], which has a density-dependent limit on the photoassociation rate, is identified with a transient regime of the two-atom dynamics exhibiting universal properties. Finally, we illustrate how these regimes could be explored by photoassociating condensates of alkaline-earth atoms.

Uncertainty principles for compact groups - Gorjan Alagic; Alexander Russell (Illinois J. Math., 2008)
We establish an uncertainty principle over arbitrary compact groups, generalizing several previous results. Specifically, we show that if P and R are operators on L2(G) such that P commutes with projection onto every measurable subset of G and R commutes with left-multiplication by elements of G, then ∥PR∥≤∥P⋅χG∥2∥R∥2, where χG:g↦1 is the characteristic function of G. As a consequence, we show that every nonzero function f in L2(G) satisfies μ(suppf)⋅∑ρ∈G^dρrankf^(ρ)≥1.

Wigner crystals of ions as quantum hard drives - J. M. Taylor; T. Calarco (Physical Review A, 2008)
Atomic systems in regular lattices are intriguing systems for implementing ideas in quantum simulation and information processing. Focusing on laser cooled ions forming Wigner crystals in Penning traps, we find a robust and simple approach to engineering non-trivial 2-body interactions sufficient for universal quantum computation. We then consider extensions of our approach to the fast generation of large cluster states, and a non-local architecture using an asymmetric entanglement generation procedure between a Penning trap system and well-established linear Paul trap designs.

Coherent, adiabatic and dissociation regimes in coupled atomic-molecular Bose-Einstein condensates - Pascal Naidon; Eite Tiesinga; Paul S. Julienne (2007)
We discuss the dynamics of a Bose-Einstein condensate of atoms which is suddenly coupled to a condensate of molecules by an optical or magnetic Feshbach resonance. Three limiting regimes are found and can be understood from the transient dynamics occuring for each pair of atoms. This transient dynamics can be summarised into a time-dependent shift and broadening of the molecular state. A simple Gross-Pitaevskii picture including this shift and broadening is proposed to describe the system in the three regimes. Finally, we suggest how to explore these regimes experimentally.

The Complexity of the Consistency and N-representability Problems for Quantum States - Yi-Kai Liu (2007)
QMA (Quantum Merlin-Arthur) is the quantum analogue of the class NP. There are a few QMA-complete problems, most notably the ``Local Hamiltonian'' problem introduced by Kitaev. In this dissertation we show some new QMA-complete problems. The first one is ``Consistency of Local Density Matrices'': given several density matrices describing different (constant-size) subsets of an n-qubit system, decide whether these are consistent with a single global state. This problem was first suggested by Aharonov. We show that it is QMA-complete, via an oracle reduction from Local Hamiltonian. This uses algorithms for convex optimization with a membership oracle, due to Yudin and Nemirovskii. Next we show that two problems from quantum chemistry, ``Fermionic Local Hamiltonian'' and ``N-representability,'' are QMA-complete. These problems arise in calculating the ground state energies of molecular systems. N-representability is a key component in recently developed numerical methods using the contracted Schrodinger equation. Although these problems have been studied since the 1960's, it is only recently that the theory of quantum computation has allowed us to properly characterize their complexity. Finally, we study some special cases of the Consistency problem, pertaining to 1-dimensional and ``stoquastic'' systems. We also give an alternative proof of a result due to Jaynes: whenever local density matrices are consistent, they are consistent with a Gibbs state.

Effective-range description of a Bose gas under strong one- or two-dimensional confinement - Pascal Naidon; Eite Tiesinga; William F. Mitchell; Paul S. Julienne (New Journal of Physics, 2007)
We point out that theories describing s-wave collisions of bosonic atoms confined in one- or two-dimensional geometries can be extended to much tighter confinements than previously thought. This is achieved by replacing the scattering length by an energy-dependent scattering length which was already introduced for the calculation of energy levels under 3D confinement. This replacement accurately predicts the position of confinement-induced resonances in strongly confined geometries.

Every NAND formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer - Andrew M. Childs; Ben W. Reichardt; Robert Spalek; Shengyu Zhang (2007)
For every NAND formula of size N, there is a bounded-error N^{1/2+o(1)}-time quantum algorithm, based on a coined quantum walk, that evaluates this formula on a black-box input. Balanced, or ``approximately balanced,'' NAND formulas can be evaluated in O(sqrtN) queries, which is optimal. It follows that the (2-o(1))-th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.

A fast and robust approach to long-distance quantum communication with atomic ensembles - L. Jiang; J. M. Taylor; M. D. Lukin (Physical Review A, 2007)
Quantum repeaters create long-distance entanglement between quantum systems while overcoming difficulties such as the attenuation of single photons in a fiber. Recently, an implementation of a repeater protocol based on single qubits in atomic ensembles and linear optics has been proposed [Nature 414, 413 (2001)]. Motivated by rapid experimental progress towards implementing that protocol, here we develop a more efficient scheme compatible with active purification of arbitrary errors. Using similar resources as the earlier protocol, our approach intrinsically purifies leakage out of the logical subspace and all errors within the logical subspace, leading to greatly improved performance in the presence of experimental inefficiencies. Our analysis indicates that our scheme could generate approximately one pair per 3 minutes over 1280 km distance with fidelity (F>78%) sufficient to violate Bell's inequality.

Improved quantum algorithms for the ordered search problem via semidefinite programming - Andrew M. Childs; Andrew J. Landahl; Pablo A. Parrilo (Physical Review A, 2007)
One of the most basic computational problems is the task of finding a desired item in an ordered list of N items. While the best classical algorithm for this problem uses log_2 N queries to the list, a quantum computer can solve the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for ordered search in terms of a semidefinite program, we find new quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using 4 log_{605} N ≈ 0.433 log_2 N queries, which improves upon the previously best known exact algorithm.

The limitations of nice mutually unbiased bases - Michael Aschbacher; Andrew M. Childs; Pawel Wocjan (Journal of Algebraic Combinatorics, 2007)
Mutually unbiased bases of a Hilbert space can be constructed by partitioning a unitary error basis. We consider this construction when the unitary error basis is a nice error basis. We show that the number of resulting mutually unbiased bases can be at most one plus the smallest prime power contained in the dimension, and therefore that this construction cannot improve upon previous approaches. We prove this by establishing a correspondence between nice mutually unbiased bases and abelian subgroups of the index group of a nice error basis and then bounding the number of such subgroups. This bound also has implications for the construction of certain combinatorial objects called nets.

The Local Consistency Problem for Stoquastic and 1-D Quantum Systems - Yi-Kai Liu (2007)
The Local Hamiltonian problem (finding the ground state energy of a quantum system) is known to be QMA-complete. The Local Consistency problem (deciding whether descriptions of small pieces of a quantum system are consistent) is also known to be QMA-complete. Here we consider special cases of Local Hamiltonian, for ``stoquastic'' and 1-dimensional systems, that seem to be strictly easier than QMA. We show that there exist analogous special cases of Local Consistency, that have equivalent complexity (up to poly-time oracle reductions). Our main technical tool is a new reduction from Local Consistency to Local Hamiltonian, using SDP duality.

The LU-LC conjecture is false - Zhengfeng Ji; Jianxin Chen; Zhaohui Wei; Mingsheng Ying (2007)
The LU-LC conjecture is an important open problem concerning the structure of entanglement of states described in the stabilizer formalism. It states that two local unitary equivalent stabilizer states are also local Clifford equivalent. If this conjecture were true, the local equivalence of stabilizer states would be extremely easy to characterize. Unfortunately, however, based on the recent progress made by Gross and Van den Nest, we find that the conjecture is false.

Multi-photon Entanglement: From Quantum Curiosity to Quantum Computing and Quantum Repeaters - Walther, P; Eisaman, M D; Nemiroski, A; Alexey V. Gorshkov; Zibrov, A S; Zeilinger, A; Lukin, M D (Proc. SPIE, 2007)

N-representability is QMA-complete - Yi-Kai Liu; Matthias Christandl; F. Verstraete (Phys. Rev. Lett., 2007)
We study the computational complexity of the N-representability problem in quantum chemistry. We show that this problem is quantum Merlin-Arthur complete, which is the quantum generalization of nondeterministic polynomial time complete. Our proof uses a simple mapping from spin systems to fermionic systems, as well as a convex optimization technique that reduces the problem of finding ground states to N representability.

Optimal control of light pulse storage and retrieval - Irina Novikova; Alexey V. Gorshkov; David F. Phillips; Anders S. Sorensen; Mikhail D. Lukin; Ronald L. Walsworth (Physical Review Letters, 2007)
We demonstrate experimentally a procedure to obtain the maximum efficiency for the storage and retrieval of light pulses in atomic media. The procedure uses time reversal to obtain optimal input signal pulse-shapes. Experimental results in warm Rb vapor are in good agreement with theoretical predictions and demonstrate a substantial improvement of efficiency. This optimization procedure is applicable to a wide range of systems.

Optimal quantum adversary lower bounds for ordered search - Andrew M. Childs; Troy Lee (2007)
The goal of the ordered search problem is to find a particular item in an ordered list of n items. Using the adversary method, Hoyer, Neerbek, and Shi proved a quantum lower bound for this problem of (1/pi) ln n + Theta(1). Here, we find the exact value of the best possible quantum adversary lower bound for a symmetrized version of ordered search (whose query complexity differs from that of the original problem by at most 1). Thus we show that the best lower bound for ordered search that can be proved by the adversary method is (1/pi) ln n + O(1). Furthermore, we show that this remains true for the generalized adversary method allowing negative weights.

Optimization of slow and stored light in atomic vapor - Novikova, I; Alexey V. Gorshkov; Phillips, D F; Xiao, Y; Klein, M; Walsworth, R L (Proc. SPIE, 2007)

Photon storage in Lambda-type optically dense atomic media. I. Cavity model - Alexey V. Gorshkov; Axel Andre; Mikhail D. Lukin; Anders S. Sorensen (Physical Review A, 2007)
In a recent paper [Gorshkov et al., Phys. Rev. Lett. 98, 123601 (2007)], we used a universal physical picture to optimize and demonstrate equivalence between a wide range of techniques for storage and retrieval of photon wave packets in Lambda-type atomic media in free space, including the adiabatic reduction of the photon group velocity, pulse-propagation control via off-resonant Raman techniques, and photon-echo-based techniques. In the present paper, we perform the same analysis for the cavity model. In particular, we show that the retrieval efficiency is equal to C/(1+C) independent of the retrieval technique, where C is the cooperativity parameter. We also derive the optimal strategy for storage and, in particular, demonstrate that at any detuning one can store, with the optimal efficiency of C/(1+C), any smooth input mode satisfying T C gamma >> 1 and a certain class of resonant input modes satisfying T C gamma ~ 1, where T is the duration of the input mode and 2 gamma is the transition linewidth. In the two subsequent papers of the series, we present the full analysis of the free-space model and discuss the effects of inhomogeneous broadening on photon storage.

Photon storage in Lambda-type optically dense atomic media. II. Free-space model - Alexey V. Gorshkov; Axel Andre; Mikhail D. Lukin; Anders S. Sorensen (Physical Review A, 2007)
In a recent paper [Gorshkov et al., Phys. Rev. Lett. 98, 123601 (2007)], we presented a universal physical picture for describing a wide range of techniques for storage and retrieval of photon wave packets in Lambda-type atomic media in free space, including the adiabatic reduction of the photon group velocity, pulse-propagation control via off-resonant Raman techniques, and photon-echo based techniques. This universal picture produced an optimal control strategy for photon storage and retrieval applicable to all approaches and yielded identical maximum efficiencies for all of them. In the present paper, we present the full details of this analysis as well some of its extensions, including the discussion of the effects of non-degeneracy of the two lower levels of the Lambda system. The analysis in the present paper is based on the intuition obtained from the study of photon storage in the cavity model in the preceding paper [Gorshkov et al., Phys. Rev. A 76, 033804 (2007)].

Photon storage in Lambda-type optically dense atomic media. III. Effects of inhomogeneous broadening - Alexey V. Gorshkov; Axel Andre; Mikhail D. Lukin; Anders S. Sorensen (Physical Review A, 2007)
In a recent paper [Gorshkov et al., Phys. Rev. Lett. 98, 123601 (2007)] and in the two preceding papers [Gorshkov et al., Phys. Rev. A 76, 033804 (2007); 76, 033805 (2007)], we used a universal physical picture to optimize and demonstrate equivalence between a wide range of techniques for storage and retrieval of photon wave packets in homogeneously broadened Lambda-type atomic media, including the adiabatic reduction of the photon group velocity, pulse-propagation control via off-resonant Raman techniques, and photon-echo-based techniques. In the present paper, we generalize this treatment to include inhomogeneous broadening. In particular, we consider the case of Doppler-broadened atoms and assume that there is a negligible difference between the Doppler shifts of the two optical transitions. In this situation, we show that, at high enough optical depth, all atoms contribute coherently to the storage process as if the medium were homogeneously broadened. We also discuss the effects of inhomogeneous broadening in solid state samples. In this context, we discuss the advantages and limitations of reversing the inhomogeneous broadening during the storage time, as well as suggest a way for achieving high efficiencies with a nonreversible inhomogeneous profile.

Practical scheme for quantum dense coding between three parties using microwave radiation in trapped ions - Wen-Xing Yang; Zhe-Xuan Gong (Journal of Physics B: Atomic, Molecular and Optical Physics, 2007)
We propose a practical scheme for implementing two-dimension quantum dense coding (QDC) between three parties through manipulating three ions confined in microtraps addressed by microwaves and assisted by a magnetic field gradient. The ions in our scheme are not required to be strictly cooled to the vibrational ground state because single-qubit and multi-qubit operations are made via Ising terms, in which the vibrational modes of the ions remain unchanged throughout the scheme, rendering our scheme robust to the heating of the ions. We also present the detailed steps and parameters for implementing the three-party QDC experimentally and show that the proposed scheme is within the current techniques of ion-trap experiments.

Quantum algorithms for hidden nonlinear structures - Andrew M. Childs; Leonard J. Schulman; Umesh V. Vazirani (2007)
Attempts to find new quantum algorithms that outperform classical computation have focused primarily on the nonabelian hidden subgroup problem, which generalizes the central problem solved by Shor's factoring algorithm. We suggest an alternative generalization, namely to problems of finding hidden nonlinear structures over finite fields. We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures.

Quantum Algorithms for Simon’s Problem over General Groups - Gorjan Alagic; Cristopher Moore; Alexander Russell (SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 2007)
Daniel Simon's 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (HSP) over Zn2 provided one of the first algebraic problems for which quantum computers are exponentially faster than their classical counterparts. In this paper, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution m = (m1,...,mn) ε Gn from an oracle f with the property that f(x) = f(x · y) ⇔ y ε {1, m}. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form Gn, where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. Although groups of the form Gn have a simple product structure, they share important representation-theoretic properties with the symmetric groups Sn, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called "standard method" requires highly entangled measurements on the tensor product of many coset states. Here we give quantum algorithms with time complexity 2O(√n log n) that recover hidden involutions m = (m1,..., mn) ε Gn where, as in Simon's problem, each mi is either the identity or the conjugate of a known element m and there is a character X of G for which X(m) = - X(1). Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the "missing harmonic" approach of Moore and Russell. These are the first nontrivial hidden subgroup algorithms for group families that require highly entangled multiregister Fourier sampling.

Quantum Computing and the Hunt for Hidden Symmetry - Gorjan Alagic; Alexander Russell (Bulletin of the EATCS, 2007)
In 1994, Peter Shor gave e cient quantum algorithms for factoring integers and extracting discrete logarithms [20]. If we believe that nature will permit us to faithfully implement our current model of quantum computation, then these algorithms dramatically contradict the Strong Church-Turing thesis. The e ect is heightened by the fact that these algorithms solve computational problems with long histories of attention by the computational and mathematical communities alike. In this article we discuss the branch of quantum algorithms research arising from attempts to generalize the core quantum algorithmic aspects of Shor's algorithms. Roughly, this can be viewed as the problem of generalizing algorithms of Simon [21] and Shor [20], which work over abelian groups, to general nonabelian groups. The article is meant to be self-contained, assuming no knowledge of quantum computing or the representation theory of nite groups. We begin in earnest in Section 2, describing the problem of symmetry nding : given a function f : G → S on a group G, this is the problem of determining {g ∈ G | ∀x, f(x) = f(gx)}, the set of symmetries of f . We switch gears in Section 3, giving a short introduction to the circuit model of quantum computation. The connection between these two sections is eventually established in Section 4, where we discuss the representation theory of nite groups and the quantum Fourier transform a unitary transformation speci cally tuned to the symmetries of the underlying group. Section 4.2 is devoted to Fourier

A quantum dot implementation of the quantum NAND algorithm - J. M. Taylor (2007)
We propose a physical implementation of the quantum NAND tree evaluation algorithm. Our approach, based on continuous time quantum walks, uses the wave interference of a single electron in a heirarchical set of tunnel coupled quantum dots. We find that the query complexity of the NAND tree evaluation does not suffer strongly from disorder and dephasing, nor is it directly limited by temperature or restricted dimensionality for 2-d structures. Finally, we suggest a potential application of this algorithm to the efficient determination of high-order correlation functions of complex quantum systems.

Relaxation, dephasing, and quantum control of electron spins in double quantum dots - J. M. Taylor; J. R. Petta; A. C. Johnson; A. Yacoby; C. M. Marcus; M. D. Lukin (Physical Review B, 2007)
Recent experiments have demonstrated quantum manipulation of two-electron spin states in double quantum dots using electrically controlled exchange interactions. Here, we present a detailed theory for electron spin dynamics in two-electron double dot systems that was used to guide these experiments and analyze experimental results. The theory treats both charge and spin degrees of freedom on an equal basis. Specifically, we analyze the relaxation and dephasing mechanisms that are relevant to experiments and discuss practical approaches for quantum control of two-electron system. We show that both charge and spin dephasing play important roles in the dynamics of the two-spin system, but neither represents a fundamental limit for electrical control of spin degrees of freedom in semiconductor quantum bits.

Signatures of incoherence in a quantum information processor - Michael K. Henry; Alexey V. Gorshkov; Yaakov S. Weinstein; Paola Cappellaro; Joseph Emerson; Nicolas Boulant; Jonathan S. Hodges; Chandrasekhar Ramanathan; Timothy F. Havel; Rudy Martinez; David G. Cory (2007)
Incoherent noise is manifest in measurements of expectation values when the underlying ensemble evolves under a classical distribution of unitary processes. While many incoherent processes appear decoherent, there are important differences. The distribution functions underlying incoherent processes are either static or slowly varying with respect to control operations and so the errors introduced by these distributions are refocusable. The observation and control of incoherence in small Hilbert spaces is well known. Here we explore incoherence during an entangling operation, such as is relevant in quantum information processing. As expected, it is more difficult to separate incoherence and decoherence over such processes. However, by studying the fidelity decay under a cyclic entangling map we are able to identify distinctive experimental signatures of incoherence. This result is demonstrated both through numerical simulations and experimentally in a three qubit nuclear magnetic resonance implementation.

Simple scheme for implementing the Deutsch-Jozsa algorithm in thermal cavity - Wen-Xing Yang; Zhe-Xuan Gong (Journal of Physics A: Mathematical and Theoretical, 2007)
We present a simple scheme to implement the Deutsch-Jozsa algorithm based on two-atom interaction in a thermal cavity. The photon-number-dependent parts in the evolution operator are canceled with the strong resonant classical field added. As a result, our scheme is immune to thermal field, and does not require the cavity to remain in the vacuum state throughout the procedure. Besides, large detuning between the atoms and the cavity is not necessary neither, leading to potential speed up of quantum operation. Finally, we show by numerical simulation that the proposed scheme is equal to demonstrate the Deutsch-Jozsa algorithm with high fidelity.

Two dogmas about quantum mechanics - Jeffrey Bub; Itamar Pitowsky (2007)
We argue that the intractable part of the measurement problem -- the 'big' measurement problem -- is a pseudo-problem that depends for its legitimacy on the acceptance of two dogmas. The first dogma is John Bell's assertion that measurement should never be introduced as a primitive process in a fundamental mechanical theory like classical or quantum mechanics, but should always be open to a complete analysis, in principle, of how the individual outcomes come about dynamically. The second dogma is the view that the quantum state has an ontological significance analogous to the significance of the classical state as the 'truthmaker' for propositions about the occurrence and non-occurrence of events, i.e., that the quantum state is a representation of physical reality. We show how both dogmas can be rejected in a realist information-theoretic interpretation of quantum mechanics as an alternative to the Everett interpretation. The Everettian, too, regards the 'big' measurement problem as a pseudo-problem, because the Everettian rejects the assumption that measurements have definite outcomes, in the sense that one particular outcome, as opposed to other possible outcomes, actually occurs in a quantum measurement process. By contrast with the Everettians, we accept that measurements have definite outcomes. By contrast with the Bohmians and the GRW 'collapse' theorists who add structure to the theory and propose dynamical solutions to the 'big' measurement problem, we take the problem to arise from the failure to see the significance of Hilbert space as a new kinematic framework for the physics of an indeterministic universe, in the sense that Hilbert space imposes kinematic (i.e., pre-dynamic) objective probabilistic constraints on correlations between events.

Universal Approach to Optimal Photon Storage in Atomic Media - Alexey V. Gorshkov; Axel Andre; Michael Fleischhauer; Anders S. Sorensen; Mikhail D. Lukin (Physical Review Letters, 2007)
We present a universal physical picture for describing storage and retrieval of photon wave packets in a Lambda-type atomic medium. This physical picture encompasses a variety of different approaches to pulse storage ranging from adiabatic reduction of the photon group velocity and pulse-propagation control via off-resonant Raman fields to photon-echo based techniques. Furthermore, we derive an optimal control strategy for storage and retrieval of a photon wave packet of any given shape. All these approaches, when optimized, yield identical maximum efficiencies, which only depend on the optical depth of the medium.

On Bounded Distance Decoding for General Lattices - Yi-Kai Liu; Vadim Lyubashevsky; Daniele Micciancio (Proc. RANDOM, 2006)
A central problem in the algorithmic study of lattices is the closest vector problem: given a lattice L represented by some basis, and a target point y⃗ , find the lattice point closest to y⃗ . Bounded Distance Decoding is a variant of this problem in which the target is guaranteed to be close to the lattice, relative to the minimum distance λ1(L) of the lattice. Specifically, in the α-Bounded Distance Decoding problem (α-BDD), we are given a lattice L and a vector y⃗ (within distance α⋅λ1(L) from the lattice), and we are asked to find a lattice point x⃗ ∈L within distance α⋅λ1(L) from the target. In coding theory, the lattice points correspond to codewords, and the target points correspond to lattice points being perturbed by noise vectors. Since in coding theory the lattice is usually fixed, we may “pre-process” it before receiving any targets, to make the subsequent decoding faster. This leads us to consider α-BDD with pre-processing. We show how a recent technique of Aharonov and Regev [2] can be used to solve α-BDD with pre-processing in polynomial time for α=O((logn)/n−−−−−−−√). This improves upon the previously best known algorithm due to Klein [13] which solved the problem for α=O(1/n). We also establish hardness results for α-BDD and α-BDD with pre-processing, as well as generalize our results to other ℓ p norms.

Cavity quantum electrodynamics with semiconductor double-dot molecules on a chip - J. M. Taylor; M. D. Lukin (2006)
We describe a coherent control technique for coupling electron spin states associated with semiconductor double-dot molecule to a microwave stripline resonator on a chip. We identify a novel regime of operation in which strong interaction between a molecule and a resonator can be achieved with minimal decoherence, reaching the so-called strong coupling regime of cavity QED. We describe potential applications of such a system, including low-noise coherent electrical control, fast QND measurements of spin states, and long-range spin coupling.

Consistency of Local Density Matrices is QMA-complete - Yi-Kai Liu (Proc. RANDOM, 2006)
Suppose we have an n-qubit system, and we are given a collection of local density matrices rho_1,...,rho_m, where each rho_i describes a subset C_i of the qubits. We say that the rho_i are ``consistent'' if there exists some global state sigma (on all n qubits) that matches each of the rho_i on the subsets C_i. This generalizes the classical notion of the consistency of marginal probability distributions. We show that deciding the consistency of local density matrices is QMA-complete (where QMA is the quantum analogue of NP). This gives an interesting example of a hard problem in QMA. Our proof is somewhat unusual: we give a Turing reduction from Local Hamiltonian, using a convex optimization algorithm by Bertsimas and Vempala, which is based on random sampling. Unlike in the classical case, simple mapping reductions do not seem to work here.

Effective error-suppression scheme for reversible quantum computer - Zhe-Xuan Gong (2006)
We construct a new error-suppression scheme that makes use of the adjoint of reversible quantum algorithms. For decoherence induced errors such as depolarization, it is presented that provided the depolarization error probability is less than 1, our scheme can exponentially reduce the final output error rate to zero using a number of cycles, and the output state can be coherently sent to another stage of quantum computation process. Besides, experimental set-ups via optical approach have been proposed using Grover's search algorithm as an example. Some further discussion on the benefits and limitations of the scheme is given in the end.

Effects of finite temperature on the Mott insulator state - Guido Pupillo; Carl J. Williams; Nikolay V. Prokof'ev (Physical Review A, 2006)
We investigate the effects of finite temperature on ultracold Bose atoms confined in an optical lattice plus a parabolic potential in the Mott insulator state. In particular, we analyze the temperature dependence of the density distribution of atomic pairs in the lattice, by means of exact Monte-Carlo simulations. We introduce a simple model that quantitatively accounts for the computed pair density distributions at low enough temperatures. We suggest that the temperature dependence of the atomic pair statistics may be used to estimate the system's temperature at energies of the order of the atoms' interaction energy.

Error correcting codes for adiabatic quantum computation - Stephen P. Jordan; Edward Farhi; Peter W. Shor (Physical Review A, 2006)
Recently, there has been growing interest in using adiabatic quantum computation as an architecture for experimentally realizable quantum computers. One of the reasons for this is the idea that the energy gap should provide some inherent resistance to noise. It is now known that universal quantum computation can be achieved adiabatically using 2-local Hamiltonians. The energy gap in these Hamiltonians scales as an inverse polynomial in the problem size. Here we present stabilizer codes which can be used to produce a constant energy gap against 1-local and 2-local noise. The corresponding fault-tolerant universal Hamiltonians are 4-local and 6-local respectively, which is the optimal result achievable within this framework.

Fault-tolerant Quantum Communication with Minimal Physical Requirements - L. Childress; J. M. Taylor; A. S. Sorensen; M. D. Lukin (Physical Review Letters, 2006)
We describe a novel protocol for a quantum repeater which enables long distance quantum communication through realistic, lossy photonic channels. Contrary to previous proposals, our protocol incorporates active purification of arbitrary errors at each step of the protocol using only two qubits at each repeater station. Because of these minimal physical requirements, the present protocol can be realized in simple physical systems such as solid-state single photon emitters. As an example, we show how nitrogen vacancy color centers in diamond can be used to implement the protocol, using the nuclear and electronic spin to form the two qubits.

Gibbs States and the Consistency of Local Density Matrices - Yi-Kai Liu (2006)
Suppose we have an n-qubit system, and we are given a collection of local density matrices rho_1,...,rho_m, where each rho_i describes some subset of the qubits. We say that rho_1,...,rho_m are "consistent" if there exists a global state sigma (on all n qubits) whose reduced density matrices match rho_1,...,rho_m. We prove the following result: if rho_1,...,rho_m are consistent with some state sigma > 0, then they are also consistent with a state sigma' of the form sigma' = (1/Z) exp(M_1+...+M_m), where each M_i is a Hermitian matrix acting on the same qubits as rho_i, and Z is a normalizing factor. (This is known as a Gibbs state.) Actually, we show a more general result, on the consistency of a set of expectation values <T_1>,...,<T_r>, where the observables T_1,...,T_r need not commute. This result was previously proved by Jaynes (1957) in the context of the maximum-entropy principle; here we provide a somewhat different proof, using properties of the partition function.

Mean-field treatment of the damping of the oscillations of a 1D Bose gas in an optical lattice - Julio Gea-Banacloche; Ana Maria Rey; Guido Pupillo; Carl J. Williams; Charles W. Clark (Physical Review A, 2006)
We present a theoretical treatment of the surprisingly large damping observed recently in one-dimensional Bose-Einstein atomic condensates in optical lattices. We show that time-dependent Hartree-Fock-Bogoliubov (HFB) calculations can describe qualitatively the main features of the damping observed over a range of lattice depths. We also derive a formula of the fluctuation-dissipation type for the damping, based on a picture in which the coherent motion of the condensate atoms is disrupted as they try to flow through the random local potential created by the irregular motion of noncondensate atoms. We expect this irregular motion to result from the well-known dynamical instability exhibited by the mean-field theory for these systems. When parameters for the characteristic strength and correlation times of the fluctuations, obtained from the HFB calculations, are substituted in the damping formula, we find very good agreement with the experimentally-observed damping, as long as the lattice is shallow enough for the fraction of atoms in the Mott insulator phase to be negligible. We also include, for completeness, the results of other calculations based on the Gutzwiller ansatz, which appear to work better for the deeper lattices.

Parallelism for Quantum Computation with Qudits - Dianne P. O'Leary; Gavin K. Brennen; Stephen S. Bullock (Physical Review A, 2006)
Robust quantum computation with d-level quantum systems (qudits) poses two requirements: fast, parallel quantum gates and high fidelity two-qudit gates. We first describe how to implement parallel single qudit operations. It is by now well known that any single-qudit unitary can be decomposed into a sequence of Givens rotations on two-dimensional subspaces of the qudit state space. Using a coupling graph to represent physically allowed couplings between pairs of qudit states, we then show that the logical depth of the parallel gate sequence is equal to the height of an associated tree. The implementation of a given unitary can then optimize the tradeoff between gate time and resources used. These ideas are illustrated for qudits encoded in the ground hyperfine states of the atomic alkalies $^{87}$Rb and $^{133}$Cs. Second, we provide a protocol for implementing parallelized non-local two-qudit gates using the assistance of entangled qubit pairs. Because the entangled qubits can be prepared non-deterministically, this offers the possibility of high fidelity two-qudit gates.

Pseudo-fermionization of 1-D bosons in optical lattices - Guido Pupillo; Ana Maria Rey; Carl J. Williams; Charles W. Clark (New Journal of Physics, 2006)
We present a model that generalizes the Bose-Fermi mapping for strongly correlated 1D bosons in an optical lattice, to cases in which the average number of atoms per site is larger than one. This model gives an accurate account of equilibrium properties of such systems, in parameter regimes relevant to current experiments. The application of this model to non-equilibrium phenomena is explored by a study of the dynamics of an atom cloud subject to a sudden displacement of the confining potential. Good agreement is found with results of recent experiments. The simplicity and intuitive appeal of this model make it attractive as a general tool for understanding bosonic systems in the strongly correlated regime.

Quantum computation from a quantum logical perspective - Jeffrey Bub (2006)
It is well-known that Shor's factorization algorithm, Simon's period-finding algorithm, and Deutsch's original XOR algorithm can all be formulated as solutions to a hidden subgroup problem. Here the salient features of the information-processing in the three algorithms are presented from a different perspective, in terms of the way in which the algorithms exploit the non-Boolean quantum logic represented by the projective geometry of Hilbert space. From this quantum logical perspective, the XOR algorithm appears directly as a special case of Simon's algorithm, and all three algorithms can be seen as exploiting the non-Boolean logic represented by the subspace structure of Hilbert space in a similar way. Essentially, a global property of a function (such as a period, or a disjunctive property) is encoded as a subspace in Hilbert space representing a quantum proposition, which can then be efficiently distinguished from alternative propositions, corresponding to alternative global properties, by a measurement (or sequence of measurements) that identifies the target proposition as the proposition represented by the subspace containing the final state produced by the algorithm.

Two-way quantum communication channels - Andrew M. Childs; Debbie W. Leung; Hoi-Kwong Lo (International Journal of Quantum Information, 2006)
We consider communication between two parties using a bipartite quantum operation, which constitutes the most general quantum mechanical model of two-party communication. We primarily focus on the simultaneous forward and backward communication of classical messages. For the case in which the two parties share unlimited prior entanglement, we give inner and outer bounds on the achievable rate region that generalize classical results due to Shannon. In particular, using a protocol of Bennett, Harrow, Leung, and Smolin, we give a one-shot expression in terms of the Holevo information for the entanglement-assisted one-way capacity of a two-way quantum channel. As applications, we rederive two known additivity results for one-way channel capacities: the entanglement-assisted capacity of a general one-way channel, and the unassisted capacity of an entanglement-breaking one-way channel.

Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem - Andrew M. Childs; Aram W. Harrow; Pawel Wocjan (2006)
Schur duality decomposes many copies of a quantum state into subspaces labeled by partitions, a decomposition with applications throughout quantum information theory. Here we consider applying Schur duality to the problem of distinguishing coset states in the standard approach to the hidden subgroup problem. We observe that simply measuring the partition (a procedure we call weak Schur sampling) provides very little information about the hidden subgroup. Furthermore, we show that under quite general assumptions, even a combination of weak Fourier sampling and weak Schur sampling fails to identify the hidden subgroup. We also prove tight bounds on how many coset states are required to solve the hidden subgroup problem by weak Schur sampling, and we relate this question to a quantum version of the collision problem.

Asymptotically Optimal Quantum Circuits for d-level Systems - Stephen S. Bullock; Dianne P. O'Leary; Gavin K. Brennen (Physical Review Letters, 2005)
As a qubit is a two-level quantum system whose state space is spanned by |0>, |1>, so a qudit is a d-level quantum system whose state space is spanned by |0>,...,|d-1>. Quantum computation has stimulated much recent interest in algorithms factoring unitary evolutions of an n-qubit state space into component two-particle unitary evolutions. In the absence of symmetry, Shende, Markov and Bullock use Sard's theorem to prove that at least C 4^n two-qubit unitary evolutions are required, while Vartiainen, Moettoenen, and Salomaa (VMS) use the QR matrix factorization and Gray codes in an optimal order construction involving two-particle evolutions. In this work, we note that Sard's theorem demands C d^{2n} two-qudit unitary evolutions to construct a generic (symmetry-less) n-qudit evolution. However, the VMS result applied to virtual-qubits only recovers optimal order in the case that d is a power of two. We further construct a QR decomposition for d-multi-level quantum logics, proving a sharp asymptotic of Theta(d^{2n}) two-qudit gates and thus closing the complexity question for all d-level systems (d finite.) Gray codes are not required, and the optimal Theta(d^{2n}) asymptotic also applies to gate libraries where two-qudit interactions are restricted by a choice of certain architectures.

Bragg Spectroscopy of ultracold atoms loaded in an optical lattice - Ana Maria Rey; P. Blair Blakie; Guido Pupillo; Carl J. Williams; Charles W. Clark (Physical Review A, 2005)
We study Bragg spectroscopy of ultra-cold atoms in one-dimensional optical lattices as a method for probing the excitation spectrum in the Mott insulator phase, in particular the one particle-hole excitation band. Within the framework of perturbation theory we obtain an analytical expression for the dynamic structure factor $S(q,ω)$ and use it to calculate the imparted energy which has shown to be a relevant observable in recent experiments. We test the accuracy of our approximations by comparing them with numerically exact solutions of the Bose-Hubbard model in restricted cases and establish the limits of validity of our linear response analysis. Finally we show that when the system is deep in the Mott insulator regime, its response to the Bragg perturbation is temperature dependent. We suggest that this dependence might be used as a tool to probe temperatures of order of the Mott gap.

Conditionalizing and commutativity: a note on Malley - Allen Stairs; Jeffrey Bub (2005)
This paper has been withdrawn.

Criteria for Exact Qudit Universality - Gavin K. Brennen; Dianne P. O'Leary; Stephen S. Bullock (Physical Review A, 2005)
We describe criteria for implementation of quantum computation in qudits. A qudit is a d-dimensional system whose Hilbert space is spanned by states |0>, |1>,... |d-1>. An important earlier work of Mathukrishnan and Stroud [1] describes how to exactly simulate an arbitrary unitary on multiple qudits using a 2d-1 parameter family of single qudit and two qudit gates. Their technique is based on the spectral decomposition of unitaries. Here we generalize this argument to show that exact universality follows given a discrete set of single qudit Hamiltonians and one two-qudit Hamiltonian. The technique is related to the QR-matrix decomposition of numerical linear algebra. We consider a generic physical system in which the single qudit Hamiltonians are a small collection of H_{jk}^x=\hbarΩ (|k><j|+|j><k|) and H_{jk}^y =\hbarΩ (i|k><j|-i|j><k|). A coupling graph results taking nodes 0,... d-1 and edges j<->k iff H_{jk}^{x,y} are allowed Hamiltonians. One qudit exact universality follows iff this graph is connected, and complete universality results if the two-qudit Hamiltonian H=-\hbarΩ |d-1,d-1><d-1,d-1| is also allowed. We discuss implementation in the eight dimensional ground electronic states of ^{87}Rb and construct an optimal gate sequence using Raman laser pulses.

Decoherence in Quantum Walks on the Hypercube - Gorjan Alagic; Alexander Russell (Phys. Rev. A, 2005)
We study a natural notion of decoherence on quantum random walks over the hypercube. We prove that in this model there is a decoherence threshold beneath which the essential properties of the hypercubic quantum walk, such as linear mixing times, are preserved. Beyond the threshold, we prove that the walks behave like their classical counterparts.

Dephasing of quantum bits by a quasi-static mesoscopic environment - J. M. Taylor; M. D. Lukin (2005)
We examine coherent processes in a two-state quantum system that is strongly coupled to a mesoscopic spin bath and weakly coupled to other environmental degrees of freedom. Our analysis is specifically aimed at understanding the quantum dynamics of solid-state quantum bits such as electron spins in semiconductor structures and superconducting islands. The role of mesoscopic degrees of freedom with long correlation times (local degrees of freedom such as nuclear spins and charge traps) in qubit-related dephasing is discussed in terms of a quasi-static bath. A mathemat- ical framework simultaneously describing coupling to the slow mesoscopic bath and a Markovian environment is developed and the dephasing and decoherence properties of the total system are investigated. The model is applied to several specific examples with direct relevance to current ex- periments. Comparisons to experiments suggests that such quasi-static degrees of freedom play an important role in current qubit implementations. Several methods of mitigating the bath-induced error are considered.

Designing Incentives for Peer-to-Peer Routing - Alberto Blanc; Yi-Kai Liu; Amin Vahda (Proc. INFOCOM, 2005)
In a peer-to-peer network, nodes are typically required to route packets for each other. This leads to a problem of “free-loaders,” nodes that use the network but refuse to route other nodes’ packets. In this paper we study ways of designing incentives to discourage free-loading. We model the interactions between nodes as a “random matching game,” and describe a simple reputation system that provides incentives for good behavior. Under certain assumptions, we obtain a stable subgame-perfect equilibrium. We use simulations to investigate the robustness of this scheme in the presence of noise and malicious nodes, and we examine some of the design trade-offs. We also evaluate some possible adversarial strategies, and discuss how our results might apply to real peer-to-peer systems.

Exponential iterated integrals and the relative solvable completion of the fundamental group of a manifold - Carl Miller (Topology, 2005)
<span style="color: rgb(46, 46, 46); font-family: Arial, Helvetica, "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", STIXGeneral, "Cambria Math", "Arial Unicode MS", sans-serif; font-size: 16px; word-spacing: -1.24453px;">We develop a class of integrals on a manifold <em style="font-size: 16px; font-family: Arial, Helvetica, "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", STIXGeneral, "Cambria Math", "Arial Unicode MS", sans-serif; color: rgb(46, 46, 46); word-spacing: -1.24453px;">M<span style="color: rgb(46, 46, 46); font-family: Arial, Helvetica, "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", STIXGeneral, "Cambria Math", "Arial Unicode MS", sans-serif; font-size: 16px; word-spacing: -1.24453px;"> called <em style="font-size: 16px; font-family: Arial, Helvetica, "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", STIXGeneral, "Cambria Math", "Arial Unicode MS", sans-serif; color: rgb(46, 46, 46); word-spacing: -1.24453px;">exponential iterated integrals <span style="color: rgb(46, 46, 46); font-family: Arial, Helvetica, "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", STIXGeneral, "Cambria Math", "Arial Unicode MS", sans-serif; font-size: 16px; word-spacing: -1.24453px;">, an extension of K.T. Chen's iterated integrals. It is shown that the matrix entries of any upper triangular representation of <span class="mathmlsrc" id="mmlsi1" style="font-size: 16px; font-family: Arial, Helvetica, "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", STIXGeneral, "Cambria Math", "Arial Unicode MS", sans-serif; position: relative; color: rgb(46, 46, 46); word-spacing: -1.24453px;"><span class="formulatext stixSupport mathImg" data-mathurl="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0040938304000795&_mathId=si1.gif&_user=111111111&_pii=S0040938304000795&_rdoc=1&_issn=00409383&md5=88bc114f2acabb7a8160b73fd55f4cfc" style="font-size: 1.1em; cursor: pointer; letter-spacing: 0.1em;" title="Click to view the MathML source">π1(M,x)<span style="color: rgb(46, 46, 46); font-family: Arial, Helvetica, "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", STIXGeneral, "Cambria Math", "Arial Unicode MS", sans-serif; font-size: 16px; word-spacing: -1.24453px;"> can be expressed via these new integrals. The ring of exponential iterated integrals contains the coordinate rings for a class of universal representations, called the <em style="font-size: 16px; font-family: Arial, Helvetica, "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", STIXGeneral, "Cambria Math", "Arial Unicode MS", sans-serif; color: rgb(46, 46, 46); word-spacing: -1.24453px;">relative solvable completions <span style="color: rgb(46, 46, 46); font-family: Arial, Helvetica, "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", STIXGeneral, "Cambria Math", "Arial Unicode MS", sans-serif; font-size: 16px; word-spacing: -1.24453px;"> of <span class="mathmlsrc" id="mmlsi2" style="font-size: 16px; font-family: Arial, Helvetica, "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", STIXGeneral, "Cambria Math", "Arial Unicode MS", sans-serif; position: relative; color: rgb(46, 46, 46); word-spacing: -1.24453px;"><span class="formulatext stixSupport mathImg" data-mathurl="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0040938304000795&_mathId=si2.gif&_user=111111111&_pii=S0040938304000795&_rdoc=1&_issn=00409383&md5=80ae4c4e1e15614f1931b796fbfe11ec" style="font-size: 1.1em; cursor: pointer; letter-spacing: 0.1em;" title="Click to view the MathML source">π1(M,x)<span style="color: rgb(46, 46, 46); font-family: Arial, Helvetica, "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", STIXGeneral, "Cambria Math", "Arial Unicode MS", sans-serif; font-size: 16px; word-spacing: -1.24453px;">. We consider exponential iterated integrals in the particular case of fibered knot complements, where the fundamental group always has a faithful relative solvable completion.

Fast quantum algorithm for numerical gradient estimation - Stephen P. Jordan (Physical Review Letters, 2005)
Given a blackbox for f, a smooth real scalar function of d real variables, one wants to estimate the gradient of f at a given point with n bits of precision. On a classical computer this requires a minimum of d+1 blackbox queries, whereas on a quantum computer it requires only one query regardless of d. The number of bits of precision to which f must be evaluated matches the classical requirement in the limit of large n.

Fault-tolerant quantum repeaters with minimal physical resources, and implementations based on single photon emitters - L. I. Childress; J. M. Taylor; A. S. Sorensen; M. D. Lukin (Physical Review A, 2005)
We analyze a novel method that uses fixed, minimal physical resources to achieve generation and nested purification of quantum entanglement for quantum communication over arbitrarily long distances, and discuss its implementation using realistic photon emitters and photonic channels. In this method, we use single photon emitters with two internal degrees of freedom formed by an electron spin and a nuclear spin to build intermediate nodes in a quantum channel. State-selective fluorescence is used for probabilistic entanglement generation between electron spins in adjacent nodes. We analyze in detail several approaches which are applicable to realistic, homogeneously broadened single photon emitters. Furthermore, the coupled electron and nuclear spins can be used to efficiently implement entanglement swapping and purification. We show that these techniques can be combined to generate high-fidelity entanglement over arbitrarily long distances. We present a specific protocol that functions in polynomial time and tolerates percent-level errors in entanglement fidelity and local operations. The scheme has the lowest requirements on physical resources of any current scheme for fully fault-tolerant quantum repeaters.

From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups - Dave Bacon; Andrew M. Childs; Wim van Dam (2005)
We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form (Z_p)^r X| Z_p for fixed r (including the Heisenberg group, r=2). In particular, our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.

Multichannel quantum-defect theory for slow atomic collisions - Bo Gao; Eite Tiesinga; Carl J. Williams; Paul S. Julienne (Physical Review A, 2005)
We present a multichannel quantum-defect theory for slow atomic collisions that takes advantages of the analytic solutions for the long-range potential, and both the energy and the angular-momentum insensitivities of the short-range parameters. The theory provides an accurate and complete account of scattering processes, including shape and Feshbach resonances, in terms of a few parameters such as the singlet and the triplet scattering lengths. As an example, results for $^{23}$Na-$^{23}$Na scattering are presented and compared close-coupling calculations.

Optimal measurements for the dihedral hidden subgroup problem - Dave Bacon; Andrew M. Childs; Wim van Dam (2005)
We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.

QR Factorizations Using a Restricted Set of Rotations - Dianne P. O'Leary; Stephen S. Bullock (Electronic Transactions on Numerical Analysis, 2005)
Any matrix A of dimension m × n (m ≥ n) can be reduced to upper triangular form by multiplying by a sequence of mn − n(n + 1)/2 appropriately chosen rotation matrices. In this work, we address the question of whether such a factorization exists when the set of allowed rotation planes is restricted. We introduce the rotation graph as a tool to devise elimination orderings in QR factorizations. Properties of this graph characterize sets of rotation planes that are sufficient (or sufficient under permutation) and identify rotation planes to add to complete a deficient set. We also devise a constructive way to determine all feasible rotation sequences for performing the QR factorization using a restricted set of rotation planes. We present applications to quantum circuit design and parallel QR factorization.

Quantum algorithm for a generalized hidden shift problem - Andrew M. Childs; Wim van Dam (2005)
Consider the following generalized hidden shift problem: given a function f on {0,...,M-1} x Z_N satisfying f(b,x)=f(b+1,x+s) for b=0,1,...,M-2, find the unknown shift s in Z_N. For M=N, this problem is an instance of the abelian hidden subgroup problem, which can be solved efficiently on a quantum computer, whereas for M=2, it is equivalent to the dihedral hidden subgroup problem, for which no efficient algorithm is known. For any fixed positive epsilon, we give an efficient (i.e., poly(log N)) quantum algorithm for this problem provided M > N^epsilon. The algorithm is based on the "pretty good measurement" and uses H. Lenstra's (classical) algorithm for integer programming as a subroutine.

On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems - Andrew M. Childs; Pawel Wocjan (2005)
We consider an approach to deciding isomorphism of rigid n-vertex graphs (and related isomorphism problems) by solving a nonabelian hidden shift problem on a quantum computer using the standard method. Such an approach is arguably more natural than viewing the problem as a hidden subgroup problem. We prove that the hidden shift approach to rigid graph isomorphism is hard in two senses. First, we prove that Omega(n) copies of the hidden shift states are necessary to solve the problem (whereas O(n log n) copies are sufficient). Second, we prove that if one is restricted to single-register measurements, an exponential number of hidden shift states are required.

Quantum information and computation - Jeffrey Bub (2005)
This article deals with theoretical developments in the subject of quantum information and quantum computation, and includes an overview of classical information and some relevant quantum mechanics. The discussion covers topics in quantum communication, quantum cryptography, and quantum computation, and concludes by considering whether a perspective in terms of quantum information sheds new light on the conceptual problems of quantum mechanics.