Nonequilibrium many-body steady states via Keldysh formalism - Mohammad F. Maghrebi; Alexey V. Gorshkov (Physical Review B, 2016)
Many-body systems with both coherent dynamics and dissipation constitute a rich class of models which are nevertheless much less explored than their dissipationless counterparts. The advent of numerous experimental platforms that simulate such dynamics poses an immediate challenge to systematically understand and classify these models. In particular, nontrivial many-body states emerge as steady states under non-equilibrium dynamics. While these states and their phase transitions have been studied extensively with mean field theory, the validity of the mean field approximation has not been systematically investigated. In this paper, we employ a field-theoretic approach based on the Keldysh formalism to study nonequilibrium phases and phase transitions in a variety of models. In all cases, a complete description via the Keldysh formalism indicates a partial or complete failure of the mean field analysis. Furthermore, we find that an effective temperature emerges as a result of dissipation, and the universal behavior including the dynamics near the steady state is generically described by a thermodynamic universality class.

Observation of Prethermalization in Long-Range Interacting Spin Chains - B. Neyenhuis; J. Smith; A. C. Lee; J. Zhang; P. Richerme; P. W. Hess; Z. -X. Gong; Alexey V. Gorshkov; C. Monroe (2016)
Statistical mechanics can predict thermal equilibrium states for most classical systems, but for an isolated quantum system there is no general understanding on how equilibrium states dynamically emerge from the microscopic Hamiltonian. For instance, quantum systems that are near-integrable usually fail to thermalize in an experimentally realistic time scale and, instead, relax to quasi-stationary prethermal states that can be described by statistical mechanics when approximately conserved quantities are appropriately included in a generalized Gibbs ensemble (GGE). Here we experimentally study the relaxation dynamics of a chain of up to 22 spins evolving under a long-range transverse field Ising Hamiltonian following a sudden quench. For sufficiently long-ranged interactions the system relaxes to a new type of prethermal state that retains a strong memory of the initial conditions. In this case, the prethermal state cannot be described by a GGE, but rather arises from an emergent double-well potential felt by the spin excitations. This result shows that prethermalization occurs in a significantly broader context than previously thought, and reveals new challenges for a generic understanding of the thermalization of quantum systems, particularly in the presence of long-range interactions.

Observation of Optomechanical Quantum Correlations at Room Temperature - T. P. Purdy; K. E. Grutter; K. Srinivasan; J. M. Taylor (2016)
By shining laser light through a nanomechanical beam, we measure the beam's thermally driven vibrations and perturb its motion with optical forces at a level dictated by the Heisenberg measurement-disturbance uncertainty relation. Such quantum backaction is typically difficult to observe at room temperature where the motion driven by optical quantum intensity fluctuations is many orders of magnitude smaller than the thermal motion. We demonstrate a cross-correlation technique to distinguish optically driven motion from thermally driven motion, observing this quantum backaction signature up to room temperature. While it is often difficult to absolutely calibrate optical detection, we use the scale of the quantum correlations, which is determined by fundamental constants, to gauge the size of thermal motion, demonstrating a path towards absolute thermometry with quantum mechanically calibrated ticks.

Optimal ancilla-free Clifford+T approximation of z-rotations - Neil J. Ross; Peter Selinger (Quantum Information and Computation, 2016)
We consider the problem of decomposing arbitrary single-qubit z-rotations into ancilla-free Clifford+T circuits, up to given epsilon. We present a new efficient algorithm for solving this problem optimally, i.e., for finding the shortest possible circuit whatsoever for the given problem instance. The algorithm requires a factoring oracle (such as a quantum computer). Even in the absence of a factoring oracle, the algorithm is still near-optimal: In this case, it finds a solution of T-count m + O(log(log(1/epsilon))), where m is the T-count of the second-to-optimal solution. In the typical case, this yields circuit decompositions of T-count 3log_2(1/epsilon) + O(log(log(1/epsilon))).

Optimal and asymptotically optimal NCT reversible circuits by the gate types - Dmitri Maslov (Quantum Information & Computation, 2016)
We report optimal and asymptotically optimal reversible circuits composed of NOT, CNOT, and Toffoli (NCT) gates, keeping the count by the subsets of the gate types used. This study fine tunes the circuit complexity figures for the realization of reversible functions via reversible NCT circuits. An important consequence is a result on the limitation of the use of the T-count quantum circuit metric popular in applications.

Optimal quantum algorithm for polynomial interpolation - Andrew M. Childs; Wim van Dam; Shih-Han Hung; Igor E. Shparlinski (43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 2016)
We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm's success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability.

Optimal state discrimination and unstructured search in nonlinear quantum mechanics - Andrew M. Childs; Joshua Young (Physical Review A, 2016)
Nonlinear variants of quantum mechanics can solve tasks that are impossible in standard quantum theory, such as perfectly distinguishing nonorthogonal states. Here we derive the optimal protocol for distinguishing two states of a qubit using the Gross-Pitaevskii equation, a model of nonlinear quantum mechanics that arises as an effective description of Bose-Einstein condensates. Using this protocol, we present an algorithm for unstructured search in the Gross-Pitaevskii model, obtaining an exponential improvement over a previous algorithm of Meyer and Wong. This result establishes a limitation on the effectiveness of the Gross-Pitaevskii approximation. More generally, we demonstrate similar behavior under a family of related nonlinearities, giving evidence that the ability to quickly discriminate nonorthogonal states and thereby solve unstructured search is a generic feature of nonlinear quantum mechanics.

Optimized tomography of continuous variable systems using excitation counting - Shen, Chao; Heeres, Reinier W.; Reinhold, Philip; Jiang, Luyao; Yi-Kai Liu; Schoelkopf, Robert J.; Jiang, Liang (Physical Review A, 2016)
We propose a systematic procedure to optimize quantum state tomography protocols for continuous variable systems based on excitation counting preceded by a displacement operation. Compared with conventional tomography based on Husimi or Wigner function measurement, the excitation counting approach can significantly reduce the number of measurement settings. We investigate both informational completeness and robustness, and provide a bound of reconstruction error involving the condition number of the sensing map. We also identify the measurement settings that optimize this error bound, and demonstrate that the improved reconstruction robustness can lead to an order-of-magnitude reduction of estimation error with given resources. This optimization procedure is general and can incorporate prior information of the unknown state to further simplify the protocol.

Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree - Cedric Yen-Yu Lin; Yechao Zhu (2016)
We consider constraint satisfaction problems of bounded degree, with a good notion of "typicality", e.g. the negation of the variables in each constraint is taken independently at random. Using the quantum approximate optimization algorithm (QAOA), we show that μ+Ω(1/D−−√) fraction of the constraints can be satisfied for typical instances, with the assignment efficiently produced by QAOA. We do so by showing that the averaged fraction of constraints being satisfied is μ+Ω(1/D−−√), with small variance. Here μ is the fraction that would be satisfied by a uniformly random assignment, and D is the number of constraints that each variable can appear. CSPs with typicality include Max-kXOR and Max-kSAT. We point out how it can be applied to determine the typical ground-state energy of some local Hamiltonians. We also give a similar result for instances with "no overlapping constraints", using the quantum algorithm. We sketch how the classical algorithm might achieve some partial result.

Photoassociation of spin polarized Chromium - Jahn Rührig; Tobias Bäuerle; Paul S. Julienne; Eite Tiesinga; Tilman Pfau (Physical Review A, 2016)
We report the homonuclear photoassociation (PA) of ultracold 52Cr atoms in an optical dipole trap. This constitutes the first measurement of PA in an element with total electron spin S~>1. Although Cr, with its 7S3 ground and 7P4,3,2 excited states, is expected to have a complicated PA spectrum we show that a spin polarized cloud exhibits a remarkably simple PA spectrum when circularly polarized light is applied. Over a scan range of 20 GHz below the 7P3 asymptote we observe two distinct vibrational series each following a LeRoy-Bernstein law for a C3/R3 potential with excellent agreement. We determine the C3 coefficients of the Hund's case c) relativistic adiabatic potentials to be -1.83±0.02 a.u. and -1.46±0.01a.u.. Theoretical non-rotating Movre-Pichler calculations enable a first assignment of the series to Ω=6u and 5g potential energy curves. In a different set of experiments we disturb the selection rules by a transverse magnetic field which leads to additional PA series.

Practical Approximation of Single-Qubit Unitaries by Single-Qubit Quantum Clifford and T Circuits - Vadym Kliuchnikov; Dmitri Maslov; Michele Mosca (IEEE Transactions on Computers, 2016)
We present an algorithm, along with its implementation that finds T-optimal approximations of single-qubit Z-rotations using quantum circuits consisting of Clifford and T gates. Our algorithm is capable of handling errors in approximation down to size 10-15, resulting in the optimal single-qubit circuit designs required for implementation of scalable quantum algorithms. Our implementation along with the experimental results are available in the public domain.

Pure-state tomography with the expectation value of Pauli operators - Xian Ma; Tyler Jackson; Hui Zhou; Jianxin Chen; Dawei Lu; Michael D. Mazurek; Kent A.G. Fisher; Xinhua Peng; David Kribs; Kevin J. Resch; Zhengfeng Ji; Bei Zeng; et al. (Physical Review A, 2016)
We examine the problem of finding the minimum number of Pauli measurements needed to uniquely determine an arbitrary n-qubit pure state among all quantum states. We show that only 11 Pauli measurements are needed to determine an arbitrary two-qubit pure state compared to the full quantum state tomography with 16 measurements, and only 31 Pauli measurements are needed to determine an arbitrary three-qubit pure state compared to the full quantum state tomography with 64 measurements. We demonstrate that our protocol is robust under depolarizing error with simulated random pure states. We experimentally test the protocol on two- and three-qubit systems with nuclear magnetic resonance techniques. We show that the pure state tomography protocol saves us a number of measurements without considerable loss of fidelity. We compare our protocol with same-size sets of randomly selected Pauli operators and find that our selected set of Pauli measurements significantly outperforms those random sampling sets. As a direct application, our scheme can also be used to reduce the number of settings needed for pure-state tomography in quantum optical systems.

Quantifying the coherence of pure quantum states - Jianxin Chen; Nathaniel Johnston; Chi-Kwong Li; Sarah Plosker (Physical Review A, 2016)
In recent years, several measures have been proposed for characterizing the coherence of a given quantum state. We derive several results that illuminate how these measures behave when restricted to pure states. Notably, we present an explicit characterization of the closest incoherent state to a given pure state under the trace distance measure of coherence, and we affirm a recent conjecture that the ℓ1 measure of coherence of a pure state is never smaller than its relative entropy of coherence. We then use our result to show that the states maximizing the trace distance of coherence are exactly the maximally coherent states, and we derive a new inequality relating the negativity and distillable entanglement of pure states.

Quantum Merlin Arthur with Exponentially Small Gap - Bill Fefferman; Cedric Yen-Yu Lin (2016)
We study the complexity of QMA proof systems with inverse exponentially small promise gap. We show that this class can be exactly characterized by PSPACE, the class of problems solvable with a polynomial amount of memory. As applications we show that a "precise" version of the Local Hamiltonian problem is PSPACE-complete, and give a provable setting in which the ability to prepare PEPS states is not as powerful as the ability to prepare the ground state of general Local Hamiltonians.

A Quantum Model for an Entropic Spring - Chiao-Hsuan Wang; J. M. Taylor (Physical Review B, 2016)
Motivated by understanding the emergence of thermodynamic restoring forces and oscillations, we develop a quantum-mechanical model of a bath of spins coupled to the elasticity of a material. We show our model reproduces the behavior of a variety of entropic springs while enabling investigation of non-equilibrium resonator states in the quantum domain. We find our model emerges naturally in disordered elastic media such as glasses, and is an additional, expected effect in systems with anomalous specific heat and 1/f noise at low temperatures due to two-level systems that fluctuate.

On Quantum Obfuscation - Gorjan Alagic; Bill Fefferman (2016)
Encryption of data is fundamental to secure communication in the modern world. Beyond encryption of data lies obfuscation, i.e., encryption of functionality. It is well-known that the most powerful means of obfuscating classical programs, so-called ``black-box obfuscation',' is provably impossible [Barak et al '12]. However, several recent results have yielded candidate schemes that satisfy a definition weaker than black-box, and yet still have numerous applications. In this work, we initialize the rigorous study of obfuscating programs via quantum-mechanical means. We define notions of quantum obfuscation which encompass several natural variants. The input to the obfuscator can describe classical or quantum functionality, and the output can be a circuit description or a quantum state. The obfuscator can also satisfy one of a number of obfuscation conditions: black-box, information-theoretic black-box, indistinguishability, and best possible; the last two conditions come in three variants: perfect, statistical, and computational. We discuss many applications, including CPA-secure quantum encryption, quantum fully-homomorphic encryption, and public-key quantum money. We then prove several impossibility results, extending a number of foundational papers on classical obfuscation to the quantum setting. We prove that quantum black-box obfuscation is impossible in a setting where adversaries can possess more than one output of the obfuscator. In particular, generic transformation of quantum circuits into black-box-obfuscated quantum circuits is impossible. We also show that statistical indistinguishability obfuscation is impossible, up to an unlikely complexity-theoretic collapse. Our proofs involve a new tool: chosen-ciphertext-secure encryption of quantum data, which was recently shown to be possible assuming quantum-secure one-way functions exist [Alagic et al '16].

A Quantum Version of Schöning's Algorithm Applied to Quantum 2-SAT - Edward Farhi; Shelby Kimmel; Kristan Temme (Quantum Information and Computation, 2016)
We study a quantum algorithm that consists of a simple quantum Markov process, and we analyze its behavior on restricted versions of Quantum 2-SAT. We prove that the algorithm solves this decision problem with high probability for n qubits, L clauses, and promise gap c in time O(n^2 L^2 c^{-2}). If the Hamiltonian is additionally polynomially gapped, our algorithm efficiently produces a state that has high overlap with the satisfying subspace. The Markov process we study is a quantum analogue of Sch\"oning's probabilistic algorithm for k-SAT.

Quantum-Enhanced Machine Learning - Dunjko, Vedran; J. M. Taylor; Briegel, Hans J. (Physical Review Letters, 2016)
The emerging field of quantum machine learning has the potential to substantially aid in the problems and scope of artificial intelligence. This is only enhanced by recent successes in the field of classical machine learning. In this work we propose an approach for the systematic treatment of machine learning, from the perspective of quantum information. Our approach is general and covers all three main branches of machine learning: supervised, unsupervised, and reinforcement learning. While quantum improvements in supervised and unsupervised learning have been reported, reinforcement learning has received much less attention. Within our approach, we tackle the problem of quantum enhancements in reinforcement learning as well, and propose a systematic scheme for providing improvements. As an example, we show that quadratic improvements in learning efficiency, and exponential improvements in performance over limited time periods, can be obtained for a broad class of learning problems.

A quasi-mode theory of chiral phonons - Xunnong Xu; Seunghwi Kim; Gaurav Bahl; J. M. Taylor (2016)
The coherence properties of mechanical resonators are often limited by multiple unavoidable forms of loss -- including phonon-phonon and phonon-defect scattering -- which result in the scattering of sound into other resonant modes and into the phonon bath. Dynamic suppression of this scattering loss can lift constraints on device structure and can improve tolerance to defects in the material, even after fabrication. Inspired by recent experiments, here we introduce a model of phonon losses resulting from disorder in a whispering gallery mode resonator with acousto-optical coupling between optical and mechanical modes. We show that a typical elastic scattering mechanism of high quality factor (Q) mechanical modes flips the direction of phonon propagation via high-angle scattering, leading to damping into modes with the opposite parity. When the optical mode overlaps co-propagating high-Q and bulk mechanical modes, the addition of laser cooling via sideband-resolved damping of the mechanical mode of a chosen parity also damps and modifies the response of the bulk modes of the same parity. This, in turn, simultaneously improves the quality factor and reduces the thermal load of the counter-propagating high-Q modes, leading to the dynamical creation of a cold phononic shield. We compare our theoretical results to the recent experiments of Kim et al., and find quantitative agreement with our theory.

Realizing Exactly Solvable SU(N) Magnets with Thermal Atoms - Michael E. Beverland; Gorjan Alagic; Michael J. Martin; Andrew P. Koller; Ana M. Rey; Alexey V. Gorshkov (Physical Review A, 2016)
We show that n thermal fermionic alkaline-earth-metal atoms in a flat-bottom trap allow one to robustly implement a spin model displaying two symmetries: the Sn symmetry that permutes atoms occupying different vibrational levels of the trap and the SU(N) symmetry associated with N nuclear spin states. The symmetries make the model exactly solvable, which, in turn, enables the analytic study of dynamical processes such as spin diffusion in this SU(N) system. We also show how to use this system to generate entangled states that allow for Heisenberg-limited metrology. This highly symmetric spin model should be experimentally realizable even when the vibrational levels are occupied according to a high-temperature thermal or an arbitrary nonthermal distribution.

Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices - Carl Miller; Yaoyun Shi (Journal of the ACM, 2016)
Randomness is a vital resource for modern-day information processing, especially for cryptography. A wide range of applications critically rely on abundant, high-quality random numbers generated securely. Here, we show how to expand a random seed at an exponential rate without trusting the underlying quantum devices. Our approach is secure against the most general adversaries, and has the following new features: cryptographic level of security, tolerating a constant level of imprecision in devices, requiring only unit size quantum memory (for each device component) in an honest implementation, and allowing a large natural class of constructions for the protocol. In conjunction with a recent work by Chung et al. [2014], it also leads to robust unbounded expansion using just 2 multipart devices. When adapted for distributing cryptographic keys, our method achieves, for the first time, exponential expansion combined with cryptographic security and noise tolerance. The proof proceeds by showing that the Rényi divergence of the outputs of the protocol (for a specific bounding operator) decreases linearly as the protocol iterates. At the heart of the proof are a new uncertainty principle on quantum measurements and a method for simulating trusted measurements with untrusted devices.
Keywords: key distribution; nonlocal games; privacy; quantum cryptography; random-number generation; untrusted device

Self-organization of atoms coupled to a chiral reservoir - Zachary Eldredge; Pablo Solano; Darrick Chang; Alexey V. Gorshkov (Physical Review A, 2016)
Tightly confined modes of light, as in optical nanofibers or photonic crystal waveguides, can lead to large optical coupling in atomic systems, which mediates long-range interactions between atoms. These one-dimensional systems can naturally possess couplings that are asymmetric between modes propagating in different directions. Strong long-range interaction among atoms via these modes can drive them to a self-organized periodic distribution. In this paper, we examine the self-organizing behavior of atoms in one dimension coupled to a chiral reservoir. We determine the solution to the equations of motion in different parameter regimes, relative to both the detuning of the pump laser that initializes the atomic dipole-dipole interactions and the degree of reservoir chirality. In addition, we calculate possible experimental signatures such as reflectivity from self-organized atoms and motional sidebands.

Serialized Quantum Error Correction Protocol for High-Bandwidth Quantum Repeaters - Andrew N. Glaudell; Edo Waks; J. M. Taylor (New Journal of Physics, 2016)
Advances in single photon creation, transmission, and detection suggest that sending quantum information over optical fibers may have losses low enough to be correctable using a quantum error correcting code. Such error-corrected communication is equivalent to a novel quantum repeater scheme, but crucial questions regarding implementation and system requirements remain open. Here we show that long range entangled bit generation with rates approaching $10^8$ ebits/s may be possible using a completely serialized protocol, in which photons are generated, entangled, and error corrected via sequential, one-way interactions with a minimal number of matter qubits. Provided loss and error rates of the required elements are below the threshold for quantum error correction, this scheme demonstrates improved performance over transmission of single photons. We find improvement in ebit rates at large distances using this serial protocol and various quantum error correcting codes.

Sisyphus Thermalization of Photons in a Cavity-Coupled Double Quantum Dot - Michael Gullans; J. Stehlik; Y. -Y. Liu; J. R. Petta; J. M. Taylor (Physical Review Letters, 2016)
A strongly driven quantum system, coupled to a thermalizing bath, generically evolves into a highly non-thermal state as the external drive competes with the equilibrating force of the bath. We demonstrate a notable exception to this picture for a microwave resonator interacting with a periodically driven double quantum dot (DQD). In the limit of strong driving and long times, we show that the resonator field can be driven into a thermal state with a chemical potential given by a harmonic of the drive frequency. Such tunable chemical potentials are achievable with current devices and would have broad utility for quantum simulation in circuit quantum electrodynamics. As an example, we show how several DQDs embedded in an array of microwave resonators can induce a phase transition to a Bose-Einstein condensate of light.

