Semidefinite programs (SDPs) are a framework for exact or approximate optimization that have widespread application in quantum information theory. We introduce a new method for using reductions to construct integrality gaps for SDPs. These are based on new limitations on the sum-of-squares (SoS) hierarchy in approximating two particularly important sets in quantum information theory, where previously no ω(1)-round integrality gaps were known: the set of separable (i.e. unentangled) states, or equivalently, the 2→4 norm of a matrix, and the set of quantum correlations; i.e. conditional probability distributions achievable with local measurements on a shared entangled state. In both cases no-go theorems were previously known based on computational assumptions such as the Exponential Time Hypothesis (ETH) which asserts that 3-SAT requires exponential time to solve. Our unconditional results achieve the same parameters as all of these previous results (for separable states) or as some of the previous results (for quantum correlations). In some cases we can make use of the framework of Lee-Raghavendra-Steurer (LRS) to establish integrality gaps for any SDP, not only the SoS hierarchy. Our hardness result on separable states also yields a dimension lower bound of approximate disentanglers, answering a question of Watrous and Aaronson et al. These results can be viewed as limitations on the monogamy principle, the PPT test, the ability of Tsirelson-type bounds to restrict quantum correlations, as well as the SDP hierarchies of Doherty-Parrilo-Spedalieri, Navascues-Pironio-Acin and Berta-Fawzi-Scholz.

VL - 366 UR - https://arxiv.org/abs/1612.09306 CP - 2 U5 - https://doi.org/10.1007/s00220-019-03382-y ER - TY - JOUR T1 - Locality and digital quantum simulation of power-law interactions JF - Phys. Rev. X 9, 031006 Y1 - 2019 A1 - Minh Cong Tran A1 - Andrew Y. Guo A1 - Yuan Su A1 - James R. Garrison A1 - Zachary Eldredge A1 - Michael Foss-Feig A1 - Andrew M. Childs A1 - Alexey V. Gorshkov AB -The propagation of information in non-relativistic quantum systems obeys a speed limit known as a Lieb-Robinson bound. We derive a new Lieb-Robinson bound for systems with interactions that decay with distance r as a power law, 1/rα. The bound implies an effective light cone tighter than all previous bounds. Our approach is based on a technique for approximating the time evolution of a system, which was first introduced as part of a quantum simulation algorithm by Haah et al. [arXiv:1801.03922]. To bound the error of the approximation, we use a known Lieb-Robinson bound that is weaker than the bound we establish. This result brings the analysis full circle, suggesting a deep connection between Lieb-Robinson bounds and digital quantum simulation. In addition to the new Lieb-Robinson bound, our analysis also gives an error bound for the Haah et al. quantum simulation algorithm when used to simulate power-law decaying interactions. In particular, we show that the gate count of the algorithm scales with the system size better than existing algorithms when α>3D (where D is the number of dimensions).

VL - 9 UR - https://arxiv.org/abs/1808.05225 CP - 031006 U5 - https://doi.org/10.1103/PhysRevX.9.031006 ER - TY - JOUR T1 - Local randomness: Examples and application JF - Phys. Rev. A Y1 - 2018 A1 - Honghao Fu A1 - Carl Miller AB -When two players achieve a superclassical score at a nonlocal game, their outputs must contain intrinsic randomness. This fact has many useful implications for quantum cryptography. Recently it has been observed [C. Miller and Y. Shi, Quantum Inf. Computat. 17, 0595 (2017)] that such scores also imply the existence of local randomness—that is, randomness known to one player but not to the other. This has potential implications for cryptographic tasks between two cooperating but mistrustful players. In the current paper we bring this notion toward practical realization, by offering near-optimal bounds on local randomness for the CHSH game, and also proving the security of a cryptographic application of local randomness (single-bit certified deletion).

