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.

%B Commun. Math. Phys. %V 366 %8 03/04/2019 %G eng %U https://arxiv.org/abs/1612.09306 %N 2 %& 423-468 %R https://doi.org/10.1007/s00220-019-03382-y %0 Journal Article %J Phys. Rev. X 9, 031006 %D 2019 %T Locality and digital quantum simulation of power-law interactions %A Minh Cong Tran %A Andrew Y. Guo %A Yuan Su %A James R. Garrison %A Zachary Eldredge %A Michael Foss-Feig %A Andrew M. Childs %A Alexey V. Gorshkov %XThe 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).

%B Phys. Rev. X 9, 031006 %V 9 %8 07/10/2019 %G eng %U https://arxiv.org/abs/1808.05225 %N 031006 %R https://doi.org/10.1103/PhysRevX.9.031006 %0 Journal Article %J Phys. Rev. A %D 2018 %T Local randomness: Examples and application %A Honghao Fu %A Carl Miller %XWhen 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).

%B Phys. Rev. A %P 032324 %8 03/2018 %G eng %U https://arxiv.org/abs/1708.04338 %N 97 %R https://doi.org/10.1103/PhysRevA.97.032324 %0 Journal Article %D 2018 %T Locality, Quantum Fluctuations, and Scrambling %A Shenglong Xu %A Brian Swingle %XThermalization 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.

%G eng %U https://arxiv.org/abs/1805.05376 %0 Journal Article %J Phys. Rev. A 96, 052334 %D 2017 %T Lieb-Robinson bounds on n-partite connected correlation functions %A Minh Cong Tran %A James R. Garrison %A Zhe-Xuan Gong %A Alexey V. Gorshkov %XLieb 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.

%B Phys. Rev. A 96, 052334 %G eng %U https://arxiv.org/abs/1705.04355 %R https://doi.org/10.1103/PhysRevA.96.052334 %0 Journal Article %J Physical Review A %D 2017 %T Lieb-Robinson bounds on n-partite connected correlations %A Minh Cong Tran %A James R. Garrison %A Zhe-Xuan Gong %A Alexey V. Gorshkov %XLieb 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.

%B Physical Review Letters %V 119 %P 247403 %8 2017/12/15 %G eng %U https://arxiv.org/abs/1612.08748 %N 24 %R 10.1103/PhysRevLett.119.247403 %0 Journal Article %J Physical Review B %D 2016 %T Landauer formulation of photon transport in driven systems %A Chiao-Hsuan Wang %A Jacob M. Taylor %XUnderstanding 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.