Space-Efficient Error Reduction for Unitary Quantum Computations - Bill Fefferman; Hirotada Kobayashi; Cedric Yen-Yu Lin; Tomoyuki Morimae; Harumichi Nishimura (43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 2016)
This paper develops general space-efficient methods for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness <span class="MathJax" id="MathJax-Element-1-Frame" style="display: inline; line-height: normal; font-size: 14.4px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: rgb(0, 0, 0); font-family: "Lucida Grande", helvetica, arial, verdana, sans-serif;" tabindex="0"><span class="math" id="MathJax-Span-1" role="math" style="transition: none; display: inline-block; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; width: 0.524em;"><span style="transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(1.276em 1000.41em 2.086em -999.997em); top: -1.907em; left: 0.003em;"><span class="mi" id="MathJax-Span-3" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">c and soundness<span class="MathJax" id="MathJax-Element-2-Frame" style="display: inline; line-height: normal; font-size: 14.4px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: rgb(0, 0, 0); font-family: "Lucida Grande", helvetica, arial, verdana, sans-serif;" tabindex="0"><span class="math" id="MathJax-Span-4" role="math" style="transition: none; display: inline-block; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; width: 0.582em;"><span style="transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(1.276em 1000.41em 2.086em -999.997em); top: -1.907em; left: 0.003em;"><span class="mi" id="MathJax-Span-6" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">s, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most <span class="MathJax" id="MathJax-Element-3-Frame" style="display: inline; line-height: normal; font-size: 14.4px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: rgb(0, 0, 0); font-family: "Lucida Grande", helvetica, arial, verdana, sans-serif;" tabindex="0"><span class="math" id="MathJax-Span-7" role="math" style="transition: none; display: inline-block; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; width: 1.855em;">2<span class="mo" id="MathJax-Span-13" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-size: 12.217px; font-family: MathJax_Main;">−<span class="mi" id="MathJax-Span-14" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-size: 12.217px; font-family: MathJax_Math-italic;">p, the most space-efficient method known requires extra workspace of <span class="MathJax" id="MathJax-Element-4-Frame" style="display: inline; line-height: normal; font-size: 14.4px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: rgb(0, 0, 0); font-family: "Lucida Grande", helvetica, arial, verdana, sans-serif;" tabindex="0"><span class="math" id="MathJax-Span-15" role="math" style="transition: none; display: inline-block; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; width: 6.484em;"><span style="transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(1.218em 1005.21em 2.781em -999.997em); top: -2.254em; left: 0.003em;"><span class="mi" id="MathJax-Span-19" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">O(<span class="mi" id="MathJax-Span-23" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">p<span class="mi" id="MathJax-Span-24" style="transition: none; display: inline; position: static; border: 0px; padding: 0px 0px 0px 0.177em; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">log<span style="transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px 0px 0px -0.171em; vertical-align: 0px; line-height: normal; clip: rect(3.359em 1000.29em 4.17em -999.997em); top: -4.395em; left: 11.5156px;"><span class="mn" id="MathJax-Span-27" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-size: 12.217px; font-family: MathJax_Main;">1<span style="transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px 0px 0px -0.576em; vertical-align: 0px; line-height: normal; clip: rect(3.533em 1001.16em 4.17em -999.997em); top: -3.643em; left: 11.5156px;"><span class="mi" id="MathJax-Span-29" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-size: 12.217px; font-family: MathJax_Math-italic;">c<span class="mo" id="MathJax-Span-30" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-size: 12.217px; font-family: MathJax_Main;">−<span class="mi" id="MathJax-Span-31" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-size: 12.217px; font-family: MathJax_Math-italic;">s) qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper presents error-reduction methods for unitary quantum computations (i.e., computations without intermediate measurements) that require extra workspace of just <span class="MathJax" id="MathJax-Element-5-Frame" style="display: inline; line-height: normal; font-size: 14.4px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: rgb(0, 0, 0); font-family: "Lucida Grande", helvetica, arial, verdana, sans-serif;" tabindex="0"><span class="math" id="MathJax-Span-35" role="math" style="transition: none; display: inline-block; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; width: 5.674em;"><span style="transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(1.218em 1004.52em 2.781em -999.997em); top: -2.254em; left: 0.003em;"><span class="mi" id="MathJax-Span-39" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">O(log<span style="transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px 0px 0px -0.171em; vertical-align: 0px; line-height: normal; clip: rect(3.533em 1000.35em 4.285em -999.997em); top: -4.569em; left: 11.5156px;"><span class="mi" id="MathJax-Span-46" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-size: 12.217px; font-family: MathJax_Math-italic;">p<span style="transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px 0px 0px -0.576em; vertical-align: 0px; line-height: normal; clip: rect(3.533em 1001.16em 4.17em -999.997em); top: -3.643em; left: 11.5156px;"><span class="mi" id="MathJax-Span-48" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-size: 12.217px; font-family: MathJax_Math-italic;">c<span class="mo" id="MathJax-Span-49" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-size: 12.217px; font-family: MathJax_Main;">−<span class="mi" id="MathJax-Span-50" style="transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-size: 12.217px; font-family: MathJax_Math-italic;">s) qubits. This in particular gives the first methods of strong amplification for logarithmic-space unitary quantum computations with two-sided bounded error. This also leads to a number of consequences in complexity theory, such as the uselessness of quantum witnesses in bounded-error logarithmic-space unitary quantum computations, the PSPACE upper bound for QMA with exponentially-small completeness-soundness gap, and strong amplification for matchgate computations.

Steady-state superradiance with Rydberg polaritons - Zhe-Xuan Gong; Minghui Xu; Michael Foss-Feig; James K. Thompson; Ana Maria Rey; Murray Holland; Alexey V. Gorshkov (arXiv:1611.00797, 2016)
A steady-state superradiant laser can be used to generate ultranarrow-linewidth light, and thus has important applications in the fields of quantum information and precision metrology. However, the light produced by such a laser is still essentially classical. Here, we show that the introduction of a Rydberg medium into a cavity containing atoms with a narrow optical transition can lead to the steady-state superradiant emission of ultranarrow-linewidth <span class="MathJax" id="MathJax-Element-1-Frame" style="display: inline; line-height: normal; font-size: 14.4px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; font-family: "Lucida Grande", helvetica, arial, verdana, sans-serif;" tabindex="0">nonclassical light. The cavity nonlinearity induced by the Rydberg medium strongly modifies the superradiance threshold, and leads to a Mollow triplet in the cavity output spectrum<span class="MathJax" id="MathJax-Element-2-Frame" style="display: inline; line-height: normal; font-size: 14.4px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; font-family: "Lucida Grande", helvetica, arial, verdana, sans-serif;" tabindex="0">−this behavior can be understood as an unusual analogue of resonance fluorescence. The cavity output spectrum has an extremely sharp central peak, with a linewidth that can be far narrower than that of a classical superradiant laser. This unprecedented spectral sharpness, together with the nonclassical nature of the light, could lead to new applications in which spectrally pure <span class="MathJax" id="MathJax-Element-3-Frame" style="display: inline; line-height: normal; font-size: 14.4px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; font-family: "Lucida Grande", helvetica, arial, verdana, sans-serif;" tabindex="0">quantum light is desired.

Subwavelength-width optical tunnel junctions for ultracold atoms - Jendrzejewski, F.; Eckel, S.; Tiecke, T. G.; G. Juzeliūnas; Campbell, G. K.; Jiang, Liang; Alexey V. Gorshkov (Physical Review A, 2016)
We propose a method for creating far-field optical barrier potentials for ultracold atoms with widths that are narrower than the diffraction limit and can approach tens of nanometers. The reduced widths stem from the nonlinear atomic response to control fields that create spatially varying dark resonances. The subwavelength barrier is the result of the geometric scalar potential experienced by an atom prepared in such a spatially varying dark state. The performance of this technique, as well as its applications to the study of many-body physics and to the implementation of quantum-information protocols with ultracold atoms, are discussed, with a focus on the implementation of tunnel junctions.

Sudden-quench dynamics of Bardeen-Cooper-Schrieffer states in deep optical lattices - Marlon Nuske; L. Mathey; Eite Tiesinga (Physical Review A, 2016)
We determine the exact time evolution of an initial Bardeen-Cooper-Schrieffer (BCS) state of ultra-cold atoms in a hexagonal optical lattice. The dynamical evolution is triggered by ramping the lattice potential up, such that the interaction strength Uf is much larger than the hopping amplitude Jf. The quench initiates collective oscillations with frequency |Uf|/(2π) in the momentum occupation numbers and imprints an oscillating phase with the same frequency on the order parameter Δ. The latter is not reproduced by treating the time evolution in mean-field theory. The momentum density-density or noise correlation functions oscillate at frequency |Uf|/2π as well as its second harmonic. For a very deep lattice, with negligible tunneling energy, the oscillations of momentum occupation numbers are undamped. Non-zero tunneling after the quench leads to dephasing of the different momentum modes and a subsequent damping of the oscillations. This occurs even for a finite-temperature initial BCS state, but not for a non-interacting Fermi gas. We therefore propose to use this dephasing to detect a BCS state. Finally, we predict that the noise correlation functions in a honeycomb lattice will develop strong anti-correlations near the Dirac point.

Tomography is necessary for universal entanglement detection with single-copy observables - Dawei Lu; Tao Xin; Nengkun Yu; Zhengfeng Ji; Jianxin Chen; Guilu Long; Jonathan Baugh; Xinhua Peng; Bei Zeng; Raymond Laflamme (Physical Review Letters, 2016)
Entanglement, one of the central mysteries of quantum mechanics, plays an essential role in numerous applications of quantum information theory. A natural question of both theoretical and experimental importance is whether universal entanglement detection is possible without full state tomography. In this work, we prove a no-go theorem that rules out this possibility for any non-adaptive schemes that employ single-copy measurements only. We also examine in detail a previously implemented experiment, which claimed to detect entanglement of two-qubit states via adaptive single-copy measurements without full state tomography. By performing the experiment and analyzing the data, we demonstrate that the information gathered is indeed sufficient to reconstruct the state. These results reveal a fundamental limit for single-copy measurements in entanglement detection, and provides a general framework to study the detection of other interesting properties of quantum states, such as the positivity of partial transpose and the k-symmetric extendibility.

Topological phases with long-range interactions - Zhe-Xuan Gong; Mohammad F. Maghrebi; Anzi Hu; Michael L. Wall; Michael Foss-Feig; Alexey V. Gorshkov (Physical Review B, 2016)
Topological phases of matter are primarily studied in quantum many-body systems with short-range interactions. Whether various topological phases can survive in the presence of long-range interactions, however, is largely unknown. Here we show that a paradigmatic example of a symmetry-protected topological phase, the Haldane phase of an antiferromagnetic spin-1 chain, surprisingly remains intact in the presence of arbitrarily slowly decaying power-law interactions. The influence of long-range interactions on the topological order is largely quantitative, and we expect similar results for more general systems. Our conclusions are based on large-scale matrix-product-state simulations and two complementary effective-field-theory calculations. The striking agreement between the numerical and analytical results rules out finite-size effects. The topological phase considered here should be experimentally observable in a recently developed trapped-ion quantum simulator.

Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester - Cedric Yen-Yu Lin; Han-Hsuan Lin (Theory of Computing, 2016)
Inspired by the Elitzur-Vaidman bomb testing problem [arXiv:hep-th/9305002], we introduce a new query complexity model, which we call bomb query complexity $B(f)$. We investigate its relationship with the usual quantum query complexity $Q(f)$, and show that $B(f)=Θ(Q(f)^2)$. This result gives a new method to upper bound the quantum query complexity: we give a method of finding bomb query algorithms from classical algorithms, which then provide nonconstructive upper bounds on $Q(f)=Θ(\sqrt{B(f)})$. We subsequently were able to give explicit quantum algorithms matching our upper bound method. We apply this method on the single-source shortest paths problem on unweighted graphs, obtaining an algorithm with $O(n^{1.5})$ quantum query complexity, improving the best known algorithm of $O(n^{1.5}\sqrt{\log n})$ [arXiv:quant-ph/0606127]. Applying this method to the maximum bipartite matching problem gives an $O(n^{1.75})$ algorithm, improving the best known trivial $O(n^2)$ upper bound.

Wannier functions using a discrete variable representation for optical lattices - Saurabh Paul; Eite Tiesinga (Physical Review A, 2016)
We propose a numerical method using the discrete variable representation (DVR) for constructing real-valued Wannier functions localized in a unit cell for both symmetric and asymmetric periodic potentials. We apply these results to finding Wannier functions for ultracold atoms trapped in laser-generated optical lattices. Following S. Kivelson [<a href="http://dx.doi.org/10.1103/PhysRevB.26.4269" style="box-sizing: border-box; background-image: initial; background-position: 0px 0px; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; color: rgb(50, 148, 216); line-height: inherit; text-decoration: none; font-family: "Helvetica Neue", Helvetica, Roboto, Arial, sans-serif; font-size: 14px;">Phys. Rev. B 26, 4269 (1982)], for a symmetric lattice with inversion symmetry, we construct Wannier functions as eigenstates of the position operators <span class="MathJax" id="MathJax-Element-1-Frame" style="box-sizing: border-box; display: inline; font-style: inherit; font-weight: inherit; line-height: normal; 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; border: 0px; padding: 0px; margin: 0px; font-family: inherit;" tabindex="0"><span class="math" id="MathJax-Span-1" role="math" style="box-sizing: border-box; transition: none; display: inline-block; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; width: 2.081em;"><span style="box-sizing: border-box; transition: none; display: inline-block; position: relative; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; width: 1.886em; height: 0px; font-size: 15.4px;"><span style="box-sizing: border-box; transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(1.172em 1001.82em 2.536em -999.997em); top: -2.14em; left: 0.003em;"><span style="box-sizing: border-box; transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(3.38em 1000.52em 4.224em -999.997em); top: -4.023em; left: 0.003em;"><span class="mi" id="MathJax-Span-4" style="box-sizing: border-box; transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">x<span style="box-sizing: border-box; transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(3.12em 1000.59em 3.705em -999.997em); top: -4.088em; left: 0.068em;">ˆ<span class="mo" id="MathJax-Span-6" style="box-sizing: border-box; transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;">,<span class="mo" id="MathJax-Span-7" style="box-sizing: border-box; transition: none; display: inline; position: static; border: 0px; padding: 0px 0px 0px 0.198em; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Main;"> <span style="box-sizing: border-box; transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(3.38em 1000.52em 4.419em -999.997em); top: -4.023em; left: 0.003em;"><span class="mi" id="MathJax-Span-9" style="box-sizing: border-box; transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">y<span style="box-sizing: border-box; transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(3.12em 1000.39em 3.705em -999.997em); top: -4.088em; left: 0.068em;">ˆ, and <span class="MathJax" id="MathJax-Element-2-Frame" style="box-sizing: border-box; display: inline; font-style: inherit; font-weight: inherit; line-height: normal; 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; border: 0px; padding: 0px; margin: 0px; font-family: inherit;" tabindex="0"><span class="math" id="MathJax-Span-11" role="math" style="box-sizing: border-box; transition: none; display: inline-block; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; width: 0.653em;"><span style="box-sizing: border-box; transition: none; display: inline-block; position: relative; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; width: 0.588em; height: 0px; font-size: 15.4px;"><span style="box-sizing: border-box; transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(1.172em 1000.46em 2.341em -999.997em); top: -2.14em; left: 0.003em;"><span style="box-sizing: border-box; transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(3.38em 1000.46em 4.224em -999.997em); top: -4.023em; left: 0.003em;"><span class="mi" id="MathJax-Span-14" style="box-sizing: border-box; transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">z<span style="box-sizing: border-box; transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(3.12em 1000.39em 3.705em -999.997em); top: -4.088em; left: 0.068em;">ˆ restricted to single-particle Bloch functions belonging to one or more bands. To ensure that the Wannier functions are real-valued, we numerically obtain the band structure and real-valued eigenstates using a uniform Fourier grid DVR. We then show, by a comparison of tunneling energies, that the Wannier functions are accurate for both inversion-symmetric and asymmetric potentials to better than 10 significant digits when using double-precision arithmetic. The calculations are performed for an optical lattice with double-wells per unit cell with tunable asymmetry along the <span class="MathJax" id="MathJax-Element-3-Frame" style="box-sizing: border-box; display: inline; font-style: inherit; font-weight: inherit; line-height: normal; 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; border: 0px; padding: 0px; margin: 0px; font-family: inherit;" tabindex="0"><span class="math" id="MathJax-Span-16" role="math" style="box-sizing: border-box; transition: none; display: inline-block; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; width: 0.653em;"><span style="box-sizing: border-box; transition: none; display: inline-block; position: relative; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; width: 0.588em; height: 0px; font-size: 15.4px;"><span style="box-sizing: border-box; transition: none; position: absolute; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; clip: rect(1.497em 1000.52em 2.341em -999.997em); top: -2.14em; left: 0.003em;"><span class="mi" id="MathJax-Span-18" style="box-sizing: border-box; transition: none; display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; font-family: MathJax_Math-italic;">x axis and a single sinusoidal potential along the perpendicular directions. Localized functions at the two potential minima within each unit cell are similarly constructed, but using a superposition of single-particle solutions from the two lowest bands. We finally use these localized basis functions to determine the two-body interaction energies in the Bose-Hubbard model and show the dependence of these energies on lattice asymmetry.

Whose Information? Information About What? - Jeffrey Bub; Anton Zeilinger; Reinhold Bertlmann (Quantum [Un]Speakables II: 50 Years of Bell’s Theorem, 2016)

Yang-Baxter operators need quantum entanglement to distinguish knots - Gorjan Alagic; Michael Jarret; Stephen P. Jordan (Journal of Physics A, 2016)
Any solution to the Yang-Baxter equation yields a family of representations of braid groups. Under certain conditions, identified by Turaev, the appropriately normalized trace of these representations yields a link invariant. Any Yang-Baxter solution can be interpreted as a two-qudit quantum gate. Here we show that if this gate is non-entangling, then the resulting invariant of knots is trivial. We thus obtain a general connection between topological entanglement and quantum entanglement, as suggested by Kauffman et al.

2D Superexchange mediated magnetization dynamics in an optical lattice - R. C. Brown; R. Wyllie; S. B. Koller; E. A. Goldschmidt; Michael Foss-Feig; J. V. Porto (Science, 2015)
The competition of magnetic exchange interactions and tunneling underlies many complex quantum phenomena observed in real materials. We study non-equilibrium magnetization dynamics in an extended 2D system by loading effective spin-1/2 bosons into a spin-dependent optical lattice, and we use the lattice to separately control the resonance conditions for tunneling and superexchange. After preparing a non-equilibrium anti-ferromagnetically ordered state, we observe relaxation dynamics governed by two well-separated rates, which scale with the underlying Hamiltonian parameters associated with superexchange and tunneling. Remarkably, with tunneling off-resonantly suppressed, we are able to observe superexchange dominated dynamics over two orders of magnitude in magnetic coupling strength, despite the presence of vacancies. In this regime, the measured timescales are in agreement with simple theoretical estimates, but the detailed dynamics of this 2D, strongly correlated, and far-from-equilibrium quantum system remain out of reach of current computational techniques.

Adiabatic optimization without local minima - Michael Jarret; Stephen P. Jordan (Quantum Information and Computation, 2015)
Several previous works have investigated the circumstances under which quantum adiabatic optimization algorithms can tunnel out of local energy minima that trap simulated annealing or other classical local search algorithms. Here we investigate the even more basic question of whether adiabatic optimization algorithms always succeed in polynomial time for trivial optimization problems in which there are no local energy minima other than the global minimum. Surprisingly, we find a counterexample in which the potential is a single basin on a graph, but the eigenvalue gap is exponentially small as a function of the number of vertices. In this counterexample, the ground state wavefunction consists of two "lobes" separated by a region of exponentially small amplitude. Conversely, we prove if the ground state wavefunction is single-peaked then the eigenvalue gap scales at worst as one over the square of the number of vertices.

Atom induced cavities and tunable long-range interactions between atoms trapped near photonic crystals - J S Douglas; H Habibian; Alexey V. Gorshkov; H J Kimble; D E Chang (Nature Photon. 9, 326 (2015), 2015)
Using cold atoms to simulate strongly interacting quantum systems represents an exciting frontier of physics. However, achieving tunable, coherent long-range interactions between atoms is an outstanding challenge, which currently leaves a large class of models inaccessible to quantum simulation. Here, we propose a solution exploiting the powerful new platform of cold atoms trapped near nano-photonic systems. We show that the dielectric contrast of an atom trapped near a photonic crystal can seed a localized cavity mode around the atomic position. In a dynamic form of “all-atomic” cavity QED, the length of these cavity modes can be tuned, and atoms separated by the order of the e↵ective cavity length can interact coherently with each other. Considering realistic conditions such as fabrication disorder and photon losses, coherent long-range potentials or spin interactions can be dominant in the system over length scales up to hundreds of wavelengths.

Bilayer fractional quantum Hall states with ultracold dysprosium - Norman Y. Yao; Steven D. Bennett; Chris R. Laumann; Benjamin L. Lev; Alexey V. Gorshkov (Physical Review A, 2015)
We show how dipolar interactions between dysprosium atoms in an optical lattice can be used to obtain fractional quantum Hall states. In our approach, dysprosium atoms are trapped one atom per site in a deep optical lattice with negligible tunneling. Microwave and spatially dependent optical dressing fields are used to define an effective spin-1/2 or spin-1 degree of freedom in each atom. Thinking of spin-1/2 particles as hardcore bosons, dipole-dipole interactions give rise to boson hopping, topological flat bands with Chern number 1, and the ν = 1/2 Laughlin state. Thinking of spin-1 particles as two-component hardcore bosons, dipole-dipole interactions again give rise to boson hopping, topological flat bands with Chern number 2, and the bilayer Halperin (2,2,1) state. By adjusting the optical fields, we find a phase diagram, in which the (2,2,1) state competes with superfluidity. Generalizations to solid-state magnetic dipoles are discussed.

Bounds on quantum communication via Newtonian gravity - D. Kafri; G. J. Milburn; J. M. Taylor (New Journal of Physics, 2015)
Newtonian gravity yields specific observable consequences, the most striking of which is the emergence of a $1/r^2$ force. In so far as communication can arise via such interactions between distant particles, we can ask what would be expected for a theory of gravity that only allows classical communication. Many heuristic suggestions for gravity-induced decoherence have this restriction implicitly or explicitly in their construction. Here we show that communication via a $1/r^2$ force has a minimum noise induced in the system when the communication cannot convey quantum information, in a continuous time analogue to Bell's inequalities. Our derived noise bounds provide tight constraints from current experimental results on any theory of gravity that does not allow quantum communication.

Capacitively coupled singlet-triplet qubits in the double charge resonant regime - V. Srinivasa; J. M. Taylor (Physical Review B, 2015)
We investigate a method for entangling two singlet-triplet qubits in adjacent double quantum dots via capacitive interactions. In contrast to prior work, here we focus on a regime with strong interactions between the qubits. The interplay of the interaction energy and simultaneous large detunings for both double dots gives rise to the double charge resonant regime, in which the unpolarized (1111) and fully polarized (0202) four-electron states in the absence of interqubit tunneling are near degeneracy, while being energetically well-separated from the partially polarized (0211 and 1102) states. A controlled-phase gate may be realized by combining time evolution in this regime in the presence of intraqubit tunneling and the interqubit Coulomb interaction with refocusing π pulses that swap the singly occupied singlet and triplet states of the two qubits via, e.g., magnetic gradients. We calculate the fidelity of this entangling gate, incorporating models for two types of noise - classical, Gaussian-distributed charge fluctuations in the single-qubit detunings and charge relaxation within the low-energy subspace via electron-phonon interaction - and identify parameter regimes that optimize the fidelity. The rates of phonon-induced decay for pairs of GaAs or Si double quantum dots vary with the sizes of the dipolar and quadrupolar contributions and are several orders of magnitude smaller for Si, leading to high theoretical gate fidelities for coupled singlet-triplet qubits in Si dots. We also consider the dependence of the capacitive coupling on the relative orientation of the double dots and find that a linear geometry provides the fastest potential gate.

A chemical potential for light - M. Hafezi; P. Adhikari; J. M. Taylor (Physical Review B, 2015)
Photons are not conserved in interactions with other matter. Consequently, when understanding the equation of state and thermodynamics of photons, while we have a concept of temperature for energy conservation, there is no equivalent chemical potential for particle number conservation. However, the notion of a chemical potential is crucial in understanding a wide variety of single- and many-body effects, from transport in conductors and semi-conductors to phase transitions in electronic and atomic systems. Here we show how a direct modification of the system-bath coupling via parametric oscillation creates an effective chemical potential for photons even in the thermodynamic limit. Specific implementations, using circuit-QED or optomechanics, are feasible using current technologies, and we show a detailed example demonstrating the emergence of Mott Insulator-superfluid transition in a lattice of nonlinear oscillators. Our approach paves the way for quantum simulation, quantum sources and even electron-like circuits with light.