U4 - 032324 UR - https://arxiv.org/abs/1708.04338 CP - 97 U5 - https://doi.org/10.1103/PhysRevA.97.032324 ER - TY - JOUR T1 - Locality, Quantum Fluctuations, and Scrambling Y1 - 2018 A1 - Shenglong Xu A1 - Brian Swingle AB -Thermalization of chaotic quantum many-body systems under unitary time evolution is related to the growth in complexity of initially simple Heisenberg operators. Operator growth is a manifestation of information scrambling and can be diagnosed by out-of-time-order correlators (OTOCs). However, the behavior of OTOCs of local operators in generic chaotic local Hamiltonians remains poorly understood, with some semiclassical and large N models exhibiting exponential growth of OTOCs and a sharp chaos wavefront and other random circuit models showing a diffusively broadened wavefront. In this paper we propose a unified physical picture for scrambling in chaotic local Hamiltonians. We construct a random time-dependent Hamiltonian model featuring a large N limit where the OTOC obeys a Fisher-Kolmogorov-Petrovsky-Piskunov (FKPP) type equation and exhibits exponential growth and a sharp wavefront. We show that quantum fluctuations manifest as noise (distinct from the randomness of the couplings in the underlying Hamiltonian) in the FKPP equation and that the noise-averaged OTOC exhibits a cross-over to a diffusively broadened wavefront. At small N we demonstrate that operator growth dynamics, averaged over the random couplings, can be efficiently simulated for all time using matrix product state techniques. To show that time-dependent randomness is not essential to our conclusions, we push our previous matrix product operator methods to very large size and show that data for a time-independent Hamiltonian model are also consistent with a diffusively-broadened wavefront.

UR - https://arxiv.org/abs/1805.05376 ER - TY - JOUR T1 - Lieb-Robinson bounds on n-partite connected correlation functions JF - Phys. Rev. A 96, 052334 Y1 - 2017 A1 - Minh Cong Tran A1 - James R. Garrison A1 - Zhe-Xuan Gong A1 - Alexey V. Gorshkov AB -Lieb and Robinson provided bounds on how fast bipartite connected correlations can arise in systems with only short-range interactions. We generalize Lieb-Robinson bounds on bipartite connected correlators to multipartite connected correlators. The bounds imply that an n-partite connected correlator can reach unit value in constant time. Remarkably, the bounds also allow for an n-partite connected correlator to reach a value that is exponentially large with system size in constant time, a feature which stands in contrast to bipartite connected correlations. We provide explicit examples of such systems.

UR - https://arxiv.org/abs/1705.04355 U5 - https://doi.org/10.1103/PhysRevA.96.052334 ER - TY - JOUR T1 - Lieb-Robinson bounds on n-partite connected correlations JF - Physical Review A Y1 - 2017 A1 - Minh Cong Tran A1 - James R. Garrison A1 - Zhe-Xuan Gong A1 - Alexey V. Gorshkov AB -Lieb and Robinson provided bounds on how fast bipartite connected correlations can arise in systems with only short-range interactions. We generalize Lieb-Robinson bounds on bipartite connected correlators to multipartite connected correlators. The bounds imply that an

We show how to realize two-component fractional quantum Hall phases in monolayer graphene by optically driving the system. A laser is tuned into resonance between two Landau levels, giving rise to an effective tunneling between these two synthetic layers. Remarkably, because of this coupling, the interlayer interaction at non-zero relative angular momentum can become dominant, resembling a hollow-core pseudo-potential. In the weak tunneling regime, this interaction favors the formation of singlet states, as we explicitly show by numerical diagonalization, at fillings ν = 1/2 and ν = 2/3. We discuss possible candidate phases, including the Haldane-Rezayi phase, the interlayer Pfaffian phase, and a Fibonacci phase. This demonstrates that our method may pave the way towards the realization of non-Abelian phases, as well as the control of topological phase transitions, in graphene quantum Hall systems using optical fields and integrated photonic structures.

VL - 119 U4 - 247403 UR - https://arxiv.org/abs/1612.08748 CP - 24 U5 - 10.1103/PhysRevLett.119.247403 ER - TY - JOUR T1 - Landauer formulation of photon transport in driven systems JF - Physical Review B Y1 - 2016 A1 - Chiao-Hsuan Wang A1 - Jacob M. Taylor AB -Understanding the behavior of light in non-equilibrium scenarios underpins much of quantum optics and optical physics. While lasers provide a severe example of a non-equilibrium problem, recent interests in the near-equilibrium physics of photon `gases', such as in Bose condensation of light or in attempts to make photonic quantum simulators, suggest one reexamine some near-equilibrium cases. Here we consider how a sinusoidal parametric coupling between two semi-infinite photonic transmission lines leads to the creation and flow of photons between the two lines. Our approach provides a photonic analogue to the Landauer transport formula, and using non-equilbrium Green's functions, we can extend it to the case of an interacting region between two photonic `leads' where the sinusoid frequency plays the role of a voltage bias. Crucially, we identify both the mathematical framework and the physical regime in which photonic transport is directly analogous to electronic transport, and regimes in which other new behavior such as two-mode squeezing can emerge.