%B Physical Review B %V 94 %P 155437 %8 2016/10/20 %G eng %U https://doi.org/10.1103/PhysRevB.94.155437 %N 15 %R 10.1103/PhysRevB.94.155437 %0 Journal Article %J Journal of Statistical Mechanics: Theory and Experiment %D 2016 %T Lattice Laughlin states on the torus from conformal field theory %A Abhinav Deshpande %A Anne E B Nielsen %X 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. %B Journal of Statistical Mechanics: Theory and Experiment %V 2016 %P 013102 %8 2016/01/28 %G eng %U http://stacks.iop.org/1742-5468/2016/i=1/a=013102 %0 Journal Article %J Linear Algebra and its Applications %D 2015 %T Laplacian matrices and Alexandrov topologies of digraphs %A Aaron Ostrander %K Laplacian matrix %X 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. %B Linear Algebra and its Applications %V 481 %P 174 - 185 %8 2015/09/15 %G eng %U http://www.sciencedirect.com/science/article/pii/S0024379515002840 %R http://dx.doi.org/10.1016/j.laa.2015.04.031 %0 Journal Article %J Phys. Rev. A 92, 023602 %D 2015 %T Large effective three-body interaction in a double-well optical lattice %A Saurabh Paul %A Eite Tiesinga %X 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. %B Phys. Rev. A 92, 023602 %V 92 %P 023602 %8 2015/08/03 %G eng %U http://journals.aps.org/pra/abstract/10.1103/PhysRevA.92.023602 %N 2 %0 Journal Article %J Journal of Mathematical Physics %D 2012 %T Levinson's theorem for graphs II %A Andrew M. Childs %A David Gosset %X 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. %B Journal of Mathematical Physics %V 53 %P 102207 %8 2012/11/21 %G eng %U http://arxiv.org/abs/1203.6557v2 %N 10 %! J. Math. Phys. %R 10.1063/1.4757665 %0 Journal Article %J Physical Review Letters %D 2012 %T Long-lived dipolar molecules and Feshbach molecules in a 3D optical lattice %A Amodsen Chotia %A Brian Neyenhuis %A Steven A. Moses %A Bo Yan %A Jacob P. Covey %A Michael Foss-Feig %A Ana Maria Rey %A Deborah S. Jin %A Jun Ye %X 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. %B Physical Review Letters %V 108 %8 2012/2/23 %G eng %U http://arxiv.org/abs/1110.4420v1 %N 8 %! Phys. Rev. Lett. %R 10.1103/PhysRevLett.108.080405 %0 Journal Article %J Physical Review Letters %D 2011 %T Laser cooling and optical detection of excitations in a LC electrical circuit %A J. M. Taylor %A A. S. Sørensen %A C. M. Marcus %A E. S. Polzik %X 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. %B Physical Review Letters %V 107 %8 2011/12/27 %G eng %U http://arxiv.org/abs/1108.2035v1 %N 27 %! Phys. Rev. Lett. %R 10.1103/PhysRevLett.107.273601 %0 Journal Article %J Journal of Mathematical Physics %D 2011 %T Levinson's theorem for graphs %A Andrew M. Childs %A DJ Strouse %X 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). %B Journal of Mathematical Physics %V 52 %P 082102 %8 2011/06/30 %G eng %U http://arxiv.org/abs/1103.5077v2 %N 8 %! J. Math. Phys. %R 10.1063/1.3622608 %0 Journal Article %J Physical Review A %D 2011 %T Light storage in an optically thick atomic ensemble under conditions of electromagnetically induced transparency and four-wave mixing %A Nathaniel B. Phillips %A Alexey V. Gorshkov %A Irina Novikova %X 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. %B Physical Review A %V 83 %8 2011/6/20 %G eng %U http://arxiv.org/abs/1103.2131v1 %N 6 %! Phys. Rev. A %R 10.1103/PhysRevA.83.063823 %0 Journal Article %D 2009 %T Limitations on the simulation of non-sparse Hamiltonians %A Andrew M. Childs %A Robin Kothari %X 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. %8 2009/08/31 %G eng %U http://arxiv.org/abs/0908.4398v2 %! Quantum Information and Computation 10 %0 Journal Article %J Quantum Information and Computation %D 2009 %T Locality Bounds on Hamiltonians for Stabilizer Codes %A Stephen S. Bullock %A Dianne P. O'Leary %X 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. %B Quantum Information and Computation %V 9 %8 2009/09/22 %G eng %U http://www.cs.umd.edu/~oleary/reprints/j91.pdf %0 Journal Article %J Journal of Algebraic Combinatorics %D 2007 %T The limitations of nice mutually unbiased bases %A Michael Aschbacher %A Andrew M. Childs %A Pawel Wocjan %X 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. %B Journal of Algebraic Combinatorics %V 25 %P 111 - 123 %8 2006/7/11 %G eng %U http://arxiv.org/abs/quant-ph/0412066v1 %N 2 %! J Algebr Comb %R 10.1007/s10801-006-0002-y %0 Journal Article %D 2007 %T The Local Consistency Problem for Stoquastic and 1-D Quantum Systems %A Yi-Kai Liu %X 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. %8 2007/12/10 %G eng %U http://arxiv.org/abs/0712.1388v2 %0 Journal Article %D 2007 %T The LU-LC conjecture is false %A Zhengfeng Ji %A Jianxin Chen %A Zhaohui Wei %A Mingsheng Ying %X 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. %8 2007/09/09 %G eng %U http://arxiv.org/abs/0709.1266v2 %! Quantum Inf. Comput. %0 Conference Paper %B Eighth European Conference on Speech Communication and Technology %D 2003 %T Language-reconfigurable universal phone recognition %A Walker, Brenton D %A Lackey, Bradley C %A Muller, JS %A Schone, Patrick John %B Eighth European Conference on Speech Communication and Technology %G eng %0 Journal Article %J Physical Review Letters %D 2003 %T Long-lived memory for mesoscopic quantum bits %A J. M. Taylor %A C. M. Marcus %A M. D. Lukin %X 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. %B Physical Review Letters %V 90 %8 2003/5/20 %G eng %U http://arxiv.org/abs/cond-mat/0301323v1 %N 20 %! Phys. Rev. Lett. %R 10.1103/PhysRevLett.90.206803 %0 Journal Article %J Physical Review A %D 2003 %T Lower bounds on the complexity of simulating quantum gates %A Andrew M. Childs %A Henry L. Haselgrove %A Michael A. Nielsen %X 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. %B Physical Review A %V 68 %8 2003/11/18 %G eng %U http://arxiv.org/abs/quant-ph/0307190v1 %N 5 %! Phys. Rev. A %R 10.1103/PhysRevA.68.052311 %0 Book Section %B The Theory of Finslerian Laplacians and Applications %D 1998 %T A Lichnerowicz Vanishing Theorem for Finsler Spaces %A Lackey, Brad %B The Theory of Finslerian Laplacians and Applications %I Springer %P 227–243 %G eng