Continuous symmetry breaking and a new universality class in 1D long-range interacting quantum systems - Mohammad F. Maghrebi; Zhe-Xuan Gong; Alexey V. Gorshkov (2015)
Continuous symmetry breaking (CSB) in low-dimensional systems, forbidden by the Mermin-Wagner theorem for short-range interactions, may take place in the presence of slowly decaying long-range interactions. Nevertheless, there is no stringent bound on how slowly interactions should decay to give rise to CSB in 1D quantum systems at zero temperature. Here, we study a long-range interacting spin chain with U(1) symmetry and power-law interactions V(r)∼1/rα, directly relevant to ion-trap experiments. Using bosonization and renormalization group theory, we find CSB for α smaller than a critical exponent αc(≤3) depending on the microscopic parameters of the model. Furthermore, the transition from the gapless XY phase to the gapless CSB phase is mediated by the breaking of conformal symmetry due to long-range interactions, and is described by a new universality class akin to the Berezinskii-Kosterlitz-Thouless transition. Our analytical findings are in good agreement with a numerical calculation. Signatures of the CSB phase should be accessible in existing trapped-ion experiments.

Coulomb bound states of strongly interacting photons - Mohammad F. Maghrebi; Michael Gullans; P. Bienias; S. Choi; I. Martin; O. Firstenberg; M. D. Lukin; H. P. Büchler; Alexey V. Gorshkov (Physical Review Letters, 2015)
We show that two photons coupled to Rydberg states via electromagnetically induced transparency can interact via an effective Coulomb potential. This interaction gives rise to a continuum of two-body bound states. Within the continuum, metastable bound states are distinguished in analogy with quasi-bound states tunneling through a potential barrier. We find multiple branches of metastable bound states whose energy spectrum is governed by the Coulomb potential, thus obtaining a photonic analogue of the hydrogen atom. Under certain conditions, the wavefunction resembles that of a diatomic molecule in which the two polaritons are separated by a finite "bond length." These states propagate with a negative group velocity in the medium, allowing for a simple preparation and detection scheme, before they slowly decay to pairs of bound Rydberg atoms.