VL - 94 U4 - 155437 UR - https://doi.org/10.1103/PhysRevB.94.155437 CP - 15 U5 - 10.1103/PhysRevB.94.155437 ER - TY - JOUR T1 - Lattice Laughlin states on the torus from conformal field theory JF - Journal of Statistical Mechanics: Theory and Experiment Y1 - 2016 A1 - Abhinav Deshpande A1 - Anne E B Nielsen AB - Conformal field theory has turned out to be a powerful tool to derive two-dimensional lattice models displaying fractional quantum Hall physics. So far most of the work has been for lattices with open boundary conditions in at least one of the two directions, but it is desirable to also be able to handle the case of periodic boundary conditions. Here, we take steps in this direction by deriving analytical expressions for a family of conformal field theory states on the torus that is closely related to the family of bosonic and fermionic Laughlin states. We compute how the states transform when a particle is moved around the torus and when the states are translated or rotated, and we provide numerical evidence in particular cases that the states become orthonormal up to a common factor for large lattices. We use these results to find the S -matrix of the states, which turns out to be the same as for the continuum Laughlin states. Finally, we show that when the states are defined on a square lattice with suitable lattice spacing they practically coincide with the Laughlin states restricted to a lattice. VL - 2016 U4 - 013102 UR - http://stacks.iop.org/1742-5468/2016/i=1/a=013102 ER - TY - JOUR T1 - Laplacian matrices and Alexandrov topologies of digraphs JF - Linear Algebra and its Applications Y1 - 2015 A1 - Aaron Ostrander KW - Laplacian matrix AB - 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. VL - 481 U4 - 174 - 185 UR - http://www.sciencedirect.com/science/article/pii/S0024379515002840 U5 - http://dx.doi.org/10.1016/j.laa.2015.04.031 ER - TY - JOUR T1 - Large effective three-body interaction in a double-well optical lattice JF - Phys. Rev. A 92, 023602 Y1 - 2015 A1 - Saurabh Paul A1 - Eite Tiesinga AB - 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. VL - 92 U4 - 023602 UR - http://journals.aps.org/pra/abstract/10.1103/PhysRevA.92.023602 CP - 2 ER - TY - JOUR T1 - Levinson's theorem for graphs II JF - Journal of Mathematical Physics Y1 - 2012 A1 - Andrew M. Childs A1 - David Gosset AB - 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. VL - 53 U4 - 102207 UR - http://arxiv.org/abs/1203.6557v2 CP - 10 J1 - J. Math. Phys. U5 - 10.1063/1.4757665 ER - TY - JOUR T1 - Long-lived dipolar molecules and Feshbach molecules in a 3D optical lattice JF - Physical Review Letters Y1 - 2012 A1 - Amodsen Chotia A1 - Brian Neyenhuis A1 - Steven A. Moses A1 - Bo Yan A1 - Jacob P. Covey A1 - Michael Foss-Feig A1 - Ana Maria Rey A1 - Deborah S. Jin A1 - Jun Ye AB - 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. VL - 108 UR - http://arxiv.org/abs/1110.4420v1 CP - 8 J1 - Phys. Rev. Lett. U5 - 10.1103/PhysRevLett.108.080405 ER - TY - JOUR T1 - Laser cooling and optical detection of excitations in a LC electrical circuit JF - Physical Review Letters Y1 - 2011 A1 - J. M. Taylor A1 - A. S. Sørensen A1 - C. M. Marcus A1 - E. S. Polzik AB - We explore a method for laser cooling and optical detection of excitations in a LC electrical circuit. Our approach uses a nanomechanical oscillator as a transducer between optical and electronic excitations. An experimentally feasible system with the oscillator capacitively coupled to the LC and at the same time interacting with light via an optomechanical force is shown to provide strong electro-mechanical coupling. Conditions for improved sensitivity and quantum limited readout of electrical signals with such an "optical loud speaker" are outlined. VL - 107 UR - http://arxiv.org/abs/1108.2035v1 CP - 27 J1 - Phys. Rev. Lett. U5 - 10.1103/PhysRevLett.107.273601 ER - TY - JOUR T1 - Levinson's theorem for graphs JF - Journal of Mathematical Physics Y1 - 2011 A1 - Andrew M. Childs A1 - DJ Strouse AB - We prove an analog of Levinson's theorem for scattering on a weighted (m+1)-vertex graph with a semi-infinite path attached to one of its vertices. In particular, we show that the number of bound states in such a scattering problem is equal to m minus half the winding number of the phase of the reflection coefficient (where each so-called half-bound state is counted as half a bound state). VL - 52 U4 - 082102 UR - http://arxiv.org/abs/1103.5077v2 CP - 8 J1 - J. Math. Phys. U5 - 10.1063/1.3622608 ER - TY - JOUR T1 - Light storage in an optically thick atomic ensemble under conditions of electromagnetically induced transparency and four-wave mixing JF - Physical Review A Y1 - 2011 A1 - Nathaniel B. Phillips A1 - Alexey V. Gorshkov A1 - Irina Novikova AB - We study the modification of a traditional electromagnetically induced transparency (EIT) stored light technique that includes both EIT and four-wave mixing (FWM) in an ensemble of hot Rb atoms. The standard treatment of light storage involves the coherent and reversible mapping of one photonic mode onto a collective spin coherence. It has been shown that unwanted, competing processes such as four-wave mixing are enhanced by EIT and can significantly modify the signal optical pulse propagation. We present theoretical and experimental evidence to indicate that while a Stokes field is indeed detected upon retrieval of the signal field, any information originally encoded in a seeded Stokes field is not independently preserved during the storage process. We present a simple model that describes the propagation dynamics of the fields and the impact of FWM on the spin wave. VL - 83 UR - http://arxiv.org/abs/1103.2131v1 CP - 6 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.83.063823 ER - TY - JOUR T1 - Limitations on the simulation of non-sparse Hamiltonians Y1 - 2009 A1 - Andrew M. Childs A1 - Robin Kothari AB - The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse N x N Hamiltonian H for time t can be simulated using O(||Ht||poly(log N)) operations, which is essentially optimal due to a no--fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time o(||Ht||), even though ||H|| is not a unique measure of the size of a dense Hamiltonian $H$. We also present a stronger limitation ruling out the possibility of generic simulations taking time poly(||Ht||,log N), showing that known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonians can be simulated efficiently, such as those with graphs of small arboricity. UR - http://arxiv.org/abs/0908.4398v2 J1 - Quantum Information and Computation 10 ER - TY - JOUR T1 - Locality Bounds on Hamiltonians for Stabilizer Codes JF - Quantum Information and Computation Y1 - 2009 A1 - Stephen S. Bullock A1 - Dianne P. O'Leary AB - In this paper, we study the complexity of Hamiltonians whose groundstate is a stabilizer code. We introduce various notions of k-locality of a stabilizer code, inherited from the associated stabilizer group. A choice of generators leads to a Hamiltonian with the code in its groundspace. We establish bounds on the locality of any other Hamiltonian whose groundspace contains such a code, whether or not its Pauli tensor summands commute. Our results provide insight into the cost of creating an energy gap for passive error correction and for adiabatic quantum computing. The results simplify in the cases of XZ-split codes such as Calderbank-Shor-Steane stabilizer codes and topologically-ordered stabilizer codes arising from surface cellulations. VL - 9 UR - http://www.cs.umd.edu/~oleary/reprints/j91.pdf ER - TY - JOUR T1 - The limitations of nice mutually unbiased bases JF - Journal of Algebraic Combinatorics Y1 - 2007 A1 - Michael Aschbacher A1 - Andrew M. Childs A1 - Pawel Wocjan AB - Mutually unbiased bases of a Hilbert space can be constructed by partitioning a unitary error basis. We consider this construction when the unitary error basis is a nice error basis. We show that the number of resulting mutually unbiased bases can be at most one plus the smallest prime power contained in the dimension, and therefore that this construction cannot improve upon previous approaches. We prove this by establishing a correspondence between nice mutually unbiased bases and abelian subgroups of the index group of a nice error basis and then bounding the number of such subgroups. This bound also has implications for the construction of certain combinatorial objects called nets. VL - 25 U4 - 111 - 123 UR - http://arxiv.org/abs/quant-ph/0412066v1 CP - 2 J1 - J Algebr Comb U5 - 10.1007/s10801-006-0002-y ER - TY - JOUR T1 - The Local Consistency Problem for Stoquastic and 1-D Quantum Systems Y1 - 2007 A1 - Yi-Kai Liu AB - The Local Hamiltonian problem (finding the ground state energy of a quantum system) is known to be QMA-complete. The Local Consistency problem (deciding whether descriptions of small pieces of a quantum system are consistent) is also known to be QMA-complete. Here we consider special cases of Local Hamiltonian, for ``stoquastic'' and 1-dimensional systems, that seem to be strictly easier than QMA. We show that there exist analogous special cases of Local Consistency, that have equivalent complexity (up to poly-time oracle reductions). Our main technical tool is a new reduction from Local Consistency to Local Hamiltonian, using SDP duality. UR - http://arxiv.org/abs/0712.1388v2 ER - TY - JOUR T1 - The LU-LC conjecture is false Y1 - 2007 A1 - Zhengfeng Ji A1 - Jianxin Chen A1 - Zhaohui Wei A1 - Mingsheng Ying AB - The LU-LC conjecture is an important open problem concerning the structure of entanglement of states described in the stabilizer formalism. It states that two local unitary equivalent stabilizer states are also local Clifford equivalent. If this conjecture were true, the local equivalence of stabilizer states would be extremely easy to characterize. Unfortunately, however, based on the recent progress made by Gross and Van den Nest, we find that the conjecture is false. UR - http://arxiv.org/abs/0709.1266v2 J1 - Quantum Inf. Comput. ER - TY - CONF T1 - Language-reconfigurable universal phone recognition T2 - Eighth European Conference on Speech Communication and Technology Y1 - 2003 A1 - Walker, Brenton D A1 - Lackey, Bradley C A1 - Muller, JS A1 - Schone, Patrick John JA - Eighth European Conference on Speech Communication and Technology ER - TY - JOUR T1 - Long-lived memory for mesoscopic quantum bits JF - Physical Review Letters Y1 - 2003 A1 - J. M. Taylor A1 - C. M. Marcus A1 - M. D. Lukin AB - We describe a technique to create long-lived quantum memory for quantum bits in mesoscopic systems. Specifically we show that electronic spin coherence can be reversibly mapped onto the collective state of the surrounding nuclei. The coherent transfer can be efficient and fast and it can be used, when combined with standard resonance techniques, to reversibly store coherent superpositions on the time scale of seconds. This method can also allow for ``engineering'' entangled states of nuclear ensembles and efficiently manipulating the stored states. We investigate the feasibility of this method through a detailed analysis of the coherence properties of the system. VL - 90 UR - http://arxiv.org/abs/cond-mat/0301323v1 CP - 20 J1 - Phys. Rev. Lett. U5 - 10.1103/PhysRevLett.90.206803 ER - TY - JOUR T1 - Lower bounds on the complexity of simulating quantum gates JF - Physical Review A Y1 - 2003 A1 - Andrew M. Childs A1 - Henry L. Haselgrove A1 - Michael A. Nielsen AB - We give a simple proof of a formula for the minimal time required to simulate a two-qubit unitary operation using a fixed two-qubit Hamiltonian together with fast local unitaries. We also note that a related lower bound holds for arbitrary n-qubit gates. VL - 68 UR - http://arxiv.org/abs/quant-ph/0307190v1 CP - 5 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.68.052311 ER - TY - CHAP T1 - A Lichnerowicz Vanishing Theorem for Finsler Spaces T2 - The Theory of Finslerian Laplacians and Applications Y1 - 1998 A1 - Lackey, Brad JA - The Theory of Finslerian Laplacians and Applications PB - Springer U4 - 227–243 ER -