Demonstration of Robust Quantum Gate Tomography via Randomized Benchmarking - Blake R. Johnson; Marcus P. da Silva; Colm A. Ryan; Shelby Kimmel; Jerry M. Chow; Thomas A. Ohki (New Journal of Physics, 2015)
Typical quantum gate tomography protocols struggle with a self-consistency problem: the gate operation cannot be reconstructed without knowledge of the initial state and final measurement, but such knowledge cannot be obtained without well-characterized gates. A recently proposed technique, known as randomized benchmarking tomography (RBT), sidesteps this self-consistency problem by designing experiments to be insensitive to preparation and measurement imperfections. We implement this proposal in a superconducting qubit system, using a number of experimental improvements including implementing each of the elements of the Clifford group in single `atomic' pulses and custom control hardware to enable large overhead protocols. We show a robust reconstruction of several single-qubit quantum gates, including a unitary outside the Clifford group. We demonstrate that RBT yields physical gate reconstructions that are consistent with fidelities obtained by randomized benchmarking.

Discontinuity of Maximum Entropy Inference and Quantum Phase Transitions - Jianxin Chen; Zhengfeng Ji; Chi-Kwong Li; Yiu-Tung Poon; Yi Shen; Nengkun Yu; Bei Zeng; Duanlu Zhou (New Journal of Physics, 2015)
In this paper, we discuss the connection between two genuinely quantum phenomena --- the discontinuity of quantum maximum entropy inference and quantum phase transitions at zero temperature. It is shown that the discontinuity of the maximum entropy inference of local observable measurements signals the non-local type of transitions, where local density matrices of the ground state change smoothly at the transition point. We then propose to use the quantum conditional mutual information of the ground state as an indicator to detect the discontinuity and the non-local type of quantum phase transitions in the thermodynamic limit.

Driving Rabi oscillations at the giant dipole resonance in xenon - Stefan Pabst; Daochen Wang; Robin Santra (Phys. Rev. A, 2015)
Free-electron lasers (FELs) produce short and very intense light pulses in the XUV and x-ray regimes. We investigate the possibility to drive Rabi oscillations in xenon with an intense FEL pulse by using the unusually large dipole strength of the giant-dipole resonance (GDR). The GDR decays within less than 30 as due to its position, which is above the 4d ionization threshold. We find that intensities around 1018 W/cm2 are required to induce Rabi oscillations with a period comparable to the lifetime. The pulse duration should not exceed 100 as because xenon will be fully ionized within a few lifetimes. Rabi oscillations reveal themselves also in the photoelectron spectrum in form of Autler-Townes splittings extending over several tens of electronvolt.

Entanglement entropy of dispersive media from thermodynamic entropy in one higher dimension - Mohammad F. Maghrebi; Homer Reid (Physical Review Letters, 2015)
A dispersive medium becomes entangled with zero-point fluctuations in the vacuum. We consider an arbitrary array of material bodies weakly interacting with a quantum field and compute the quantum mutual information between them. It is shown that the mutual information in D dimensions can be mapped to classical thermodynamic entropy in D+1 dimensions. As a specific example, we compute the mutual information both analytically and numerically for a range of separation distances between two bodies in D=2 dimensions and find a logarithmic correction to the area law at short separations. A key advantage of our method is that it allows the strong subadditivity property---notoriously difficult to prove for quantum systems---to be easily verified.

Entangling two transportable neutral atoms via local spin exchange - A. M. Kaufman; B. J. Lester; Michael Foss-Feig; M. L. Wall; A. M. Rey; C. A. Regal (Nature, 2015)
To advance quantum information science a constant pursuit is the search for physical systems that meet the stringent requirements for creating and preserving quantum entanglement. In atomic physics, robust two-qubit entanglement is typically achieved by strong, long-range interactions in the form of Coulomb interactions between ions or dipolar interactions between Rydberg atoms. While these interactions allow fast gates, atoms subject to these interactions must overcome the associated coupling to the environment and cross-talk among qubits. Local interactions, such as those requiring significant wavefunction overlap, can alleviate these detrimental effects yet present a new challenge: To distribute entanglement, qubits must be transported, merged for interaction, and then isolated for storage and subsequent operations. Here we show how, via a mobile optical tweezer, it is possible to prepare and locally entangle two ultracold neutral atoms, and then separate them while preserving their entanglement. While ultracold neutral atom experiments have measured dynamics consistent with spin entanglement, we are now able to demonstrate two-particle coherence via application of a local gradient and parity measurements; this new entanglement-verification protocol could be applied to arbitrary spin-entangled states of spatially-separated atoms. The local entangling operation is achieved via ultracold spin-exchange interactions, and quantum tunneling is used to combine and separate atoms. Our toolset provides a framework for dynamically entangling remote qubits via local operations within a large-scale quantum register.

Fractional Quantum Hall States of Rydberg Polaritons - Mohammad F. Maghrebi; Norman Y. Yao; Mohammad Hafezi; Thomas Pohl; Ofer Firstenberg; Alexey V. Gorshkov (Physical Review A, 2015)
We propose a scheme for realizing fractional quantum Hall states of light. In our scheme, photons of two polarizations are coupled to different atomic Rydberg states to form two flavors of Rydberg polaritons that behave as an effective spin. An array of optical cavity modes overlapping with the atomic cloud enables the realization of an effective spin-1/2 lattice. We show that the dipolar interaction between such polaritons, inherited from the Rydberg states, can be exploited to create a flat, topological band for a single spin-flip excitation. At half filling, this gives rise to a photonic (or polaritonic) fractional Chern insulator -- a lattice-based, fractional quantum Hall state of light.

Framework for learning agents in quantum environments - Vedran Dunjko; J. M. Taylor; Hans J. Briegel (2015)
In this paper we provide a broad framework for describing learning agents in general quantum environments. We analyze the types of classically specified environments which allow for quantum enhancements in learning, by contrasting environments to quantum oracles. We show that whether or not quantum improvements are at all possible depends on the internal structure of the quantum environment. If the environments are constructed and the internal structure is appropriately chosen, or if the agent has limited capacities to influence the internal states of the environment, we show that improvements in learning times are possible in a broad range of scenarios. Such scenarios we call luck-favoring settings. The case of constructed environments is particularly relevant for the class of model-based learning agents, where our results imply a near-generic improvement.

From membrane-in-the-middle to mirror-in-the-middle with a high-reflectivity sub-wavelength grating - Corey Stambaugh; Haitan Xu; Utku Kemiktarak; J. M. Taylor; John Lawall (Annalen der Physik, 2015)
We demonstrate a "membrane in the middle" optomechanical system using a silicon nitride membrane patterned as a subwavelength grating. The grating has a reflectivity of over 99.8%, effectively creating two sub-cavities, with free spectral ranges of 6 GHz, optically coupled via photon tunneling. Measurements of the transmission and reflection spectra show an avoided crossing where the two sub-cavities simultaneously come into resonance, with a frequency splitting of 54 MHz. We derive expressions for the lineshapes of the symmetric and antisymmetric modes at the avoided crossing, and infer the grating reflection, transmission, absorption, and scattering through comparison with the experimental data.

Hamiltonian simulation with nearly optimal dependence on all parameters - Dominic W. Berry; Andrew M. Childs; Robin Kothari (Proceedings of the 56th IEEE Symposium on Foundations of Computer Science, 2015)
We present an algorithm for sparse Hamiltonian simulation that has optimal dependence on all parameters of interest (up to log factors). Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity $d$ at the expense of poor scaling in the allowed error $\epsilon$. In contrast, an approach based on fractional-query simulation provides optimal scaling in $\epsilon$ at the expense of poor scaling in $d$. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm achieves near-linear scaling in $\tau := d \|H\|_{\max} t$ and sublogarithmic scaling in $1/\epsilon$. Our dependence on $\epsilon$ is optimal, and we prove a new lower bound showing that no algorithm can have sublinear dependence on $\tau$.

Injection Locking of a Semiconductor Double Quantum Dot Micromaser - Y. -Y. Liu; J. Stehlik; Michael Gullans; J. M. Taylor; J. R. Petta (Physical Review A, 2015)
Emission linewidth is an important figure of merit for masers and lasers. We recently demonstrated a semiconductor double quantum dot (DQD) micromaser where photons are generated through single electron tunneling events. Charge noise directly couples to the DQD energy levels, resulting in a maser linewidth that is more than 100 times larger than the Schawlow-Townes prediction. Here we demonstrate a linewidth narrowing of more than a factor 10 by locking the DQD emission to a coherent tone that is injected to the input port of the cavity. We measure the injection locking range as a function of cavity input power and show that it is in agreement with the Adler equation. The position and amplitude of distortion sidebands that appear outside of the injection locking range are quantitatively examined. Our results show that this unconventional maser, which is impacted by strong charge noise and electron-phonon coupling, is well described by standard laser models.

Laplacian matrices and Alexandrov topologies of digraphs - Aaron Ostrander (Linear Algebra and its Applications, 2015)
We explore the spectral properties of digraph Laplacians and how they relate to topological properties of digraphs (such as openness, closure, and strong connectedness) under the Alexandrov topology.
Keywords: Laplacian matrix

Large effective three-body interaction in a double-well optical lattice - Saurabh Paul; Eite Tiesinga (Phys. Rev. A 92, 023602, 2015)
We study ultracold atoms in an optical lattice with two local minima per unit cell and show that the low energy states of a multi-band Bose-Hubbard (BH) Hamiltonian with only pair-wise interactions is equivalent to an effective single-band Hamiltonian with strong three-body interactions. We focus on a double-well optical lattice with a symmetric double well along the $x$ axis and single well structure along the perpendicular directions. Tunneling and two-body interaction energies are obtained from an exact band-structure calculation and numerically-constructed Wannier functions in order to construct a BH Hamiltonian spanning the lowest two bands. Our effective Hamiltonian is constructed from the ground state of the $N$-atom Hamiltonian for each unit cell obtained within the subspace spanned by the Wannier functions of two lowest bands. The model includes hopping between ground states of neighboring unit cells. We show that such an effective Hamiltonian has strong three-body interactions that can be easily tuned by changing the lattice parameters. Finally, relying on numerical mean-field simulations, we show that the effective Hamiltonian is an excellent approximation of the two-band BH Hamiltonian over a wide range of lattice parameters, both in the superfluid and Mott insulator regions.

The Measurement Problem from the Perspective of an Information Theoretic Interpretation of Quantum Mechanics - Jeffrey Bub (Entropy, 2015)
The aim of this paper is to consider the consequences of an information-theoretic interpretation of quantum mechanics for the measurement problem. The motivating idea of the interpretation is that the relation between quantum mechanics and the structure of information is analogous to the relation between special relativity and the structure of space-time. Insofar as quantum mechanics deals with a class of probabilistic correlations that includes correlations structurally different from classical correlations, the theory is about the structure of information: the possibilities for representing, manipulating, and communicating information in a genuinely indeterministic quantum world in which measurement outcomes are intrinsically random are different than we thought. Part of the measurement problem is deflated as a pseudo-problem on this view, and the theory has the resources to deal with the remaining part, given certain idealizations in the treatment of macrosystems.

The Minimum Size of Unextendible Product Bases in the Bipartite Case (and Some Multipartite Cases) - Jianxin Chen; Nathaniel Johnston (Communications in Mathematical Physics, 2015)
A long-standing open question asks for the minimum number of vectors needed to form an unextendible product basis in a given bipartite or multipartite Hilbert space. A partial solution was found by Alon and Lovasz in 2001, but since then only a few other cases have been solved. We solve all remaining bipartite cases, as well as a large family of multipartite cases.

Momentum switches - Andrew M. Childs; David Gosset; Daniel Nagaj; Mouktik Raha; Zak Webb (Quantum Information and Computation, 2015)
Certain continuous-time quantum walks can be viewed as scattering processes. These processes can perform quantum computations, but it is challenging to design graphs with desired scattering behavior. In this paper, we study and construct momentum switches, graphs that route particles depending on their momenta. We also give an example where there is no exact momentum switch, although we construct an arbitrarily good approximation.

Nearly-linear light cones in long-range interacting quantum systems - Michael Foss-Feig; Zhe-Xuan Gong; Charles W. Clark; Alexey V. Gorshkov (Physical Review Letters, 2015)
In non-relativistic quantum theories with short-range Hamiltonians, a velocity $v$ can be chosen such that the influence of any local perturbation is approximately confined to within a distance $r$ until a time $t \sim r/v$, thereby defining a linear light cone and giving rise to an emergent notion of locality. In systems with power-law ($1/r^{α}$) interactions, when $α$ exceeds the dimension $D$, an analogous bound confines influences to within a distance $r$ only until a time $t\sim(α/v)\log r$, suggesting that the velocity, as calculated from the slope of the light cone, may grow exponentially in time. We rule out this possibility; light cones of power-law interacting systems are algebraic for $α>2D$, becoming linear as $α→∞$. Our results impose strong new constraints on the growth of correlations and the production of entangled states in a variety of rapidly emerging, long-range interacting atomic, molecular, and optical systems.

Observation of optomechanical buckling phase transitions - Haitan Xu; Utku Kemiktarak; Jingyun Fan; Stephen Ragole; John Lawall; J. M. Taylor (2015)
Correlated phases of matter provide long-term stability for systems as diverse as solids, magnets, and potential exotic quantum materials. Mechanical systems, such as relays and buckling transition spring switches can yield similar stability by exploiting non-equilibrium phase transitions. Curiously, in the optical domain, observations of such phase transitions remain elusive. However, efforts to integrate optical and mechanical systems -- optomechanics -- suggest that a hybrid approach combining the quantum control of optical systems with the engineerability of mechanical systems may provide a new avenue for such explorations. Here we report the first observation of the buckling of an optomechanical system, in which transitions between stable mechanical states corresponding to both first- and second-order phase transitions are driven by varying laser power and detuning. Our results enable new applications in photonics and, given rapid progress in pushing optomechanical systems into the quantum regime, the potential for explorations of quantum phase transitions.

Optical Control of Donor Spin Qubits in Silicon - Michael Gullans; J. M. Taylor (Physical Review B, 2015)
We show how to achieve optical, spin-selective transitions from the ground state to excited orbital states of group-V donors (P, As, Sb, Bi) in silicon. We consider two approaches based on either resonant, far-infrared (IR) transitions of the neutral donor or resonant, near-IR excitonic transitions. For far-IR light, we calculate the dipole matrix elements between the valley-orbit and spin-orbit split states for all the goup-V donors using effective mass theory. We then calculate the maximum rate and amount of electron-nuclear spin-polarization achievable through optical pumping with circularly polarized light. We find this approach is most promising for Bi donors due to their large spin-orbit and valley-orbit interactions. Using near-IR light, spin-selective excitation is possible for all the donors by driving a two-photon $Λ$-transition from the ground state to higher orbitals with even parity. We show that externally applied electric fields or strain allow similar, spin-selective $Λ$-transition to odd-parity excited states. We anticipate these results will be useful for future spectroscopic investigations of donors, quantum control and state preparation of donor spin qubits, and for developing a coherent interface between donor spin qubits and single photons.

Optimal ancilla-free Clifford+V approximation of z-rotations - Neil J. Ross (Quantum Information and Computation, 2015)
We describe a new efficient algorithm to approximate z-rotations by ancilla-free Clifford+V circuits, up to a given precision epsilon. Our algorithm is optimal in the presence of an oracle for integer factoring: it outputs the shortest Clifford+V circuit solving the given problem instance. In the absence of such an oracle, our algorithm is still near-optimal, producing circuits of V-count m + O(log(log(1/epsilon))), where m is the V-count of the third-to-optimal solution. A restricted version of the algorithm approximates z-rotations in the Pauli+V gate set. Our method is based on previous work by the author and Selinger on the optimal ancilla-free approximation of z-rotations using Clifford+T gates and on previous work by Bocharov, Gurevich, and Svore on the asymptotically optimal ancilla-free approximation of z-rotations using Clifford+V gates.

Optimization of collisional Feshbach cooling of an ultracold nondegenerate gas - Marlon Nuske; Eite Tiesinga; L. Mathey (Physical Review A, 2015)
We optimize a collision-induced cooling process for ultracold atoms in the nondegenerate regime. It makes use of a Feshbach resonance, instead of rf radiation in evaporative cooling, to selectively expel hot atoms from a trap. Using functional minimization we analytically show that for the optimal cooling process the resonance energy must be tuned such that it linearly follows the temperature. Here, optimal cooling is defined as maximizing the phase-space density after a fixed cooling duration. The analytical results are confirmed by numerical Monte-Carlo simulations. In order to simulate more realistic experimental conditions, we show that background losses do not change our conclusions, while additional non-resonant two-body losses make a lower initial resonance energy with non-linear dependence on temperature preferable.

Optomechanical reference accelerometer - Oliver Gerberding; Felipe Guzman Cervantes; John Melcher; Jon R. Pratt; J. M. Taylor (Metrologia, 2015)
We present an optomechanical accelerometer with high dynamic range, high bandwidth and read-out noise levels below 8 ${μ}$g/$\sqrt{Hz}$. The straightforward assembly and low cost of our device make it a prime candidate for on-site reference calibrations and autonomous navigation. We present experimental data taken with a vacuum sealed, portable prototype and deduce the achieved bias stability and scale factor accuracy. Additionally, we present a comprehensive model of the device physics that we use to analyze the fundamental noise sources and accuracy limitations of such devices.

Oracles with Costs - Shelby Kimmel; Cedric Yen-Yu Lin; Han-Hsuan Lin (10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015), 2015)
While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.

Parafermionic zero modes in ultracold bosonic systems - Mohammad F. Maghrebi; Sriram Ganeshan; David J. Clarke; Alexey V. Gorshkov; Jay D. Sau (Physical Review Letters, 2015)
Exotic topologically protected zero modes with parafermionic statistics (also called fractionalized Majorana modes) have been proposed to emerge in devices fabricated from a fractional quantum Hall system and a superconductor. The fractionalized statistics of these modes takes them an important step beyond the simplest non-Abelian anyons, Majorana fermions. Building on recent advances towards the realization of fractional quantum Hall states of bosonic ultracold atoms, we propose a realization of parafermions in a system consisting of Bose-Einstein-condensate trenches within a bosonic fractional quantum Hall state. We show that parafermionic zero modes emerge at the endpoints of the trenches and give rise to a topologically protected degeneracy. We also discuss methods for preparing and detecting these modes.

Phase Retrieval Without Small-Ball Probability Assumptions: Stability and Uniqueness - Felix Krahmer; Yi-Kai Liu (SampTA, 2015)
We study stability and uniqueness for the phase retrieval problem. That is, we ask when is a signal x ∈ R n stably and uniquely determined (up to small perturbations), when one performs phaseless measurements of the form yi = |a T i x| 2 (for i = 1, . . . , N), where the vectors ai ∈ R n are chosen independently at random, with each coordinate aij ∈ R being chosen independently from a fixed sub-Gaussian distribution D. It is well known that for many common choices of D, certain ambiguities can arise that prevent x from being uniquely determined. In this note we show that for any sub-Gaussian distribution D, with no additional assumptions, most vectors x cannot lead to such ambiguities. More precisely, we show stability and uniqueness for all sets of vectors T ⊂ R n which are not too peaky, in the sense that at most a constant fraction of their mass is concentrated on any one coordinate. The number of measurements needed to recover x ∈ T depends on the complexity of T in a natural way, extending previous results of Eldar and Mendelson [12].

Phonon-Assisted Gain in a Semiconductor Double Quantum Dot Maser - Michael Gullans; Y. -Y. Liu; J. Stehlik; J. R. Petta; J. M. Taylor (Physical Review Letters, 2015)
We develop a microscopic model for the recently demonstrated double quantum dot (DQD) maser. In characterizing the gain of this device we find that, in addition to the direct stimulated emission of photons, there is a large contribution from the simultaneous emission of a photon and a phonon, i.e., the phonon sideband. We show that this phonon-assisted gain typically dominates the overall gain which leads to masing. Recent experimental data are well fit with our model.

The Power of Quantum Fourier Sampling - Bill Fefferman; Chris Umans (2015)
A line of work initiated by Terhal and DiVincenzo and Bremner, Jozsa, and Shepherd, shows that quantum computers can efficiently sample from probability distributions that cannot be exactly sampled efficiently on a classical computer, unless the PH collapses. Aaronson and Arkhipov take this further by considering a distribution that can be sampled efficiently by linear optical quantum computation, that under two feasible conjectures, cannot even be approximately sampled classically within bounded total variation distance, unless the PH collapses. In this work we use Quantum Fourier Sampling to construct a class of distributions that can be sampled by a quantum computer. We then argue that these distributions cannot be approximately sampled classically, unless the PH collapses, under variants of the Aaronson and Arkhipov conjectures. In particular, we show a general class of quantumly sampleable distributions each of which is based on an "Efficiently Specifiable" polynomial, for which a classical approximate sampler implies an average-case approximation. This class of polynomials contains the Permanent but also includes, for example, the Hamiltonian Cycle polynomial, and many other familiar #P-hard polynomials. Although our construction, unlike that proposed by Aaronson and Arkhipov, likely requires a universal quantum computer, we are able to use this additional power to weaken the conjectures needed to prove approximate sampling hardness results.

Programming the Quantum Future - D. Scott Alexander; Neil J. Ross; Peter Selinger; Jonathan M. Smith; Benoît Valiron (Communications of the ACM, 2015)
The earliest computers, like the ENIAC, were rare and heroically difficult to program. That difficulty stemmed from the requirement that algorithms be expressed in a "vocabulary" suited to the particular hardware available, ranging from function tables for the ENIAC to more conventional arithmetic and movement operations on later machines. Introduction of symbolic programming languages, exemplified by FORTRAN, solved a major difficulty for the next generation of computing devices by enabling specification of an algorithm in a form more suitable for human understanding, then translating this specification to a form executable by the machine. The "programming language" used for such specification bridged a semantic gap between the human and the computing device. It provided two important features: high-level abstractions, taking care of automated bookkeeping, and modularity, making it easier to reason about sub-parts of programs.

Quantum Compressed Sensing Using 2-Designs - Shelby Kimmel; Yi-Kai Liu (2015)
We develop a method for quantum process tomography that combines the efficiency of compressed sensing with the robustness of randomized benchmarking. Our method is robust to state preparation and measurement errors, and it achieves a quadratic speedup over conventional tomography when the unknown process is a generic unitary evolution. Our method is based on PhaseLift, a convex programming technique for phase retrieval. We show that this method achieves approximate recovery of almost all signals, using measurements sampled from spherical or unitary 2-designs. This is the first positive result on PhaseLift using 2-designs. We also show that exact recovery of all signals is possible using unitary 4-designs. Previous positive results for PhaseLift required spherical 4-designs, while PhaseLift was known to fail in certain cases when using spherical 2-designs.

Quantum Entanglement and Information - Jeffrey Bub; Edward N. Zalta (The Stanford Encyclopedia of Philosophy, 2015)
Quantum entanglement is a physical resource, like energy, associated with the peculiar nonclassical correlations that are possible between separated quantum systems. Entanglement can be measured, transformed, and purified. A pair of quantum systems in an entangled state can be used as a quantum information channel to perform computational and cryptographic tasks that are impossible for classical systems. The general study of the information-processing capabilities of quantum systems is the subject of quantum information theory.

Quantum many-body models with cold atoms coupled to photonic crystals - Douglas, J. S.; Habibian, H.; Hung, C.-L.; Alexey V. Gorshkov; Kimble, H. J.; Chang, D. E. (Nature Photonics, 2015)

Quantum Nonlinear Optics Near Optomechanical Instabilities - Xunnong Xu; Michael Gullans; J. M. Taylor (Physical Review A, 2015)
Optomechanical systems provide a unique platform for observing quantum behavior of macroscopic objects. However, efforts towards realizing nonlinear behavior at the single photon level have been inhibited by the small size of the radiation pressure interaction. Here we show that it is not necessary to reach the single-photon strong-coupling regime in order to realize significant optomechanical nonlinearities. Instead, nonlinearities at the few quanta level can be achieved, even with weak-coupling, in a two-mode optomechanical system driven near instability. In this limit, we establish a new figure of merit for realizing strong nonlinearity which scales with the single-photon optomechanical coupling and the sideband resolution of the mechanical mode with respect to the cavity linewidth. We find that current devices based on optomechanical crystals, thought to be in the weak-coupling regime, can still achieve strong quantum nonlinearity; enabling deterministic interactions between single photons.

Quantum vs Classical Proofs and Subset Verification - Bill Fefferman; Shelby Kimmel (2015)
We study the ability of efficient quantum verifiers to decide properties of exponentially large subsets given either a classical or quantum witness. We develop a general framework that can be used to prove that QCMA machines, with only classical witnesses, cannot verify certain properties of subsets given implicitly via an oracle. We use this framework to prove an oracle separation between QCMA and QMA using an ``in-place'' permutation oracle, making the first progress on this question since Aaronson and Kuperberg in 2007. We also use the framework to prove a particularly simple standard oracle separation between QCMA and AM.

Robust Single-Qubit Process Calibration via Robust Phase Estimation - Shelby Kimmel; Guang Hao Low; Theodore J. Yoder (Physical Review A, 2015)
An important step in building a quantum computer is calibrating experimentally implemented quantum gates to produce operations that are close to ideal unitaries. The calibration step involves estimating the error in gates and then using controls to correct the implementation. Quantum process tomography is a standard technique for estimating these errors, but is both time consuming, (when one only wants to learn a few key parameters), and requires resources, like perfect state preparation and measurement, that might not be available. With the goal of efficiently estimating specific errors using minimal resources, we develop a parameter estimation technique, which can gauge two key parameters (amplitude and off-resonance errors) in a single-qubit gate with provable robustness and efficiency. In particular, our estimates achieve the optimal efficiency, Heisenberg scaling. Our main theorem making this possible is a robust version of the phase estimation procedure of Higgins et al. [B. L. Higgins, New J. Phys. 11, 073023 (2009)].

Self-heterodyne detection of the \it in-situ phase of an atomic-SQUID - Ranchu Mathew; Avinash Kumar; Stephen Eckel; Fred Jendrzejewski; Gretchen K. Campbell; Mark Edwards; Eite Tiesinga (Physical Review A, 2015)
We present theoretical and experimental analysis of an interferometric measurement of the {\it in-situ} phase drop across and current flow through a rotating barrier in a toroidal Bose-Einstein condensate (BEC). This experiment is the atomic analog of the rf-superconducting quantum interference device (SQUID). The phase drop is extracted from a spiral-shaped density profile created by the spatial interference of the expanding toroidal BEC and a reference BEC after release from all trapping potentials. We characterize the interferometer when it contains a single particle, which is initially in a coherent superposition of a torus and reference state, as well as when it contains a many-body state in the mean-field approximation. The single-particle picture is sufficient to explain the origin of the spirals, to relate the phase-drop across the barrier to the geometry of a spiral, and to bound the expansion times for which the {\it in-situ} phase can be accurately determined. Mean-field estimates and numerical simulations show that the inter-atomic interactions shorten the expansion time scales compared to the single-particle case. Finally, we compare the mean-field simulations with our experimental data and confirm that the interferometer indeed accurately measures the {\it in-situ} phase drop.

Semiconductor double quantum dot micromaser - Y. -Y. Liu; J. Stehlik; C. Eichler; Michael Gullans; J. M. Taylor; J. R. Petta (Science, 2015)
The coherent generation of light, from masers to lasers, relies upon the specific structure of the individual emitters that lead to gain. Devices operating as lasers in the few-emitter limit provide opportunities for understanding quantum coherent phenomena, from THz sources to quantum communication. Here we demonstrate a maser that is driven by single electron tunneling events. Semiconductor double quantum dots (DQDs) serve as a gain medium and are placed inside of a high quality factor microwave cavity. We verify maser action by comparing the statistics of the emitted microwave field above and below the maser threshold.

Simulating Hamiltonian dynamics with a truncated Taylor series - Dominic W. Berry; Andrew M. Childs; Richard Cleve; Robin Kothari; Rolando D. Somma (Physical Review Letters, 2015)
We describe a simple, efficient method for simulating Hamiltonian dynamics on a quantum computer by approximating the truncated Taylor series of the evolution operator. Our method can simulate the time evolution of a wide variety of physical systems. As in another recent algorithm, the cost of our method depends only logarithmically on the inverse of the desired precision, which is optimal. However, we simplify the algorithm and its analysis by using a method for implementing linear combinations of unitary operations to directly apply the truncated Taylor series.

Tensor network non-zero testing - Sevag Gharibian; Zeph Landau; Seung Woo Shin; Guoming Wang (Quantum Information & Computation, 2015)
Tensor networks are a central tool in condensed matter physics. In this paper, we initiate the study of tensor network non-zero testing (TNZ): Given a tensor network T, does T represent a non-zero vector? We show that TNZ is not in the Polynomial-Time Hierarchy unless the hierarchy collapses. We next show (among other results) that the special cases of TNZ on non-negative and injective tensor networks are in NP. Using this, we make a simple observation: The commuting variant of the MA-complete stoquastic k-SAT problem on D-dimensional qudits is in NP for logarithmic k and constant D. This reveals the first class of quantum Hamiltonians whose commuting variant is known to be in NP for all (1) logarithmic k, (2) constant D, and (3) for arbitrary interaction graphs.

Tunable Spin Qubit Coupling Mediated by a Multi-Electron Quantum Dot - V. Srinivasa; H. Xu; J. M. Taylor (Physical Review Letters, 2015)
We present an approach for entangling electron spin qubits localized on spatially separated impurity atoms or quantum dots via a multi-electron, two-level quantum dot. The effective exchange interaction mediated by the dot can be understood as the simplest manifestation of Ruderman-Kittel-Kasuya-Yosida exchange, and can be manipulated through gate voltage control of level splittings and tunneling amplitudes within the system. This provides both a high degree of tuneability and a means for realizing high-fidelity two-qubit gates between spatially separated spins, yielding an experimentally accessible method of coupling donor electron spins in silicon via a hybrid impurity-dot system.

Universal Subspaces for Local Unitary Groups of Fermionic Systems - Lin Chen; Jianxin Chen; Dragomir Z. Djokovic; Bei Zeng (Communications in Mathematical Physics, 2015)
Let $\mathcal{V}=\wedge^N V$ be the $N$-fermion Hilbert space with $M$-dimensional single particle space $V$ and $2N\le M$. We refer to the unitary group $G$ of $V$ as the local unitary (LU) group. We fix an orthonormal (o.n.) basis $\ket{v_1},...,\ket{v_M}$ of $V$. Then the Slater determinants $e_{i_1,...,i_N}:= \ket{v_{i_1}\we v_{i_2}\we...\we v_{i_N}}$ with $i_1<...<i_N$ form an o.n. basis of $\cV$. Let $\cS\subseteq\cV$ be the subspace spanned by all $e_{i_1,...,i_N}$ such that the set $\{i_1,...,i_N\}$ contains no pair $\{2k-1,2k\}$, $k$ an integer. We say that the $\ket{ψ}\in\cS$ are single occupancy states (with respect to the basis $\ket{v_1},...,\ket{v_M}$). We prove that for N=3 the subspace $\cS$ is universal, i.e., each $G$-orbit in $\cV$ meets $\cS$, and that this is false for N>3. If $M$ is even, the well known BCS states are not LU-equivalent to any single occupancy state. Our main result is that for N=3 and $M$ even there is a universal subspace $\cW\subseteq\cS$ spanned by $M(M-1)(M-5)/6$ states $e_{i_1,...,i_N}$. Moreover the number $M(M-1)(M-5)/6$ is minimal.

Adaptive change of basis in entropy-based moment closures for linear kinetic equations - Graham W. Alldredge; Cory D. Hauck; Dianne P. O'Leary; André L. Tits (Journal of Computational Physics, 2014)
Entropy-based (M_N) moment closures for kinetic equations are defined by a constrained optimization problem that must be solved at every point in a space-time mesh, making it important to solve these optimization problems accurately and efficiently. We present a complete and practical numerical algorithm for solving the dual problem in one-dimensional, slab geometries. The closure is only well-defined on the set of moments that are realizable from a positive underlying distribution, and as the boundary of the realizable set is approached, the dual problem becomes increasingly difficult to solve due to ill-conditioning of the Hessian matrix. To improve the condition number of the Hessian, we advocate the use of a change of polynomial basis, defined using a Cholesky factorization of the Hessian, that permits solution of problems nearer to the boundary of the realizable set. We also advocate a fixed quadrature scheme, rather than adaptive quadrature, since the latter introduces unnecessary expense and changes the computationally realizable set as the quadrature changes. For very ill-conditioned problems, we use regularization to make the optimization algorithm robust. We design a manufactured solution and demonstrate that the adaptive-basis optimization algorithm reduces the need for regularization. This is important since we also show that regularization slows, and even stalls, convergence of the numerical simulation when refining the space-time mesh. We also simulate two well-known benchmark problems. There we find that our adaptive-basis, fixed-quadrature algorithm uses less regularization than alternatives, although differences in the resulting numerical simulations are more sensitive to the regularization strategy than to the choice of basis.

Beyond the spin model approximation for Ramsey spectroscopy - A P Koller; M Beverland; Alexey V. Gorshkov; A M Rey (Phys. Rev. Lett., 2014)

The Bose-Hubbard model is QMA-complete - Andrew M. Childs; David Gosset; Zak Webb (Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), 2014)
The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMA-complete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i.e., hard-core bosons). This feature, along with the well-known mapping between hard-core bosons and spin systems, lets us prove a related result for a class of 2-local Hamiltonians defined by graphs that generalizes the XY model. By avoiding the use of perturbation theory in our analysis, we circumvent the need to multiply terms in the Hamiltonian by large coefficients.

A classical channel model for gravitational decoherence - D. Kafri; J. M. Taylor; G. J. Milburn (New Journal of Physics, 2014)
We show that, by treating the gravitational interaction between two mechanical resonators as a classical measurement channel, a gravitational decoherence model results that is equivalent to a model first proposed by Diosi. The resulting decoherence model implies that the classically mediated gravitational interaction between two gravitationally coupled resonators cannot create entanglement. The gravitational decoherence rate ( and the complementary heating rate) is of the order of the gravitationally induced normal mode splitting of the two resonators.

Classical simulation of Yang-Baxter gates - Gorjan Alagic; Aniruddha Bapat; Stephen P. Jordan (9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014), 2014)
A unitary operator that satisfies the constant Yang-Baxter equation immediately yields a unitary representation of the braid group B n for every $n \ge 2$. If we view such an operator as a quantum-computational gate, then topological braiding corresponds to a quantum circuit. A basic question is when such a representation affords universal quantum computation. In this work, we show how to classically simulate these circuits when the gate in question belongs to certain families of solutions to the Yang-Baxter equation. These include all of the qubit (i.e., $d = 2$) solutions, and some simple families that include solutions for arbitrary $d \ge 2$. Our main tool is a probabilistic classical algorithm for efficient simulation of a more general class of quantum circuits. This algorithm may be of use outside the present setting.

The computational power of matchgates and the XY interaction on arbitrary graphs - Daniel J. Brod; Andrew M. Childs (Quantum Information and Computation, 2014)
Matchgates are a restricted set of two-qubit gates known to be classically simulable when acting on nearest-neighbor qubits on a path, but universal for quantum computation when the qubits are arranged on certain other graphs. Here we characterize the power of matchgates acting on arbitrary graphs. Specifically, we show that they are universal on any connected graph other than a path or a cycle, and that they are classically simulable on a cycle. We also prove the same dichotomy for the XY interaction, a proper subset of matchgates related to some implementations of quantum computing.

The computational power of normalizer circuits over black-box groups - Juan Bermejo-Vega; Cedric Yen-Yu Lin; Maarten Van den Nest (2014)
This work presents a precise connection between Clifford circuits, Shor's factoring algorithm and several other famous quantum algorithms with exponential quantum speed-ups for solving Abelian hidden subgroup problems. We show that all these different forms of quantum computation belong to a common new restricted model of quantum operations that we call black-box normalizer circuits. To define these, we extend the previous model of normalizer circuits [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], which are built of quantum Fourier transforms, group automorphism and quadratic phase gates associated to an Abelian group $G$. In previous works, the group $G$ is always given in an explicitly decomposed form. In our model, we remove this assumption and allow $G$ to be a black-box group. While standard normalizer circuits were shown to be efficiently classically simulable [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], we find that normalizer circuits are powerful enough to factorize and solve classically-hard problems in the black-box setting. We further set upper limits to their computational power by showing that decomposing finite Abelian groups is complete for the associated complexity class. In particular, solving this problem renders black-box normalizer circuits efficiently classically simulable by exploiting the generalized stabilizer formalism in [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208]. Lastly, we employ our connection to draw a few practical implications for quantum algorithm design: namely, we give a no-go theorem for finding new quantum algorithms with black-box normalizer circuits, a universality result for low-depth normalizer circuits, and identify two other complete problems.

Constructing elliptic curve isogenies in quantum subexponential time - Andrew M. Childs; David Jao; Vladimir Soukharev (Journal of Mathematical Cryptology, 2014)
Given two elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit an isogeny between them, but finding such an isogeny is believed to be computationally difficult. The fastest known classical algorithm takes exponential time, and prior to our work no faster quantum algorithm was known. Recently, public-key cryptosystems based on the presumed hardness of this problem have been proposed as candidates for post-quantum cryptography. In this paper, we give a subexponential-time quantum algorithm for constructing isogenies, assuming the Generalized Riemann Hypothesis (but with no other assumptions). Our algorithm is based on a reduction to a hidden shift problem, together with a new subexponential-time algorithm for evaluating isogenies from kernel ideals (under only GRH), and represents the first nontrivial application of Kuperberg's quantum algorithm for the hidden shift problem. This result suggests that isogeny-based cryptosystems may be uncompetitive with more mainstream quantum-resistant cryptosystems such as lattice-based cryptosystems.

Different Strategies for Optimization Using the Quantum Adiabatic Algorithm - Elizabeth Crosson; Edward Farhi; Cedric Yen-Yu Lin; Han-Hsuan Lin; Peter Shor (2014)
We present the results of a numerical study, with 20 qubits, of the performance of the Quantum Adiabatic Algorithm on randomly generated instances of MAX 2-SAT with a unique assignment that maximizes the number of satisfied clauses. The probability of obtaining this assignment at the end of the quantum evolution measures the success of the algorithm. Here we report three strategies which consistently increase the success probability for the hardest instances in our ensemble: decreasing the overall evolution time, initializing the system in excited states, and adding a random local Hamiltonian to the middle of the evolution.

Discrete optimization using quantum annealing on sparse Ising models - Bian, Zhengbing; Chudak, Fabian; Israel, Robert; Brad Lackey; Macready, William G; Roy, Aidan (Frontiers in Physics, 2014)
This paper discusses techniques for solving discrete optimization problems using quantum annealing. Practical issues likely to affect the computation include precision limitations, finite temperature, bounded energy range, sparse connectivity, and small numbers of qubits. To address these concerns we propose a way of finding energy representations with large classical gaps between ground and first excited states, efficient algorithms for mapping non-compatible Ising models into the hardware, and the use of decomposition methods for problems that are too large to fit in hardware. We validate the approach by describing experiments with D-Wave quantum hardware for low density parity check decoding with up to 1000 variables.

"Einstein and Bohr Meet Alice and Bob', Logic and Science Facing the New Technologies - Jeffrey Bub; Peter Schroeder-Heister; Gerhard Heinzmann; Wilfrid Hodges; Pierre Edouard Bour (Proceedings of the 14th Congress for Logic (Nancy), Logic, Methodology and Philosophy of Science, 2014)

Exponential improvement in precision for simulating sparse Hamiltonians - Dominic W. Berry; Andrew M. Childs; Richard Cleve; Robin Kothari; Rolando D. Somma (Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014), 2014)
We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a $d$-sparse Hamiltonian $H$ acting on $n$ qubits can be simulated for time $t$ with precision $\epsilon$ using $O\big(\tau \frac{\log(\tau/\epsilon)}{\log\log(\tau/\epsilon)}\big)$ queries and $O\big(\tau \frac{\log^2(\tau/\epsilon)}{\log\log(\tau/\epsilon)}n\big)$ additional 2-qubit gates, where $\tau = d^2 \|{H}\|_{\max} t$. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.

Extended order parameter and conjugate field for the dynamic phase transition in a Ginzburg-Landau mean-field model in an oscillating field - Daniel T. Robb; Aaron Ostrander (Physical Review E, 2014)
We present numerical evidence for an extended order parameter and conjugate field for the dynamic phase transition in a Ginzburg-Landau mean-field model driven by an oscillating field. The order parameter, previously taken to be the time-averaged magnetization, comprises the deviations of the Fourier components of the magnetization from their values at the critical period. The conjugate field, previously taken to be the time-averaged magnetic field, comprises the even Fourier components of the field. The scaling exponents β and δ associated with the extended order parameter and conjugate field are shown numerically to be consistent with their values in the equilibrium mean-field model.

The Fundamental Gap for a Class of Schrödinger Operators on Path and Hypercube Graphs - Michael Jarret; Stephen P. Jordan (Journal of Mathematical Physics, 2014)
We consider the difference between the two lowest eigenvalues (the fundamental gap) of a Schrödinger operator acting on a class of graphs. In particular, we derive tight bounds for the gap of Schrödinger operators with convex potentials acting on the path graph. Additionally, for the hypercube graph, we derive a tight bound for the gap of Schrödinger operators with convex potentials dependent only upon vertex Hamming weight. Our proof makes use of tools from the literature of the fundamental gap theorem as proved in the continuum combined with techniques unique to the discrete case. We prove the tight bound for the hypercube graph as a corollary to our path graph results.

Hong-Ou-Mandel atom interferometry in tunnel-coupled optical tweezers - A. M. Kaufman; B. J. Lester; C. M. Reynolds; M. L. Wall; Michael Foss-Feig; K. R. A. Hazzard; A. M. Rey; C. A. Regal (Science, 2014)
The quantum statistics of atoms is typically observed in the behavior of an ensemble via macroscopic observables. However, quantum statistics modifies the behavior of even two particles, inducing remarkable consequences that are at the heart of quantum science. Here we demonstrate near-complete control over all the internal and external degrees of freedom of two laser-cooled 87Rb atoms trapped in two optical tweezers. This full controllability allows us to implement a massive-particle analog of a Hong-Ou-Mandel interferometer where atom tunneling plays the role of a photon beamsplitter. We use the interferometer to probe the effect of quantum statistics on the two-atom dynamics under tunable initial conditions, chosen to adjust the degree of atomic indistinguishability. Our work thereby establishes laser-cooled atoms in optical tweezers as a new route to bottom-up engineering of scalable, low-entropy quantum systems.

Kitaev chains with long-range pairing - Davide Vodola; Luca Lepori; Elisa Ercolessi; Alexey V. Gorshkov; Guido Pupillo (Physical Review Letters, 2014)
We propose and analyze a generalization of the Kitaev chain for fermions with long-range $p$-wave pairing, which decays with distance as a power-law with exponent $α$. Using the integrability of the model, we demonstrate the existence of two types of gapped regimes, where correlation functions decay exponentially at short range and algebraically at long range ($α > 1$) or purely algebraically ($α < 1$). Most interestingly, along the critical lines, long-range pairing is found to break conformal symmetry for sufficiently small $α$. This is accompanied by a violation of the area law for the entanglement entropy in large parts of the phase diagram in the presence of a gap, and can be detected via the dynamics of entanglement following a quench. Some of these features may be relevant for current experiments with cold atomic ions.

Many-body dynamics of dipolar molecules in an optical lattice - Kaden R. A. Hazzard; Bryce Gadway; Michael Foss-Feig; Bo Yan; Steven A. Moses; Jacob P. Covey; Norman Y. Yao; Mikhail D. Lukin; Jun Ye; Deborah S. Jin; Ana Maria Rey (Physical Review Letters, 2014)
Understanding the many-body dynamics of isolated quantum systems is one of the central challenges in modern physics. To this end, the direct experimental realization of strongly correlated quantum systems allows one to gain insights into the emergence of complex phenomena. Such insights enable the development of theoretical tools that broaden our understanding. Here, we theoretically model and experimentally probe with Ramsey spectroscopy the quantum dynamics of disordered, dipolar-interacting, ultracold molecules in a partially filled optical lattice. We report the capability to control the dipolar interaction strength, and we demonstrate that the many-body dynamics extends well beyond a nearest-neighbor or mean-field picture, and cannot be quantitatively described using previously available theoretical tools. We develop a novel cluster expansion technique and demonstrate that our theoretical method accurately captures the measured dependence of the spin dynamics on molecule number and on the dipolar interaction strength. In the spirit of quantum simulation, this agreement simultaneously benchmarks the new theoretical method and verifies our microscopic understanding of the experiment. Our findings pave the way for numerous applications in quantum information science, metrology, and condensed matter physics.

Nonequilibrium quantum fluctuations of a dispersive medium: Spontaneous emission, photon statistics, entropy generation, and stochastic motion - Mohammad F. Maghrebi; Robert L. Jaffe; Mehran Kardar (Physical Review A, 2014)
We study the implications of quantum fluctuations of a dispersive medium, under steady rotation, either in or out of thermal equilibrium with its environment. A rotating object exhibits a quantum instability by dissipating its mechanical motion via spontaneous emission of photons, as well as internal heat generation. Universal relations are derived for the radiated energy and angular momentum as trace formulas involving the object's scattering matrix. We also compute the quantum noise by deriving the full statistics of the radiated photons out of thermal and/or dynamic equilibrium. The (entanglement) entropy generation is quantified, and the total entropy is shown to be always increasing. Furthermore, we derive a Fokker-Planck equation governing the stochastic angular motion resulting from the fluctuating back-reaction frictional torque. As a result, we find a quantum limit on the uncertainty of the object's angular velocity in steady rotation. Finally, we show in some detail that a rotating object drags nearby objects, making them spin parallel to its axis of rotation. A scalar toy model is introduced in the first part to simplify the technicalities and ease the conceptual complexities; a detailed discussion of quantum electrodynamics is presented in the second part.

Non-local propagation of correlations in long-range interacting quantum systems - Philip Richerme; Zhe-Xuan Gong; Aaron Lee; Crystal Senko; Jacob Smith; Michael Foss-Feig; Spyridon Michalakis; Alexey V. Gorshkov; Christopher Monroe (Nature, 2014)
The maximum speed with which information can propagate in a quantum many-body system directly affects how quickly disparate parts of the system can become correlated and how difficult the system will be to describe numerically. For systems with only short-range interactions, Lieb and Robinson derived a constant-velocity bound that limits correlations to within a linear effective light cone. However, little is known about the propagation speed in systems with long-range interactions, since the best long-range bound is too loose to give the correct light-cone shape for any known spin model and since analytic solutions rarely exist. In this work, we experimentally determine the spatial and time-dependent correlations of a far-from-equilibrium quantum many-body system evolving under a long-range Ising- or XY-model Hamiltonian. For several different interaction ranges, we extract the shape of the light cone and measure the velocity with which correlations propagate through the system. In many cases we find increasing propagation velocities, which violate the Lieb-Robinson prediction, and in one instance cannot be explained by any existing theory. Our results demonstrate that even modestly-sized quantum simulators are well-poised for studying complicated many-body systems that are intractable to classical computation.

Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems - Juan Bermejo-Vega; Cedric Yen-Yu Lin; Maarten Van den Nest (2014)
$Normalizer circuits$ [1,2] are generalized Clifford circuits that act on arbitrary finite-dimensional systems $\mathcal{H}_{d_1}\otimes ... \otimes \mathcal{H}_{d_n}$ with a standard basis labeled by the elements of a finite Abelian group $G=\mathbb{Z}_{d_1}×... × \mathbb{Z}_{d_n}$. Normalizer gates implement operations associated with the group $G$ and can be of three types: quantum Fourier transforms, group automorphism gates and quadratic phase gates. In this work, we extend the normalizer formalism [1,2] to infinite dimensions, by allowing normalizer gates to act on systems of the form $\mathcal{H}_\mathbb{Z}^{\otimes a}$: each factor $\mathcal{H}_\mathbb{Z}$ has a standard basis labeled by $integers$ $\mathbb{Z}$, and a Fourier basis labeled by $angles$, elements of the circle group $\mathbb{T}$. Normalizer circuits become hybrid quantum circuits acting both on continuous- and discrete-variable systems. We show that infinite-dimensional normalizer circuits can be efficiently simulated classically with a generalized $stabilizer formalism$ for Hilbert spaces associated with groups of the form $\mathbb{Z}^a× \mathbb{T}^b × \mathbb{Z}_{d_1}×...× \mathbb{Z}_{d_n}$. We develop new techniques to track stabilizer-groups based on normal forms for group automorphisms and quadratic functions. We use our normal forms to reduce the problem of simulating normalizer circuits to that of finding general solutions of systems of mixed real-integer linear equations [3] and exploit this fact to devise a robust simulation algorithm: the latter remains efficient even in pathological cases where stabilizer groups become infinite, uncountable and non-compact. The techniques developed in this paper might find applications in the study of fault-tolerant quantum computation with superconducting qubits [4,5].

Optical detection of radio waves through a nanomechanical transducer - T. Bagci; A. Simonsen; S. Schmid; L. G. Villanueva; E. Zeuthen; J. Appel; J. M. Taylor; A. Sørensen; K. Usami; A. Schliesser; E. S. Polzik (Nature, 2014)
Low-loss transmission and sensitive recovery of weak radio-frequency (rf) and microwave signals is an ubiquitous technological challenge, crucial in fields as diverse as radio astronomy, medical imaging, navigation and communication, including those of quantum states. Efficient upconversion of rf-signals to an optical carrier would allow transmitting them via optical fibers dramatically reducing losses, and give access to the mature toolbox of quantum optical techniques, routinely enabling quantum-limited signal detection. Research in the field of cavity optomechanics has shown that nanomechanical oscillators can couple very strongly to either microwave or optical fields. An oscillator accommodating both functionalities would bear great promise as the intermediate platform in a radio-to-optical transduction cascade. Here, we demonstrate such an opto-electro-mechanical transducer utilizing a high-Q nanomembrane. A moderate voltage bias (<10V) is sufficient to induce strong coupling between the voltage fluctuations in a rf resonance circuit and the membrane's displacement, which is simultaneously coupled to light reflected off its metallized surface. The circuit acts as an antenna; the voltage signals it induces are detected as an optical phase shift with quantum-limited sensitivity. The half-wave voltage is in the microvolt range, orders of magnitude below that of standard optical modulators. The noise added by the membrane is suppressed by the electro-mechanical cooperativity C~6800 and has a temperature of 40mK, far below 300K where the entire device is operated. This corresponds to a sensitivity limit as low as 5 pV/Hz^1/2, or -210dBm/Hz in a narrow band around 1 MHz. Our work introduces an entirely new approach to all-optical, ultralow-noise detection of classical electronic signals, and sets the stage for coherent upconversion of low-frequency quantum signals to the optical domain.

Partial-indistinguishability obfuscation using braids - Gorjan Alagic; Stacey Jeffery; Stephen P. Jordan (In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC14), 2014)
An obfuscator is an algorithm that translates circuits into functionally-equivalent similarly-sized circuits that are hard to understand. Efficient obfuscators would have many applications in cryptography. Until recently, theoretical progress has mainly been limited to no-go results. Recent works have proposed the first efficient obfuscation algorithms for classical logic circuits, based on a notion of indistinguishability against polynomial-time adversaries. In this work, we propose a new notion of obfuscation, which we call partial-indistinguishability. This notion is based on computationally universal groups with efficiently computable normal forms, and appears to be incomparable with existing definitions. We describe universal gate sets for both classical and quantum computation, in which our definition of obfuscation can be met by polynomial-time algorithms. We also discuss some potential applications to testing quantum computers. We stress that the cryptographic security of these obfuscators, especially when composed with translation from other gate sets, remains an open question.

Persistence of locality in systems with power-law interactions - Zhe-Xuan Gong; Michael Foss-Feig; Spyridon Michalakis; Alexey V. Gorshkov (Physical Review Letters, 2014)
Motivated by recent experiments with ultra-cold matter, we derive a new bound on the propagation of information in $D$-dimensional lattice models exhibiting $1/r^{α}$ interactions with $α>D$. The bound contains two terms: One accounts for the short-ranged part of the interactions, giving rise to a bounded velocity and reflecting the persistence of locality out to intermediate distances, while the other contributes a power-law decay at longer distances. We demonstrate that these two contributions not only bound but, except at long times, qualitatively reproduce the short- and long-distance dynamical behavior following a local quench in an $XY$ chain and a transverse-field Ising chain. In addition to describing dynamics in numerous intractable long-range interacting lattice models, our results can be experimentally verified in a variety of ultracold-atomic and solid-state systems.

Privacy Amplification in the Isolated Qubits Model - Yi-Kai Liu (Eurocrypt, 2014)
Isolated qubits are a special class of quantum devices, which can be used to implement tamper-resistant cryptographic hardware such as one-time memories (OTM's). Unfortunately, these OTM constructions leak some information, and standard methods for privacy amplification cannot be applied here, because the adversary has advance knowledge of the hash function that the honest parties will use. In this paper we show a stronger form of privacy amplification that solves this problem, using a fixed hash function that is secure against all possible adversaries in the isolated qubits model. This allows us to construct single-bit OTM's which only leak an exponentially small amount of information. We then study a natural generalization of the isolated qubits model, where the adversary is allowed to perform a polynomially-bounded number of entangling gates, in addition to unbounded local operations and classical communication (LOCC). We show that our technique for privacy amplification is also secure in this setting.

Probing many-body interactions in an optical lattice clock - Rey, A M; Alexey V. Gorshkov; Kraus, C V; Martin, M J; Bishof, M; Swallows, M D; Zhang, X; Benko, C; Ye, J; Lemke, N D; Ludlow, A D (Ann. Phys., 2014)

Quantum Algorithms for Curve Fitting - Guoming Wang (2014)
We present quantum algorithms for estimating the best-fit parameters and the quality of least-square curve fitting. The running times of these algorithms are polynomial in logn, d, κ, ν, χ, 1/Φ and 1/ϵ, where n is the number of data points to be fitted, d is the dimension of feature vectors, κ is the condition number of the design matrix, ν and χ are some parameters reflecting the variances of the design matrix and response vector, Φ is the fit quality, and ϵ is the tolerable error. Different from previous quantum algorithms for these tasks, our algorithms do not require the design matrix to be sparse, and they do completely determine the fitted curve. They are developed by combining phase estimation and the density matrix exponentiation technique for dense Hamiltonian simulation.

Quantum Algorithms for Fermionic Quantum Field Theories - Stephen P. Jordan; Keith S. M. Lee; John Preskill (2014)
Extending previous work on scalar field theories, we develop a quantum algorithm to compute relativistic scattering amplitudes in fermionic field theories, exemplified by the massive Gross-Neveu model, a theory in two spacetime dimensions with quartic interactions. The algorithm introduces new techniques to meet the additional challenges posed by the characteristics of fermionic fields, and its run time is polynomial in the desired precision and the energy. Thus, it constitutes further progress towards an efficient quantum algorithm for simulating the Standard Model of particle physics.

Quantum computation of discrete logarithms in semigroups - Andrew M. Childs; Gábor Ivanyos (Journal of Mathematical Cryptology, 2014)
We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor's algorithms for period finding and discrete log as subroutines. Thus proposed cryptosystems based on the presumed hardness of discrete logarithms in semigroups are insecure against quantum attacks. In contrast, we show that some generalizations of the discrete log problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete log problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to $k \ge 2$ generators in a black-box abelian semigroup of order $N$ requires $\tilde Θ(N^{\frac{1}{2}-\frac{1}{2k}})$ quantum queries.

Quantum Computation of Scattering in Scalar Quantum Field Theories - Stephen P. Jordan; Keith S. M. Lee; John Preskill (Quantum Information and Computation, 2014)
Quantum field theory provides the framework for the most fundamental physical theories to be confirmed experimentally, and has enabled predictions of unprecedented precision. However, calculations of physical observables often require great computational complexity and can generally be performed only when the interaction strength is weak. A full understanding of the foundations and rich consequences of quantum field theory remains an outstanding challenge. We develop a quantum algorithm to compute relativistic scattering amplitudes in massive phi-fourth theory in spacetime of four and fewer dimensions. The algorithm runs in a time that is polynomial in the number of particles, their energy, and the desired precision, and applies at both weak and strong coupling. Thus, it offers exponential speedup over existing classical methods at high precision or strong coupling.

Quantum correlations and entanglement in far-from-equilibrium spin systems - Kaden R. A. Hazzard; Mauritz van den Worm; Michael Foss-Feig; Salvatore R. Manmana; Emanuele Dalla Torre; Tilman Pfau; Michael Kastner; Ana Maria Rey (Physical Review A, 2014)
By applying complementary analytic and numerical methods, we investigate the dynamics of spin-$1/2$ XXZ models with variable-range interactions in arbitrary dimensions. The dynamics we consider is initiated from uncorrelated states that are easily prepared in experiments, and can be equivalently viewed as either Ramsey spectroscopy or a quantum quench. Our primary focus is the dynamical emergence of correlations and entanglement in these far-from-equilibrium interacting quantum systems: we characterize these correlations by the entanglement entropy, concurrence, and squeezing, which are inequivalent measures of entanglement corresponding to different quantum resources. In one spatial dimension, we show that the time evolution of correlation functions manifests a non-perturbative dynamic singularity. This singularity is characterized by a universal power-law exponent that is insensitive to small perturbations. Explicit realizations of these models in current experiments using polar molecules, trapped ions, Rydberg atoms, magnetic atoms, and alkaline-earth and alkali atoms in optical lattices, along with the relative merits and limitations of these different systems, are discussed.

Quantum Correlations and the Measurement Problem - Jeffrey Bub (International Journal of Theoretical Physics, 2014)
The transition from classical to quantum mechanics rests on the recognition that the structure of information is not what we thought it was: there are operational, i.e., phenomenal, probabilistic correlations that lie outside the polytope of local correlations. Such correlations cannot be simulated with classical resources, which generate classical correlations represented by the points in a simplex, where the vertices of the simplex represent joint deterministic states that are the common causes of the correlations. The `no go' hidden variable theorems tell us that we can't shoe-horn correlations outside the local polytope into a classical simplex by supposing that something has been left out of the story. The replacement of the classical simplex by the quantum convex set as the structure representing probabilistic correlations is the analogue for quantum mechanics of the replacement of Newton's Euclidean space and time by Minkowski spacetime in special relativity. The nonclassical features of quantum mechanics, including the irreducible information loss on measurement, are generic features of correlations that lie outside the local correlation polytope. This paper is an elaboration of these ideas, and its consequences for the measurement problem of quantum mechanics. A large part of the difficulty is removed by seeing that the inconsistency in reconciling the entangled state at the end of a quantum measurement process with the definiteness of the macroscopic pointer reading and the definiteness of the correlated value of the measured micro-observable is only apparent and depends on a stipulation that is not required by the structure of the quantum possibility space. Replacing this stipulation by an alternative consistent stipulation resolves the problem.

Quantum Interactions with Closed Timelike Curves and Superluminal Signaling - Jeffrey Bub; Allen Stairs (Physical Review A, 2014)
There is now a significant body of results on quantum interactions with closed timelike curves (CTCs) in the quantum information literature, for both the Deutsch model of CTC interactions (D-CTCs) and the projective model (P-CTCs). As a consequence, there is a prima facie argument exploiting entanglement that CTC interactions would enable superluminal and, indeed, effectively instantaneous signaling. In cases of spacelike separation between the sender of a signal and the receiver, whether a receiver measures the local part of an entangled state or a disentangled state to access the signal can depend on the reference frame. We propose a consistency condition that gives priority to either an entangled perspective or a disentangled perspective in spacelike separated scenarios. For D-CTC interactions, the consistency condition gives priority to frames of reference in which the state is disentangled, while for P-CTC interactions the condition selects the entangled state. Using the consistency condition, we show that there is a procedure that allows Alice to signal to Bob in the past via relayed superluminal communications between spacelike separated Alice and Clio, and spacelike separated Clio and Bob. This opens the door to time travel paradoxes in the classical domain. Ralph (arXiv:1107.4675) first pointed this out for P-CTCs, but we show that Ralph's procedure for a 'radio to the past' is flawed. Since both D-CTCs and P-CTCs allow classical information to be sent around a spacetime loop, it follows from a result by Aaronson and Watrous (Proc.Roy.Soc.A, 465:631-647 (2009)) for CTC-enhanced classical computation that a quantum computer with access to P-CTCs would have the power of PSPACE, equivalent to a D-CTC-enhanced quantum computer.

A Quantum Network of Silicon Qubits using Mid-Infrared Graphene Plasmons - Michael Gullans; J. M. Taylor (2014)
We consider a quantum network of mid-infrared, graphene plasmons coupled to the hydrogen-like excited states of group-V donors in silicon. First, we show how to use plasmon-enhanced light-matter interactions to achieve single-shot spin readout of the donor qubits via optical excitation and electrical detection of the emitted plasmons. We then show how plasmons in high mobility graphene nanoribbons can be used to achieve high-fidelity, two-qubit gates and entanglement of distant Si donor qubits. The proposed device is readily compatible with existing technology and fabrication methods.

Quipper: Concrete Resource Estimation in Quantum Algorithms - Jonathan M. Smith; Neil J. Ross; Peter Selinger; Benoît Valiron (2014)
Despite the rich literature on quantum algorithms, there is a surprisingly small amount of coverage of their concrete logical design and implementation. Most resource estimation is done at the level of complexity analysis, but actual concrete numbers (of quantum gates, qubits, etc.) can differ by orders of magnitude. The line of work we present here is a formal framework to write, and reason about, quantum algorithms. Specifically, we designed a language, Quipper, with scalability in mind, and we are able to report actual resource counts for seven non-trivial algorithms found in the quantum computer science literature.

Remote tomography and entanglement swapping via von Neumann–Arthurs–Kelly interaction - S. M. Roy; Abhinav Deshpande; Nitica Sakharwade (Physical Review A, 2014)
We propose an interaction-based method for remote tomography and entanglement swapping. Alice arranges a von Neumann-Arthurs-Kelly interaction between a system particle P and two apparatus particles A1,A2, and then transports the latter to Bob. Bob can reconstruct the unknown initial state of particle P not received by him by quadrature measurements on A1,A2. Further, if another particle P′ in Alice's hands is EPR entangled with P, it will be EPR entangled with the distant pair A1,A2. This method will be contrasted with the usual teleportation protocols.

Robust Extraction of Tomographic Information via Randomized Benchmarking - Shelby Kimmel; Marcus P. da Silva; Colm A. Ryan; Blake R. Johnson; Thomas Ohki (Physical Review X, 2014)
We describe how randomized benchmarking can be used to reconstruct the unital part of any trace-preserving quantum map, which in turn is sufficient for the full characterization of any unitary evolution, or more generally, any unital trace-preserving evolution. This approach inherits randomized benchmarking's robustness to preparation and measurement imperfections, therefore avoiding systematic errors caused by these imperfections. We also extend these techniques to efficiently estimate the average fidelity of a quantum map to unitary maps outside of the Clifford group. The unitaries we consider include operations commonly used to achieve universal quantum computation in a fault-tolerant setting. In addition, we rigorously bound the time and sampling complexities of randomized benchmarking procedures.

Scattering resonances and bound states for strongly interacting Rydberg polaritons - P. Bienias; S. Choi; O. Firstenberg; Mohammad F. Maghrebi; Michael Gullans; M. D. Lukin; Alexey V. Gorshkov; H. P. Büchler (Physical Review A, 2014)
We provide a theoretical framework describing slow-light polaritons interacting via atomic Rydberg states. We use a diagrammatic method to analytically derive the scattering properties of two polaritons. We identify parameter regimes where polariton-polariton interactions are repulsive. Furthermore, in the regime of attractive interactions, we identify multiple two-polariton bound states, calculate their dispersion, and study the resulting scattering resonances. Finally, the two-particle scattering properties allow us to derive the effective low-energy many-body Hamiltonian. This theoretical platform is applicable to ongoing experiments.

Single-shot security for one-time memories in the isolated qubits model - Yi-Kai Liu (CRYPTO, 2014)
One-time memories (OTM's) are simple, tamper-resistant cryptographic devices, which can be used to implement sophisticated functionalities such as one-time programs. Can one construct OTM's whose security follows from some physical principle? This is not possible in a fully-classical world, or in a fully-quantum world, but there is evidence that OTM's can be built using "isolated qubits" -- qubits that cannot be entangled, but can be accessed using adaptive sequences of single-qubit measurements. Here we present new constructions for OTM's using isolated qubits, which improve on previous work in several respects: they achieve a stronger "single-shot" security guarantee, which is stated in terms of the (smoothed) min-entropy; they are proven secure against adversaries who can perform arbitrary local operations and classical communication (LOCC); and they are efficiently implementable. These results use Wiesner's idea of conjugate coding, combined with error-correcting codes that approach the capacity of the q-ary symmetric channel, and a high-order entropic uncertainty relation, which was originally developed for cryptography in the bounded quantum storage model.

Spatial search by continuous-time quantum walks on crystal lattices - Andrew M. Childs; Yimin Ge (Physical Review A, 2014)
We consider the problem of searching a general $d$-dimensional lattice of $N$ vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behaviour near a Dirac point, we develop algorithms that solve the problem in a time of $O(\sqrt N)$ for $d>2$ and $O(\sqrt N \log N)$ in $d=2$. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory.

Spin-orbit-coupled topological Fulde-Ferrell states of fermions in a harmonic trap - Lei Jiang; Eite Tiesinga; Xia-Ji Liu; Hui Hu; Han Pu (Physical Review A, 2014)
Motivated by recent experimental breakthroughs in generating spin-orbit coupling in ultracold Fermi gases using Raman laser beams, we present a systematic study of spin-orbit-coupled Fermi gases confined in a quasi-one-dimensional trap in the presence of an in-plane Zeeman field (which can be realized using a finite two-photon Raman detuning). We find that a topological Fulde-Ferrell state will emerge, featuring finite-momentum Cooper pairing and zero-energy Majorana excitations localized near the edge of the trap based on the self-consistent Bogoliubov-de Genes (BdG) equations. We find analytically the wavefunctions of the Majorana modes. Finally using the time-dependent BdG we show how the finite-momentum pairing field manifests itself in the expansion dynamics of the atomic cloud.

Strong Equivalence of Reversible Circuits is coNP-complete - Stephen P. Jordan (Quantum Information Computation, 2014)
It is well-known that deciding equivalence of logic circuits is a coNP-complete problem. As a corollary, the problem of deciding weak equivalence of reversible circuits, i.e. allowing initialized ancilla bits in the input and ignoring "garbage" ancilla bits in the output, is also coNP-complete. The complexity of deciding strong equivalence, including the ancilla bits, is less obvious and may depend on gate set. Here we use Barrington's theorem to show that deciding strong equivalence of reversible circuits built from the Fredkin gate is coNP-complete. This implies coNP-completeness of deciding strong equivalence for other commonly used universal reversible gate sets, including any gate set that includes the Toffoli or Fredkin gate.
Keywords: complexity; reversible circuits

Suppressing the loss of ultracold molecules via the continuous quantum Zeno effect - Bihui Zhu; Bryce Gadway; Michael Foss-Feig; Johannes Schachenmayer; Michael Wall; Kaden R. A. Hazzard; Bo Yan; Steven A. Moses; Jacob P. Covey; Deborah S. Jin; Jun Ye; Murray Holland; et al. (Physical Review Letters, 2014)
We investigate theoretically the suppression of two-body losses when the on-site loss rate is larger than all other energy scales in a lattice. This work quantitatively explains the recently observed suppression of chemical reactions between two rotational states of fermionic KRb molecules confined in one-dimensional tubes with a weak lattice along the tubes [Yan et al., Nature 501, 521-525 (2013)]. New loss rate measurements performed for different lattice parameters but under controlled initial conditions allow us to show that the loss suppression is a consequence of the combined effects of lattice confinement and the continuous quantum Zeno effect. A key finding, relevant for generic strongly reactive systems, is that while a single-band theory can qualitatively describe the data, a quantitative analysis must include multiband effects. Accounting for these effects reduces the inferred molecule filling fraction by a factor of five. A rate equation can describe much of the data, but to properly reproduce the loss dynamics with a fixed filling fraction for all lattice parameters we develop a mean-field model and benchmark it with numerically exact time-dependent density matrix renormalization group calculations.

Symmetric Extension of Two-Qubit States - Jianxin Chen; Zhengfeng Ji; David Kribs; Norbert Lütkenhaus; Bei Zeng (Physical Review A, 2014)
Quantum key distribution uses public discussion protocols to establish shared secret keys. In the exploration of ultimate limits to such protocols, the property of symmetric extendibility of underlying bipartite states $ρ_{AB}$ plays an important role. A bipartite state $ρ_{AB}$ is symmetric extendible if there exits a tripartite state $ρ_{ABB'}$, such that the $AB$ marginal state is identical to the $AB'$ marginal state, i.e. $ρ_{AB'}=ρ_{AB}$. For a symmetric extendible state $ρ_{AB}$, the first task of the public discussion protocol is to break this symmetric extendibility. Therefore to characterize all bi-partite quantum states that possess symmetric extensions is of vital importance. We prove a simple analytical formula that a two-qubit state $ρ_{AB}$ admits a symmetric extension if and only if $\tr(ρ_B^2)≥ \tr(ρ_{AB}^2)-4\sqrt{\det{ρ_{AB}}}$. Given the intimate relationship between the symmetric extension problem and the quantum marginal problem, our result also provides the first analytical necessary and sufficient condition for the quantum marginal problem with overlapping marginals.

Unextendible Product Basis for Fermionic Systems - Jianxin Chen; Lin Chen; Bei Zeng (Journal of Mathematical Physics, 2014)
We discuss the concept of unextendible product basis (UPB) and generalized UPB for fermionic systems, using Slater determinants as an analogue of product states, in the antisymmetric subspace $\wedge^ N \bC^M$. We construct an explicit example of generalized fermionic unextendible product basis (FUPB) of minimum cardinality $N(M-N)+1$ for any $N\ge2,M\ge4$. We also show that any bipartite antisymmetric space $\wedge^ 2 \bC^M$ of codimension two is spanned by Slater determinants, and the spaces of higher codimension may not be spanned by Slater determinants. Furthermore, we construct an example of complex FUPB of $N=2,M=4$ with minimum cardinality $5$. In contrast, we show that a real FUPB does not exist for $N=2,M=4$ . Finally we provide a systematic construction for FUPBs of higher dimensions using FUPBs and UPBs of lower dimensions.

When the asymptotic limit offers no advantage in the local-operations-and-classical-communication paradigm - Honghao Fu; Debbie Leung; Laura Mancinska (Phys. Rev. A, 2014)
We consider bipartite LOCC, the class of operations implementable by local quantum operations and classical communication between two parties. Surprisingly, there are operations that can be approximated to arbitrary precision but are impossible to implement exactly if only a finite number of messages are exchanged. This significantly complicates the analysis of what can or cannot be approximated with LOCC. Toward alleviating this problem, we exhibit two scenarios in which allowing vanishing error does not help. The first scenario is implementation of projective measurements with product measurement operators. The second scenario is the discrimination of unextendable product bases on two three-dimensional systems.

All-Optical Switch and Transistor Gated by One Stored Photon - Wenlan Chen; Kristin M. Beck; Robert Bücker; Michael Gullans; Mikhail D. Lukin; Haruka Tanji-Suzuki; Vladan Vuletic (Science, 2013)
The realization of an all-optical transistor where one 'gate' photon controls a 'source' light beam, is a long-standing goal in optics. By stopping a light pulse in an atomic ensemble contained inside an optical resonator, we realize a device in which one stored gate photon controls the resonator transmission of subsequently applied source photons. A weak gate pulse induces bimodal transmission distribution, corresponding to zero and one gate photons. One stored gate photon produces fivefold source attenuation, and can be retrieved from the atomic ensemble after switching more than one source photon. Without retrieval, one stored gate photon can switch several hundred source photons. With improved storage and retrieval efficiency, our work may enable various new applications, including photonic quantum gates, and deterministic multiphoton entanglement.

Attractive Photons in a Quantum Nonlinear Medium - Ofer Firstenberg; Thibault Peyronel; Qi-Yu Liang; Alexey V. Gorshkov; Mikhail D. Lukin; Vladan Vuletic (Nature (London), 2013)

Building one-time memories from isolated qubits - Yi-Kai Liu (Innovations in Theoretical Computer Science (ITCS), 2013)
One-time memories (OTM's) are simple tamper-resistant cryptographic devices, which can be used to implement one-time programs, a very general form of software protection and program obfuscation. Here we investigate the possibility of building OTM's using quantum mechanical devices. It is known that OTM's cannot exist in a fully-quantum world or in a fully-classical world. Instead, we propose a new model based on "isolated qubits" -- qubits that can only be accessed using local operations and classical communication (LOCC). This model combines a quantum resource (single-qubit measurements) with a classical restriction (on communication between qubits), and can be implemented using current technologies, such as nitrogen vacancy centers in diamond. In this model, we construct OTM's that are information-theoretically secure against one-pass LOCC adversaries that use 2-outcome measurements. Our construction resembles Wiesner's old idea of quantum conjugate coding, implemented using random error-correcting codes; our proof of security uses entropy chaining to bound the supremum of a suitable empirical process. In addition, we conjecture that our random codes can be replaced by some class of efficiently-decodable codes, to get computationally-efficient OTM's that are secure against computationally-bounded LOCC adversaries. In addition, we construct data-hiding states, which allow an LOCC sender to encode an (n-O(1))-bit messsage into n qubits, such that at most half of the message can be extracted by a one-pass LOCC receiver, but the whole message can be extracted by a general quantum receiver.

Controllable quantum spin glasses with magnetic impurities embedded in quantum solids - Mikhail Lemeshko; Norman Y. Yao; Alexey V. Gorshkov; Hendrik Weimer; Steven D. Bennett; Takamasa Momose; Sarang Gopalakrishnan (Physical Review B, 2013)
Magnetic impurities embedded in inert solids can exhibit long coherence times and interact with one another via their intrinsic anisotropic dipolar interaction. We argue that, as a consequence of these properties, disordered ensembles of magnetic impurities provide an effective platform for realizing a controllable, tunable version of the dipolar quantum spin glass seen in LiHo$_x$Y$_{1-x}$F$_4$. Specifically, we propose and analyze a system composed of dysprosium atoms embedded in solid helium. We describe the phase diagram of the system and discuss the realizability and detectability of the quantum spin glass and antiglass phases.

Controlling the group velocity of colliding atomic Bose-Einstein condensates with Feshbach resonances - Ranchu Mathew; Eite Tiesinga (Physical Review A, 2013)
We report on a proposal to change the group velocity of a small Bose Einstein Condensate (BEC) upon collision with another BEC in analogy to slowing of light passing through dispersive media. We make use of ultracold collisions near a magnetic Feshbach resonance, which gives rise to a sharp variation in scattering length with collision energy and thereby changes the group velocity. A generalized Gross-Pitaveskii equation is derived for a small BEC moving through a larger stationary BEC. We denote the two condensates by laser and medium BEC, respectively, to highlight the analogy to a laser pulse travelling through a medium. We derive an expression for the group velocity in a homogeneous medium as well as for the difference in distance, $δ$, covered by the laser BEC in the presence and absence of a finite-sized medium BEC with a Thomas-Fermi density distribution. For a medium and laser of the same isotopic species, the shift $δ$ has an upper bound of twice the Thomas-Fermi radius of the medium. For typical narrow Feshbach resonances and a medium with number density $10^{15}$ cm$^{-3}$ up to 85% of the upper bound can be achieved, making the effect experimentally observable. We also derive constraints on the experimental realization of our proposal.

Dissipative Many-body Quantum Optics in Rydberg Media - Alexey V. Gorshkov; Rejish Nath; Thomas Pohl (Physical Review Letters, 2013)
We develop a theoretical framework for the dissipative propagation of quantized light in interacting optical media under conditions of electromagnetically induced transparency (EIT). The theory allows us to determine the peculiar spatiotemporal structure of the output of two complementary Rydberg-EIT-based light-processing modules: the recently demonstrated single-photon filter and the recently proposed single-photon subtractor, which, respectively, let through and absorb a single photon. In addition to being crucial for applications of these and other optical quantum devices, the theory opens the door to the study of exotic dissipative many-body dynamics of strongly interacting photons in nonlinear nonlocal media.

Dynamical quantum correlations of Ising models on an arbitrary lattice and their resilience to decoherence - Michael Foss-Feig; Kaden R A Hazzard; John J Bollinger; Ana Maria Rey; Charles W Clark (New Journal of Physics, 2013)
Ising models, and the physical systems described by them, play a central role in generating entangled states for use in quantum metrology and quantum information. In particular, ultracold atomic gases, trapped ion systems, and Rydberg atoms realize long-ranged Ising models, which even in the absence of a transverse field can give rise to highly non-classical dynamics and long-range quantum correlations. In the first part of this paper, we present a detailed theoretical framework for studying the dynamics of such systems driven (at time t=0) into arbitrary unentangled non-equilibrium states, thus greatly extending and unifying the work of Ref. [1]. Specifically, we derive exact expressions for closed-time-path ordered correlation functions, and use these to study experimentally relevant observables, e.g. Bloch vector and spin-squeezing dynamics. In the second part, these correlation functions are then used to derive closed-form expressions for the dynamics of arbitrary spin-spin correlation functions in the presence of both T_1 (spontaneous spin relaxation/excitation) and T_2 (dephasing) type decoherence processes. Even though the decoherence is local, our solution reveals that the competition between Ising dynamics and T_1 decoherence gives rise to an emergent non-local dephasing effect, thereby drastically amplifying the degradation of quantum correlations. In addition to identifying the mechanism of this deleterious effect, our solution points toward a scheme to eliminate it via measurement-based coherent feedback.

Easy and hard functions for the Boolean hidden shift problem - Andrew M. Childs; Robin Kothari; Maris Ozols; Martin Roetteler (Proceedings of TQC 2013, 2013)
We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact one-query algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state; its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem.

Electrically-protected resonant exchange qubits in triple quantum dots - J. M. Taylor; V. Srinivasa; J. Medford (Physical Review Letters, 2013)
We present a modulated microwave approach for quantum computing with qubits comprising three spins in a triple quantum dot. This approach includes single- and two-qubit gates that are protected against low-frequency electrical noise, due to an operating point with a narrowband response to high frequency electric fields. Furthermore, existing double quantum dot advances, including robust preparation and measurement via spin-to-charge conversion, are immediately applicable to the new qubit. Finally, the electric dipole terms implicit in the high frequency coupling enable strong coupling with superconducting microwave resonators, leading to more robust two-qubit gates.

Evasiveness of Graph Properties and Topological Fixed-Point Theorems - Carl Miller (Foundations and Trends in Theoretical Computer Science, 2013)
Many graph properties (e.g., connectedness, containing a complete subgraph) are known to be difficult to check. In a decision-tree model, the cost of an algorithm is measured by the number of edges in the graph that it queries. R. Karp conjectured in the early 1970s that all monotone graph properties are evasive -- that is, any algorithm which computes a monotone graph property must check all edges in the worst case. This conjecture is unproven, but a lot of progress has been made. Starting with the work of Kahn, Saks, and Sturtevant in 1984, topological methods have been applied to prove partial results on the Karp conjecture. This text is a tutorial on these topological methods. I give a fully self-contained account of the central proofs from the paper of Kahn, Saks, and Sturtevant, with no prior knowledge of topology assumed. I also briefly survey some of the more recent results on evasiveness.

Experimental Performance of a Quantum Simulator: Optimizing Adiabatic Evolution and Identifying Many-Body Ground States - Philip Richerme; Crystal Senko; Jacob Smith; Aaron Lee; Simcha Korenblit; Christopher Monroe (Physical Review A, 2013)
We use local adiabatic evolution to experimentally create and determine the ground state spin ordering of a fully-connected Ising model with up to 14 spins. Local adiabatic evolution -- in which the system evolution rate is a function of the instantaneous energy gap -- is found to maximize the ground state probability compared with other adiabatic methods while only requiring knowledge of the lowest $\sim N$ of the $2^N$ Hamiltonian eigenvalues. We also demonstrate that the ground state ordering can be experimentally identified as the most probable of all possible spin configurations, even when the evolution is highly non-adiabatic.

Far from equilibrium quantum magnetism with ultracold polar molecules - Kaden R. A. Hazzard; Salvatore R. Manmana; Michael Foss-Feig; Ana Maria Rey (Physical Review Letters, 2013)
Recent theory has indicated how to emulate tunable models of quantum magnetism with ultracold polar molecules. Here we show that present molecule optical lattice experiments can accomplish three crucial goals for quantum emulation, despite currently being well below unit filling and not quantum degenerate. The first is to verify and benchmark the models proposed to describe these systems. The second is to prepare correlated and possibly useful states in well-understood regimes. The third is to explore many-body physics inaccessible to existing theoretical techniques. Our proposal relies on a non-equilibrium protocol that can be viewed either as Ramsey spectroscopy or an interaction quench. It uses only routine experimental tools available in any ultracold molecule experiment.

Formation and decay of Bose-Einstein condensates in an excited band of a double-well optical lattice - Saurabh Paul; Eite Tiesinga (Physical Review A, 2013)
We study the formation and collision-aided decay of an ultra-cold atomic Bose-Einstein condensate in the first excited band of a double-well 2D-optical lattice with weak harmonic confinement in the perpendicular $z$ direction. This lattice geometry is based on an experiment by Wirth et al. The double well is asymmetric, with the local ground state in the shallow well nearly degenerate with the first excited state of the adjacent deep well. We compare the band structure obtained from a tight-binding (TB) model with that obtained numerically using a plane wave basis. We find the TB model to be in quantitative agreement for the lowest two bands, qualitative for next two bands, and inadequate for even higher bands. The band widths of the excited bands are much larger than the harmonic oscillator energy spacing in the $z$ direction. We then study the thermodynamics of a non-interacting Bose gas in the first excited band. We estimate the condensate fraction and critical temperature, $T_c$, as functions of lattice parameters. For typical atom numbers, the critical energy $k_BT_c$, with $k_B$ the Boltzmann constant, is larger than the excited band widths and harmonic oscillator energy. Using conservation of total energy and atom number, we show that the temperature increases after the lattice transformation. Finally, we estimate the time scale for a two-body collision-aided decay of the condensate as a function of lattice parameters. The decay involves two processes, the dominant one in which both colliding atoms decay to the ground band, and the second involving excitation of one atom to a higher band. For this estimate, we have used TB wave functions for the lowest four bands, and numerical estimates for higher bands. The decay rate rapidly increases with lattice depth, but stays smaller than the tunneling rate between the $s$ and $p$ orbitals in adjacent wells.

A framework for bounding nonlocality of state discrimination - Andrew M. Childs; Debbie Leung; Laura Mancinska; Maris Ozols (Communications in Mathematical Physics, 2013)
We consider the class of protocols that can be implemented by local quantum operations and classical communication (LOCC) between two parties. In particular, we focus on the task of discriminating a known set of quantum states by LOCC. Building on the work in the paper "Quantum nonlocality without entanglement" [BDF+99], we provide a framework for bounding the amount of nonlocality in a given set of bipartite quantum states in terms of a lower bound on the probability of error in any LOCC discrimination protocol. We apply our framework to an orthonormal product basis known as the domino states and obtain an alternative and simplified proof that quantifies its nonlocality. We generalize this result for similar bases in larger dimensions, as well as the "rotated" domino states, resolving a long-standing open question [BDF+99].

Individual Addressing in Quantum Computation through Spatial Refocusing - Chao Shen; Zhe-Xuan Gong; Luming Duan (Physical Review A, 2013)
Separate addressing of individual qubits is a challenging requirement for scalable quantum computation, and crosstalk between operations on neighboring qubits remains as a significant source of noise for current experimental implementation of multi-qubit platforms. We propose a scheme based on spatial refocusing from interference of several coherent laser beams to significantly reduce the crosstalk noise for any type of quantum gates. A general framework is developed for the spatial refocusing technique, in particular with practical Gaussian beams, and we show under typical experimental conditions, the crosstalk-induced infidelity of quantum gates can be reduced by several orders of magnitude with a moderate cost of a few correction laser beams.

Interpolatability distinguishes LOCC from separable von Neumann measurements - Andrew M. Childs; Debbie Leung; Laura Mancinska; Maris Ozols (Journal of Mathematical Physics, 2013)
Local operations with classical communication (LOCC) and separable operations are two classes of quantum operations that play key roles in the study of quantum entanglement. Separable operations are strictly more powerful than LOCC, but no simple explanation of this phenomenon is known. We show that, in the case of von Neumann measurements, the ability to interpolate measurements is an operational principle that sets apart LOCC and separable operations.

An Introduction to Quantum Programming in Quipper - Alexander S. Green; Peter LeFanu Lumsdaine; Neil J. Ross; Peter Selinger; Benoît Valiron (Lecture Notes in Computer Science, 2013)
Quipper is a recently developed programming language for expressing quantum computations. This paper gives a brief tutorial introduction to the language, through a demonstration of how to make use of some of its key features. We illustrate many of Quipper's language features by developing a few well known examples of Quantum computation, including quantum teleportation, the quantum Fourier transform, and a quantum circuit for addition.

Kitaev honeycomb and other exotic spin models with polar molecules - Alexey V. Gorshkov; Kaden R. A. Hazzard; Ana Maria Rey (Molecular Physics, 2013)
We show that ultracold polar molecules pinned in an optical lattice can be used to access a variety of exotic spin models, including the Kitaev honeycomb model. Treating each molecule as a rigid rotor, we use DC electric and microwave fields to define superpositions of rotational levels as effective spin degrees of freedom, while dipole-dipole interactions give rise to interactions between the spins. In particular, we show that, with sufficient microwave control, the interaction between two spins can be written as a sum of five independently controllable Hamiltonian terms proportional to the five rank-2 spherical harmonics Y_{2,q}(theta,phi), where (theta,phi) are the spherical coordinates of the vector connecting the two molecules. To demonstrate the potential of this approach beyond the simplest examples studied in [S. R. Manmana et al., arXiv:1210.5518v2], we focus on the realization of the Kitaev honeycomb model, which can support exotic non-Abelian anyonic excitations. We also discuss the possibility of generating spin Hamiltonians with arbitrary spin S, including those exhibiting SU(N=2S+1) symmetry.

Multilingual Summarization: Dimensionality Reduction and a Step Towards Optimal Term Coverage - John M. Conroy; Sashka T. Davis; Jeff Kubina; Yi-Kai Liu; Dianne P. O'Leary; Judith D. Schlesinger (MultiLing (Workshop on Multilingual Multi-document Summarization), 2013)
In this paper we present three term weighting approaches for multi-lingual document summarization and give results on the DUC 2002 data as well as on the 2013 Multilingual Wikipedia feature articles data set. We introduce a new intervalbounded nonnegative matrix factorization. We use this new method, latent semantic analysis (LSA), and latent Dirichlet allocation (LDA) to give three term-weighting methods for multi-document multi-lingual summarization. Results on DUC and TAC data, as well as on the MultiLing 2013 data, demonstrate that these methods are very promising, since they achieve oracle coverage scores in the range of humans for 6 of the 10 test languages. Finally, we present three term weighting approaches for the MultiLing13 single document summarization task on the Wikipedia featured articles. Our submissions signifi- cantly outperformed the baseline in 19 out of 41 languages.

A noise inequality for classical forces - Dvir Kafri; J. M. Taylor (2013)
Lorentz invariance requires local interactions, with force laws such as the Coulomb interaction arising via virtual exchange of force carriers such as photons. Many have considered the possibility that, at long distances or large mass scales, this process changes in some way to lead to classical behavior. Here we hypothesize that classical behavior could be due to an inability of some force carriers to convey entanglement, a characteristic measure of nonlocal, quantum behavior. We then prove that there exists a local test that allows one to verify entanglement generation, falsifying our hypothesis. Crucially, we show that noise measurements can directly verify entanglement generation. This provides a step forward for a wide variety of experimental systems where traditional entanglement tests are challenging, including entanglement generation by gravity alone between macroscopic torsional oscillators.

Non-equilibrium dynamics of Ising models with decoherence: an exact solution - Michael Foss-Feig; Kaden R. A. Hazzard; John J. Bollinger; Ana Maria Rey (Physical Review A, 2013)
The interplay between interactions and decoherence in many-body systems is of fundamental importance in quantum physics: Decoherence can degrade correlations, but can also give rise to a variety of rich dynamical and steady-state behaviors. We obtain an exact analytic solution for the non-equilibrium dynamics of Ising models with arbitrary interactions and subject to the most general form of local Markovian decoherence. Our solution shows that decoherence affects the relaxation of observables more than predicted by single-particle considerations. It also reveals a dynamical phase transition, specifically a Hopf bifurcation, which is absent at the single-particle level. These calculations are applicable to ongoing quantum information and emulation efforts using a variety of atomic, molecular, optical, and solid-state systems.

Optimal entanglement-assisted one-shot classical communication - Hemenway, Brett; Carl Miller; Shi, Yaoyun; Wootters, Mary (Physical Review A, 2013)
The one-shot success probability of a noisy classical channel for transmitting one classical bit is the optimal probability with which the bit can be successfully sent via a single use of the channel. Prevedel et al. [<a href="http://dx.doi.org/10.1103/PhysRevLett.106.110505" style="box-sizing: border-box; background-image: initial; background-position: 0px 0px; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; color: rgb(50, 148, 216); line-height: inherit; font-family: "Helvetica Neue", Helvetica, Roboto, Arial, sans-serif; font-size: 14px;">Phys. Rev. Lett. 106, 110505 (2011)] recently showed that for a specific channel, this quantity can be increased if the parties using the channel share an entangled quantum state. In this paper, we characterize the optimal entanglement-assisted protocols in terms of the radius of a set of operators associated with the channel. This characterization can be used to construct optimal entanglement-assisted protocols for a given classical channel and to prove the limits of such protocols. As an example, we show that the Prevedel et al. protocol is optimal for two-qubit entanglement. We also prove some tight upper bounds on the improvement that can be obtained from quantum and nonsignaling correlations.

Optimal robust self-testing by binary nonlocal XOR games - Carl Miller; Yaoyun Shi (8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013, 2013)
Self-testing a quantum apparatus means verifying the existence of a certain quantum state as well as the effect of the associated measuring devices based only on the statistics of the measurement outcomes. Robust (i.e., error-tolerant) self-testing quantum apparatuses are critical building blocks for quantum cryptographic protocols that rely on imperfect or untrusted devices. We devise a general scheme for proving optimal robust self-testing properties for tests based on nonlocal binary XOR games. We offer some simplified proofs of known results on self-testing, and also prove some new results.
Keywords: nonlocal games; quantum cryptography; Random number generation; Self-testing

Preparation of Non-equilibrium Nuclear Spin States in Double Quantum Dots - Michael Gullans; J. J. Krich; J. M. Taylor; B. I. Halperin; M. D. Lukin (Physical Review B, 2013)
We theoretically study the dynamic polarization of lattice nuclear spins in GaAs double quantum dots containing two electrons. In our prior work [Phys. Rev. Lett. 104, 226807 (2010)] we identified three regimes of long-term dynamics, 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. In particular, when the dots are different sizes we found that the Overhauser field becomes larger in the smaller dot. Here we present a detailed theoretical analysis of these problems including a model of the polarization dynamics and the development of a new numerical method to efficiently simulate semiclassical central-spin problems. When nuclear spin noise is included, the results agree with our prior work indicating that large difference fields and dark states are stable configurations, while the elimination of the difference field is unstable; however, in the absence of noise we find all three steady states are achieved depending on parameters. These results are in good agreement with dynamic nuclear polarization experiments in double quantum dots.

Prethermalization and dynamical transition in an isolated trapped ion spin chain - Zhe-Xuan Gong; L. -M. Duan (New Journal of Physics, 2013)
We propose an experimental scheme to observe prethermalization and dynamical transition in one-dimensional XY spin chain with long range interaction and inhomogeneous lattice spacing, which can be readily implemented with the recently developed trapped-ion quantum simulator. Local physical observables are found to relax to prethermal values at intermediate time scale, followed by complete relaxation to thermal values at much longer time. The physical origin of prethermalization is explained by spotting a non-trivial structure in lower half of the energy spectrum. The dynamical behavior of the system is shown to cross difference phases when the interaction range is continuously tuned, indicating the existence of dynamical phase transition.

Product Formulas for Exponentials of Commutators - Andrew M. Childs; Nathan Wiebe (Journal of Mathematical Physics, 2013)
We provide a recursive method for constructing product formula approximations to exponentials of commutators, giving the first approximations that are accurate to arbitrarily high order. Using these formulas, we show how to approximate unitary exponentials of (possibly nested) commutators using exponentials of the elementary operators, and we upper bound the number of elementary exponentials needed to implement the desired operation within a given error tolerance. By presenting an algorithm for quantum search using evolution according to a commutator, we show that the scaling of the number of exponentials in our product formulas with the evolution time is nearly optimal. Finally, we discuss applications of our product formulas to quantum control and to implementing anticommutators, providing new methods for simulating many-body interaction Hamiltonians.

Quadrature interferometry for nonequilibrium ultracold bosons in optical lattices - Eite Tiesinga; Philip R. Johnson (Physical Review A, 2013)
We develop an interferometric technique for making time-resolved measurements of field-quadrature operators for nonequilibrium ultracold bosons in optical lattices. The technique exploits the internal state structure of magnetic atoms to create two subsystems of atoms in different spin states and lattice sites. A Feshbach resonance turns off atom-atom interactions in one spin subsystem, making it a well-characterized reference state, while atoms in the other subsystem undergo nonequilibrium dynamics for a variable hold time. Interfering the subsystems via a second beam-splitting operation, time-resolved quadrature measurements on the interacting atoms are obtained by detecting relative spin populations. The technique can provide quadrature measurements for a variety of Hamiltonians and lattice geometries (e.g., cubic, honeycomb, superlattices), including systems with tunneling, spin-orbit couplings using artificial gauge fields, and higher-band effects. Analyzing the special case of a deep lattice with negligible tunneling, we obtain the time evolution of both quadrature observables and their fluctuations. As a second application, we show that the interferometer can be used to measure atom-atom interaction strengths with super-Heisenberg scaling n^(-3/2) in the mean number of atoms per lattice site n, and standard quantum limit scaling M^(-1/2) in the number of lattice sites M. In our analysis, we require M >> 1 and for realistic systems n is small, and therefore the scaling in total atom number N = nM is below the Heisenberg limit; nevertheless, measurements testing the scaling behaviors for interaction-based quantum metrologies should be possible in this system.

Quantum Adversary (Upper) Bound - Shelby Kimmel (Chicago Journal of Theoretical Computer Science, 2013)
We describe a method to upper bound the quantum query complexity of Boolean formula evaluation problems, using fundamental theorems about the general adversary bound. This nonconstructive method can give an upper bound on query complexity without producing an algorithm. For example, we describe an oracle problem which we prove (non-constructively) can be solved in $O(1)$ queries, where the previous best quantum algorithm uses a polylogarithmic number of queries. We then give an explicit $O(1)$-query algorithm for this problem based on span programs.

Quantum Catalysis of Magnetic Phase Transitions in a Quantum Simulator - Philip Richerme; Crystal Senko; Simcha Korenblit; Jacob Smith; Aaron Lee; Rajibul Islam; Wesley C. Campbell; Christopher Monroe (Physical Review Letters, 2013)
We control quantum fluctuations to create the ground state magnetic phases of a classical Ising model with a tunable longitudinal magnetic field using a system of 6 to 10 atomic ion spins. Due to the long-range Ising interactions, the various ground state spin configurations are separated by multiple first-order phase transitions, which in our zero temperature system cannot be driven by thermal fluctuations. We instead use a transverse magnetic field as a quantum catalyst to observe the first steps of the complete fractal devil's staircase, which emerges in the thermodynamic limit and can be mapped to a large number of many-body and energy-optimization problems.

Quantum Cherenkov Radiation and Non-contact Friction - Mohammad F. Maghrebi; Ramin Golestanian; Mehran Kardar (Physical Review A, 2013)
We present a number of arguments to demonstrate that a quantum analog of Cherenkov effect occurs when two dispersive objects are in relative motion. Specifically we show that two semi-infinite plates experience friction beyond a threshold velocity which, in their center-of-mass frame, is the phase speed of light within their medium. The loss in mechanical energy is radiated away through the plates before getting fully absorbed in the form of heat. By deriving various correlation functions inside and outside the two plates, we explicitly compute the radiation, and discuss its dependence on the reference frame.

Quantum Logic between Remote Quantum Registers - Norman Y. Yao; Zhe-Xuan Gong; Chris R. Laumann; Steven D. Bennett; L. -M. Duan; Mikhail D. Lukin; Liang Jiang; Alexey V. Gorshkov (Physical Review A, 2013)
We analyze two approaches to quantum state transfer in solid-state spin systems. First, we consider unpolarized spin-chains and extend previous analysis to various experimentally relevant imperfections, including quenched disorder, dynamical decoherence, and uncompensated long range coupling. In finite-length chains, the interplay between disorder-induced localization and decoherence yields a natural optimal channel fidelity, which we calculate. Long-range dipolar couplings induce a finite intrinsic lifetime for the mediating eigenmode; extensive numerical simulations of dipolar chains of lengths up to L=12 show remarkably high fidelity despite these decay processes. We further consider the extension of the protocol to bosonic systems of coupled oscillators. Second, we introduce a quantum mirror based architecture for universal quantum computing which exploits all of the spins in the system as potential qubits. While this dramatically increases the number of qubits available, the composite operations required to manipulate "dark" spin qubits significantly raise the error threshold for robust operation. Finally, as an example, we demonstrate that eigenmode-mediated state transfer can enable robust long-range logic between spatially separated Nitrogen-Vacancy registers in diamond; numerical simulations confirm that high fidelity gates are achievable even in the presence of moderate disorder.

A quantum many-body spin system in an optical lattice clock - M J Martin; Bishof, M; Swallows, M D; X Zhang; C Benko; J von-Stecher; Alexey V. Gorshkov; Rey, A M; Jun Ye (Science, 2013)

Quantum Nonlinear Optics: Strongly Interacting Photons - Firstenberg, O; Lukin, M D; Peyronel, T; Liang, Q -Y; Vuletic, V; Alexey V. Gorshkov; Hofferberth, S; Pohl, T (Opt. Photonics News, 2013)

Quipper: A Scalable Quantum Programming Language - Alexander S. Green; Peter LeFanu Lumsdaine; Neil J. Ross; Peter Selinger; Benoît Valiron (ACM SIGPLAN Notices, 2013)
The field of quantum algorithms is vibrant. Still, there is currently a lack of programming languages for describing quantum computation on a practical scale, i.e., not just at the level of toy problems. We address this issue by introducing Quipper, a scalable, expressive, functional, higher-order quantum programming language. Quipper has been used to program a diverse set of non-trivial quantum algorithms, and can generate quantum gate representations using trillions of gates. It is geared towards a model of computation that uses a classical computer to control a quantum device, but is not dependent on any particular model of quantum hardware. Quipper has proven effective and easy to use, and opens the door towards using formal methods to analyze quantum algorithms.

Realizing Fractional Chern Insulators with Dipolar Spins - Norman Y. Yao; Alexey V. Gorshkov; Chris R. Laumann; Andreas M. Läuchli; Jun Ye; Mikhail D. Lukin (Physical Review Letters, 2013)
Strongly correlated quantum systems can exhibit exotic behavior controlled by topology. We predict that the ν=1/2 fractional Chern insulator arises naturally in a two-dimensional array of driven, dipolar-interacting spins. As a specific implementation, we analyze how to prepare and detect synthetic gauge potentials for the rotational excitations of ultra-cold polar molecules trapped in a deep optical lattice. While the orbital motion of the molecules is pinned, at finite densities, the rotational excitations form a fractional Chern insulator. We present a detailed experimental blueprint for KRb, and demonstrate that the energetics are consistent with near-term capabilities. Prospects for the realization of such phases in solid-state dipolar systems are discussed as are their possible applications.

The Resonant Exchange Qubit - J. Medford; J. Beil; J. M. Taylor; E. I. Rashba; H. Lu; A. C. Gossard; C. M. Marcus (Physical Review Letters, 2013)
We introduce a solid-state qubit in which exchange interactions among confined electrons provide both the static longitudinal field and the oscillatory transverse field, allowing rapid and full qubit control via rf gate-voltage pulses. We demonstrate two-axis control at a detuning sweet-spot, where leakage due to hyperfine coupling is suppressed by the large exchange gap. A π/2-gate time of 2.5 ns and a coherence time of 19 μs, using multi-pulse echo, are also demonstrated. Model calculations that include effects of hyperfine noise are in excellent quantitative agreement with experiment.

A Scattering Approach to the Dynamical Casimir Effect - Mohammad F. Maghrebi; Ramin Golestanian; Mehran Kardar (Physical Review D, 2013)
We develop a unified scattering approach to dynamical Casimir problems which can be applied to both accelerating boundaries, as well as dispersive objects in relative motion. A general (trace) formula is derived for the radiation from accelerating boundaries. Applications are provided for objects with different shapes in various dimensions, and undergoing rotational or linear motion. Within this framework, photon generation is discussed in the context of a modulated optical mirror. For dispersive objects, we find general results solely in terms of the scattering matrix. Specifically, we discuss the vacuum friction on a rotating object, and the friction on an atom moving parallel to a surface.

Self-Consistent Measurement and State Tomography of an Exchange-Only Spin Qubit - J. Medford; J. Beil; J. M. Taylor; S. D. Bartlett; A. C. Doherty; E. I. Rashba; D. P. DiVincenzo; H. Lu; A. C. Gossard; C. M. Marcus (Nature Nanotechnology, 2013)
We report initialization, complete electrical control, and single-shot readout of an exchange-only spin qubit. Full control via the exchange interaction is fast, yielding a demonstrated 75 qubit rotations in under 2 ns. Measurement and state tomography are performed using a maximum-likelihood estimator method, allowing decoherence, leakage out of the qubit state space, and measurement fidelity to be quantified. The methods developed here are generally applicable to systems with state leakage, noisy measurements, and non-orthogonal control axes.

Single-photon nonlinear optics with graphene plasmons - Michael Gullans; D. E. Chang; F. H. L. Koppens; F. J. García de Abajo; M. D. Lukin (Physical Review Letters, 2013)
We show that it is possible to realize significant nonlinear optical interactions at the few photon level in graphene nanostructures. Our approach takes advantage of the electric field enhancement associated with the strong confinement of graphene plasmons and the large intrinsic nonlinearity of graphene. Such a system could provide a powerful platform for quantum nonlinear optical control of light. As an example, we consider an integrated optical device that exploits this large nonlinearity to realize a single photon switch.

Soliton dynamics of an atomic spinor condensate on a Ring Lattice - Indubala I Satija; Carlos L. Pando; Eite Tiesinga (Physical Review A, 2013)
We study the dynamics of macroscopically-coherent matter waves of an ultra-cold atomic spin-one or spinor condensate on a ring lattice of six sites and demonstrate a novel type of spatio-temporal internal Josephson effect. Using a discrete solitary mode of uncoupled spin components as an initial condition, the time evolution of this many-body system is found to be characterized by two dominant frequencies leading to quasiperiodic dynamics at various sites. The dynamics of spatially-averaged and spin-averaged degrees of freedom, however, is periodic enabling an unique identification of the two frequencies. By increasing the spin-dependent atom-atom interaction strength we observe a resonance state, where the ratio of the two frequencies is a characteristic integer multiple and the spin-and-spatial degrees of freedom oscillate in "unison". Crucially, this resonant state is found to signal the onset to chaotic dynamics characterized by a broad band spectrum. In a ferromagnetic spinor condensate with attractive spin-dependent interactions, the resonance is accompanied by a transition from oscillatory- to rotational-type dynamics as the time evolution of the relative phase of the matter wave of the individual spin projections changes from bounded to unbounded.

Spinor dynamics in an antiferromagnetic spin-1 thermal Bose gas - Hyewon K. Pechkis; Jonathan P. Wrubel; Arne Schwettmann; Paul F. Griffin; Ryan Barnett; Eite Tiesinga; Paul D. Lett (Physical Review Letters, 2013)
We present experimental observations of coherent spin-population oscillations in a cold thermal, Bose gas of spin-1 sodium-23 atoms. The population oscillations in a multi-spatial-mode thermal gas have the same behavior as those observed in a single-spatial-mode antiferromagnetic spinor Bose Einstein condensate. We demonstrate this by showing that the two situations are described by the same dynamical equations, with a factor of two change in the spin-dependent interaction coefficient, which results from the change to particles with distinguishable momentum states in the thermal gas. We compare this theory to the measured spin population evolution after times up to a few hundreds of ms, finding quantitative agreement with the amplitude and period. We also measure the damping time of the oscillations as a function of magnetic field.

Symmetries of Codeword Stabilized Quantum Codes - Salman Beigi; Jianxin Chen; Markus Grassl; Zhengfeng Ji; Qiang Wang; Bei Zeng (8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), 2013)
Symmetry is at the heart of coding theory. Codes with symmetry, especially cyclic codes, play an essential role in both theory and practical applications of classical error-correcting codes. Here we examine symmetry properties for codeword stabilized (CWS) quantum codes, which is the most general framework for constructing quantum error-correcting codes known to date. A CWS code Q can be represented by a self-dual additive code S and a classical code C, i.,e., Q=(S,C), however this representation is in general not unique. We show that for any CWS code Q with certain permutation symmetry, one can always find a self-dual additive code S with the same permutation symmetry as Q such that Q=(S,C). As many good CWS codes have been found by starting from a chosen S, this ensures that when trying to find CWS codes with certain permutation symmetry, the choice of S with the same symmetry will suffice. A key step for this result is a new canonical representation for CWS codes, which is given in terms of a unique decomposition as union stabilizer codes. For CWS codes, so far mainly the standard form (G,C) has been considered, where G is a graph state. We analyze the symmetry of the corresponding graph of G, which in general cannot possess the same permutation symmetry as Q. We show that it is indeed the case for the toric code on a square lattice with translational symmetry, even if its encoding graph can be chosen to be translational invariant.

Testing quantum expanders is co-QMA-complete - Adam D. Bookatz; Stephen P. Jordan; Yi-Kai Liu; Pawel Wocjan (Physical Review A, 2013)
A quantum expander is a unital quantum channel that is rapidly mixing, has only a few Kraus operators, and can be implemented efficiently on a quantum computer. We consider the problem of estimating the mixing time (i.e., the spectral gap) of a quantum expander. We show that this problem is co-QMA-complete. This has applications to testing randomized constructions of quantum expanders, and studying thermalization of open quantum systems.

A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates - Andrew M. Childs; Stacey Jeffery; Robin Kothari; Frederic Magniez (2013)
We present an extension to the quantum walk search framework that facilitates quantum walks with nested updates. We apply it to give a quantum walk algorithm for 3-Distinctness with query complexity ~O(n^{5/7}), matching the best known upper bound (obtained via learning graphs) up to log factors. Furthermore, our algorithm has time complexity ~O(n^{5/7}), improving the previous ~O(n^{3/4}).

Topological phases in ultracold polar-molecule quantum magnets - Salvatore R. Manmana; E. M. Stoudenmire; Kaden R. A. Hazzard; Ana Maria Rey; Alexey V. Gorshkov (Physical Review B, 2013)
We show how to use polar molecules in an optical lattice to engineer quantum spin models with arbitrary spin S >= 1/2 and with interactions featuring a direction-dependent spin anisotropy. This is achieved by encoding the effective spin degrees of freedom in microwave-dressed rotational states of the molecules and by coupling the spins through dipolar interactions. We demonstrate how one of the experimentally most accessible anisotropies stabilizes symmetry protected topological phases in spin ladders. Using the numerically exact density matrix renormalization group method, we find that these interacting phases -- previously studied only in the nearest-neighbor case -- survive in the presence of long-range dipolar interactions. We also show how to use our approach to realize the bilinear-biquadratic spin-1 and the Kitaev honeycomb models. Experimental detection schemes and imperfections are discussed.

Topologically Protected Quantum State Transfer in a Chiral Spin Liquid - Norman Y. Yao; Chris R. Laumann; Alexey V. Gorshkov; Hendrik Weimer; Liang Jiang; J. Ignacio Cirac; Peter Zoller; Mikhail D. Lukin (Nature Communications, 2013)
Topology plays a central role in ensuring the robustness of a wide variety of physical phenomena. Notable examples range from the robust current carrying edge states associated with the quantum Hall and the quantum spin Hall effects to proposals involving topologically protected quantum memory and quantum logic operations. Here, we propose and analyze a topologically protected channel for the transfer of quantum states between remote quantum nodes. In our approach, state transfer is mediated by the edge mode of a chiral spin liquid. We demonstrate that the proposed method is intrinsically robust to realistic imperfections associated with disorder and decoherence. Possible experimental implementations and applications to the detection and characterization of spin liquid phases are discussed.

Uniqueness of Quantum States Compatible with Given Measurement Results - Jianxin Chen; Hillary Dawkins; Zhengfeng Ji; Nathaniel Johnston; David Kribs; Frederic Shultz; Bei Zeng (Physical Review A, 2013)
We discuss the uniqueness of quantum states compatible with given results for measuring a set of observables. For a given pure state, we consider two different types of uniqueness: (1) no other pure state is compatible with the same measurement results and (2) no other state, pure or mixed, is compatible with the same measurement results. For case (1), it is known that for a d-dimensional Hilbert space, there exists a set of 4d-5 observables that uniquely determines any pure state. We show that for case (2), 5d-7 observables suffice to uniquely determine any pure state. Thus there is a gap between the results for (1) and (2), and we give some examples to illustrate this. The case of observables corresponding to reduced density matrices (RDMs) of a multipartite system is also discussed, where we improve known bounds on local dimensions for case (2) in which almost all pure states are uniquely determined by their RDMs. We further discuss circumstances where (1) can imply (2). We use convexity of the numerical range of operators to show that when only two observables are measured, (1) always implies (2). More generally, if there is a compact group of symmetries of the state space which has the span of the observables measured as the set of fixed points, then (1) implies (2). We analyze the possible dimensions for the span of such observables. Our results extend naturally to the case of low rank quantum states.

Universal computation by multi-particle quantum walk - Andrew M. Childs; David Gosset; Zak Webb (Science, 2013)
A quantum walk is a time-homogeneous quantum-mechanical process on a graph defined by analogy to classical random walk. The quantum walker is a particle that moves from a given vertex to adjacent vertices in quantum superposition. Here we consider a generalization of quantum walk to systems with more than one walker. A continuous-time multi-particle quantum walk is generated by a time-independent Hamiltonian with a term corresponding to a single-particle quantum walk for each particle, along with an interaction term. Multi-particle quantum walk includes a broad class of interacting many-body systems such as the Bose-Hubbard model and systems of fermions or distinguishable particles with nearest-neighbor interactions. We show that multi-particle quantum walk is capable of universal quantum computation. Since it is also possible to efficiently simulate a multi-particle quantum walk of the type we consider using a universal quantum computer, this model exactly captures the power of quantum computation. In principle our construction could be used as an architecture for building a scalable quantum computer with no need for time-dependent control.

Universal Entanglers for Bosonic and Fermionic Systems - Joel Klassen; Jianxin Chen; Bei Zeng (2013)
A universal entangler (UE) is a unitary operation which maps all pure product states to entangled states. It is known that for a bipartite system of particles $1,2$ with a Hilbert space $\mathbb{C}^{d_1}\otimes\mathbb{C}^{d_2}$, a UE exists when $\min{(d_1,d_2)}≥ 3$ and $(d_1,d_2)≠ (3,3)$. It is also known that whenever a UE exists, almost all unitaries are UEs; however to verify whether a given unitary is a UE is very difficult since solving a quadratic system of equations is NP-hard in general. This work examines the existence and construction of UEs of bipartite bosonic/fermionic systems whose wave functions sit in the symmetric/antisymmetric subspace of $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$. The development of a theory of UEs for these types of systems needs considerably different approaches from that used for UEs of distinguishable systems. This is because the general entanglement of identical particle systems cannot be discussed in the usual way due to the effect of (anti)-symmetrization which introduces "pseudo entanglement" that is inaccessible in practice. We show that, unlike the distinguishable particle case, UEs exist for bosonic/fermionic systems with Hilbert spaces which are symmetric (resp. antisymmetric) subspaces of $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ if and only if $d≥ 3$ (resp. $d≥ 8$). To prove this we employ algebraic geometry to reason about the different algebraic structures of the bosonic/fermionic systems. Additionally, due to the relatively simple coherent state form of unentangled bosonic states, we are able to give the explicit constructions of two bosonic UEs. Our investigation provides insight into the entanglement properties of systems of indisitinguishable particles, and in particular underscores the difference between the entanglement structures of bosonic, fermionic and distinguishable particle systems.

Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems - Stephen P. Jordan; Hirotada Kobayashi; Daniel Nagaj; Harumichi Nishimura (Quantum Information and Computation, 2012)
This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, QCMA = QCMA1. This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, e.g., {Hadamard, Toffoli, NOT}. The proof is quantumly nonrelativizing, and uses a simple but novel quantum technique that additively adjusts the success probability, which may be of independent interest.

Algorithmic Cooling of a Quantum Simulator - Dvir Kafri; J. M. Taylor (2012)
Controlled quantum mechanical devices provide a means of simulating more complex quantum systems exponentially faster than classical computers. Such "quantum simulators" rely heavily upon being able to prepare the ground state of Hamiltonians, whose properties can be used to calculate correlation functions or even the solution to certain classical computations. While adiabatic preparation remains the primary means of producing such ground states, here we provide a different avenue of preparation: cooling to the ground state via simulated dissipation. This is in direct analogy to contemporary efforts to realize generalized forms of simulated annealing in quantum systems.

Anisotropy induced Feshbach resonances in a quantum dipolar gas of magnetic atoms - Alexander Petrov; Eite Tiesinga; Svetlana Kotochigova (Physical Review Letters, 2012)
We explore the anisotropic nature of Feshbach resonances in the collision between ultracold magnetic submerged-shell dysprosium atoms, which can only occur due to couplings to rotating bound states. This is in contrast to well-studied alkali-metal atom collisions, where most Feshbach resonances are hyperfine induced and due to rotation-less bound states. Our novel first-principle coupled-channel calculation of the collisions between open-4f-shell spin-polarized bosonic dysprosium reveals a striking correlation between the anisotropy due to magnetic dipole-dipole and electrostatic interactions and the Feshbach spectrum as a function of an external magnetic field. Over a 20 mT magnetic field range we predict about a dozen Feshbach resonances and show that the resonance locations are exquisitely sensitive to the dysprosium isotope.

On Beating the Hybrid Argument - Bill Fefferman; Ronen Shaltiel; Christopher Umans; Emanuele Viola (Proceedings, ITCS, 2012)
The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor k equal to the bit-length of the distributions: -distinguishability implies only /k-predictability. This paper studies the consequences of avoiding this loss – what we call “beating the hybrid argument” – and develops new proof techniques that circumvent the loss in certain natural settings. Specifically, we obtain the following results: 1. We give an instantiation of the Nisan-Wigderson generator (JCSS ’94) that can be broken by quantum computers, and that is o(1)-unpredictable against AC0 . This is not enough to imply indistinguishability via the hybrid argument because of the hybrid-argument loss; nevertheless, we conjecture that this generator indeed fools AC0 , and we prove this statement for a simplified version of the problem. Our conjecture implies the existence of an oracle relative to which BQP is not in the PH, a longstanding open problem. 2. We show that the “INW” generator by Impagliazzo, Nisan, and Wigderson (STOC ’94) with seed length O(log n log log n) produces a distribution that is 1/ log n-unpredictable against poly-logarithmic width (general) read-once oblivious branching programs. Thus avoiding the hybrid-argument loss would lead to a breakthrough in generators against small space. 3. We study pseudorandom generators obtained from a hard function by repeated sampling. We identify a property of functions, “resamplability,” that allows us to beat the hybrid argument, leading to new pseudorandom generators for AC0 [p] and similar classes. Although the generators have sub-linear stretch, they represent the best-known generators for these classes. Thus we establish that “beating” or bypassing the hybrid argument would have two significant consequences in complexity, and we take steps toward that goal by developing techniques that indeed beat the hybrid argument in related (but simpler) settings, leading to best-known PRGs for certain complexity classes.

Cavity QED with atomic mirrors - D E Chang; Jiang, L; Alexey V. Gorshkov; H J Kimble (New J. Phys., 2012)

Comment on some results of Erdahl and the convex structure of reduced density matrices - Jianxin Chen; Zhengfeng Ji; Mary Beth Ruskai; Bei Zeng; Duan-Lu Zhou (Journal of Mathematical Physics, 2012)
In J. Math. Phys. 13, 1608-1621 (1972), Erdahl considered the convex structure of the set of $N$-representable 2-body reduced density matrices in the case of fermions. Some of these results have a straightforward extension to the $m$-body setting and to the more general quantum marginal problem. We describe these extensions, but can not resolve a problem in the proof of Erdahl's claim that every extreme point is exposed in finite dimensions. Nevertheless, we can show that when $2m ≥ N$ every extreme point of the set of $N$-representable $m$-body reduced density matrices has a unique pre-image in both the symmetric and anti-symmetric setting. Moreover, this extends to the quantum marginal setting for a pair of complementary $m$-body and $(N-m)$-body reduced density matrices.

Correlations in excited states of local Hamiltonians - Jianxin Chen; Zhengfeng Ji; Zhaohui Wei; Bei Zeng (Physical Review A, 2012)
Physical properties of the ground and excited states of a $k$-local Hamiltonian are largely determined by the $k$-particle reduced density matrices ($k$-RDMs), or simply the $k$-matrix for fermionic systems---they are at least enough for the calculation of the ground state and excited state energies. Moreover, for a non-degenerate ground state of a $k$-local Hamiltonian, even the state itself is completely determined by its $k$-RDMs, and therefore contains no genuine ${>}k$-particle correlations, as they can be inferred from $k$-particle correlation functions. It is natural to ask whether a similar result holds for non-degenerate excited states. In fact, for fermionic systems, it has been conjectured that any non-degenerate excited state of a 2-local Hamiltonian is simultaneously a unique ground state of another 2-local Hamiltonian, hence is uniquely determined by its 2-matrix. And a weaker version of this conjecture states that any non-degenerate excited state of a 2-local Hamiltonian is uniquely determined by its 2-matrix among all the pure $n$-particle states. We construct explicit counterexamples to show that both conjectures are false. It means that correlations in excited states of local Hamiltonians could be dramatically different from those in ground states. We further show that any non-degenerate excited state of a $k$-local Hamiltonian is a unique ground state of another $2k$-local Hamiltonian, hence is uniquely determined by its $2k$-RDMs (or $2k$-matrix).

The equilibrium states of open quantum systems in the strong coupling regime - Y. Subasi; C. H. Fleming; J. M. Taylor; B. L. Hu (Physical Review E, 2012)
In this work we investigate the late-time stationary states of open quantum systems coupled to a thermal reservoir in the strong coupling regime. In general such systems do not necessarily relax to a Boltzmann distribution if the coupling to the thermal reservoir is non-vanishing or equivalently if the relaxation timescales are finite. Using a variety of non-equilibrium formalisms valid for non-Markovian processes, we show that starting from a product state of the closed system = system + environment, with the environment in its thermal state, the open system which results from coarse graining the environment will evolve towards an equilibrium state at late-times. This state can be expressed as the reduced state of the closed system thermal state at the temperature of the environment. For a linear (harmonic) system and environment, which is exactly solvable, we are able to show in a rigorous way that all multi-time correlations of the open system evolve towards those of the closed system thermal state. Multi-time correlations are especially relevant in the non-Markovian regime, since they cannot be generated by the dynamics of the single-time correlations. For more general systems, which cannot be exactly solved, we are able to provide a general proof that all single-time correlations of the open system evolve to those of the closed system thermal state, to first order in the relaxation rates. For the special case of a zero-temperature reservoir, we are able to explicitly construct the reduced closed system thermal state in terms of the environmental correlations.

From Ground States to Local Hamiltonians - Jianxin Chen; Zhengfeng Ji; Bei Zeng; D. L. Zhou (Physical Review A, 2012)
Traditional quantum physics solves ground states for a given Hamiltonian, while quantum information science asks for the existence and construction of certain Hamiltonians for given ground states. In practical situations, one would be mainly interested in local Hamiltonians with certain interaction patterns, such as nearest neighbour interactions on some type of lattices. A necessary condition for a space $V$ to be the ground-state space of some local Hamiltonian with a given interaction pattern, is that the maximally mixed state supported on $V$ is uniquely determined by its reduced density matrices associated with the given pattern, based on the principle of maximum entropy. However, it is unclear whether this condition is in general also sufficient. We examine the situations for the existence of such a local Hamiltonian to have $V$ satisfying the necessary condition mentioned above as its ground-state space, by linking to faces of the convex body of the local reduced states. We further discuss some methods for constructing the corresponding local Hamiltonians with given interaction patterns, mainly from physical points of view, including constructions related to perturbation methods, local frustration-free Hamiltonians, as well as thermodynamical ensembles.

Full Abstraction for Set-Based Models of the Symmetric Interaction Combinators - Damiano Mazza; Neil J. Ross (Proceedings of the 15th International Conference on Foundations of Software Science and Computation Structures, 2012)
The symmetric interaction combinators are a model of distributed and deterministic computation based on Lafont’s interaction nets, a special form of graph rewriting. The interest of the symmetric interaction combinators lies in their universality, that is, the fact that they may encode all other interaction net systems; for instance, several implementations of the lambda-calculus in the symmetric interaction combinators exist, related to Lamping’s sharing graphs for optimal reduction. A certain number of observational equivalences were introduced for this system, by Lafont, Fernandez and Mackie, and the first author. In this paper, we study the problem of full abstraction with respect to one of these equivalences, using a class of very simple denotational models based on pointed sets.

On Galilean connections and the first jet bundle - Grant, James DE; Brad Lackey (Central European Journal of Mathematics, 2012)
We see how the first jet bundle of curves into affine space can be realized as a homogeneous space of the Galilean group. Cartan connections with this model are precisely the geometric structure of second-order ordinary differential equations under time-preserving transformations — sometimes called KCC-theory. With certain regularity conditions, we show that any such Cartan connection induces “laboratory” coordinate systems, and the geodesic equations in this coordinates form a system of second-order ordinary differential equations. We then show the converse — the “fundamental theorem” — that given such a coordinate system, and a system of second order ordinary differential equations, there exists regular Cartan connections yielding these, and such connections are completely determined by their torsion.

Gluon chain formation in presence of static charges - Aaron Ostrander; Santopinto, E.; Szczepaniak, A. P.; Vassallo, A. (Physical Review D, 2012)
We consider the origins of the gluon chain model. The model serves as a realization of the dynamics of the chromoelectric flux between static quark-antiquark sources. The derivation is based on the large-NC limit of the Coulomb gauge Hamiltonian in the presence of a background field introduced to model magnetic charge condensation inducing electric confinement.

Ground-State Spaces of Frustration-Free Hamiltonians - Jianxin Chen; Zhengfeng Ji; David Kribs; Zhaohui Wei; Bei Zeng (Journal of Mathematical Physics, 2012)
We study the ground-state space properties for frustration-free Hamiltonians. We introduce a concept of `reduced spaces' to characterize local structures of ground-state spaces. For a many-body system, we characterize mathematical structures for the set $Θ_k$ of all the $k$-particle reduced spaces, which with a binary operation called join forms a semilattice that can be interpreted as an abstract convex structure. The smallest nonzero elements in $Θ_k$, called atoms, are analogs of extreme points. We study the properties of atoms in $Θ_k$ and discuss its relationship with ground states of $k$-local frustration-free Hamiltonians. For spin-1/2 systems, we show that all the atoms in $Θ_2$ are unique ground states of some 2-local frustration-free Hamiltonians. Moreover, we show that the elements in $Θ_k$ may not be the join of atoms, indicating a richer structure for $Θ_k$ beyond the convex structure. Our study of $Θ_k$ deepens the understanding of ground-state space properties for frustration-free Hamiltonians, from a new angle of reduced spaces.

Hamiltonian Simulation Using Linear Combinations of Unitary Operations - Andrew M. Childs; Nathan Wiebe (Quantum Information and Computation, 2012)
We present a new approach to simulating Hamiltonian dynamics based on implementing linear combinations of unitary operations rather than products of unitary operations. The resulting algorithm has superior performance to existing simulation algorithms based on product formulas and, most notably, scales better with the simulation error than any known Hamiltonian simulation technique. Our main tool is a general method to nearly deterministically implement linear combinations of nearby unitary operations, which we show is optimal among a large class of methods.

Levinson's theorem for graphs II - Andrew M. Childs; David Gosset (Journal of Mathematical Physics, 2012)
We prove Levinson's theorem for scattering on an (m+n)-vertex graph with n semi-infinite paths each attached to a different vertex, generalizing a previous result for the case n=1. This theorem counts the number of bound states in terms of the winding of the determinant of the S-matrix. We also provide a proof that the bound states and incoming scattering states of the Hamiltonian together form a complete basis for the Hilbert space, generalizing another result for the case n=1.

Long-lived dipolar molecules and Feshbach molecules in a 3D optical lattice - Amodsen Chotia; Brian Neyenhuis; Steven A. Moses; Bo Yan; Jacob P. Covey; Michael Foss-Feig; Ana Maria Rey; Deborah S. Jin; Jun Ye (Physical Review Letters, 2012)
We have realized long-lived ground-state polar molecules in a 3D optical lattice, with a lifetime of up to 25 s, which is limited only by off-resonant scattering of the trapping light. Starting from a 2D optical lattice, we observe that the lifetime increases dramatically as a small lattice potential is added along the tube-shaped lattice traps. The 3D optical lattice also dramatically increases the lifetime for weakly bound Feshbach molecules. For a pure gas of Feshbach molecules, we observe a lifetime of >20 s in a 3D optical lattice; this represents a 100-fold improvement over previous results. This lifetime is also limited by off-resonant scattering, the rate of which is related to the size of the Feshbach molecule. Individually trapped Feshbach molecules in the 3D lattice can be converted to pairs of K and Rb atoms and back with nearly 100% efficiency.

Minimum Entangling Power is Close to Its Maximum - Jianxin Chen; Zhengfeng Ji; David W Kribs; Bei Zeng (2012)
Given a quantum gate $U$ acting on a bipartite quantum system, its maximum (average, minimum) entangling power is the maximum (average, minimum) entanglement generation with respect to certain entanglement measure when the inputs are restricted to be product states. In this paper, we mainly focus on the 'weakest' one, i.e., the minimum entangling power, among all these entangling powers. We show that, by choosing von Neumann entropy of reduced density operator or Schmidt rank as entanglement measure, even the 'weakest' entangling power is generically very close to its maximal possible entanglement generation. In other words, maximum, average and minimum entangling powers are generically close. We then study minimum entangling power with respect to other Lipschitiz-continuous entanglement measures and generalize our results to multipartite quantum systems. As a straightforward application, a random quantum gate will almost surely be an intrinsically fault-tolerant entangling device that will always transform every low-entangled state to near-maximally entangled state.

Nanoplasmonic Lattices for Ultracold atoms - Michael Gullans; T. Tiecke; D. E. Chang; J. Feist; J. D. Thompson; J. I. Cirac; P. Zoller; M. D. Lukin (Physical Review Letters, 2012)
We propose to use sub-wavelength confinement of light associated with the near field of plasmonic systems to create nanoscale optical lattices for ultracold atoms. Our approach combines the unique coherence properties of isolated atoms with the sub-wavelength manipulation and strong light-matter interaction associated with nano-plasmonic systems. It allows one to considerably increase the energy scales in the realization of Hubbard models and to engineer effective long-range interactions in coherent and dissipative many-body dynamics. Realistic imperfections and potential applications are discussed.

Non-Additivity of the Entanglement of Purification (Beyond Reasonable Doubt) - Jianxin Chen; Andreas Winter (2012)
We demonstrate the convexity of the difference between the regularized entanglement of purification and the entropy, as a function of the state. This is proved by means of a new asymptotic protocol to prepare a state from pre-shared entanglement and by local operations only. We go on to employ this convexity property in an investigation of the additivity of the (single-copy) entanglement of purification: using numerical results for two-qubit Werner states we find strong evidence that the entanglement of purification is different from its regularization, hence that entanglement of purification is not additive.

Non-Recursively Constructible Recursive Families of Graphs - Colleen Bouey; Christina Graves; Aaron Ostrander; Gregory Palma (The Electronic Journal of Combinatorics, 2012)
In a publication by Noy and Ribó, it was shown that recursively constructible families of graphs are recursive. The authors also conjecture that the converse holds; that is, recursive families are also recursively constructible. In this paper, we provide two specific counterexamples to this conjecture, which we then extend to an infinite family of counterexamples.

Photonic quantum simulation of ground state configurations of Heisenberg square and checkerboard lattice spin systems - Xiao-song Ma; Borivoje Dakic; Sebastian Kropatsche; William Naylor; Yang-hao Chan; Zhe-Xuan Gong; Lu-ming Duan; Anton Zeilinger; Philip Walther (2012)
Photonic quantum simulators are promising candidates for providing insight into other small- to medium-sized quantum systems. The available photonic quantum technology is reaching the state where significant advantages arise for the quantum simulation of interesting questions in Heisenberg spin systems. Here we experimentally simulate such spin systems with single photons and linear optics. The effective Heisenberg-type interactions among individual single photons are realized by quantum interference at the tunable direction coupler followed by the measurement process. The effective interactions are characterized by comparing the entanglement dynamics using pairwise concurrence of a four-photon quantum system. We further show that photonic quantum simulations of generalized Heisenberg interactions on a four-site square lattice and a six-site checkerboard lattice are in reach of current technology.

Polymer-mediated entropic forces between scale-free objects - Mohammad F. Maghrebi; Yacov Kantor; Mehran Kardar (Physical Review E, 2012)
The number of configurations of a polymer is reduced in the presence of a barrier or an obstacle. The resulting loss of entropy adds a repulsive component to other forces generated by interaction potentials. When the obstructions are scale invariant shapes (such as cones, wedges, lines or planes) the only relevant length scales are the polymer size R_0 and characteristic separations, severely constraining the functional form of entropic forces. Specifically, we consider a polymer (single strand or star) attached to the tip of a cone, at a separation h from a surface (or another cone). At close proximity, such that h<<R_0, separation is the only remaining relevant scale and the entropic force must take the form F=AkT/h. The amplitude A is universal, and can be related to exponents η governing the anomalous scaling of polymer correlations in the presence of obstacles. We use analytical, numerical and epsilon-expansion techniques to compute the exponent η for a polymer attached to the tip of the cone (with or without an additional plate or cone) for ideal and self-avoiding polymers. The entropic force is of the order of 0.1 pN at 0.1 micron for a single polymer, and can be increased for a star polymer.

Quantum Algorithms for Invariants of Triangulated Manifolds - Gorjan Alagic; E. A. Bering (Quantum Info. Comput. Vol., 2012)
One of the apparent advantages of quantum computers over their classical counterparts is their ability to efficiently contract tensor networks. In this article, we study some implications of this fact in the case of topological tensor networks. The graph underlying these networks is given by the triangulation of a manifold, and the structure of the tensors ensures that the overall tensor is independent of the choice of internal triangulation. This leads to quantum algorithms for additively approximating certain invariants of triangulated manifolds. We discuss the details of this construction in two specific cases. In the first case, we consider triangulated surfaces, where the triangle tensor is defined by the multiplication operator of a finite group; the resulting invariant has a simple closed-form expression involving the dimensions of the irreducible representations of the group and the Euler characteristic of the surface. In the second case, we consider triangulated 3-manifolds, where the tetrahedral tensor is defined by the so-called Fibonacci anyon model; the resulting invariant is the well-known Turaev-Viro invariant of 3-manifolds.

Quantum Algorithms for Quantum Field Theories - Stephen P. Jordan; Keith S. M. Lee; John Preskill (Science, 2012)
Quantum field theory reconciles quantum mechanics and special relativity, and plays a central role in many areas of physics. We develop a quantum algorithm to compute relativistic scattering probabilities in a massive quantum field theory with quartic self-interactions (phi-fourth theory) in spacetime of four and fewer dimensions. Its run time is polynomial in the number of particles, their energy, and the desired precision, and applies at both weak and strong coupling. In the strong-coupling and high-precision regimes, our quantum algorithm achieves exponential speedup over the fastest known classical algorithm.