01807nas a2200181 4500008004100000022001400041245003600055210003500091260001400126490000600140520134200146100001501488700002301503700001701526700002401543700002101567856003701588 2024 eng d a2691-339900aClifford-Deformed Surface Codes0 aCliffordDeformed Surface Codes c3/19/20240 v53 a

Various realizations of Kitaev's surface code perform surprisingly well for biased Pauli noise. Attracted by these potential gains, we study the performance of Clifford-deformed surface codes (CDSCs) obtained from the surface code by applying single-qubit Clifford operators. We first analyze CDSCs on the 3×3 square lattice and find that, depending on the noise bias, their logical error rates can differ by orders of magnitude. To explain the observed behavior, we introduce the effective distance d′, which reduces to the standard distance for unbiased noise. To study CDSC performance in the thermodynamic limit, we focus on random CDSCs. Using the statistical mechanical mapping for quantum codes, we uncover a phase diagram that describes random CDSC families with 50% threshold at infinite bias. In the high-threshold region, we further demonstrate that typical code realizations outperform the thresholds and subthreshold logical error rates, at finite bias, of the best-known translationally invariant codes. We demonstrate the practical relevance of these random CDSC families by constructing a translation-invariant CDSC belonging to a high-performance random CDSC family. We also show that our translation-invariant CDSC outperforms well-known translation-invariant CDSCs such as the XZZX and XY codes.

1 aDua, Arpit1 aKubica, Aleksander1 aJiang, Liang1 aFlammia, Steven, T.1 aGullans, Michael uhttps://arxiv.org/abs/2201.0780201965nas a2200205 4500008004100000245009400041210006900135260001400204520132100218100002001539700002101559700001701580700002301597700001701620700001801637700001801655700002501673700002401698856003701722 2024 eng d00aLong-Distance Nuclear Matrix Elements for Neutrinoless Double-Beta Decay from Lattice QCD0 aLongDistance Nuclear Matrix Elements for Neutrinoless DoubleBeta c2/14/20243 a

Neutrinoless double-beta (0νββ) decay is a heretofore unobserved process which, if observed, would imply that neutrinos are Majorana particles. Interpretations of the stringent experimental constraints on 0νββ-decay half-lives require calculations of nuclear matrix elements. This work presents the first lattice quantum-chromodynamics (LQCD) calculation of the matrix element for 0νββ decay in a multi-nucleon system, specifically the nn→ppee transition, mediated by a light left-handed Majorana neutrino propagating over nuclear-scale distances. This calculation is performed with quark masses corresponding to a pion mass of mπ=806 MeV at a single lattice spacing and volume. The statistically cleaner Σ−→Σ+ee transition is also computed in order to investigate various systematic uncertainties. The prospects for matching the results of LQCD calculations onto a nuclear effective field theory to determine a leading-order low-energy constant relevant for 0νββ decay with a light Majorana neutrino are investigated. This work, therefore, sets the stage for future calculations at physical values of the quark masses that, combined with effective field theory and nuclear many-body studies, will provide controlled theoretical inputs to experimental searches of 0νββ decay.

1 aDavoudi, Zohreh1 aDetmold, William1 aFu, Zhenghao1 aGrebe, Anthony, V.1 aJay, William1 aMurphy, David1 aOare, Patrick1 aShanahan, Phiala, E.1 aWagman, Michael, L. uhttps://arxiv.org/abs/2402.0936201467nas a2200193 4500008004100000245005900041210005900100260001400159520089600173100002101069700003001090700001901120700001801139700001601157700002401173700001801197700002101215856003701236 2024 eng d00aPhase transition in magic with random quantum circuits0 aPhase transition in magic with random quantum circuits c4/11/20243 a

Magic is a property of quantum states that enables universal fault-tolerant quantum computing using simple sets of gate operations. Understanding the mechanisms by which magic is created or destroyed is, therefore, a crucial step towards efficient and practical fault-tolerant computation. We observe that a random stabilizer code subject to coherent errors exhibits a phase transition in magic, which we characterize through analytic, numeric and experimental probes. Below a critical error rate, stabilizer syndrome measurements remove the accumulated magic in the circuit, effectively protecting against coherent errors; above the critical error rate syndrome measurements concentrate magic. A better understanding of such rich behavior in the resource theory of magic could shed more light on origins of quantum speedup and pave pathways for more efficient magic state generation.

1 aNiroula, Pradeep1 aWhite, Christopher, David1 aWang, Qingfeng1 aJohri, Sonika1 aZhu, Daiwei1 aMonroe, Christopher1 aNoel, Crystal1 aGullans, Michael uhttps://arxiv.org/abs/2304.1048102530nas a2200205 4500008004100000245006700041210006600108260001400174520187400188100003502062700002502097700002302122700002002145700002302165700002702188700002202215700002202237700002802259856003702287 2024 eng d00aProperties and Applications of the Kirkwood-Dirac Distribution0 aProperties and Applications of the KirkwoodDirac Distribution c3/27/20243 a

The most famous quasi-probability distribution, the Wigner function, has played a pivotal role in the development of a continuous-variable quantum theory that has clear analogues of position and momentum. However, the Wigner function is ill-suited for much modern quantum-information research, which is focused on finite-dimensional systems and general observables. Instead, recent years have seen the Kirkwood-Dirac (KD) distribution come to the forefront as a powerful quasi-probability distribution for analysing quantum mechanics. The KD distribution allows tools from statistics and probability theory to be applied to problems in quantum-information processing. A notable difference to the Wigner function is that the KD distribution can represent a quantum state in terms of arbitrary observables. This paper reviews the KD distribution, in three parts. First, we present definitions and basic properties of the KD distribution and its generalisations. Second, we summarise the KD distribution's extensive usage in the study or development of measurement disturbance; quantum metrology; weak values; direct measurements of quantum states; quantum thermodynamics; quantum scrambling and out-of-time-ordered correlators; and the foundations of quantum mechanics, including Leggett-Garg inequalities, the consistent-histories interpretation, and contextuality. We emphasise connections between operational quantum advantages and negative or non-real KD quasi-probabilities. Third, we delve into the KD distribution's mathematical structure. We summarise the current knowledge regarding the geometry of KD-positive states (the states for which the KD distribution is a classical probability distribution), describe how to witness and quantify KD non-positivity, and outline relationships between KD non-positivity and observables' incompatibility.

1 aArvidsson-Shukur, David, R. M.1 aBraasch, William, F.1 aDe Bievre, Stephan1 aDressel, Justin1 aJordan, Andrew, N.1 aLangrenez, Christopher1 aLostaglio, Matteo1 aLundeen, Jeff, S.1 aHalpern, Nicole, Yunger uhttps://arxiv.org/abs/2403.1889902067nas a2200169 4500008004100000245008100041210006900122260001300191520151900204100002001723700002701743700002001770700002301790700001901813700002801832856003701860 2024 eng d00aQuantum thermodynamics of nonequilibrium processes in lattice gauge theories0 aQuantum thermodynamics of nonequilibrium processes in lattice ga c4/3/20243 a

A key objective in nuclear and high-energy physics is to describe nonequilibrium dynamics of matter, e.g., in the early universe and in particle colliders, starting from the Standard Model. Classical-computing methods, via the framework of lattice gauge theory, have experienced limited success in this mission. Quantum simulation of lattice gauge theories holds promise for overcoming computational limitations. Because of local constraints (Gauss's laws), lattice gauge theories have an intricate Hilbert-space structure. This structure complicates the definition of thermodynamic properties of systems coupled to reservoirs during equilibrium and nonequilibrium processes. We show how to define thermodynamic quantities such as work and heat using strong-coupling thermodynamics, a framework that has recently burgeoned within the field of quantum thermodynamics. Our definitions suit instantaneous quenches, simple nonequilibrium processes undertaken in quantum simulators. To illustrate our framework, we compute the work and heat exchanged during a quench in a Z2 lattice gauge theory coupled to matter in 1+1 dimensions. The thermodynamic quantities, as functions of the quench parameter, evidence an expected phase transition. For general thermal states, we derive a simple relation between a quantum many-body system's entanglement Hamiltonian, measurable with quantum-information-processing tools, and the Hamiltonian of mean force, used to define strong-coupling thermodynamic quantities.

1 aDavoudi, Zohreh1 aJarzynski, Christopher1 aMueller, Niklas1 aOruganti, Greeshma1 aPowers, Connor1 aHalpern, Nicole, Yunger uhttps://arxiv.org/abs/2404.0296502465nas a2200517 4500008004100000245011600041210006900157260001400226520098200240100001701222700001701239700002501256700002001281700002401301700002201325700001601347700001901363700001901382700001801401700001901419700002001438700001901458700002101477700003101498700001801529700001901547700001601566700001601582700001601598700002001614700001901634700002101653700001901674700002201693700001801715700002401733700002301757700001801780700002001798700001801818700002301836700001901859700002001878700001201898856003701910 2023 eng d00aAccelerating Progress Towards Practical Quantum Advantage: The Quantum Technology Demonstration Project Roadmap0 aAccelerating Progress Towards Practical Quantum Advantage The Qu c3/20/20233 a

Quantum information science and technology (QIST) is a critical and emerging technology with the potential for enormous world impact and is currently invested in by over 40 nations. To bring these large-scale investments to fruition and bridge the lower technology readiness levels (TRLs) of fundamental research at universities to the high TRLs necessary to realize the promise of practical quantum advantage accessible to industry and the public, we present a roadmap for Quantum Technology Demonstration Projects (QTDPs). Such QTDPs, focused on intermediate TRLs, are large-scale public-private partnerships with a high probability of translation from laboratory to practice. They create technology demonstrating a clear 'quantum advantage' for science breakthroughs that are user-motivated and will provide access to a broad and diverse community of scientific users. Successful implementation of a program of QTDPs will have large positive economic impacts.

1 aAlsing, Paul1 aBattle, Phil1 aBienfang, Joshua, C.1 aBorders, Tammie1 aBrower-Thomas, Tina1 aCarr, Lincoln, D.1 aChong, Fred1 aDadras, Siamak1 aDeMarco, Brian1 aDeutsch, Ivan1 aFigueroa, Eden1 aFreedman, Danna1 aEveritt, Henry1 aGauthier, Daniel1 aJohnston-Halperin, Ezekiel1 aKim, Jungsang1 aKira, Mackillo1 aKumar, Prem1 aKwiat, Paul1 aLekki, John1 aLoiacono, Anjul1 aLončar, Marko1 aLowell, John, R.1 aLukin, Mikhail1 aMerzbacher, Celia1 aMiller, Aaron1 aMonroe, Christopher1 aPollanen, Johannes1 aPappas, David1 aRaymer, Michael1 aReano, Ronald1 aRodenburg, Brandon1 aSavage, Martin1 aSearles, Thomas1 aYe, Jun uhttps://arxiv.org/abs/2210.1475702172nas a2200133 4500008004100000245008500041210006900126260001500195520173200210100002401942700001701966700001801983856003702001 2023 eng d00aEvaluating the security of CRYSTALS-Dilithium in the quantum random oracle model0 aEvaluating the security of CRYSTALSDilithium in the quantum rand c12/17/20233 a

In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have been well-studied and are widely believed to be secure. However, SelfTargetMSIS is novel and, though classically as hard as MSIS, its quantum hardness is unclear. In this paper, we provide the first proof of the hardness of SelfTargetMSIS via a reduction from MLWE in the Quantum Random Oracle Model (QROM). Our proof uses recently developed techniques in quantum reprogramming and rewinding. A central part of our approach is a proof that a certain hash function, derived from the MSIS problem, is collapsing. From this approach, we deduce a new security proof for Dilithium under appropriate parameter settings. Compared to the only other rigorous security proof for a variant of Dilithium, Dilithium-QROM, our proof has the advantage of being applicable under the condition q = 1 mod 2n, where q denotes the modulus and n the dimension of the underlying algebraic ring. This condition is part of the original Dilithium proposal and is crucial for the efficient implementation of the scheme. We provide new secure parameter sets for Dilithium under the condition q = 1 mod 2n, finding that our public key sizes and signature sizes are about 2.5 to 2.8 times larger than those of Dilithium-QROM for the same security levels.

1 aJackson, Kelsey, A.1 aMiller, Carl1 aWang, Daochen uhttps://arxiv.org/abs/2312.1661901881nas a2200193 4500008004100000245007300041210006900114260001400183490000600197520129800203100002001501700002201521700002101543700001601564700001801580700002401598700002801622856003701650 2023 eng d00aExperimental Observation of Thermalization with Noncommuting Charges0 aExperimental Observation of Thermalization with Noncommuting Cha c4/28/20230 v43 a

Quantum simulators have recently enabled experimental observations of quantum many-body systems' internal thermalization. Often, the global energy and particle number are conserved, and the system is prepared with a well-defined particle number - in a microcanonical subspace. However, quantum evolution can also conserve quantities, or charges, that fail to commute with each other. Noncommuting charges have recently emerged as a subfield at the intersection of quantum thermodynamics and quantum information. Until now, this subfield has remained theoretical. We initiate the experimental testing of its predictions, with a trapped-ion simulator. We prepare 6-21 spins in an approximate microcanonical subspace, a generalization of the microcanonical subspace for accommodating noncommuting charges, which cannot necessarily have well-defined nontrivial values simultaneously. We simulate a Heisenberg evolution using laser-induced entangling interactions and collective spin rotations. The noncommuting charges are the three spin components. We find that small subsystems equilibrate to near a recently predicted non-Abelian thermal state. This work bridges quantum many-body simulators to the quantum thermodynamics of noncommuting charges, whose predictions can now be tested.

1 aKranzl, Florian1 aLasek, Aleksander1 aJoshi, Manoj, K.1 aKalev, Amir1 aBlatt, Rainer1 aRoos, Christian, F.1 aHalpern, Nicole, Yunger uhttps://arxiv.org/abs/2202.0465201025nas a2200145 4500008004100000245002800041210002800069260001400097520064400111100002200755700002200777700002000799700002300819856003700842 2023 eng d00aQuantum spherical codes0 aQuantum spherical codes c12/7/20233 a

We introduce a framework for constructing quantum codes defined on spheres by recasting such codes as quantum analogues of the classical spherical codes. We apply this framework to bosonic coding, obtaining multimode extensions of the cat codes that can outperform previous constructions while requiring a similar type of overhead. Our polytope-based cat codes consist of sets of points with large separation that at the same time form averaging sets known as spherical designs. We also recast concatenations of CSS codes with cat codes as quantum spherical codes, revealing a new way to autonomously protect against dephasing noise

1 aJain, Shubham, P.1 aIosue, Joseph, T.1 aBarg, Alexander1 aAlbert, Victor, V. uhttps://arxiv.org/abs/2302.1159305435nas a2201621 4500008004100000245010800041210006900149260001500218520094500233100001801178700002301196700001601219700002801235700002001263700002001283700001601303700002001319700002101339700002401360700001901384700001901403700002601422700001801448700002301466700002101489700001601510700001701526700002101543700002301564700002101587700001601608700001701624700003101641700003401672700001801706700001801724700002101742700001801763700002401781700001801805700002001823700003501843700002201878700001601900700002001916700001901936700001701955700001901972700002301991700001802014700002402032700002302056700002302079700001802102700001702120700001902137700002602156700002002182700001902202700001902221700002302240700001802263700002202281700001802303700001902321700002802340700002402368700001902392700002002411700002002431700002702451700001202478700001702490700001502507700002102522700001802543700001902561700003202580700002402612700002202636700003102658700001702689700002302706700002402729700002002753700001902773700001902792700001602811700001702827700001802844700001802862700002002880700001902900700002302919700001902942700001702961700002602978700001603004700002003020700001603040700001803056700002803074700002103102700001803123700002403141700001403165700002303179700002003202700002103222700002003243700001803263700001803281700002103299700002103320700002303341700001803364700001803382700001403400700001903414700001603433700001503449700002003464700002103484700002103505700001703526700002803543700002203571700002303593700002603616700001503642700001703657700002303674700002403697700001803721700001703739700002003756856003703776 2023 eng d00aQuantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions0 aQuantumcentric Supercomputing for Materials Science A Perspectiv c12/14/20233 a

Computational models are an essential tool for the design, characterization, and discovery of novel materials. Hard computational tasks in materials science stretch the limits of existing high-performance supercomputing centers, consuming much of their simulation, analysis, and data resources. Quantum computing, on the other hand, is an emerging technology with the potential to accelerate many of the computational tasks needed for materials science. In order to do that, the quantum technology must interact with conventional high-performance computing in several ways: approximate results validation, identification of hard problems, and synergies in quantum-centric supercomputing. In this paper, we provide a perspective on how quantum-centric supercomputing can help address critical computational problems in materials science, the challenges to face in order to solve representative use cases, and new suggested directions.

1 aAlexeev, Yuri1 aAmsler, Maximilian1 aBaity, Paul1 aBarroca, Marco, Antonio1 aBassini, Sanzio1 aBattelle, Torey1 aCamps, Daan1 aCasanova, David1 aChoi, Young, jai1 aChong, Frederic, T.1 aChung, Charles1 aCodella, Chris1 aCorcoles, Antonio, D.1 aCruise, James1 aDi Meglio, Alberto1 aDubois, Jonathan1 aDuran, Ivan1 aEckl, Thomas1 aEconomou, Sophia1 aEidenbenz, Stephan1 aElmegreen, Bruce1 aFare, Clyde1 aFaro, Ismael1 aFernández, Cristina, Sanz1 aFerreira, Rodrigo, Neumann Ba1 aFuji, Keisuke1 aFuller, Bryce1 aGagliardi, Laura1 aGalli, Giulia1 aGlick, Jennifer, R.1 aGobbi, Isacco1 aGokhale, Pranav1 aGonzalez, Salvador, de la Puen1 aGreiner, Johannes1 aGropp, Bill1 aGrossi, Michele1 aGull, Emmanuel1 aHealy, Burns1 aHuang, Benchen1 aHumble, Travis, S.1 aIto, Nobuyasu1 aIzmaylov, Artur, F.1 aJavadi-Abhari, Ali1 aJennewein, Douglas1 aJha, Shantenu1 aJiang, Liang1 aJones, Barbara1 ade Jong, Wibe, Albert1 aJurcevic, Petar1 aKirby, William1 aKister, Stefan1 aKitagawa, Masahiro1 aKlassen, Joel1 aKlymko, Katherine1 aKoh, Kwangwon1 aKondo, Masaaki1 aKurkcuoglu, Doga, Murat1 aKurowski, Krzysztof1 aLaino, Teodoro1 aLandfield, Ryan1 aLeininger, Matt1 aLeyton-Ortega, Vicente1 aLi, Ang1 aLin, Meifeng1 aLiu, Junyu1 aLorente, Nicolas1 aLuckow, Andre1 aMartiel, Simon1 aMartin-Fernandez, Francisco1 aMartonosi, Margaret1 aMarvinney, Claire1 aMedina, Arcesio, Castaneda1 aMerten, Dirk1 aMezzacapo, Antonio1 aMichielsen, Kristel1 aMitra, Abhishek1 aMittal, Tushar1 aMoon, Kyungsun1 aMoore, Joel1 aMotta, Mario1 aNa, Young-Hye1 aNam, Yunseong1 aNarang, Prineha1 aOhnishi, Yu-ya1 aOttaviani, Daniele1 aOtten, Matthew1 aPakin, Scott1 aPascuzzi, Vincent, R.1 aPenault, Ed1 aPiontek, Tomasz1 aPitera, Jed1 aRall, Patrick1 aRavi, Gokul, Subramania1 aRobertson, Niall1 aRossi, Matteo1 aRydlichowski, Piotr1 aRyu, Hoon1 aSamsonidze, Georgy1 aSato, Mitsuhisa1 aSaurabh, Nishant1 aSharma, Vidushi1 aSharma, Kunal1 aShin, Soyoung1 aSlessman, George1 aSteiner, Mathias1 aSitdikov, Iskandar1 aSuh, In-Saeng1 aSwitzer, Eric1 aTang, Wei1 aThompson, Joel1 aTodo, Synge1 aTran, Minh1 aTrenev, Dimitar1 aTrott, Christian1 aTseng, Huan-Hsin1 aTureci, Esin1 aValinas, David, García1 aVallecorsa, Sofia1 aWever, Christopher1 aWojciechowski, Konrad1 aWu, Xiaodi1 aYoo, Shinjae1 aYoshioka, Nobuyuki1 aYu, Victor, Wen-zhe1 aYunoki, Seiji1 aZhuk, Sergiy1 aZubarev, Dmitry uhttps://arxiv.org/abs/2312.0973301560nas a2200181 4500008004100000245006500041210005800106260001500164520103400179100001701213700002101230700002201251700002301273700002001296700001801316700002301334856002101357 2023 eng d00aOn the Rational Degree of Boolean Functions and Applications0 aRational Degree of Boolean Functions and Applications c10/12/20233 a

We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions f, it is conjectured that rdeg(f) is polynomially related to deg(f), where deg(f) is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least deg(f)/2 and monotone functions have rational degree at least deg(f)−−−−−√. We observe that both of these lower bounds are tight. In addition, we show that all read-once depth-d Boolean formulae have rational degree at least Ω(deg(f)1/d). Furthermore, we show that almost every Boolean function on n variables has rational degree at least n/2−O(n−−√).
In contrast to total functions, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model.

1 aIyer, Vishnu1 aJain, Siddhartha1 aKovacs-Deak, Matt1 aKumar, Vinayak, M.1 aSchaeffer, Luke1 aWang, Daochen1 aWhitmeyer, Michael uarXiv:2310.0800401752nas a2200133 4500008004100000245009000041210007000131260001400201520130500215100002201520700002001542700001901562856003701581 2023 eng d00aOn the stability of solutions to Schrödinger's equation short of the adiabatic limit0 astability of solutions to Schrödingers equation short of the adi c3/23/20233 a

We prove an adiabatic theorem that applies at timescales short of the adiabatic limit. Our proof analyzes the stability of solutions to Schrodinger's equation under perturbation. We directly characterize cross-subspace effects of perturbation, which are typically significantly less than suggested by the perturbation's operator norm. This stability has numerous consequences: we can (1) find timescales where the solution of Schrodinger's equation converges to the ground state of a block, (2) lower bound the convergence to the global ground state by demonstrating convergence to some other known quantum state, (3) guarantee faster convergence than the standard adiabatic theorem when the ground state of the perturbed Hamiltonian (H) is close to that of the unperturbed H, and (4) bound tunneling effects in terms of the global spectral gap when H is ``stoquastic'' (a Z-matrix). Our results apply to quantum annealing protocols with faster convergence than usually guaranteed by a standard adiabatic theorem. Our upper and lower bounds demonstrate that at timescales short of the adiabatic limit, subspace dynamics can dominate over global dynamics. Thus, we see that convergence to particular target states can be understood as the result of otherwise local dynamics.

1 aBringewatt, Jacob1 aJarret, Michael1 aMooney, T., C. uhttps://arxiv.org/abs/2303.1347801108nas a2200145 4500008004100000245001300041210001300054260001500067520075200082100002200834700002100856700002500877700002300902856003700925 2023 eng d00aÆ codes0 aÆ codes c11/21/20233 a

Diatomic molecular codes [{arXiv:1911.00099}] are designed to encode quantum information in the orientation of a diatomic molecule, allowing error correction from small torques and changes in angular momentum. Here, we directly study noise native to atomic and molecular platforms -- spontaneous emission, stray electromagnetic fields, and Raman scattering -- and derive simple necessary and sufficient conditions for codes to protect against such noise. We identify existing and develop new absorption-emission (Æ) codes that are more practical than molecular codes, require lower average momentum, can directly protect against photonic processes up to arbitrary order, and are applicable to a broader set of atomic and molecular systems.

1 aJain, Shubham, P.1 aHudson, Eric, R.1 aCampbell, Wesley, C.1 aAlbert, Victor, V. uhttps://arxiv.org/abs/2311.1232402045nas a2200337 4500008004100000245009200041210006900133260001500202300001100217490000800228520091000236100001301146700001301159700001401172700001701186700002001203700001401223700001401237700001601251700001901267700001801286700001701304700002101321700001501342700002001357700001701377700001701394700001801411700001801429856026001447 2022 eng d00aClosing the Locality and Detection Loopholes in Multiparticle Entanglement Self-Testing0 aClosing the Locality and Detection Loopholes in Multiparticle En c06/23/2022 a2504010 v1283 a

First proposed by Mayers and Yao, self-testing provides a certification method to infer the underlying physics of quantum experiments in a black-box scenario. Numerous demonstrations have been reported to self-test various types of entangled states. However, all the multiparticle self-testing experiments reported so far suffer from both detection and locality loopholes. Here, we report the first experimental realization of multiparticle entanglement self-testing closing the locality loophole in a photonic system, and the detection loophole in a superconducting system, respectively. We certify three-party and four-party GHZ states with at least 0.84 (1) and 0.86 (3) fidelities in a device-independent way. These results can be viewed as a meaningful advance in multiparticle loophole-free self-testing, and also significant progress on the foundations of quantum entanglement certification.

1 aWu, Dian1 aZhao, Qi1 aWang, Can1 aHuang, Liang1 aJiang, Yang-Fan1 aBai, Bing1 aZhou, You1 aGu, Xue-Mei1 aLiu, Feng-Ming1 aMao, Ying-Qiu1 aSun, Qi-Chao1 aChen, Ming-Cheng1 aZhang, Jun1 aPeng, Cheng-Zhi1 aZhu, Xiao-Bo1 aZhang, Qiang1 aLu, Chao-Yang1 aPan, Jian-Wei uhttps://www.researchgate.net/profile/Dian-Wu/publication/361497881_Closing_the_Locality_and_Detection_Loopholes_in_Multiparticle_Entanglement_Self-Testing/links/62b55a8c1010dc02cc57530c/Closing-the-Locality-and-Detection-Loopholes-in-Multiparticle-Entangl02428nas a2200217 4500008004100000245010600041210006900147260001400216520171900230653004301949653002701992653002902019653003102048100001702079700001502096700001302111700001702124700001602141700001602157856003702173 2022 eng d00aEfficient and practical quantum compiler towards multi-qubit systems with deep reinforcement learning0 aEfficient and practical quantum compiler towards multiqubit syst c4/14/20223 a

Efficient quantum compiling tactics greatly enhance the capability of quantum computers to execute complicated quantum algorithms. Due to its fundamental importance, a plethora of quantum compilers has been designed in past years. However, there are several caveats to current protocols, which are low optimality, high inference time, limited scalability, and lack of universality. To compensate for these defects, here we devise an efficient and practical quantum compiler assisted by advanced deep reinforcement learning (RL) techniques, i.e., data generation, deep Q-learning, and AQ* search. In this way, our protocol is compatible with various quantum machines and can be used to compile multi-qubit operators. We systematically evaluate the performance of our proposal in compiling quantum operators with both inverse-closed and inverse-free universal basis sets. In the task of single-qubit operator compiling, our proposal outperforms other RL-based quantum compilers in the measure of compiling sequence length and inference time. Meanwhile, the output solution is near-optimal, guaranteed by the Solovay-Kitaev theorem. Notably, for the inverse-free universal basis set, the achieved sequence length complexity is comparable with the inverse-based setting and dramatically advances previous methods. These empirical results contribute to improving the inverse-free Solovay-Kitaev theorem. In addition, for the first time, we demonstrate how to leverage RL-based quantum compilers to accomplish two-qubit operator compiling. The achieved results open an avenue for integrating RL with quantum compiling to unify efficiency and practicality and thus facilitate the exploration of quantum advantages.

10aFOS: Computer and information sciences10aFOS: Physical sciences10aMachine Learning (cs.LG)10aQuantum Physics (quant-ph)1 aChen, Qiuhao1 aDu, Yuxuan1 aZhao, Qi1 aJiao, Yuling1 aLu, Xiliang1 aWu, Xingyao uhttps://arxiv.org/abs/2204.0690401492nas a2200181 4500008004100000245008600041210006900127260001500196490000600211520094800217100001601165700002301181700002101204700001701225700001701242700001401259856003701273 2022 eng d00aEfficient Product Formulas for Commutators and Applications to Quantum Simulation0 aEfficient Product Formulas for Commutators and Applications to Q c03/10/20220 v43 a

We construct product formulas for exponentials of commutators and explore their applications. First, we directly construct a third-order product formula with six exponentials by solving polynomial equations obtained using the operator differential method. We then derive higher-order product formulas recursively from the third-order formula. We improve over previous recursive constructions, reducing the number of gates required to achieve the same accuracy. In addition, we demonstrate that the constituent linear terms in the commutator can be included at no extra cost. As an application, we show how to use the product formulas in a digital protocol for counterdiabatic driving, which increases the fidelity for quantum state preparation. We also discuss applications to quantum simulation of one-dimensional fermion chains with nearest- and next-nearest-neighbor hopping terms, and two-dimensional fractional quantum Hall phases.

1 aChen, Yu-An1 aChilds, Andrew, M.1 aHafezi, Mohammad1 aJiang, Zhang1 aKim, Hwanmun1 aXu, Yijia uhttps://arxiv.org/abs/2111.1217701837nas a2200169 4500008004100000245009700041210006900138260001300207520131000220100001301530700001301543700002001556700001801576700002001594700001601614856003701630 2022 eng d00aEfficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation0 aEfficient quantum algorithm for nonlinear reactiondiffusion equa c5/2/20223 a

Nonlinear differential equations exhibit rich phenomena in many fields but are notoriously challenging to solve. Recently, Liu et al. [1] demonstrated the first efficient quantum algorithm for dissipative quadratic differential equations under the condition R<1, where R measures the ratio of nonlinearity to dissipation using the ℓ2 norm. Here we develop an efficient quantum algorithm based on [1] for reaction-diffusion equations, a class of nonlinear partial differential equations (PDEs). To achieve this, we improve upon the Carleman linearization approach introduced in [1] to obtain a faster convergence rate under the condition RD<1, where RD measures the ratio of nonlinearity to dissipation using the ℓ∞ norm. Since RD is independent of the number of spatial grid points n while R increases with n, the criterion RD<1 is significantly milder than R<1 for high-dimensional systems and can stay convergent under grid refinement for approximating PDEs. As applications of our quantum algorithm we consider the Fisher-KPP and Allen-Cahn equations, which have interpretations in classical physics. In particular, we show how to estimate the mean square kinetic energy in the solution by postprocessing the quantum state that encodes it to extract derivative information.

1 aAn, Dong1 aFang, Di1 aJordan, Stephen1 aLiu, Jin-Peng1 aLow, Guang, Hao1 aWang, Jiasu uhttps://arxiv.org/abs/2205.0114101880nas a2200133 4500008004100000245008500041210006900126260001500195520144100210100001701651700002101668700002001689856003701709 2022 eng d00aEstimating gate complexities for the site-by-site preparation of fermionic vacua0 aEstimating gate complexities for the sitebysite preparation of f c07/04/20223 a

An important aspect of quantum simulation is the preparation of physically interesting states on a quantum computer, and this task can often be costly or challenging to implement. A digital, ``site-by-site'' scheme of state preparation was introduced in arXiv:1911.03505 as a way to prepare the vacuum state of certain fermionic field theory Hamiltonians with a mass gap. More generally, this algorithm may be used to prepare ground states of Hamiltonians by adding one site at a time as long as successive intermediate ground states share a non-zero overlap and the Hamiltonian has a non-vanishing spectral gap at finite lattice size. In this paper, we study the ground state overlap as a function of the number of sites for a range of quadratic fermionic Hamiltonians. Using analytical formulas known for free fermions, we are able to explore the large-N behavior and draw conclusions about the state overlap. For all models studied, we find that the overlap remains large (e.g. >0.1) up to large lattice sizes (N=64,72) except near quantum phase transitions or in the presence of gapless edge modes. For one-dimensional systems, we further find that two N/2-site ground states also share a large overlap with the N-site ground state everywhere except a region near the phase boundary. Based on these numerical results, we additionally propose a recursive alternative to the site-by-site state preparation algorithm.

1 aSewell, Troy1 aBapat, Aniruddha1 aJordan, Stephen uhttps://arxiv.org/abs/2207.0169202003nas a2200217 4500008004100000245007300041210006900114260001300183520129800196653002701494653003101521653004701552100002001599700002201619700002101641700001601662700001801678700002401696700002801720856003701748 2022 eng d00aExperimental observation of thermalisation with noncommuting charges0 aExperimental observation of thermalisation with noncommuting cha c2/9/20223 a

Quantum simulators have recently enabled experimental observations of quantum many-body systems' internal thermalisation. Often, the global energy and particle number are conserved, and the system is prepared with a well-defined particle number - in a microcanonical subspace. However, quantum evolution can also conserve quantities, or charges, that fail to commute with each other. Noncommuting charges have recently emerged as a subfield at the intersection of quantum thermodynamics and quantum information. Until now, this subfield has remained theoretical. We initiate the experimental testing of its predictions, with a trapped-ion simulator. We prepare 6-15 spins in an approximate microcanonical subspace, a generalisation of the microcanonical subspace for accommodating noncommuting charges, which cannot necessarily have well-defined nontrivial values simultaneously. We simulate a Heisenberg evolution using laser-induced entangling interactions and collective spin rotations. The noncommuting charges are the three spin components. We find that small subsystems equilibrate to near a recently predicted non-Abelian thermal state. This work bridges quantum many-body simulators to the quantum thermodynamics of noncommuting charges, whose predictions can now be tested.

10aFOS: Physical sciences10aQuantum Physics (quant-ph)10aStatistical Mechanics (cond-mat.stat-mech)1 aKranzl, Florian1 aLasek, Aleksander1 aJoshi, Manoj, K.1 aKalev, Amir1 aBlatt, Rainer1 aRoos, Christian, F.1 aHalpern, Nicole, Yunger uhttps://arxiv.org/abs/2202.0465201587nas a2200181 4500008004100000245010600041210006900147260001400216520099600230653002701226653003101253100001801284700001701302700001501319700001701334700001701351856003701368 2022 eng d00aShadow Distillation: Quantum Error Mitigation with Classical Shadows for Near-Term Quantum Processors0 aShadow Distillation Quantum Error Mitigation with Classical Shad c3/14/20223 a

Mitigating errors in quantum information processing devices is especially important in the absence of fault tolerance. An effective method in suppressing state-preparation errors is using multiple copies to distill the ideal component from a noisy quantum state. Here, we use classical shadows and randomized measurements to circumvent the need for coherent access to multiple copies at an exponential cost. We study the scaling of resources using numerical simulations and find that the overhead is still favorable compared to full state tomography. We optimize measurement resources under realistic experimental constraints and apply our method to an experiment preparing Greenberger-Horne-Zeilinger (GHZ) state with trapped ions. In addition to improving stabilizer measurements, the analysis of the improved results reveals the nature of errors affecting the experiment. Hence, our results provide a directly applicable method for mitigating errors in near-term quantum computers.

10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aSeif, Alireza1 aCian, Ze-Pei1 aZhou, Sisi1 aChen, Senrui1 aJiang, Liang uhttps://arxiv.org/abs/2203.0730901880nas a2200229 4500008004100000245005800041210005800099260001500157490000700172520123000179100002001409700002101429700001701450700002601467700002001493700001701513700001801530700001901548700002201567700002401589856003701613 2022 eng d00aToward Robust Autotuning of Noisy Quantum dot Devices0 aToward Robust Autotuning of Noisy Quantum dot Devices c02/26/20220 v173 a

The current autotuning approaches for quantum dot (QD) devices, while showing some success, lack an assessment of data reliability. This leads to unexpected failures when noisy or otherwise low-quality data is processed by an autonomous system. In this work, we propose a framework for robust autotuning of QD devices that combines a machine learning (ML) state classifier with a data quality control module. The data quality control module acts as a "gatekeeper" system, ensuring that only reliable data are processed by the state classifier. Lower data quality results in either device recalibration or termination. To train both ML systems, we enhance the QD simulation by incorporating synthetic noise typical of QD experiments. We confirm that the inclusion of synthetic noise in the training of the state classifier significantly improves the performance, resulting in an accuracy of 95.0(9) % when tested on experimental data. We then validate the functionality of the data quality control module by showing that the state classifier performance deteriorates with decreasing data quality, as expected. Our results establish a robust and flexible ML framework for autonomous tuning of noisy QD devices.

1 aZiegler, Joshua1 aMcJunkin, Thomas1 aJoseph, E.S.1 aKalantre, Sandesh, S.1 aHarpt, Benjamin1 aSavage, D.E.1 aLagally, M.G.1 aEriksson, M.A.1 aTaylor, Jacob, M.1 aZwolak, Justyna, P. uhttps://arxiv.org/abs/2108.0004301434nas a2200169 4500008004100000022001400041245009100055210006900146260001400215490000600229520089000235100001801125700002301143700002301166700002501189856005001214 2021 eng d a2691-339900aComplexity of Fermionic Dissipative Interactions and Applications to Quantum Computing0 aComplexity of Fermionic Dissipative Interactions and Application c9/17/20210 v23 a

Interactions between particles are usually a resource for quantum computing, making quantum many-body systems intractable by any known classical algorithm. In contrast, noise is typically considered as being inimical to quantum many-body correlations, ultimately leading the system to a classically tractable state. This work shows that noise represented by two-body processes, such as pair loss, plays the same role as many-body interactions and makes otherwise classically simulable systems universal for quantum computing. We analyze such processes in detail and establish a complexity transition between simulable and nonsimulable systems as a function of a tuning parameter. We determine important classes of simulable and nonsimulable two-body dissipation. Finally, we show how using resonant dissipation in cold atoms can enhance the performance of two-qubit gates. 

1 aShtanko, Oles1 aDeshpande, Abhinav1 aJulienne, Paul, S.1 aGorshkov, Alexey, V. uhttp://dx.doi.org/10.1103/PRXQuantum.2.03035001588nas a2200241 4500008004100000022001400041245008300055210006900138260001400207300001100221490000600232520086600238100002401104700002201128700002101150700001801171700002801189700001401217700002401231700002301255700002101278856004701299 2021 eng d a2058-956500aEntangled quantum cellular automata, physical complexity, and Goldilocks rules0 aEntangled quantum cellular automata physical complexity and Gold c9/29/2021 a0450170 v63 a

Cellular automata are interacting classical bits that display diverse emergent behaviors, from fractals to random-number generators to Turing-complete computation. We discover that quantum cellular automata (QCA) can exhibit complexity in the sense of the complexity science that describes biology, sociology, and economics. QCA exhibit complexity when evolving under "Goldilocks rules" that we define by balancing activity and stasis. Our Goldilocks rules generate robust dynamical features (entangled breathers), network structure and dynamics consistent with complexity, and persistent entropy fluctuations. Present-day experimental platforms -- Rydberg arrays, trapped ions, and superconducting qubits -- can implement our Goldilocks protocols, making testable the link between complexity science and quantum computation exposed by our QCA.

1 aHillberry, Logan, E1 aJones, Matthew, T1 aVargas, David, L1 aRall, Patrick1 aHalpern, Nicole, Yunger1 aBao, Ning1 aNotarnicola, Simone1 aMontangero, Simone1 aCarr, Lincoln, D uhttp://dx.doi.org/10.1088/2058-9565/ac1c4101481nas a2200193 4500008004100000245004300041210004200084260001400126300001100140490000800151520095100159100001501110700002001125700002301145700001801168700002001186700001701206856006401223 2021 eng d00aPhase-engineered bosonic quantum codes0 aPhaseengineered bosonic quantum codes c6/29/2021 a0624270 v1033 a

Continuous-variable systems protected by bosonic quantum codes have emerged as a promising platform for quantum information. To date, the design of code words has centered on optimizing the state occupation in the relevant basis to generate the distance needed for error correction. Here, we show tuning the phase degree of freedom in the design of code words can affect, and potentially enhance, the protection against Markovian errors that involve excitation exchange with the environment. As illustrations, we first consider phase engineering bosonic codes with uniform spacing in the Fock basis that correct excitation loss with a Kerr unitary and show that these modified codes feature destructive interference between error code words and, with an adapted “two-level” recovery, the error protection is significantly enhanced. We then study protection against energy decay with the presence of mode nonlinearities …

1 aLi, Linshu1 aYoung, Dylan, J1 aAlbert, Victor, V.1 aNoh, Kyungjoo1 aZou, Chang-Ling1 aJiang, Liang uhttps://authors.library.caltech.edu/109764/2/1901.05358.pdf01810nas a2200121 4500008004100000245006600041210006600107260001400173520141900187100002101606700002401627856003701651 2021 eng d00aPreparing Renormalization Group Fixed Points on NISQ Hardware0 aPreparing Renormalization Group Fixed Points on NISQ Hardware c9/20/20213 a

Noisy intermediate-scale quantum (NISQ) hardware is typically limited to low-depth quantum circuits to limit the number of opportunities for introduction of error by unreliable quantum gates. A less-explored alternative approach is to repeatedly apply a quantum channel with a desired quantum state as a stable fixed point. Increased circuit depth can in this case be beneficial rather than harmful due to dissipative self-correction. The quantum channels constructed from MERA circuits can be interpreted in terms of the renormalization group(RG), and their fixed points are RG fixed points, i.e. scale-invariant systems such as conformal field theories. Here, building upon the theoretical proposal of Kim and Swingle, we numerically and experimentally study the robust preparation of the ground state of the critical Ising model using circuits adapted from the work of Evenbly and White. The experimental implementation exhibits self-correction through renormalization seen in the convergence and stability of local observables, and makes essential use of the ability to measure and reset individual qubits afforded by the "quantum CCD" architecture of the Honeywell ion-trap. We also numerically test error mitigation by zero-noise extrapolation schemes specially adapted for renormalization circuits, which are able to outperform typical extrapolation schemes using lower gate overhead. 

1 aSewell, Troy, J.1 aJordan, Stephen, P. uhttps://arxiv.org/abs/2109.0978701237nas a2200253 4500008004100000245004100041210004100082260001300123520055200136100001900688700002400707700002100731700002000752700002700772700001800799700001600817700001700833700002000850700002100870700001900891700001300910700002300923856003700946 2021 eng d00aQuantum Machine Learning for Finance0 aQuantum Machine Learning for Finance c9/9/20213 a

Quantum computers are expected to surpass the computational capabilities of classical computers during this decade, and achieve disruptive impact on numerous industry sectors, particularly finance. In fact, finance is estimated to be the first industry sector to benefit from Quantum Computing not only in the medium and long terms, but even in the short term. This review paper presents the state of the art of quantum algorithms for financial applications, with particular focus to those use cases that can be solved via Machine Learning.

1 aPistoia, Marco1 aAhmad, Syed, Farhan1 aAjagekar, Akshay1 aButs, Alexander1 aChakrabarti, Shouvanik1 aHerman, Dylan1 aHu, Shaohan1 aJena, Andrew1 aMinssen, Pierre1 aNiroula, Pradeep1 aRattew, Arthur1 aSun, Yue1 aYalovetzky, Romina uhttps://arxiv.org/abs/2109.0429801449nas a2200169 4500008004100000245007200041210006900113260001500182520093700197100002301134700001701157700001601174700001501190700001801205700001901223856003701242 2021 eng d00aSpin chains, defects, and quantum wires for the quantum-double edge0 aSpin chains defects and quantum wires for the quantumdouble edge c11/23/20213 a

Non-Abelian defects that bind Majorana or parafermion zero modes are prominent in several topological quantum computation schemes. Underpinning their established understanding is the quantum Ising spin chain, which can be recast as a fermionic model or viewed as a standalone effective theory for the surface-code edge -- both of which harbor non-Abelian defects. We generalize these notions by deriving an effective Ising-like spin chain describing the edge of quantum-double topological order. Relating Majorana and parafermion modes to anyonic strings, we introduce quantum-double generalizations of non-Abelian defects. We develop a way to embed finite-group valued qunits into those valued in continuous groups. Using this embedding, we provide a continuum description of the spin chain and recast its non-interacting part as a quantum wire via addition of a Wess-Zumino-Novikov-Witten term and non-Abelian bosonization.

1 aAlbert, Victor, V.1 aAasen, David1 aXu, Wenqing1 aJi, Wenjie1 aAlicea, Jason1 aPreskill, John uhttps://arxiv.org/abs/2111.1209601814nas a2200121 4500008004100000245006700041210006700108260001400175520142100189100002101610700002401631856003701655 2020 eng d00aApproximate optimization of MAXCUT with a local spin algorithm0 aApproximate optimization of MAXCUT with a local spin algorithm c8/13/20203 a

Local tensor methods are a class of optimization algorithms that was introduced in [Hastings,arXiv:1905.07047v2][1] as a classical analogue of the quantum approximate optimization algorithm (QAOA). These algorithms treat the cost function as a Hamiltonian on spin degrees of freedom and simulate the relaxation of the system to a low energy configuration using local update rules on the spins. Whereas the emphasis in [1] was on theoretical worst-case analysis, we here investigate performance in practice through benchmarking experiments on instances of the MAXCUT problem.Through heuristic arguments we propose formulas for choosing the hyperparameters of the algorithm which are found to be in good agreement with the optimal choices determined from experiment. We observe that the local tensor method is closely related to gradient descent on a relaxation of maxcut to continuous variables, but consistently outperforms gradient descent in all instances tested. We find time to solution achieved by the local tensor method is highly uncorrelated with that achieved by a widely used commercial optimization package; on some MAXCUT instances the local tensor method beats the commercial solver in time to solution by up to two orders of magnitude and vice-versa. Finally, we argue that the local tensor method closely follows discretized, imaginary-time dynamics of the system under the problem Hamiltonian.

1 aBapat, Aniruddha1 aJordan, Stephen, P. uhttps://arxiv.org/abs/2008.0605401710nas a2200121 4500008004100000245011300041210006900154260001400223520127200237100002201509700002001531856003701551 2020 eng d00aEffective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians0 aEffective gaps are not effective quasipolynomial classical simul c4/21/20203 a

All known examples confirming the possibility of an exponential separation between classical simulation algorithms and stoquastic adiabatic quantum computing (AQC) exploit symmetries that constrain adiabatic dynamics to effective, symmetric subspaces. The symmetries produce large effective eigenvalue gaps, which in turn make adiabatic computation efficient. We present a classical algorithm to efficiently sample from the effective subspace of a k-local stoquastic Hamiltonian H, without a priori knowledge of its symmetries (or near-symmetries). Our algorithm maps any k-local Hamiltonian to a graph G=(V,E) with |V|=O(poly(n)) where n is the number of qubits. Given the well-known result of Babai, we exploit graph isomorphism to study the automorphisms of G and arrive at an algorithm quasi-polynomial in |V| for producing samples from the effective subspace eigenstates of H. Our results rule out exponential separations between stoquastic AQC and classical computation that arise from hidden symmetries in k-local Hamiltonians. Furthermore, our graph representation of H is not limited to stoquastic Hamiltonians and may rule out corresponding obstructions in non-stoquastic cases, or be useful in studying additional properties of k-local Hamiltonians.

1 aBringewatt, Jacob1 aJarret, Michael uhttps://arxiv.org/abs/2004.0868101260nas a2200133 4500008004100000245006500041210006000106260001400166520085200180100001901032700001901051700001901070856003701089 2020 eng d00aAn exponential ramp in the quadratic Sachdev-Ye-Kitaev model0 aexponential ramp in the quadratic SachdevYeKitaev model c6/26/20203 a

A long period of linear growth in the spectral form factor provides a universal diagnostic of quantum chaos at intermediate times. By contrast, the behavior of the spectral form factor in disordered integrable many-body models is not well understood. Here we study the two-body Sachdev-Ye-Kitaev model and show that the spectral form factor features an exponential ramp, in sharp contrast to the linear ramp in chaotic models. We find a novel mechanism for this exponential ramp in terms of a high-dimensional manifold of saddle points in the path integral formulation of the spectral form factor. This manifold arises because the theory enjoys a large symmetry group. With finite nonintegrable interaction strength, these delicate symmetries reduce to a relative time translation, causing the exponential ramp to give way to a linear ramp.

1 aWiner, Michael1 aJian, Shao-Kai1 aSwingle, Brian uhttps://arxiv.org/abs/2006.1515201547nas a2200145 4500008004100000245006900041210006900110260001400179520108200193100001801275700002301293700002301316700002501339856003701364 2020 eng d00aLimits on Classical Simulation of Free Fermions with Dissipation0 aLimits on Classical Simulation of Free Fermions with Dissipation c5/21/20203 a

Free-fermionic systems are a valuable, but limited, class of many-body problems efficiently simulable on a classical computer. We examine how classical simulability of noninteracting fermions is modified in the presence of Markovian dissipation described by quadratic Lindblad operators, including, for example, incoherent transitions or pair losses. On the one hand, we establish three broad classes of Markovian dynamics that are efficiently simulable classically, by devising efficient algorithms. On the other hand, we demonstrate that, in the worst case, simulating Markovian dynamics with quadratic Lindblad operators is at least as hard as simulating universal quantum circuits. This result is applicable to an experimentally relevant setting in cold atomic systems, where magnetic Feshbach resonances can be used to engineer the desired dissipation. For such systems, our hardness result provides a direct scheme for dissipation-assisted quantum computing with a potential significant advantage in the speed of two-qubit gates and, therefore, in error tolerance.

1 aShtanko, Oles1 aDeshpande, Abhinav1 aJulienne, Paul, S.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2005.1084001316nas a2200145 4500008004100000245005300041210005300094260001500147300000800162520089700170100001801067700002101085700002701106856003701133 2020 eng d00aMachine learning the thermodynamic arrow of time0 aMachine learning the thermodynamic arrow of time c09/21/2020 a1-93 a

The mechanism by which thermodynamics sets the direction of time's arrow has long fascinated scientists. Here, we show that a machine learning algorithm can learn to discern the direction of time's arrow when provided with a system's microscopic trajectory as input. The performance of our algorithm matches fundamental bounds predicted by nonequilibrium statistical mechanics. Examination of the algorithm's decision-making process reveals that it discovers the underlying thermodynamic mechanism and the relevant physical observables. Our results indicate that machine learning techniques can be used to study systems out of equilibrium, and ultimately to uncover physical principles.

1 aSeif, Alireza1 aHafezi, Mohammad1 aJarzynski, Christopher uhttps://arxiv.org/abs/1909.1238001576nas a2200157 4500008004100000245010800041210006900149260001400218490000600232520106400238100001701302700001601319700002701335700001901362856003701381 2020 eng d00aOptimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning0 aOptimal fermiontoqubit mapping via ternary trees with applicatio c5/26/20200 v43 a

We introduce a fermion-to-qubit mapping defined on ternary trees, where any single Majorana operator on an n-mode fermionic system is mapped to a multi-qubit Pauli operator acting nontrivially on ⌈log3(2n+1)⌉ qubits. The mapping has a simple structure and is optimal in the sense that it is impossible to construct Pauli operators in any fermion-to-qubit mapping acting nontrivially on less than log3(2n) qubits on average. We apply it to the problem of learning k-fermion reduced density matrix (RDM), a problem relevant in various quantum simulation applications. We show that using the ternary-tree mapping one can determine the elements of all k-fermion RDMs, to precision ϵ, by repeating a single quantum circuit for ≲(2n+1)kϵ−2 times. This result is based on a method we develop here that allows one to determine the elements of all k-qubit RDMs, to precision ϵ, by repeating a single quantum circuit for ≲3kϵ−2 times, independent of the system size. This improves over existing schemes for determining qubit RDMs.

1 aJiang, Zhang1 aKalev, Amir1 aMruczkiewicz, Wojciech1 aNeven, Hartmut uhttps://arxiv.org/abs/1910.1074601468nas a2200157 4500008004100000245005700041210005600098260001200154300001400166490000700180520103700187100001601224700001701240700001601257856003701273 2020 eng d00aParallel Device-Independent Quantum Key Distribution0 aParallel DeviceIndependent Quantum Key Distribution c09/2020 a5567-55840 v663 a

A prominent application of quantum cryptography is the distribution of cryptographic keys that are provably secure. Such security proofs were extended by Vazirani and Vidick ( Physical Review Letters , 113, 140501, 2014) to the device-independent (DI) scenario, where the users do not need to trust the integrity of the underlying quantum devices. The protocols analyzed by them and by subsequent authors all require a sequential execution of N multiplayer games, where N is the security parameter. In this work, we prove the security of a protocol where all games are executed in parallel. Besides decreasing the number of time-steps necessary for key generation, this result reduces the security requirements for DI-QKD by allowing arbitrary information leakage of each user’s inputs within his or her lab. To the best of our knowledge, this is the first parallel security proof for a fully device-independent QKD protocol. Our protocol tolerates a constant level of device imprecision and achieves a linear key rate.

1 aJain, Rahul1 aMiller, Carl1 aShi, Yaoyun uhttps://arxiv.org/abs/1703.0542601620nas a2200193 4500008004100000245006300041210006200104260001400166520106800180100001201248700001401260700001901274700002101293700002101314700001801335700001501353700002101368856003701389 2020 eng d00aProbing many-body localization on a noisy quantum computer0 aProbing manybody localization on a noisy quantum computer c6/22/20203 a

A disordered system of interacting particles exhibits localized behavior when the disorder is large compared to the interaction strength. Studying this phenomenon on a quantum computer without error correction is challenging because even weak coupling to a thermal environment destroys most signatures of localization. Fortunately, spectral functions of local operators are known to contain features that can survive the presence of noise. In these spectra, discrete peaks and a soft gap at low frequencies compared to the thermal phase indicate localization. Here, we present the computation of spectral functions on a trapped-ion quantum computer for a one-dimensional Heisenberg model with disorder. Further, we design an error-mitigation technique which is effective at removing the noise from the measurement allowing clear signatures of localization to emerge as the disorder increases. Thus, we show that spectral functions can serve as a robust and scalable diagnostic of many-body localization on the current generation of quantum computers. 

1 aZhu, D.1 aJohri, S.1 aNguyen, N., H.1 aAlderete, Huerta1 aLandsman, K., A.1 aLinke, N., M.1 aMonroe, C.1 aMatsuura, A., Y. uhttps://arxiv.org/abs/2006.1235502525nas a2200169 4500008004100000245006600041210006200107260001400169300000700183490000600190520198300196100001902179700002002198700001702218700002302235856009702258 2020 eng d00aOn Quantum Chosen-Ciphertext Attacks and Learning with Errors0 aQuantum ChosenCiphertext Attacks and Learning with Errors c3/21/2020 a100 v43 a

Large-scale quantum computing poses a major threat to classical public-key cryptography. Recently, strong “quantum access” security models have shown that numerous symmetric-key cryptosystems are also vulnerable. In this paper, we consider classical encryption in a model that grants the adversary quantum oracle access to encryption and decryption, but where we restrict the latter to non-adaptive (i.e., pre-challenge) queries only. We formalize this model using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. We show that the standard pseudorandom function ( PRF )-based encryption schemes are QCCA1 -secure when instantiated with quantum-secure primitives. Our security proofs use a strong bound on quantum random-access codes with shared randomness. Revisiting plain IND−CPA -secure Learning with Errors ( LWE ) encryption, we show that leaking only a single quantum decryption query (and no other leakage or queries of any kind) allows the adversary to recover the full secret key with constant success probability. Information-theoretically, full recovery of the key in the classical setting requires at least a linear number of decryption queries. Our results thus challenge the notion that LWE is unconditionally “just as secure” quantumly as it is classically. The algorithm at the core of our attack is a new variant of the well-known Bernstein–Vazirani algorithm. Finally, we emphasize that our results should not be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones.

1 aAlagic, Gorjan1 aJeffery, Stacey1 aOzols, Maris1 aPoremba, Alexander uhttps://www.quics.umd.edu/publications/quantum-chosen-ciphertext-attacks-and-learning-errors02376nas a2200157 4500008004100000245005000041210004900091260001500140520192200155100002102077700002202098700002002120700001702140700002402157856003702181 2020 eng d00aQuantum coding with low-depth random circuits0 aQuantum coding with lowdepth random circuits c10/19/20203 a

Random quantum circuits have played a central role in establishing the computational advantages of near-term quantum computers over their conventional counterparts. Here, we use ensembles of low-depth random circuits with local connectivity in D≥1 spatial dimensions to generate quantum error-correcting codes. For random stabilizer codes and the erasure channel, we find strong evidence that a depth O(logN) random circuit is necessary and sufficient to converge (with high probability) to zero failure probability for any finite amount below the channel capacity for any D. Previous results on random circuits have only shown that O(N1/D) depth suffices or that O(log3N) depth suffices for all-to-all connectivity (D→∞). We then study the critical behavior of the erasure threshold in the so-called moderate deviation limit, where both the failure probability and the distance to the channel capacity converge to zero with N. We find that the requisite depth scales like O(logN) only for dimensions D≥2, and that random circuits require O(N−−√) depth for D=1. Finally, we introduce an "expurgation" algorithm that uses quantum measurements to remove logical operators that cause the code to fail by turning them into either additional stabilizers or into gauge operators in a subsystem code. With such targeted measurements, we can achieve sub-logarithmic depth in D≥2 spatial dimensions below capacity without increasing the maximum weight of the check operators. We find that for any rate beneath the capacity, high-performing codes with thousands of logical qubits are achievable with depth 4-8 expurgated random circuits in D=2 dimensions. These results indicate that finite-rate quantum codes are practically relevant for near-term devices and may significantly reduce the resource requirements to achieve fault tolerance for near-term applications. 

1 aGullans, Michael1 aKrastanov, Stefan1 aHuse, David, A.1 aJiang, Liang1 aFlammia, Steven, T. uhttps://arxiv.org/abs/2010.0977501826nas a2200145 4500008004100000245009400041210006900135260001300204300001200217490000700229520136600236100002101602700002001623856003701643 2019 eng d00aBang-bang control as a design principle for classical and quantum optimization algorithms0 aBangbang control as a design principle for classical and quantum c8/1/2019 a424-4460 v193 a

Physically motivated classical heuristic optimization algorithms such as simulated annealing (SA) treat the objective function as an energy landscape, and allow walkers to escape local minima. It has been argued that quantum properties such as tunneling may give quantum algorithms advantage in finding ground states of vast, rugged cost landscapes. Indeed, the Quantum Adiabatic Algorithm (QAO) and the recent Quantum Approximate Optimization Algorithm (QAOA) have shown promising results on various problem instances that are considered classically hard. Here, we argue that the type of control strategy used by the optimization algorithm may be crucial to its success. Along with SA, QAO and QAOA, we define a new, bang-bang version of simulated annealing, BBSA, and study the performance of these algorithms on two well-studied problem instances from the literature. Both classically and quantumly, the successful control strategy is found to be bang-bang, exponentially outperforming the quasistatic analogues on the same instances. Lastly, we construct O(1)-depth QAOA protocols for a class of symmetric cost functions, and provide an accompanying physical picture.

1 aBapat, Aniruddha1 aJordan, Stephen uhttps://arxiv.org/abs/1812.0274602955nas a2200397 4500008004100000245008600041210006900127260001500196520181200211100002102023700002302044700002002067700001702087700002202104700001702126700002502143700001802168700001902186700001702205700001702222700002702239700001502266700001702281700001802298700001702316700001602333700002002349700001902369700002302388700002502411700002402436700001802460700002002478700002202498856003702520 2019 eng d00aDevelopment of Quantum InterConnects for Next-Generation Information Technologies0 aDevelopment of Quantum InterConnects for NextGeneration Informat c12/13/20193 a

Just as classical information technology rests on a foundation built of interconnected information-processing systems, quantum information technology (QIT) must do the same. A critical component of such systems is the interconnect, a device or process that allows transfer of information between disparate physical media, for example, semiconductor electronics, individual atoms, light pulses in optical fiber, or microwave fields. While interconnects have been well engineered for decades in the realm of classical information technology, quantum interconnects (QuICs) present special challenges, as they must allow the transfer of fragile quantum states between different physical parts or degrees of freedom of the system. The diversity of QIT platforms (superconducting, atomic, solid-state color center, optical, etc.) that will form a quantum internet poses additional challenges. As quantum systems scale to larger size, the quantum interconnect bottleneck is imminent, and is emerging as a grand challenge for QIT. For these reasons, it is the position of the community represented by participants of the NSF workshop on Quantum Interconnects that accelerating QuIC research is crucial for sustained development of a national quantum science and technology program. Given the diversity of QIT platforms, materials used, applications, and infrastructure required, a convergent research program including partnership between academia, industry and national laboratories is required. This document is a summary from a U.S. National Science Foundation supported workshop held on 31 October - 1 November 2019 in Alexandria, VA. Attendees were charged to identify the scientific and community needs, opportunities, and significant challenges for quantum interconnects over the next 2-5 years. 

1 aAwschalom, David1 aBerggren, Karl, K.1 aBernien, Hannes1 aBhave, Sunil1 aCarr, Lincoln, D.1 aDavids, Paul1 aEconomou, Sophia, E.1 aEnglund, Dirk1 aFaraon, Andrei1 aFejer, Marty1 aGuha, Saikat1 aGustafsson, Martin, V.1 aHu, Evelyn1 aJiang, Liang1 aKim, Jungsang1 aKorzh, Boris1 aKumar, Prem1 aKwiat, Paul, G.1 aLončar, Marko1 aLukin, Mikhail, D.1 aMiller, David, A. B.1 aMonroe, Christopher1 aNam, Sae, Woo1 aNarang, Prineha1 aOrcutt, Jason, S. uhttps://arxiv.org/abs/1912.0664202399nas a2200145 4500008004100000245007900041210006900120300001400189520193400203100001902137700002002156700001702176700002302193856003702216 2019 eng d00aOn non-adaptive quantum chosen-ciphertext attacks and Learning with Errors0 anonadaptive quantum chosenciphertext attacks and Learning with E a1:1-1:23 3 a

Large-scale quantum computing is a significant threat to classical public-key cryptography. In strong "quantum access" security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum random-access codes, we show that the standard PRF- and PRP-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives. We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key uses a linear number of decryption queries, and this is optimal. The algorithm at the core of our attack is a (large-modulus version of) the well-known Bernstein-Vazirani algorithm. We emphasize that our results should *not* be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones. 

1 aAlagic, Gorjan1 aJeffery, Stacey1 aOzols, Maris1 aPoremba, Alexander uhttps://arxiv.org/abs/1808.0965502010nas a2200409 4500008004100000245006800041210006600109260001500175520084400190100001901034700002601053700002001079700002001099700002001119700001701139700002501156700002201181700001901203700001701222700002201239700002101261700002501282700001901307700002301326700001801349700001901367700002101386700002101407700001501428700002001443700002401463700001801487700002301505700001901528700001601547856003701563 2019 eng d00aOpportunities for Nuclear Physics & Quantum Information Science0 aOpportunities for Nuclear Physics Quantum Information Science c03/13/20193 a

his whitepaper is an outcome of the workshop Intersections between Nuclear Physics and Quantum Information held at Argonne National Laboratory on 28-30 March 2018 [www.phy.anl.gov/npqi2018/]. The workshop brought together 116 national and international experts in nuclear physics and quantum information science to explore opportunities for the two fields to collaborate on topics of interest to the U.S. Department of Energy (DOE) Office of Science, Office of Nuclear Physics, and more broadly to U.S. society and industry. The workshop consisted of 22 invited and 10 contributed talks, as well as three panel discussion sessions. Topics discussed included quantum computation, quantum simulation, quantum sensing, nuclear physics detectors, nuclear many-body problem, entanglement at collider energies, and lattice gauge theories.

1 aCloët, I., C.1 aDietrich, Matthew, R.1 aArrington, John1 aBazavov, Alexei1 aBishof, Michael1 aFreese, Adam1 aGorshkov, Alexey, V.1 aGrassellino, Anna1 aHafidi, Kawtar1 aJacob, Zubin1 aMcGuigan, Michael1 aMeurice, Yannick1 aMeziani, Zein-Eddine1 aMueller, Peter1 aMuschik, Christine1 aOsborn, James1 aOtten, Matthew1 aPetreczky, Peter1 aPolakovic, Tomas1 aPoon, Alan1 aPooser, Raphael1 aRoggero, Alessandro1 aSaffman, Mark1 aVanDevender, Brent1 aZhang, Jiehang1 aZohar, Erez uhttps://arxiv.org/abs/1903.0545301434nas a2200193 4500008004100000245005500041210005500096260001500151490000800166520090200174100001701076700001601093700001701109700001801126700002101144700001701165700002101182856003701203 2019 eng d00aPhoton pair condensation by engineered dissipation0 aPhoton pair condensation by engineered dissipation c04/02/20190 v1233 a

Dissipation can usually induce detrimental decoherence in a quantum system. However, engineered dissipation can be used to prepare and stabilize coherent quantum many-body states. Here, we show that by engineering dissipators containing photon pair operators, one can stabilize an exotic dark state, which is a condensate of photon pairs with a phase-nematic order. In this system, the usual superfluid order parameter, i.e. single-photon correlation, is absent, while the photon pair correlation exhibits long-range order. Although the dark state is not unique due to multiple parity sectors, we devise an additional type of dissipators to stabilize the dark state in a particular parity sector via a diffusive annihilation process which obeys Glauber dynamics in an Ising model. Furthermore, we propose an implementation of these photon-pair dissipators in circuit-QED architecture. 

1 aCian, Ze-Pei1 aZhu, Guanyu1 aChu, Su-Kuan1 aSeif, Alireza1 aDeGottardi, Wade1 aJiang, Liang1 aHafezi, Mohammad uhttps://arxiv.org/abs/1904.0001601973nas a2200145 4500008004100000245008000041210006900121260001400190490000800204520151100212100002201723700002101745700002401766856003701790 2019 eng d00aPolynomial Time Algorithms for Estimating Spectra of Adiabatic Hamiltonians0 aPolynomial Time Algorithms for Estimating Spectra of Adiabatic H c10/1/20200 v1003 a

Much research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians with Hamming symmetric potentials, such as the well studied "spike" example. Due to the large amount of symmetry in these potentials such problems are readily open to analysis both analytically and computationally. However, more realistic potentials do not have such a high degree of symmetry and may have many local minima. Here we present a somewhat more realistic class of problems consisting of many individually Hamming symmetric potential wells. For two or three such wells we demonstrate that such a problem can be solved exactly in time polynomial in the number of qubits and wells. For greater than three wells, we present a tight binding approach with which to efficiently analyze the performance of such Hamiltonians in an adiabatic computation. We provide several basic examples designed to highlight the usefulness of this toy model and to give insight into using the tight binding approach to examining it, including: (1) adiabatic unstructured search with a transverse field driver and a prior guess to the marked item and (2) a scheme for adiabatically simulating the ground states of small collections of strongly interacting spins, with an explicit demonstration for an Ising model Hamiltonian.

1 aBringewatt, Jacob1 aDorland, William1 aJordan, Stephen, P. uhttps://arxiv.org/abs/1905.0746101091nas a2200145 4500008004100000245005500041210005500096260001500151490000800166520066600174100002300840700002400863700002100887856003700908 2019 eng d00aQuantum Algorithm for Simulating the Wave Equation0 aQuantum Algorithm for Simulating the Wave Equation c03/24/20190 v99 3 a

We present a quantum algorithm for simulating the wave equation under Dirichlet and Neumann boundary conditions. The algorithm uses Hamiltonian simulation and quantum linear system algorithms as subroutines. It relies on factorizations of discretized Laplacian operators to allow for improved scaling in truncation errors and improved scaling for state preparation relative to general purpose linear differential equation algorithms. We also consider using Hamiltonian simulation for Klein-Gordon equations and Maxwell's equations.

1 aCosta, Pedro, C.S.1 aJordan, Stephen, P.1 aOstrander, Aaron uhttps://arxiv.org/abs/1711.0539401764nas a2200289 4500008004100000245007400041210006900115260001500184520095900199100001501158700001401173700001501187700002001202700001101222700001701233700001901250700002001269700001601289700002901305700001801334700001801352700001201370700001501382700002501397700001501422856003701437 2019 eng d00aQuantum Approximate Optimization with a Trapped-Ion Quantum Simulator0 aQuantum Approximate Optimization with a TrappedIon Quantum Simul c06/06/20193 a

Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly solving exponentially hard problems, such as optimization and satisfiability. Here we report the first implementation of a shallow-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator to estimate the ground state energy of the transverse field Ising model with tunable long-range interactions. First, we exhaustively search the variational control parameters to approximate the ground state energy with up to 40 trapped-ion qubits. We then interface the quantum simulator with a classical algorithm to more efficiently find the optimal set of parameters that minimizes the resulting energy of the system. We finally sample from the full probability distribution of the QAOA output with single-shot and efficient measurements of every qubit. 

1 aPagano, G.1 aBapat, A.1 aBecker, P.1 aCollins, K., S.1 aDe, A.1 aHess, P., W.1 aKaplan, H., B.1 aKyprianidis, A.1 aTan, W., L.1 aBaldwin, Christopher, L.1 aBrady, L., T.1 aDeshpande, A.1 aLiu, F.1 aJordan, S.1 aGorshkov, Alexey, V.1 aMonroe, C. uhttps://arxiv.org/abs/1906.0270001711nas a2200181 4500008004100000245005600041210005600097260001500153490000700168520117600175100002301351700002701374700002101401700001701422700002401439700002901463856003701492 2019 eng d00aQuantum repeaters based on two species trapped ions0 aQuantum repeaters based on two species trapped ions c05/02/20190 v213 a

We examine the viability of quantum repeaters based on two-species trapped ion modules for long distance quantum key distribution. Repeater nodes comprised of ion-trap modules of co-trapped ions of distinct species are considered. The species used for communication qubits has excellent optical properties while the other longer lived species serves as a memory qubit in the modules. Each module interacts with the network only via single photons emitted by the communication ions. Coherent Coulomb interaction between ions is utilized to transfer quantum information between the communication and memory ions and to achieve entanglement swapping between two memory ions. We describe simple modular quantum repeater architectures realizable with the ion-trap modules and numerically study the dependence of the quantum key distribution rate on various experimental parameters, including coupling efficiency, gate infidelity, operation time and length of the elementary links. Our analysis suggests crucial improvements necessary in a physical implementation for co-trapped two-species ions to be a competitive platform in long-distance quantum communication. 

1 aSantra, Siddhartha1 aMuralidharan, Sreraman1 aLichtman, Martin1 aJiang, Liang1 aMonroe, Christopher1 aMalinovsky, Vladimir, S. uhttps://arxiv.org/abs/1811.1072301623nas a2200133 4500008004100000245011100041210006900152260001400221520114300235100002601378700002401404700002401428856003701452 2019 eng d00aSite-by-site quantum state preparation algorithm for preparing vacua of fermionic lattice field theories 0 aSitebysite quantum state preparation algorithm for preparing vac c2019/11/83 a

Answering whether quantum computers can efficiently simulate quantum field theories has both theoretical and practical motivation. From the theoretical point of view, it answers the question of whether a hypothetical computer that utilizes quantum field theory would be more powerful than other quantum computers. From the practical point of view, when reliable quantum computers are eventually built, these algorithms can help us better understand the underlying physics that govern our world. In the best known quantum algorithms for simulating quantum field theories, the time scaling is dominated by initial state preparation. In this paper, we exclusively focus on state preparation and present a heuristic algorithm that can prepare the vacuum of fermionic systems in more general cases and more efficiently than previous methods. With our method, state preparation is no longer the bottleneck, as its runtime has the same asymptotic scaling with the desired precision as the remainder of the simulation algorithm. We numerically demonstrate the effectiveness of our proposed method for the 1+1 dimensional Gross-Neveu model.

1 aMoosavian, Ali, Hamed1 aGarrison, James, R.1 aJordan, Stephen, P. uhttps://arxiv.org/abs/1911.0350501856nas a2200169 4500008004100000245006600041210006500107260001500172300000700187490000600194520134900200100002401549700001601573700002201589700001901611856005601630 2018 eng d00aBQP-completeness of Scattering in Scalar Quantum Field Theory0 aBQPcompleteness of Scattering in Scalar Quantum Field Theory c2018/01/08 a440 v23 a

Recent work has shown that quantum computers can compute scattering probabilities in massive quantum field theories, with a run time that is polynomial in the number of particles, their energy, and the desired precision. Here we study a closely related quantum field-theoretical problem: estimating the vacuum-to-vacuum transition amplitude, in the presence of spacetime-dependent classical sources, for a massive scalar field theory in (1+1) dimensions. We show that this problem is BQP-hard; in other words, its solution enables one to solve any problem that is solvable in polynomial time by a quantum computer. Hence, the vacuum-to-vacuum amplitude cannot be accurately estimated by any efficient classical algorithm, even if the field theory is very weakly coupled, unless BQP=BPP. Furthermore, the corresponding decision problem can be solved by a quantum computer in a time scaling polynomially with the number of bits needed to specify the classical source fields, and this problem is therefore BQP-complete. Our construction can be regarded as an idealized architecture for a universal quantum computer in a laboratory system described by massive phi^4 theory coupled to classical spacetime-dependent sources.

1 aJordan, Stephen, P.1 aKrovi, Hari1 aLee, Keith, S. M.1 aPreskill, John uhttps://quantum-journal.org/papers/q-2018-01-08-44/01379nas a2200217 4500008004100000245005600041210005400097520077800151100001600929700001800945700001300963700001400976700002200990700001501012700002001027700001401047700002001061700001801081700002501099856003701124 2018 eng d00aCoherent optical nano-tweezers for ultra-cold atoms0 aCoherent optical nanotweezers for ultracold atoms3 a

There has been a recent surge of interest and progress in creating subwavelength free-space optical potentials for ultra-cold atoms. A key open question is whether geometric potentials, which are repulsive and ubiquitous in the creation of subwavelength free-space potentials, forbid the creation of narrow traps with long lifetimes. Here, we show that it is possible to create such traps. We propose two schemes for realizing subwavelength traps and demonstrate their superiority over existing proposals. We analyze the lifetime of atoms in such traps and show that long-lived bound states are possible. This work opens a new frontier for the subwavelength control and manipulation of ultracold matter, with applications in quantum chemistry and quantum simulation.

1 aBienias, P.1 aSubhankar, S.1 aWang, Y.1 aTsui, T-C1 aJendrzejewski, F.1 aTiecke, T.1 aJuzeliūnas, G.1 aJiang, L.1 aRolston, S., L.1 aPorto, J., V.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1808.0248701752nas a2200169 4500008004100000245007800041210006900119260001500188300001100203490000700214520121000221100002201431700002101453700002401474700001501498856006901513 2018 eng d00aDiffusion Monte Carlo Versus Adiabatic Computation for Local Hamiltonians0 aDiffusion Monte Carlo Versus Adiabatic Computation for Local Ham c2018/02/15 a0223230 v973 a

Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real, nonnegative amplitudes. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-k-SAT problems, use k-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved n-body interactions. Here we present a new 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.

1 aBringewatt, Jacob1 aDorland, William1 aJordan, Stephen, P.1 aMink, Alan uhttps://journals.aps.org/pra/abstract/10.1103/PhysRevA.97.02232301425nas a2200157 4500008004100000245007800041210006900119260001500188520092400203100001601127700001701143700002201160700002501182700002301207856003701230 2018 eng d00aDistributed Quantum Metrology and the Entangling Power of Linear Networks0 aDistributed Quantum Metrology and the Entangling Power of Linear c2018/07/253 a

We derive a bound on the ability of a linear optical network to estimate a linear combination of independent phase shifts by using an arbitrary non-classical but unentangled input state, thereby elucidating the quantum resources required to obtain the Heisenberg limit with a multi-port interferometer. Our bound reveals that while linear networks can generate highly entangled states, they cannot effectively combine quantum resources that are well distributed across multiple modes for the purposes of metrology: in this sense linear networks endowed with well-distributed quantum resources behave classically. Conversely, our bound shows that linear networks can achieve the Heisenberg limit for distributed metrology when the input photons are hoarded in a small number of input modes, and we present an explicit scheme for doing so. Our results also have implications for measures of non-classicality. 

1 aGe, Wenchao1 aJacobs, Kurt1 aEldredge, Zachary1 aGorshkov, Alexey, V.1 aFoss-Feig, Michael uhttps://arxiv.org/abs/1707.0665501538nas a2200157 4500008004100000245007800041210006900119260001500188520103700203100001601240700001701256700002201273700002501295700002301320856003701343 2018 eng d00aDistributed Quantum Metrology and the Entangling Power of Linear Networks0 aDistributed Quantum Metrology and the Entangling Power of Linear c2018/07/253 a

We derive a bound on the ability of a linear optical network to estimate a linear combination of independent phase shifts by using an arbitrary non-classical but unentangled input state, thereby elucidating the quantum resources required to obtain the Heisenberg limit with a multi-port interferometer. Our bound reveals that while linear networks can generate highly entangled states, they cannot effectively combine quantum resources that are well distributed across multiple modes for the purposes of metrology: in this sense linear networks endowed with well-distributed quantum resources behave classically. Conversely, our bound shows that linear networks can achieve the Heisenberg limit for distributed metrology when the input photons are hoarded in a small number of input modes, and we present an explicit scheme for doing so. Our results also have implications for measures of non-classicality.

1 aGe, Wenchao1 aJacobs, Kurt1 aEldredge, Zachary1 aGorshkov, Alexey, V.1 aFoss-Feig, Michael uhttps://arxiv.org/abs/1707.0665502638nas a2200265 4500008004100000245009500041210006900136260001500205300001200220490000800232520186000240100002102100700001902121700001802140700001802158700001502176700002002191700001902211700001602230700002502246700001802271700002402289700002202313856003702335 2018 eng d00aExperimentally Generated Randomness Certified by the Impossibility of Superluminal Signals0 aExperimentally Generated Randomness Certified by the Impossibili c2018/04/11 a223-2260 v5563 a

From dice to modern complex circuits, there have been many attempts to build increasingly better devices to generate random numbers. Today, randomness is fundamental to security and cryptographic systems, as well as safeguarding privacy. A key challenge with random number generators is that it is hard to ensure that their outputs are unpredictable. For a random number generator based on a physical process, such as a noisy classical system or an elementary quantum measurement, a detailed model describing the underlying physics is required to assert unpredictability. Such a model must make a number of assumptions that may not be valid, thereby compromising the integrity of the device. However, it is possible to exploit the phenomenon of quantum nonlocality with a loophole-free Bell test to build a random number generator that can produce output that is unpredictable to any adversary limited only by general physical principles. With recent technological developments, it is now possible to carry out such a loophole-free Bell test. Here we present certified randomness obtained from a photonic Bell experiment and extract 1024 random bits uniform to within 10−12. These random bits could not have been predicted within any physical theory that prohibits superluminal signaling and allows one to make independent measurement choices. To certify and quantify the randomness, we describe a new protocol that is optimized for apparatuses characterized by a low per-trial violation of Bell inequalities. We thus enlisted an experimental result that fundamentally challenges the notion of determinism to build a system that can increase trust in random sources. In the future, random number generators based on loophole-free Bell tests may play a role in increasing the security and trust of our cryptographic systems and infrastructure.

1 aBierhorst, Peter1 aKnill, Emanuel1 aGlancy, Scott1 aZhang, Yanbao1 aMink, Alan1 aJordan, Stephen1 aRommal, Andrea1 aLiu, Yi-Kai1 aChristensen, Bradley1 aNam, Sae, Woo1 aStevens, Martin, J.1 aShalm, Lynden, K. uhttps://arxiv.org/abs/1803.0621901418nas a2200145 4500008004100000245007200041210006900113260001500182300001100197490000600208520097500214100002601189700002001215856003701235 2018 eng d00aFaster Quantum Algorithm to simulate Fermionic Quantum Field Theory0 aFaster Quantum Algorithm to simulate Fermionic Quantum Field The c2018/05/04 a0123320 vA3 a

In quantum algorithms discovered so far for simulating scattering processes in quantum field theories, state preparation is the slowest step. We present a new algorithm for preparing particle states to use in simulation of Fermionic Quantum Field Theory (QFT) on a quantum computer, which is based on the matrix product state ansatz. We apply this to the massive Gross-Neveu model in one spatial dimension to illustrate the algorithm, but we believe the same algorithm with slight modifications can be used to simulate any one-dimensional massive Fermionic QFT. In the case where the number of particle species is one, our algorithm can prepare particle states using O(ε−3.23…) gates, which is much faster than previous known results, namely O(ε−8−o(1)). Furthermore, unlike previous methods which were based on adiabatic state preparation, the method given here should be able to simulate quantum phases unconnected to the free theory.

1 aMoosavian, Ali, Hamed1 aJordan, Stephen uhttps://arxiv.org/abs/1711.0400601180nas a2200157 4500008004100000245007300041210006900114490000800183520068500191100001800876700002900894700002400923700001600947700002200963856003700985 2018 eng d00aOptimal Pure-State Qubit Tomography via Sequential Weak Measurements0 aOptimal PureState Qubit Tomography via Sequential Weak Measureme0 v1213 a

The spin-coherent-state positive-operator-valued-measure (POVM) is a fundamental measurement in quantum science, with applications including tomography, metrology, teleportation, benchmarking, and measurement of Husimi phase space probabilities. We prove that this POVM is achieved by collectively measuring the spin projection of an ensemble of qubits weakly and isotropically. We apply this in the context of optimal tomography of pure qubits. We show numerically that through a sequence of weak measurements of random directions of the collective spin component, sampled discretely or in a continuous measurement with random controls, one can approach the optimal bound.

1 aShojaee, Ezad1 aJackson, Christopher, S.1 aRiofrio, Carlos, A.1 aKalev, Amir1 aDeutsch, Ivan, H. uhttps://arxiv.org/abs/1805.0101201127nas a2200145 4500008004100000245006400041210006200105260001500167490001000182520070300192100001800895700001600913700001500929856003700944 2018 eng d00aPseudorandom States, Non-Cloning Theorems and Quantum Money0 aPseudorandom States NonCloning Theorems and Quantum Money c2017/11/010 v109933 a

We propose the concept of pseudorandom states and study their constructions, properties, and applications. Under the assumption that quantum-secure one-way functions exist, we present concrete and efficient constructions of pseudorandom states. The non-cloning theorem plays a central role in our study—it motivates the proper definition and characterizes one of the important properties of pseudorandom quantum states. Namely, there is no efficient quantum algorithm that can create more copies of the state from a given number of pseudorandom states. As the main application, we prove that any family of pseudorandom states naturally gives rise to a private-key quantum money scheme.

1 aJi, Zhengfeng1 aLiu, Yi-Kai1 aSong, Fang uhttps://arxiv.org/abs/1711.0038502027nas a2200133 4500008004100000245005400041210005400095520164000149100002001789700001701809700001401826700001601840856003701856 2018 eng d00aQuantum adiabatic optimization without heuristics0 aQuantum adiabatic optimization without heuristics3 a

Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian H(s) with spectral gap γ(s). Assuming the existence of an oracle Γ such that γ(s)=Θ(Γ(s)), we provide an algorithm that reliably performs QAO in time Oγ−1minlog(γ−1min) with Olog(γ−1min) oracle queries, where γmin=minsγ(s). Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that dH/ds≈γ(s) and chooses its own runtime T to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle Γ for the problem of finding a vertex m=argminuW(u) of the cost function W:V⟶[0,1], restricting ourselves to computational basis measurements and driving Hamiltonian H(0)=I−V−1∑u,v∈V|u⟩⟨v|, with V=|V|. Requiring only that W have a constant lower bound on its spectral gap and upper bound κ on its spectral ratio, our QAO algorithm returns m using Γ with probability (1−ε)(1−e−1/ε) in time O˜(ε−1[V−−√+(κ−1)2/3V2/3]). This achieves a quantum advantage for all κ, and when κ≈1, recovers Grover scaling up to logarithmic factors. We implement the algorithm as a subroutine in an optimization procedure that produces m with exponentially small failure probability and expected runtime O˜(ε−1[V−−√+(κ−1)2/3V2/3]), even when κ is not known beforehand.

1 aJarret, Michael1 aLackey, Brad1 aLiu, Aike1 aWan, Kianna uhttps://arxiv.org/abs/1810.0468600433nas a2200133 4500008004100000245005200041210004900093260001200142300001000154490000700164100002400171700001600195856008800211 2018 eng d00aQuantum Cryptanalysis: Shor, Grover, and Beyond0 aQuantum Cryptanalysis Shor Grover and Beyond c2018/09 a14-210 v161 aJordan, Stephen, P.1 aLiu, Yi-Kai uhttps://www.quics.umd.edu/publications/quantum-cryptanalysis-shor-grover-and-beyond01805nas a2200217 4500008004100000245005000041210005000091260001500141300001100156490000800167520121700175100002101392700001401413700002401427700001801451700002001469700001701489700002501506700001901531856003701550 2017 eng d00aEfimov States of Strongly Interacting Photons0 aEfimov States of Strongly Interacting Photons c2017/12/04 a2336010 v1193 a

We demonstrate the emergence of universal Efimov physics for interacting photons in cold gases of Rydberg atoms. We consider the behavior of three photons injected into the gas in their propagating frame, where a paraxial approximation allows us to consider them as massive particles. In contrast to atoms and nuclei, the photons have a large anisotropy between their longitudinal mass, arising from dispersion, and their transverse mass, arising from diffraction. Nevertheless, we show that in suitably rescaled coordinates the effective interactions become dominated by s-wave scattering near threshold and, as a result, give rise to an Efimov effect near unitarity, but with spatially anisotropic wavefunctions in the original coordinates. We show that the three-body loss of these Efimov trimers can be strongly suppressed and determine conditions under which these states are observable in current experiments. These effects can be naturally extended to probe few-body universality beyond three bodies, as well as the role of Efimov physics in the non-equilbrium, many-body regime.

1 aGullans, Michael1 aDiehl, S.1 aRittenhouse, S., T.1 aRuzic, B., P.1 aD'Incao, J., P.1 aJulienne, P.1 aGorshkov, Alexey, V.1 aTaylor, J., M. uhttps://arxiv.org/abs/1709.0195501341nas a2200193 4500008004100000245007600041210006900117260001500186300001100201490000800212520075400220100002200974700001800996700002001014700001401034700002001048700001901068856006001087 2017 eng d00aExperimental Study of Optimal Measurements for Quantum State Tomography0 aExperimental Study of Optimal Measurements for Quantum State Tom c2017/10/13 a1504010 v1193 a

Quantum tomography is a critically important tool to evaluate quantum hardware, making it essential to develop optimized measurement strategies that are both accurate and efficient. We compare a variety of strategies using nearly pure test states. Those that are informationally complete for all states are found to be accurate and reliable even in the presence of errors in the measurements themselves, while those designed to be complete only for pure states are far more efficient but highly sensitive to such errors. Our results highlight the unavoidable trade-offs inherent in quantum tomography.

1 aSosa-Martinez, H.1 aLysne, N., K.1 aBaldwin, C., H.1 aKalev, A.1 aDeutsch, I., H.1 aJessen, P., S. uhttps://link.aps.org/doi/10.1103/PhysRevLett.119.15040101575nas a2200217 4500008004100000245010100041210006900142260001500211520089600226100002101122700001901143700001801162700001501180700002401195700001901219700001601238700002501254700001801279700002201297856003801319 2017 eng d00aExperimentally Generated Random Numbers Certified by the Impossibility of Superluminal Signaling0 aExperimentally Generated Random Numbers Certified by the Impossi c2017/02/163 a

Random numbers are an important resource for applications such as numerical simulation and secure communication. However, it is difficult to certify whether a physical random number generator is truly unpredictable. Here, we exploit the phenomenon of quantum nonlocality in a loophole-free photonic Bell test experiment for the generation of randomness that cannot be predicted within any physical theory that allows one to make independent measurement choices and prohibits superluminal signaling. To certify and quantify the randomness, we describe a new protocol that performs well in an experimental regime characterized by low violation of Bell inequalities. Applying an extractor function to our data, we obtained 256 new random bits, uniform to within 0.001.

1 aBierhorst, Peter1 aKnill, Emanuel1 aGlancy, Scott1 aMink, Alan1 aJordan, Stephen, P.1 aRommal, Andrea1 aLiu, Yi-Kai1 aChristensen, Bradley1 aNam, Sae, Woo1 aShalm, Lynden, K. uhttps://arxiv.org/abs/1702.05178#01300nas a2200169 4500008004100000245006300041210006300104260001500167300001100182490000700193520081800200100001401018700002001032700002401052700001701076856003701093 2017 eng d00aFast optimization algorithms and the cosmological constant0 aFast optimization algorithms and the cosmological constant c2017/11/13 a1035120 v963 a

Denef and Douglas have observed that in certain landscape models the problem of finding small values of the cosmological constant is a large instance of an NP-hard problem. The number of elementary operations (quantum gates) needed to solve this problem by brute force search exceeds the estimated computational capacity of the observable universe. Here we describe a way out of this puzzling circumstance: despite being NP-hard, the problem of finding a small cosmological constant can be attacked by more sophisticated algorithms whose performance vastly exceeds brute force search. In fact, in some parameter regimes the average-case complexity is polynomial. We demonstrate this by explicitly finding a cosmological constant of order 10−120 in a randomly generated 109 -dimensional ADK landscape.

1 aBao, Ning1 aBousso, Raphael1 aJordan, Stephen, P.1 aLackey, Brad uhttps://arxiv.org/abs/1706.0850322768nas a2200133 45000080041000002450055000412100055000962600015001513000011001664900007001775202237100184100002422555856005522579 2017 eng d00aFast quantum computation at arbitrarily low energy0 aFast quantum computation at arbitrarily low energy c2017/03/06 a0323050 v953 a

One version of the energy-time uncertainty principle states that the minimum time T for a quantum system to evolve from a given state to any orthogonal state is h/(4ΔE), where ΔE is the energy uncertainty. A related bound called the Margolus-Levitin theorem states that Th/(2E), where E is the expectation value of energy and the ground energy is taken to be zero. Many subsequent works have interpreted T as defining a minimal time for an elementary computational operation and correspondingly a fundamental limit on clock speed determined by a system's energy. Here we present local time-independent Hamiltonians in which computational clock speed becomes arbitrarily large relative to E and ΔE as the number of computational steps goes to infinity. We argue that energy considerations alone are not sufficient to obtain an upper bound on computational speed, and that additional physical assumptions such as limits to information density and information transmission speed are necessary to obtain such a bound.

1 aJordan, Stephen, P. uhttp://link.aps.org/doi/10.1103/PhysRevA.95.03230501224nas a2200145 4500008004100000245013100041210006900172260001500241300001400256490000800270520068500278100002000963700002400983856007101007 2017 eng d00aModulus of continuity eigenvalue bounds for homogeneous graphs and convex subgraphs with applications to quantum Hamiltonians0 aModulus of continuity eigenvalue bounds for homogeneous graphs a c2017/03/03 a1269-12900 v4523 a

We adapt modulus of continuity estimates to the study of spectra of combinatorial graph Laplacians, as well as the Dirichlet spectra of certain weighted Laplacians. The latter case is equivalent to stoquastic Hamiltonians and is of current interest in both condensed matter physics and quantum computing. In particular, we introduce a new technique which bounds the spectral gap of such Laplacians (Hamiltonians) by studying the limiting behavior of the oscillations of their eigenvectors when introduced into the heat equation. Our approach is based on recent advances in the PDE literature, which include a proof of the fundamental gap theorem by Andrews and Clutterbuck.

1 aJarret, Michael1 aJordan, Stephen, P. uhttp://www.sciencedirect.com/science/article/pii/S0022247X1730272X01240nas a2200121 4500008004100000245006900041210006900110260001500179520084800194100002001042700001901062856003701081 2017 eng d00aQuantum Algorithms for Graph Connectivity and Formula Evaluation0 aQuantum Algorithms for Graph Connectivity and Formula Evaluation c2017/04/033 a

We give a new upper bound on the quantum query complexity of deciding st-connectivity on certain classes of planar graphs, and show the bound is sometimes exponentially better than previous results. We then show Boolean formula evaluation reduces to deciding connectivity on just such a class of graphs. Applying the algorithm for st-connectivity to Boolean formula evaluation problems, we match the O( √ N) bound on the quantum query complexity of evaluating formulas on N variables, give a quadratic speed-up over the classical query complexity of a certain class of promise Boolean formulas, and show this approach can yield superpolynomial quantum/classical separations. These results indicate that this st-connectivity-based approach may be the “right” way of looking at quantum algorithms for formula evaluation.

1 aJeffery, Stacey1 aKimmel, Shelby uhttps://arxiv.org/abs/1704.0076501598nas a2200241 4500008004100000245005800041210005800099260001500157300001100172490000800183520093100191100001301122700001401135700001801149700001601167700001801183700001801201700001301219700001601232700001401248700002201262856007201284 2017 eng d00aQuantum state tomography via reduced density matrices0 aQuantum state tomography via reduced density matrices c2017/01/09 a0204010 v1183 a

Quantum state tomography via local measurements is an efficient tool for characterizing quantum states. However it requires that the original global state be uniquely determined (UD) by its local reduced density matrices (RDMs). In this work we demonstrate for the first time a class of states that are UD by their RDMs under the assumption that the global state is pure, but fail to be UD in the absence of that assumption. This discovery allows us to classify quantum states according to their UD properties, with the requirement that each class be treated distinctly in the practice of simplifying quantum state tomography. Additionally we experimentally test the feasibility and stability of performing quantum state tomography via the measurement of local RDMs for each class. These theoretical and experimental results advance the project of performing efficient and accurate quantum state tomography in practice.

1 aXin, Tao1 aLu, Dawei1 aKlassen, Joel1 aYu, Nengkun1 aJi, Zhengfeng1 aChen, Jianxin1 aMa, Xian1 aLong, Guilu1 aZeng, Bei1 aLaflamme, Raymond uhttp://journals.aps.org/prl/abstract/10.1103/PhysRevLett.118.02040103676nas a2200121 4500008004100000245004100041210004100082260001500123520334200138100002003480700001703500856003703517 2017 eng d00aSubstochastic Monte Carlo Algorithms0 aSubstochastic Monte Carlo Algorithms c2017/04/283 a

In this paper we introduce and formalize Substochastic Monte Carlo (SSMC) algorithms. These algorithms, originally intended to be a better classical foil to quantum annealing than simulated annealing, prove to be worthy optimization algorithms in their own right. In SSMC, a population of walkers is initialized according to a known distribution on an arbitrary search space and varied into the solution of some optimization problem of interest. The first argument of this paper shows how an existing classical algorithm, "Go-With-The-Winners" (GWW), is a limiting case of SSMC when restricted to binary search and particular driving dynamics. 
Although limiting to GWW, SSMC is more general. We show that (1) GWW can be efficiently simulated within the SSMC framework, (2) SSMC can be exponentially faster than GWW, (3) by naturally incorporating structural information, SSMC can exponentially outperform the quantum algorithm that first inspired it, and (4) SSMC exhibits desirable search features in general spaces. Our approach combines ideas from genetic algorithms (GWW), theoretical probability (Fleming-Viot processes), and quantum computing. Not only do we demonstrate that SSMC is often more efficient than competing algorithms, but we also hope that our results connecting these disciplines will impact each independently. An implemented version of SSMC has previously enjoyed some success as a competitive optimization algorithm for Max-k-SAT.

1 aJarret, Michael1 aLackey, Brad uhttps://arxiv.org/abs/1704.0901401455nas a2200157 4500008004100000245005600041210005600097260001500153300001100168490000700179520101300186100002001199700002401219700001701243856003701260 2016 eng d00aAdiabatic optimization versus diffusion Monte Carlo0 aAdiabatic optimization versus diffusion Monte Carlo c2016/07/12 a0423180 v943 a

Most experimental and theoretical studies of adiabatic optimization use stoquastic Hamiltonians, whose ground states are expressible using only real nonnegative amplitudes. This raises a question as to whether classical Monte Carlo methods can simulate stoquastic adiabatic algorithms with polynomial overhead. Here, we analyze diffusion Monte Carlo algorithms. We argue that, based on differences between L1 and L2 normalized states, these algorithms suffer from certain obstructions preventing them from efficiently simulating stoquastic adiabatic evolution in generality. In practice however, we obtain good performance by introducing a method that we call Substochastic Monte Carlo. In fact, our simulations are good classical optimization algorithms in their own right, competitive with the best previously known heuristic solvers for MAX-k-SAT at k=2,3,4.

1 aJarret, Michael1 aJordan, Stephen, P.1 aLackey, Brad uhttps://arxiv.org/abs/1607.0338900790nas a2200145 4500008004100000022001400041245008400055210006900139260001500208300001200223490000700235520033900242100002400581856003900605 2016 eng d a1528-497200aBlack Holes, Quantum Mechanics, and the Limits of Polynomial-time Computability0 aBlack Holes Quantum Mechanics and the Limits of Polynomialtime C c2016/09/20 a30–330 v233 a

Which computational problems can be solved in polynomial-time and which cannot? Though seemingly technical, this question has wide-ranging implications and brings us to the heart of both theoretical computer science and modern physics.

1 aJordan, Stephen, P. uhttp://doi.acm.org/10.1145/298353901599nas a2200169 4500008004100000245004900041210004900090260001500139520107400154100001901228700002001247700002001267700002501287700002501312700002401337856006801361 2016 eng d00aComputational Security of Quantum Encryption0 aComputational Security of Quantum Encryption c2016/11/103 a

Quantum-mechanical devices have the potential to transform cryptography. Most research in this area has focused either on the information-theoretic advantages of quantum protocols or on the security of classical cryptographic schemes against quantum attacks. In this work, we initiate the study of another relevant topic: the encryption of quantum data in the computational setting. In this direction, we establish quantum versions of several fundamental classical results. First, we develop natural definitions for private-key and public-key encryption schemes for quantum data. We then define notions of semantic security and indistinguishability, and, in analogy with the classical work of Goldwasser and Micali, show that these notions are equivalent. Finally, we construct secure quantum encryption schemes from basic primitives. In particular, we show that quantum-secure one-way functions imply IND-CCA1-secure symmetric-key quantum encryption, and that quantum-secure trapdoor one-way permutations imply semantically-secure public-key quantum encryption.

1 aAlagic, Gorjan1 aBroadbent, Anne1 aFefferman, Bill1 aGagliardoni, Tommaso1 aSchaffner, Christian1 aJules, Michael, St. uhttps://link.springer.com/chapter/10.1007%2F978-3-319-49175-2_301164nas a2200169 4500008004100000245007500041210006900116260001500185300001100200490000700211520067400218100001800892700001800910700001600928700001400944856003600958 2016 eng d00aDetecting Consistency of Overlapping Quantum Marginals by Separability0 aDetecting Consistency of Overlapping Quantum Marginals by Separa c2016/03/03 a0321050 v933 a The quantum marginal problem asks whether a set of given density matrices are consistent, i.e., whether they can be the reduced density matrices of a global quantum state. Not many non-trivial analytic necessary (or sufficient) conditions are known for the problem in general. We propose a method to detect consistency of overlapping quantum marginals by considering the separability of some derived states. Our method works well for the $k$-symmetric extension problem in general, and for the general overlapping marginal problems in some cases. Our work is, in some sense, the converse to the well-known $k$-symmetric extension criterion for separability. 1 aChen, Jianxin1 aJi, Zhengfeng1 aYu, Nengkun1 aZeng, Bei uhttp://arxiv.org/abs/1509.0659101660nas a2200157 4500008004100000245004900041210004800090260001500138300001100153490000800164520123800172100001401410700001801424700002401442856003601466 2016 eng d00aGrover search and the no-signaling principle0 aGrover search and the nosignaling principle c2016/09/14 a1205010 v1173 a

From an information processing point of view, two of the key properties of quantum physics are the no-signaling principle and the Grover search lower bound. That is, despite admitting stronger-than-classical correlations, quantum mechanics does not imply superluminal signaling, and despite a form of exponential parallelism, quantum mechanics does not imply polynomial-time brute force solution of NP-complete problems. Here, we investigate the degree to which these two properties are connected. We examine four classes of deviations from quantum mechanics, for which we draw inspiration from the literature on the black hole information paradox: nonunitary dynamics, non-Born-rule measurement, cloning, and postselection. We find that each model admits superluminal signaling if and only if it admits a query complexity speedup over Grover's algorithm. Furthermore, we show that the physical resources required to send a superluminal signal scale polynomially with the resources needed to speed up Grover's algorithm. Hence, one can perform a physically reasonable experiment demonstrating superluminal signaling if and only if one can perform a reasonable experiment inducing a speedup over Grover's algorithm.

1 aBao, Ning1 aBouland, Adam1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1511.0065701247nas a2200169 4500008004100000245005400041210005400095260001500149300001200164520072500176100002400901700002000925700002100945700001600966700001800982856007701000 2016 eng d00aHigh resolution adaptive imaging of a single atom0 aHigh resolution adaptive imaging of a single atom c2016/07/18 a606-6103 a

We report the optical imaging of a single atom with nanometer resolution using an adaptive optical alignment technique that is applicable to general optical microscopy. By decomposing the image of a single laser-cooled atom, we identify and correct optical aberrations in the system and realize an atomic position sensitivity of ≈ 0.5 nm/Hz−−−√ with a minimum uncertainty of 1.7 nm, allowing the direct imaging of atomic motion. This is the highest position sensitivity ever measured for an isolated atom, and opens up the possibility of performing out-of-focus 3D particle tracking, imaging of atoms in 3D optical lattices or sensing forces at the yoctonewton (10−24 N) scale.

1 aWong-Campos, J., D.1 aJohnson, K., G.1 aNeyenhuis, Brian1 aMizrahi, J.1 aMonroe, Chris uhttps://www.nature.com/nphoton/journal/v10/n9/full/nphoton.2016.136.html01855nas a2200157 4500008004100000245011400041210006900155260001500224300001100239490000700250520131500257100001801572700002001590700001901610856006801629 2016 eng d00aA Hubbard model for ultracold bosonic atoms interacting via zero-point-energy induced three-body interactions0 aHubbard model for ultracold bosonic atoms interacting via zeropo c2016/04/19 a0436160 v933 a

We show that for ultra-cold neutral bosonic atoms held in a three-dimensional periodic potential or optical lattice, a Hubbard model with dominant, attractive three-body interactions can be generated. In fact, we derive that the effect of pair-wise interactions can be made small or zero starting from the realization that collisions occur at the zero-point energy of an optical lattice site and the strength of the interactions is energy dependent from effective-range contributions. We determine the strength of the two- and three-body interactions for scattering from van-der-Waals potentials and near Fano-Feshbach resonances. For van-der-Waals potentials, which for example describe scattering of alkaline-earth atoms, we find that the pair-wise interaction can only be turned off for species with a small negative scattering length, leaving the 88Sr isotope a possible candidate. Interestingly, for collisional magnetic Feshbach resonances this restriction does not apply and there often exist magnetic fields where the two-body interaction is small. We illustrate this result for several known narrow resonances between alkali-metal atoms as well as chromium atoms. Finally, we compare the size of the three-body interaction with hopping rates and describe limits due to three-body recombination.

1 aPaul, Saurabh1 aJohnson, P., R.1 aTiesinga, Eite uhttp://journals.aps.org/pra/abstract/10.1103/PhysRevA.93.04361601692nas a2200181 4500008004100000245007500041210006900116260001500185520116000200100001801360700001501378700001801393700001901411700001601430700001401446700001401460856003601474 2016 eng d00aJoint product numerical range and geometry of reduced density matrices0 aJoint product numerical range and geometry of reduced density ma c2016/06/233 aThe reduced density matrices of a many-body quantum system form a convex set, whose three-dimensional projection Θ is convex in R3. The boundary ∂Θ of Θ may exhibit nontrivial geometry, in particular ruled surfaces. Two physical mechanisms are known for the origins of ruled surfaces: symmetry breaking and gapless. In this work, we study the emergence of ruled surfaces for systems with local Hamiltonians in infinite spatial dimension, where the reduced density matrices are known to be separable as a consequence of the quantum de Finetti's theorem. This allows us to identify the reduced density matrix geometry with joint product numerical range Π of the Hamiltonian interaction terms. We focus on the case where the interaction terms have certain structures, such that ruled surface emerge naturally when taking a convex hull of Π. We show that, a ruled surface on ∂Θ sitting in Π has a gapless origin, otherwise it has a symmetry breaking origin. As an example, we demonstrate that a famous ruled surface, known as the oloid, is a possible shape of Θ, with two boundary pieces of symmetry breaking origin separated by two gapless lines.1 aChen, Jianxin1 aGuo, Cheng1 aJi, Zhengfeng1 aPoon, Yiu-Tung1 aYu, Nengkun1 aZeng, Bei1 aZhou, Jie uhttp://arxiv.org/abs/1606.0742201645nas a2200205 4500008004100000245008200041210006900123260001500192300001100207490000700218520102200225100001501247700002401262700002101286700001701307700001601324700002701340700001701367856005501384 2016 eng d00aOptimized tomography of continuous variable systems using excitation counting0 aOptimized tomography of continuous variable systems using excita c2016/11/21 a0523270 v943 a

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.

1 aShen, Chao1 aHeeres, Reinier, W.1 aReinhold, Philip1 aJiang, Luyao1 aLiu, Yi-Kai1 aSchoelkopf, Robert, J.1 aJiang, Liang uhttp://link.aps.org/doi/10.1103/PhysRevA.94.05232701486nas a2200181 4500008004100000245004800041210004800089260001500137300001100152490000700163520100000170100001801170700002101188700002301209700001901232700001701251856003601268 2016 eng d00aPhotoassociation of spin polarized Chromium0 aPhotoassociation of spin polarized Chromium c2016/02/29 a0214060 v933 aWe 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.1 aRührig, Jahn1 aBäuerle, Tobias1 aJulienne, Paul, S.1 aTiesinga, Eite1 aPfau, Tilman uhttp://arxiv.org/abs/1512.0437801933nas a2200277 4500008004100000245007200041210006900113260001500182300001100197490000700208520116900215100001301384700001901397700001401416700001801430700001401448700002501462700002301487700001701510700001701527700002101544700001801565700001401583700002201597856003601619 2016 eng d00aPure-state tomography with the expectation value of Pauli operators0 aPurestate tomography with the expectation value of Pauli operato c2016/03/31 a0321400 v933 a

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.

1 aMa, Xian1 aJackson, Tyler1 aZhou, Hui1 aChen, Jianxin1 aLu, Dawei1 aMazurek, Michael, D.1 aFisher, Kent, A.G.1 aPeng, Xinhua1 aKribs, David1 aResch, Kevin, J.1 aJi, Zhengfeng1 aZeng, Bei1 aLaflamme, Raymond uhttp://arxiv.org/abs/1601.0537901224nas a2200169 4500008004100000245005300041210005300094260001500147300001100162490000700173520074800180100001800928700002400946700001800970700001900988856004701007 2016 eng d00aQuantifying the coherence of pure quantum states0 aQuantifying the coherence of pure quantum states c2016/10/07 a0423130 v943 a

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.

1 aChen, Jianxin1 aJohnston, Nathaniel1 aLi, Chi-Kwong1 aPlosker, Sarah uhttps://doi.org/10.1103/PhysRevA.94.04231301465nas a2200205 4500008004100000245006900041210006800110260001500178300001100193490000700204520085500211100002201066700001401088700001901102700002001121700002101141700001701162700002501179856005501204 2016 eng d00aSubwavelength-width optical tunnel junctions for ultracold atoms0 aSubwavelengthwidth optical tunnel junctions for ultracold atoms c2016/12/27 a0634220 v943 a

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.

1 aJendrzejewski, F.1 aEckel, S.1 aTiecke, T., G.1 aJuzeliūnas, G.1 aCampbell, G., K.1 aJiang, Liang1 aGorshkov, Alexey, V. uhttp://link.aps.org/doi/10.1103/PhysRevA.94.06342201747nas a2200241 4500008004100000245009400041210006900135260001500204300001100219490000800230520106300238100001401301700001301315700001601328700001801344700001801362700001601380700002001396700001701416700001401433700002201447856003601469 2016 eng d00aTomography is necessary for universal entanglement detection with single-copy observables0 aTomography is necessary for universal entanglement detection wit c2016/06/07 a2305010 v1163 aEntanglement, 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.1 aLu, Dawei1 aXin, Tao1 aYu, Nengkun1 aJi, Zhengfeng1 aChen, Jianxin1 aLong, Guilu1 aBaugh, Jonathan1 aPeng, Xinhua1 aZeng, Bei1 aLaflamme, Raymond uhttp://arxiv.org/abs/1511.0058101014nas a2200157 4500008004100000245007300041210006900114260001500183300001100198490000700209520054100216100001900757700002000776700002400796856003600820 2016 eng d00aYang-Baxter operators need quantum entanglement to distinguish knots0 aYangBaxter operators need quantum entanglement to distinguish kn c2016/01/12 a0752030 v493 a 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. 1 aAlagic, Gorjan1 aJarret, Michael1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1507.0597901350nas a2200145 4500008004100000245004800041210004800089260001500137300001200152490000700164520095400171100002001125700002401145856003501169 2015 eng d00aAdiabatic optimization without local minima0 aAdiabatic optimization without local minima c2015/05/01 a181-1990 v153 a 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. 1 aJarret, Michael1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1405.755201589nas a2200193 4500008004100000245008100041210006900122260001500191300001100206490000700217520100800224100002301232700002501255700001901280700001901299700002001318700002101338856003601359 2015 eng d00aDemonstration of Robust Quantum Gate Tomography via Randomized Benchmarking0 aDemonstration of Robust Quantum Gate Tomography via Randomized B c2015/11/05 a1130190 v173 a 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. 1 aJohnson, Blake, R.1 ada Silva, Marcus, P.1 aRyan, Colm, A.1 aKimmel, Shelby1 aChow, Jerry, M.1 aOhki, Thomas, A. uhttp://arxiv.org/abs/1505.0668601250nas a2200217 4500008004100000245007700041210006900118260001500187300001100202490000700213520064200220100001800862700001800880700001800898700001900916700001300935700001600948700001400964700001700978856003700995 2015 eng d00aDiscontinuity of Maximum Entropy Inference and Quantum Phase Transitions0 aDiscontinuity of Maximum Entropy Inference and Quantum Phase Tra c2015/08/10 a0830190 v173 a 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. 1 aChen, Jianxin1 aJi, Zhengfeng1 aLi, Chi-Kwong1 aPoon, Yiu-Tung1 aShen, Yi1 aYu, Nengkun1 aZeng, Bei1 aZhou, Duanlu uhttp://arxiv.org/abs/1406.5046v200853nas a2200145 4500008004100000245010600041210006900147260001500216300001400231490000800245520037500253100001800628700002400646856003700670 2015 eng d00aThe Minimum Size of Unextendible Product Bases in the Bipartite Case (and Some Multipartite Cases) 0 aMinimum Size of Unextendible Product Bases in the Bipartite Case c2014/10/10 a351 - 3650 v3333 a 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. 1 aChen, Jianxin1 aJohnston, Nathaniel uhttp://arxiv.org/abs/1301.1406v101945nas a2200205 4500008004100000245007600041210006900117260001500186300001100201490000700212520133700219100001901556700001901575700001901594700002401613700002701637700001801664700001901682856003801701 2015 eng d00aSelf-heterodyne detection of the {\it in-situ} phase of an atomic-SQUID0 aSelfheterodyne detection of the it insitu phase of an atomicSQUI c2015/09/03 a0336020 v923 a 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. 1 aMathew, Ranchu1 aKumar, Avinash1 aEckel, Stephen1 aJendrzejewski, Fred1 aCampbell, Gretchen, K.1 aEdwards, Mark1 aTiesinga, Eite uhttp://arxiv.org/abs/1506.09149v201280nas a2200157 4500008004100000245004600041210004500087260001500132300001200147490000700159520085500166100001901021700002101040700002401061856003701085 2014 eng d00aClassical simulation of Yang-Baxter gates0 aClassical simulation of YangBaxter gates c2014/07/05 a161-1750 v273 a 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. 1 aAlagic, Gorjan1 aBapat, Aniruddha1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1407.1361v101598nas a2200157 4500008004100000245007300041210006900114260001500183300001100198490000600209520112600215100002301341700001501364700002401379856003701403 2014 eng d00aConstructing elliptic curve isogenies in quantum subexponential time0 aConstructing elliptic curve isogenies in quantum subexponential  c2014/01/01 a1 - 290 v83 a 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. 1 aChilds, Andrew, M.1 aJao, David1 aSoukharev, Vladimir uhttp://arxiv.org/abs/1012.4019v201173nas a2200145 4500008004100000245009200041210007000133260001500203300001100218490000700229520071000236100002000946700002400966856003700990 2014 eng d00aThe Fundamental Gap for a Class of Schrödinger Operators on Path and Hypercube Graphs0 aFundamental Gap for a Class of Schrödinger Operators on Path and c2014/03/06 a0521040 v553 a We consider the difference between the two lowest eigenvalues (the fundamental gap) of a Schr\"{o}dinger operator acting on a class of graphs. In particular, we derive tight bounds for the gap of Schr\"{o}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\"{o}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. 1 aJarret, Michael1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1403.1473v102029nas a2200241 4500008004100000245006600041210006500107260001400172490000800186520133800194100002601532700001801558700002301576700001201599700002201611700002101633700002001654700002301674700001201697700002101709700002001730856003701750 2014 eng d00aMany-body dynamics of dipolar molecules in an optical lattice0 aManybody dynamics of dipolar molecules in an optical lattice c2014/11/70 v1133 a 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. 1 aHazzard, Kaden, R. A.1 aGadway, Bryce1 aFoss-Feig, Michael1 aYan, Bo1 aMoses, Steven, A.1 aCovey, Jacob, P.1 aYao, Norman, Y.1 aLukin, Mikhail, D.1 aYe, Jun1 aJin, Deborah, S.1 aRey, Ana, Maria uhttp://arxiv.org/abs/1402.2354v101828nas a2200145 4500008004100000245015000041210006900191260001400260490000700274520129600281100002701577700002201604700001901626856003701645 2014 eng d00aNonequilibrium quantum fluctuations of a dispersive medium: Spontaneous emission, photon statistics, entropy generation, and stochastic motion 0 aNonequilibrium quantum fluctuations of a dispersive medium Spont c2014/7/160 v903 a 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. 1 aMaghrebi, Mohammad, F.1 aJaffe, Robert, L.1 aKardar, Mehran uhttp://arxiv.org/abs/1401.0701v101518nas a2200133 4500008004100000245005800041210005700099260001500156520111500171100001901286700002001305700002401325856003501349 2014 eng d00aPartial-indistinguishability obfuscation using braids0 aPartialindistinguishability obfuscation using braids c2014/08/213 a

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.

1 aAlagic, Gorjan1 aJeffery, Stacey1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1212.635801013nas a2200133 4500008004100000245006000041210006000101260001500161520060100176100002400777700002200801700001900823856003700842 2014 eng d00aQuantum Algorithms for Fermionic Quantum Field Theories0 aQuantum Algorithms for Fermionic Quantum Field Theories c2014/04/283 a 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. 1 aJordan, Stephen, P.1 aLee, Keith, S. M.1 aPreskill, John uhttp://arxiv.org/abs/1404.7115v101375nas a2200157 4500008004100000245007100041210006900112260001500181300001400196490000700210520089800217100002401115700002201139700001901161856003701180 2014 eng d00aQuantum Computation of Scattering in Scalar Quantum Field Theories0 aQuantum Computation of Scattering in Scalar Quantum Field Theori c2014/09/01 a1014-10800 v143 a 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. 1 aJordan, Stephen, P.1 aLee, Keith, S. M.1 aPreskill, John uhttp://arxiv.org/abs/1112.4833v101337nas a2200169 4500008004100000245007700041210006900118260001400187490000600201520082000207100001901027700002501046700001901071700002301090700001701113856003701130 2014 eng d00aRobust Extraction of Tomographic Information via Randomized Benchmarking0 aRobust Extraction of Tomographic Information via Randomized Benc c2014/3/250 v43 a 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. 1 aKimmel, Shelby1 ada Silva, Marcus, P.1 aRyan, Colm, A.1 aJohnson, Blake, R.1 aOhki, Thomas uhttp://arxiv.org/abs/1306.2348v101304nas a2200169 4500008004100000245009000041210006900131260001400200490000700214520080200221100001501023700001901038700001601057700001201073700001201085856003701097 2014 eng d00aSpin-orbit-coupled topological Fulde-Ferrell states of fermions in a harmonic trap 0 aSpinorbitcoupled topological FuldeFerrell states of fermions in  c2014/11/70 v903 a 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. 1 aJiang, Lei1 aTiesinga, Eite1 aLiu, Xia-Ji1 aHu, Hui1 aPu, Han uhttp://arxiv.org/abs/1404.6211v101364nas a2200169 4500008004100000022001400041245006300055210006200118260001500180300001600195490000700211520085900218653001501077653002401092100002401116856005401140 2014 eng d a1533-714600aStrong Equivalence of Reversible Circuits is coNP-complete0 aStrong Equivalence of Reversible Circuits is coNPcomplete c2014/11/01 a1302–13070 v143 a

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.

10acomplexity10areversible circuits1 aJordan, Stephen, P. uhttp://dl.acm.org/citation.cfm?id=2685179.268518202020nas a2200265 4500008004100000245009000041210006900131260001400200490000800214520123900222100001501461700001801476700002301494700002801517700001801545700002601563700001201589700002201601700002101623700002101644700001201665700002001677700002001697856003701717 2014 eng d00aSuppressing the loss of ultracold molecules via the continuous quantum Zeno effect 0 aSuppressing the loss of ultracold molecules via the continuous q c2014/2/200 v1123 a 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. 1 aZhu, Bihui1 aGadway, Bryce1 aFoss-Feig, Michael1 aSchachenmayer, Johannes1 aWall, Michael1 aHazzard, Kaden, R. A.1 aYan, Bo1 aMoses, Steven, A.1 aCovey, Jacob, P.1 aJin, Deborah, S.1 aYe, Jun1 aHolland, Murray1 aRey, Ana, Maria uhttp://arxiv.org/abs/1310.2221v201596nas a2200169 4500008004100000245004400041210004300085260001400128490000700142520114800149100001801297700001801315700001701333700002501350700001401375856003701389 2014 eng d00aSymmetric Extension of Two-Qubit States0 aSymmetric Extension of TwoQubit States c2014/9/170 v903 a 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 $\rho_{AB}$ plays an important role. A bipartite state $\rho_{AB}$ is symmetric extendible if there exits a tripartite state $\rho_{ABB'}$, such that the $AB$ marginal state is identical to the $AB'$ marginal state, i.e. $\rho_{AB'}=\rho_{AB}$. For a symmetric extendible state $\rho_{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 $\rho_{AB}$ admits a symmetric extension if and only if $\tr(\rho_B^2)\geq \tr(\rho_{AB}^2)-4\sqrt{\det{\rho_{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. 1 aChen, Jianxin1 aJi, Zhengfeng1 aKribs, David1 aLütkenhaus, Norbert1 aZeng, Bei uhttp://arxiv.org/abs/1310.3530v202134nas a2200133 4500008004100000245008900041210006900130260001400199490000700213520170000220100001901920700002401939856003701963 2013 eng d00aQuadrature interferometry for nonequilibrium ultracold bosons in optical lattices 0 aQuadrature interferometry for nonequilibrium ultracold bosons in c2013/1/220 v873 a 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. 1 aTiesinga, Eite1 aJohnson, Philip, R. uhttp://arxiv.org/abs/1212.1193v201995nas a2200205 4500008004100000245005100041210005100092260001300143490000700156520142000163100002001583700001901603700002301622700002401645700001801669700002301687700001701710700002501727856003701752 2013 eng d00aQuantum Logic between Remote Quantum Registers0 aQuantum Logic between Remote Quantum Registers c2013/2/60 v873 a 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. 1 aYao, Norman, Y.1 aGong, Zhe-Xuan1 aLaumann, Chris, R.1 aBennett, Steven, D.1 aDuan, L., -M.1 aLukin, Mikhail, D.1 aJiang, Liang1 aGorshkov, Alexey, V. uhttp://arxiv.org/abs/1206.0014v101999nas a2200193 4500008004100000245005200041210005200093260001500145300001200160490000700172520148600179100001801665700001801683700001901701700001801720700001601738700001401754856003701768 2013 eng d00aSymmetries of Codeword Stabilized Quantum Codes0 aSymmetries of Codeword Stabilized Quantum Codes c2013/03/28 a192-2060 v223 a 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. 1 aBeigi, Salman1 aChen, Jianxin1 aGrassl, Markus1 aJi, Zhengfeng1 aWang, Qiang1 aZeng, Bei uhttp://arxiv.org/abs/1303.7020v200882nas a2200157 4500008004100000245004900041210004700090260001400137490000700151520044900158100002200607700002400629700001600653700001800669856003700687 2013 eng d00aTesting quantum expanders is co-QMA-complete0 aTesting quantum expanders is coQMAcomplete c2013/4/150 v873 a 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. 1 aBookatz, Adam, D.1 aJordan, Stephen, P.1 aLiu, Yi-Kai1 aWocjan, Pawel uhttp://arxiv.org/abs/1210.0787v200867nas a2200145 4500008004100000245007400041210006900115260001500184520040100199100002300600700002000623700001900643700002200662856003700684 2013 eng d00aA Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates0 aTimeEfficient Quantum Walk for 3Distinctness Using Nested Update c2013/02/283 a 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}). 1 aChilds, Andrew, M.1 aJeffery, Stacey1 aKothari, Robin1 aMagniez, Frederic uhttp://arxiv.org/abs/1302.7316v101443nas a2200217 4500008004100000245007500041210006900116260001400185300000900199490000600208520080900214100002001023700002301043700002501066700002001091700001701111700001901128700001801147700002301165856003701188 2013 eng d00aTopologically Protected Quantum State Transfer in a Chiral Spin Liquid0 aTopologically Protected Quantum State Transfer in a Chiral Spin  c2013/3/12 a15850 v43 a 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. 1 aYao, Norman, Y.1 aLaumann, Chris, R.1 aGorshkov, Alexey, V.1 aWeimer, Hendrik1 aJiang, Liang1 aCirac, Ignacio1 aZoller, Peter1 aLukin, Mikhail, D. uhttp://arxiv.org/abs/1110.3788v102008nas a2200193 4500008004100000245007500041210006900116260001400185490000700199520143800206100001801644700002101662700001801683700002401701700001701725700002101742700001401763856003701777 2013 eng d00aUniqueness of Quantum States Compatible with Given Measurement Results0 aUniqueness of Quantum States Compatible with Given Measurement R c2013/7/110 v883 a 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. 1 aChen, Jianxin1 aDawkins, Hillary1 aJi, Zhengfeng1 aJohnston, Nathaniel1 aKribs, David1 aShultz, Frederic1 aZeng, Bei uhttp://arxiv.org/abs/1212.3503v201021nas a2200169 4500008004100000245009300041210006900134260001500203300001200218490000700230520048600237100002400723700002400747700001800771700002500789856003700814 2012 eng d00aAchieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems0 aAchieving perfect completeness in classicalwitness quantum Merli c2012/05/01 a461-4710 v123 a 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. 1 aJordan, Stephen, P.1 aKobayashi, Hirotada1 aNagaj, Daniel1 aNishimura, Harumichi uhttp://arxiv.org/abs/1111.5306v200399nas a2200145 4500008004100000245003500041210003500076300001100111490000700122100001600129700001300145700002500158700001700183856005300200 2012 eng d00aCavity QED with atomic mirrors0 aCavity QED with atomic mirrors a0630030 v141 aChang, D, E1 aJiang, L1 aGorshkov, Alexey, V.1 aKimble, H, J uhttp://iopscience.iop.org/1367-2630/14/6/063003/01351nas a2200181 4500008004100000245009200041210006900133260001500202300001100217490000700228520080600235100001801041700001801059700002301077700001401100700001801114856003701132 2012 eng d00aComment on some results of Erdahl and the convex structure of reduced density matrices0 aComment on some results of Erdahl and the convex structure of re c2012/05/16 a0722030 v533 a 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 \geq 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. 1 aChen, Jianxin1 aJi, Zhengfeng1 aRuskai, Mary, Beth1 aZeng, Bei1 aZhou, Duan-Lu uhttp://arxiv.org/abs/1205.3682v101936nas a2200157 4500008004100000245005700041210005700098260001300155490000700168520149900175100001801674700001801692700001701710700001401727856003701741 2012 eng d00aCorrelations in excited states of local Hamiltonians0 aCorrelations in excited states of local Hamiltonians c2012/4/90 v853 a 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). 1 aChen, Jianxin1 aJi, Zhengfeng1 aWei, Zhaohui1 aZeng, Bei uhttp://arxiv.org/abs/1106.1373v201702nas a2200157 4500008004100000245004500041210004500086260001400131490000700145520128800152100001801440700001801458700001401476700001701490856003701507 2012 eng d00aFrom Ground States to Local Hamiltonians0 aFrom Ground States to Local Hamiltonians c2012/8/300 v863 a 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. 1 aChen, Jianxin1 aJi, Zhengfeng1 aZeng, Bei1 aZhou, D., L. uhttp://arxiv.org/abs/1110.6583v401607nas a2200181 4500008004100000245005700041210005500098260001500153300001100168490000700179520111800186100001801304700001801322700001701340700001701357700001401374856003701388 2012 eng d00aGround-State Spaces of Frustration-Free Hamiltonians0 aGroundState Spaces of FrustrationFree Hamiltonians c2012/01/01 a1022010 v533 a 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 $\Theta_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 $\Theta_k$, called atoms, are analogs of extreme points. We study the properties of atoms in $\Theta_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 $\Theta_2$ are unique ground states of some 2-local frustration-free Hamiltonians. Moreover, we show that the elements in $\Theta_k$ may not be the join of atoms, indicating a richer structure for $\Theta_k$ beyond the convex structure. Our study of $\Theta_k$ deepens the understanding of ground-state space properties for frustration-free Hamiltonians, from a new angle of reduced spaces. 1 aChen, Jianxin1 aJi, Zhengfeng1 aKribs, David1 aWei, Zhaohui1 aZeng, Bei uhttp://arxiv.org/abs/1112.0762v101519nas a2200217 4500008004100000245008300041210006900124260001400193490000800207520087700215100002001092700002101112700002201133700001201155700002101167700002301188700002001211700002101231700001201252856003701264 2012 eng d00aLong-lived dipolar molecules and Feshbach molecules in a 3D optical lattice 0 aLonglived dipolar molecules and Feshbach molecules in a 3D optic c2012/2/230 v1083 a 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. 1 aChotia, Amodsen1 aNeyenhuis, Brian1 aMoses, Steven, A.1 aYan, Bo1 aCovey, Jacob, P.1 aFoss-Feig, Michael1 aRey, Ana, Maria1 aJin, Deborah, S.1 aYe, Jun uhttp://arxiv.org/abs/1110.4420v101508nas a2200145 4500008004100000245005300041210005300094260001500147520109300162100001801255700001801273700002001291700001401311856003701325 2012 eng d00aMinimum Entangling Power is Close to Its Maximum0 aMinimum Entangling Power is Close to Its Maximum c2012/10/043 a 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. 1 aChen, Jianxin1 aJi, Zhengfeng1 aKribs, David, W1 aZeng, Bei uhttp://arxiv.org/abs/1210.1296v101068nas a2200157 4500008004100000245005000041210005000091260001500141300001600156490000800172520062800180100002400808700002200832700001900854856003700873 2012 eng d00aQuantum Algorithms for Quantum Field Theories0 aQuantum Algorithms for Quantum Field Theories c2012/05/31 a1130 - 11330 v3363 a 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. 1 aJordan, Stephen, P.1 aLee, Keith, S. M.1 aPreskill, John uhttp://arxiv.org/abs/1111.3633v201124nas a2200181 4500008004100000245005300041210005300094260001500147300001100162490000700173520063000180100001800810700001800828700002400846700002100870700001400891856003700905 2012 eng d00aRank Reduction for the Local Consistency Problem0 aRank Reduction for the Local Consistency Problem c2012/02/09 a0222020 v533 a We address the problem of how simple a solution can be for a given quantum local consistency instance. More specifically, we investigate how small the rank of the global density operator can be if the local constraints are known to be compatible. We prove that any compatible local density operators can be satisfied by a low rank global density operator. Then we study both fermionic and bosonic versions of the N-representability problem as applications. After applying the channel-state duality, we prove that any compatible local channels can be obtained through a global quantum channel with small Kraus rank. 1 aChen, Jianxin1 aJi, Zhengfeng1 aKlyachko, Alexander1 aKribs, David, W.1 aZeng, Bei uhttp://arxiv.org/abs/1106.3235v201195nas a2200157 4500008004100000245006200041210006200103260001300165490000700178520072500185100002200910700001900932700002600951700002300977856003701000 2012 eng d00aResonant control of polar molecules in an optical lattice0 aResonant control of polar molecules in an optical lattice c2012/2/80 v853 a We study the resonant control of two nonreactive polar molecules in an optical lattice site, focussing on the example of RbCs. Collisional control can be achieved by tuning bound states of the intermolecular dipolar potential, by varying the applied electric field or trap frequency. We consider a wide range of electric fields and trapping geometries, showing that a three-dimensional optical lattice allows for significantly wider avoided crossings than free space or quasi-two dimensional geometries. Furthermore, we find that dipolar confinement induced resonances can be created with reasonable trapping frequencies and electric fields, and have widths that will enable useful control in forthcoming experiments. 1 aHanna, Thomas, M.1 aTiesinga, Eite1 aMitchell, William, F.1 aJulienne, Paul, S. uhttp://arxiv.org/abs/1111.0227v101927nas a2200205 4500008004100000245009400041210006900135260001400204300000800218490000600226520130900232100002001541700001701561700002501578700002201603700001701625700001901642700002301661856003701684 2012 eng d00aScalable Architecture for a Room Temperature Solid-State Quantum Information Processor 0 aScalable Architecture for a Room Temperature SolidState Quantum  c2012/4/24 a8000 v33 a The realization of a scalable quantum information processor has emerged over the past decade as one of the central challenges at the interface of fundamental science and engineering. Much progress has been made towards this goal. Indeed, quantum operations have been demonstrated on several trapped ion qubits, and other solid-state systems are approaching similar levels of control. Extending these techniques to achieve fault-tolerant operations in larger systems with more qubits remains an extremely challenging goal, in part, due to the substantial technical complexity of current implementations. Here, we propose and analyze an architecture for a scalable, solid-state quantum information processor capable of operating at or near room temperature. The architecture is applicable to realistic conditions, which include disorder and relevant decoherence mechanisms, and includes a hierarchy of control at successive length scales. Our approach is based upon recent experimental advances involving Nitrogen-Vacancy color centers in diamond and will provide fundamental insights into the physics of non-equilibrium many-body quantum systems. Additionally, the proposed architecture may greatly alleviate the stringent constraints, currently limiting the realization of scalable quantum processors. 1 aYao, Norman, Y.1 aJiang, Liang1 aGorshkov, Alexey, V.1 aMaurer, Peter, C.1 aGiedke, Geza1 aCirac, Ignacio1 aLukin, Mikhail, D. uhttp://arxiv.org/abs/1012.2864v100969nas a2200145 4500008004100000245006800041210006700109260001300176490000800189520052100197100002700718700002200745700001900767856003700786 2012 eng d00aSpontaneous emission by rotating objects: A scattering approach0 aSpontaneous emission by rotating objects A scattering approach c2012/6/70 v1083 a We study the quantum electrodynamics (QED) vacuum in the presence of a body rotating along its axis of symmetry and show that the object spontaneously emits energy if it is lossy. The radiated power is expressed as a general trace formula solely in terms of the scattering matrix, making an explicit connection to the conjecture of Zel'dovich [JETP Lett. 14, 180 (1971)] on rotating objects. We further show that a rotating body drags along nearby objects while making them spin parallel to its own rotation axis. 1 aMaghrebi, Mohammad, F.1 aJaffe, Robert, L.1 aKardar, Mehran uhttp://arxiv.org/abs/1202.1485v201079nas a2200121 4500008004100000245009300041210006900134260001500203520066100218100002400879700001900903856003500922 2011 eng d00aApproximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit0 aApproximating the TuraevViro Invariant of Mapping Tori is Comple c2011/05/313 a

The Turaev-Viro invariants are scalar topological invariants of three-dimensional manifolds. Here we show that the problem of estimating the Fibonacci version of the Turaev-Viro invariant of a mapping torus is a complete problem for the one clean qubit complexity class (DQC1). This complements a previous result showing that estimating the Turaev-Viro invariant for arbitrary manifolds presented as Heegaard splittings is a complete problem for the standard quantum computation model (BQP). We also discuss a beautiful analogy between these results and previously known results on the computational complexity of approximating the Jones polynomial.

1 aJordan, Stephen, P.1 aAlagic, Gorjan uhttp://arxiv.org/abs/1105.510001641nas a2200193 4500008004100000245005000041210004900091260001500140300001600155490000800171520110300179100002701282700002401309700001901333700001701352700002201369700001901391856003701410 2011 eng d00aCasimir force between sharp-shaped conductors0 aCasimir force between sharpshaped conductors c2011/04/11 a6867 - 68710 v1083 a Casimir forces between conductors at the sub-micron scale cannot be ignored in the design and operation of micro-electromechanical (MEM) devices. However, these forces depend non-trivially on geometry, and existing formulae and approximations cannot deal with realistic micro-machinery components with sharp edges and tips. Here, we employ a novel approach to electromagnetic scattering, appropriate to perfect conductors with sharp edges and tips, specifically to wedges and cones. The interaction of these objects with a metal plate (and among themselves) is then computed systematically by a multiple-scattering series. For the wedge, we obtain analytical expressions for the interaction with a plate, as functions of opening angle and tilt, which should provide a particularly useful tool for the design of MEMs. Our result for the Casimir interactions between conducting cones and plates applies directly to the force on the tip of a scanning tunneling probe; the unexpectedly large temperature dependence of the force in these configurations should attract immediate experimental interest. 1 aMaghrebi, Mohammad, F.1 aRahi, Sahand, Jamal1 aEmig, Thorsten1 aGraham, Noah1 aJaffe, Robert, L.1 aKardar, Mehran uhttp://arxiv.org/abs/1010.3223v101106nas a2200145 4500008004100000245006700041210006700108260001300175490000700188520065800195100002700853700002100880700002200901856003700923 2011 eng d00aImplications of the Babinet Principle for Casimir Interactions0 aImplications of the Babinet Principle for Casimir Interactions c2011/9/10 v843 a We formulate the Babinet Principle (BP) as a relation between the scattering amplitudes for electromagnetic waves, and combine it with multiple scattering techniques to derive new properties of Casimir forces. We show that the Casimir force exerted by a planar conductor or dielectric on a self- complementary perforated planar mirror is approximately half that on a uniform mirror independent of the distance between them. The BP suggests that Casimir edge effects are anomalously small, supporting results obtained earlier in special cases. Finally, we illustrate how the BP can be used to estimate Casimir forces between perforated planar mirrors. 1 aMaghrebi, Mohammad, F.1 aAbravanel, Ronen1 aJaffe, Robert, L. uhttp://arxiv.org/abs/1103.5395v102114nas a2200169 4500008004100000245009200041210006900133260001300202490000700215520160400222100001801826700001401844700001701858700001801875700001401893856003701907 2011 eng d00aNo-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems 0 aNogo Theorem for Oneway Quantum Computing on Naturally Occurring c2011/5/90 v833 a One-way quantum computing achieves the full power of quantum computation by performing single particle measurements on some many-body entangled state, known as the resource state. As single particle measurements are relatively easy to implement, the preparation of the resource state becomes a crucial task. An appealing approach is simply to cool a strongly correlated quantum many-body system to its ground state. In addition to requiring the ground state of the system to be universal for one-way quantum computing, we also want the Hamiltonian to have non-degenerate ground state protected by a fixed energy gap, to involve only two-body interactions, and to be frustration-free so that measurements in the course of the computation leave the remaining particles in the ground space. Recently, significant efforts have been made to the search of resource states that appear naturally as ground states in spin lattice systems. The approach is proved to be successful in spin-5/2 and spin-3/2 systems. Yet, it remains an open question whether there could be such a natural resource state in a spin-1/2, i.e., qubit system. Here, we give a negative answer to this question by proving that it is impossible for a genuinely entangled qubit states to be a non-degenerate ground state of any two-body frustration-free Hamiltonian. What is more, we prove that every spin-1/2 frustration-free Hamiltonian with two-body interaction always has a ground state that is a product of single- or two-qubit states, a stronger result that is interesting independent of the context of one-way quantum computing. 1 aChen, Jianxin1 aChen, Xie1 aDuan, Runyao1 aJi, Zhengfeng1 aZeng, Bei uhttp://arxiv.org/abs/1004.3787v101404nas a2200193 4500008004100000245006800041210006800109260001400177490000800191520083700199100002001036700001701056700002501073700001901098700001501117700001801132700002301150856003701173 2011 eng d00aRobust Quantum State Transfer in Random Unpolarized Spin Chains0 aRobust Quantum State Transfer in Random Unpolarized Spin Chains c2011/1/270 v1063 a We propose and analyze a new approach for quantum state transfer between remote spin qubits. Specifically, we demonstrate that coherent quantum coupling between remote qubits can be achieved via certain classes of random, unpolarized (infinite temperature) spin chains. Our method is robust to coupling strength disorder and does not require manipulation or control over individual spins. In principle, it can be used to attain perfect state transfer over arbitrarily long range via purely Hamiltonian evolution and may be particularly applicable in a solid-state quantum information processor. As an example, we demonstrate that it can be used to attain strong coherent coupling between Nitrogen-Vacancy centers separated by micrometer distances at room temperature. Realistic imperfections and decoherence effects are analyzed. 1 aYao, Norman, Y.1 aJiang, Liang1 aGorshkov, Alexey, V.1 aGong, Zhe-Xuan1 aZhai, Alex1 aDuan, L., -M.1 aLukin, Mikhail, D. uhttp://arxiv.org/abs/1011.2762v201279nas a2200181 4500008004100000245009100041210006900132260001400201490000700215520071200222100002000934700002000954700001900974700002500993700002301018700001901041856003701060 2011 eng d00aSpatial separation in a thermal mixture of ultracold $^{174}$Yb and $^{87}$Rb atoms 0 aSpatial separation in a thermal mixture of ultracold 174 Yb and  c2011/4/210 v833 a We report on the observation of unusually strong interactions in a thermal mixture of ultracold atoms which cause a significant modification of the spatial distribution. A mixture of $^{87}$Rb and $^{174}$Yb with a temperature of a few $\mu$K is prepared in a hybrid trap consisting of a bichromatic optical potential superimposed on a magnetic trap. For suitable trap parameters and temperatures, a spatial separation of the two species is observed. We infer that the separation is driven by a large interaction strength between $^{174}$Yb and $^{87}$Rb accompanied by a large three-body recombination rate. Based on this assumption we have developed a diffusion model which reproduces our observations. 1 aBaumer, Florian1 aMünchow, Frank1 aGörlitz, Axel1 aMaxwell, Stephen, E.1 aJulienne, Paul, S.1 aTiesinga, Eite uhttp://arxiv.org/abs/1104.1722v101327nas a2200157 4500008004100000245009200041210006900133260001400202490000700216520082400223100001901047700002401066700001901090700002301109856003701132 2010 eng d00aApproximating Turaev-Viro 3-manifold invariants is universal for quantum computation 0 aApproximating TuraevViro 3manifold invariants is universal for q c2010/10/80 v823 a The Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and (2+1)-D topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a novel relation between the task of distinguishing non-homeomorphic 3-manifolds and the power of a general quantum computer. 1 aAlagic, Gorjan1 aJordan, Stephen, P.1 aKoenig, Robert1 aReichardt, Ben, W. uhttp://arxiv.org/abs/1003.0923v101723nas a2200157 4500008004100000245008700041210006900128260001500197300001100212490000700223520123400230100002201464700001901486700002301505856003701528 2010 eng d00aCreation and manipulation of Feshbach resonances with radio-frequency radiation 0 aCreation and manipulation of Feshbach resonances with radiofrequ c2010/08/12 a0830310 v123 a We present a simple technique for studying collisions of ultracold atoms in the presence of a magnetic field and radio-frequency radiation (rf). Resonant control of scattering properties can be achieved by using rf to couple a colliding pair of atoms to a bound state. We show, using the example of 6Li, that in some ranges of rf frequency and magnetic field this can be done without giving rise to losses. We also show that halo molecules of large spatial extent require much less rf power than deeply bound states. Another way to exert resonant control is with a set of rf-coupled bound states, linked to the colliding pair through the molecular interactions that give rise to magnetically tunable Feshbach resonances. This was recently demonstrated for 87Rb [Kaufman et al., Phys. Rev. A 80:050701(R), 2009]. We examine the underlying atomic and molecular physics which made this possible. Lastly, we consider the control that may be exerted over atomic collisions by placing atoms in superpositions of Zeeman states, and suggest that it could be useful where small changes in scattering length are required. We suggest other species for which rf and magnetic field control could together provide a useful tuning mechanism. 1 aHanna, Thomas, M.1 aTiesinga, Eite1 aJulienne, Paul, S. uhttp://arxiv.org/abs/1004.0636v100869nas a2200133 4500008004100000245005100041210004200092260001500134520048400149100002400633700002000657700002100677856003700698 2010 eng d00aOn the degeneracy of SU(3)k topological phases0 adegeneracy of SU3k topological phases c2010/09/013 a

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

1 aJordan, Stephen, P.1 aMansour, Toufik1 aSeverini, Simone uhttp://arxiv.org/abs/1009.0114v100782nas a2200265 4500008004100000245009300041210006900134300000800203490000600211100001700217700001500234700001800249700001300267700002500280700001700305700001300322700001700335700001700352700001400369700001600383700001500399700002000414700001600434856006600450 2010 eng d00aFar-field optical imaging and manipulation of individual spins with nanoscale resolution0 aFarfield optical imaging and manipulation of individual spins wi a9120 v61 aMaurer, P, C1 aMaze, J, R1 aStanwix, P, L1 aJiang, L1 aGorshkov, Alexey, V.1 aZibrov, A, A1 aHarke, B1 aHodges, J, S1 aZibrov, A, S1 aYacoby, A1 aTwitchen, D1 aHell, S, W1 aWalsworth, R, L1 aLukin, M, D uhttp://www.nature.com/nphys/journal/v6/n11/abs/nphys1774.html01226nas a2200181 4500008004100000245008600041210006900127260001400196490000700210520065700217100002300874700001700897700002500914700002000939700002500959700002300984856003701007 2010 eng d00aFast Entanglement Distribution with Atomic Ensembles and Fluorescent Detection 0 aFast Entanglement Distribution with Atomic Ensembles and Fluores c2010/2/120 v813 a Quantum repeaters based on atomic ensemble quantum memories are promising candidates for achieving scalable distribution of entanglement over long distances. Recently, important experimental progress has been made towards their implementation. However, the entanglement rates and scalability of current approaches are limited by relatively low retrieval and single-photon detector efficiencies. We propose a scheme, which makes use of fluorescent detection of stored excitations to significantly increase the efficiency of connection and hence the rate. Practical performance and possible experimental realizations of the new protocol are discussed. 1 aBrask, Jonatan, B.1 aJiang, Liang1 aGorshkov, Alexey, V.1 aVuletic, Vladan1 aSorensen, Anders, S.1 aLukin, Mikhail, D. uhttp://arxiv.org/abs/0907.3839v201169nas a2200169 4500008004100000245004300041210004300084260001400127300001600141490000700157520072600164100001600890700001800906700001900924700001900943856003700962 2010 eng d00aFeshbach Resonances in Ultracold Gases0 aFeshbach Resonances in Ultracold Gases c2010/4/29 a1225 - 12860 v823 a Feshbach resonances are the essential tool to control the interaction between atoms in ultracold quantum gases. They have found numerous experimental applications, opening up the way to important breakthroughs. This Review broadly covers the phenomenon of Feshbach resonances in ultracold gases and their main applications. This includes the theoretical background and models for the description of Feshbach resonances, the experimental methods to find and characterize the resonances, a discussion of the main properties of resonances in various atomic species and mixed atomic species systems, and an overview of key experiments with atomic Bose-Einstein condensates, degenerate Fermi gases, and ultracold molecules. 1 aChin, Cheng1 aGrimm, Rudolf1 aJulienne, Paul1 aTiesinga, Eite uhttp://arxiv.org/abs/0812.1496v201293nas a2200133 4500008004100000245003600041210003600077260001500113300001200128490000700140520094200147100002401089856004601113 2010 eng d00aPermutational Quantum Computing0 aPermutational Quantum Computing c2010/05/01 a470-4970 v103 a

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

1 aJordan, Stephen, P. uhttp://dl.acm.org/citation.cfm?id=201136901132nas a2200157 4500008004100000245007300041210006900114260001500183520064900198100001800847700001800865700002300883700001400906700001700920856003700937 2010 eng d00aPrinciple of Maximum Entropy and Ground Spaces of Local Hamiltonians0 aPrinciple of Maximum Entropy and Ground Spaces of Local Hamilton c2010/10/133 a The structure of the ground spaces of quantum systems consisting of local interactions is of fundamental importance to different areas of physics. In this Letter, we present a necessary and sufficient condition for a subspace to be the ground space of a k-local Hamiltonian. Our analysis are motivated by the concept of irreducible correlations studied by [Linden et al., PRL 89, 277906] and [Zhou, PRL 101, 180505], which is in turn based on the principle of maximum entropy. It establishes a better understanding of the ground spaces of local Hamiltonians and builds an intimate link of ground spaces to the correlations of quantum states. 1 aChen, Jianxin1 aJi, Zhengfeng1 aRuskai, Mary, Beth1 aZeng, Bei1 aZhou, Duanlu uhttp://arxiv.org/abs/1010.2739v401051nas a2200145 4500008004100000245007400041210006900115260001400184490000700198520060100205100002400806700001800830700002000848856003700868 2010 eng d00aQMA-complete problems for stoquastic Hamiltonians and Markov matrices0 aQMAcomplete problems for stoquastic Hamiltonians and Markov matr c2010/3/290 v813 a We show that finding the lowest eigenvalue of a 3-local symmetric stochastic matrix is QMA-complete. We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation using certain excited states of a stoquastic Hamiltonian is universal. We also show that adiabatic evolution in the ground state of a stochastic frustration free Hamiltonian is universal. Our results give a new QMA-complete problem arising in the classical setting of Markov chains, and new adiabatically universal Hamiltonians that arise in many physical systems. 1 aJordan, Stephen, P.1 aGosset, David1 aLove, Peter, J. uhttp://arxiv.org/abs/0905.4755v202052nas a2200193 4500008004100000245002200041210002200063260001300085300001200098490000800110520156800118100002301686700001901709700002201728700002301750700002401773700002401797856003701821 2010 eng d00aQuantum Computing0 aQuantum Computing c2010/3/4 a45 - 530 v4643 a Quantum mechanics---the theory describing the fundamental workings of nature---is famously counterintuitive: it predicts that a particle can be in two places at the same time, and that two remote particles can be inextricably and instantaneously linked. These predictions have been the topic of intense metaphysical debate ever since the theory's inception early last century. However, supreme predictive power combined with direct experimental observation of some of these unusual phenomena leave little doubt as to its fundamental correctness. In fact, without quantum mechanics we could not explain the workings of a laser, nor indeed how a fridge magnet operates. Over the last several decades quantum information science has emerged to seek answers to the question: can we gain some advantage by storing, transmitting and processing information encoded in systems that exhibit these unique quantum properties? Today it is understood that the answer is yes. Many research groups around the world are working towards one of the most ambitious goals humankind has ever embarked upon: a quantum computer that promises to exponentially improve computational power for particular tasks. A number of physical systems, spanning much of modern physics, are being developed for this task---ranging from single particles of light to superconducting circuits---and it is not yet clear which, if any, will ultimately prove successful. Here we describe the latest developments for each of the leading approaches and explain what the major challenges are for the future. 1 aLadd, Thaddeus, D.1 aJelezko, Fedor1 aLaflamme, Raymond1 aNakamura, Yasunobu1 aMonroe, Christopher1 aO'Brien, Jeremy, L. uhttp://arxiv.org/abs/1009.2267v100622nas a2200217 4500008004100000245006800041210006400109300000800173490000600181100002500187700001500212700001500227700001000242700001900252700001000271700001400281700001400295700001600309700001400325856006500339 2010 eng d00aTwo-orbital SU(N) magnetism with ultracold alkaline-earth atoms0 aTwoorbital SUN magnetism with ultracold alkalineearth atoms a2890 v61 aGorshkov, Alexey, V.1 aHermele, M1 aGurarie, V1 aXu, C1 aJulienne, P, S1 aYe, J1 aZoller, P1 aDemler, E1 aLukin, M, D1 aRey, A, M uhttp://www.nature.com/nphys/journal/v6/n4/abs/nphys1535.html01137nas a2200157 4500008004100000245008200041210006900123260001300192490000700205520065000212100001500862700001900877700002300896700002300919856003700942 2009 eng d00aCollisional cooling of ultra-cold atom ensembles using Feshbach resonances 0 aCollisional cooling of ultracold atom ensembles using Feshbach r c2009/9/80 v803 a We propose a new type of cooling mechanism for ultra-cold fermionic atom ensembles, which capitalizes on the energy dependence of inelastic collisions in the presence of a Feshbach resonance. We first discuss the case of a single magnetic resonance, and find that the final temperature and the cooling rate is limited by the width of the resonance. A concrete example, based on a p-wave resonance of $^{40}$K, is given. We then improve upon this setup by using both a very sharp optical or radio-frequency induced resonance and a very broad magnetic resonance and show that one can improve upon temperatures reached with current technologies. 1 aMathey, L.1 aTiesinga, Eite1 aJulienne, Paul, S.1 aClark, Charles, W. uhttp://arxiv.org/abs/0903.2568v100832nas a2200169 4500008004100000245005200041210005100093260001500144300001400159490000600173520035600179100002300535700001900558700002400577700001700601856004400618 2009 eng d00aDiscrete-query quantum algorithm for NAND trees0 aDiscretequery quantum algorithm for NAND trees c2009/07/01 a119 - 1230 v53 a Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional quantum query model, for any fixed epsilon > 0. 1 aChilds, Andrew, M.1 aCleve, Richard1 aJordan, Stephen, P.1 aYeung, David uhttp://arxiv.org/abs/quant-ph/0702160v101162nas a2200133 4500008004100000245006200041210006200103260001400165490000700179520076300186100002400949700001800973856003700991 2009 eng d00aEfficient quantum circuits for arbitrary sparse unitaries0 aEfficient quantum circuits for arbitrary sparse unitaries c2009/12/10 v803 a Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided it has at most polynomially many nonzero entries in any row or column, and these entries are efficiently computable. One can formulate a model of computation based on the composition of sparse unitaries which includes the quantum Turing machine model, the quantum circuit model, anyonic models, permutational quantum computation, and discrete time quantum walks as special cases. Thus we obtain a simple unified proof that these models are all contained in BQP. Furthermore our general method for implementing sparse unitaries simplifies several existing quantum algorithms. 1 aJordan, Stephen, P.1 aWocjan, Pawel uhttp://arxiv.org/abs/0904.2211v201422nas a2200145 4500008004100000245005900041210005900100260001500159520097700174100002201151700002401173700001801197700002401215856003701239 2009 eng d00aEfficient quantum processing of ideals in finite rings0 aEfficient quantum processing of ideals in finite rings c2009/07/313 a Suppose we are given black-box access to a finite ring R, and a list of generators for an ideal I in R. We show how to find an additive basis representation for I in poly(log |R|) time. This generalizes a recent quantum algorithm of Arvind et al. which finds a basis representation for R itself. We then show that our algorithm is a useful primitive allowing quantum computers to rapidly solve a wide variety of problems regarding finite rings. In particular we show how to test whether two ideals are identical, find their intersection, find their quotient, prove whether a given ring element belongs to a given ideal, prove whether a given element is a unit, and if so find its inverse, find the additive and multiplicative identities, compute the order of an ideal, solve linear equations over rings, decide whether an ideal is maximal, find annihilators, and test the injectivity and surjectivity of ring homomorphisms. These problems appear to be hard classically. 1 aWocjan, Pawel, M.1 aJordan, Stephen, P.1 aAhmadi, Hamed1 aBrennan, Joseph, P. uhttp://arxiv.org/abs/0908.0022v101125nas a2200145 4500008004100000245006500041210006500106260001500171300001200186490000600198520068700204100002400891700001800915856004600933 2009 eng d00aEstimating Jones and HOMFLY polynomials with One Clean Qubit0 aEstimating Jones and HOMFLY polynomials with One Clean Qubit c2009/03/01 a264-2890 v93 a

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

1 aJordan, Stephen, P.1 aWocjan, Pawel uhttp://dl.acm.org/citation.cfm?id=201178701547nas a2200157 4500008004100000245009000041210006900131260001500200300001100215490000700226520105100233100002601284700001901310700002301329856003701352 2009 eng d00aMulti-channel modelling of the formation of vibrationally cold polar KRb molecules 0 aMultichannel modelling of the formation of vibrationally cold po c2009/05/14 a0550430 v113 a We describe the theoretical advances that influenced the experimental creation of vibrationally and translationally cold polar $^{40}$K$^{87}$Rb molecules \cite{nphys08,science08}. Cold molecules were created from very-weakly bound molecules formed by magnetic field sweeps near a Feshbach resonance in collisions of ultra-cold $^{40}$K and $^{87}$Rb atoms. Our analysis include the multi-channel bound-state calculations of the hyperfine and Zeeman mixed X$^1\Sigma^+$ and a$^3\Sigma^+$ vibrational levels. We find excellent agreement with the hyperfine structure observed in experimental data. In addition, we studied the spin-orbit mixing in the intermediate state of the Raman transition. This allowed us to investigate its effect on the vibrationally-averaged transition dipole moment to the lowest ro-vibrational level of the X$^1\Sigma^+$ state. Finally, we obtained an estimate of the polarizability of the initial and final ro-vibrational states of the Raman transition near frequencies relevant for optical trapping of the molecules. 1 aKotochigova, Svetlana1 aTiesinga, Eite1 aJulienne, Paul, S. uhttp://arxiv.org/abs/0901.1486v101221nas a2200145 4500008004100000245006600041210006600107260001400173490000700187520078000194100002200974700001900996700002301015856003701038 2009 eng d00aPrediction of Feshbach resonances from three input parameters0 aPrediction of Feshbach resonances from three input parameters c2009/4/300 v793 a We have developed a model of Feshbach resonances in gases of ultracold alkali metal atoms using the ideas of multichannel quantum defect theory. Our model requires just three parameters describing the interactions - the singlet and triplet scattering lengths, and the long range van der Waals coefficient - in addition to known atomic properties. Without using any further details of the interactions, our approach can accurately predict the locations of resonances. It can also be used to find the singlet and triplet scattering lengths from measured resonance data. We apply our technique to $^{6}$Li--$^{40}$K and $^{40}$K--$^{87}$Rb scattering, obtaining good agreement with experimental results, and with the more computationally intensive coupled channels technique. 1 aHanna, Thomas, M.1 aTiesinga, Eite1 aJulienne, Paul, S. uhttp://arxiv.org/abs/0903.0884v201274nas a2200181 4500008004100000245011400041210006900155260001400224490000800238520068400246100001700930700002000947700002500967700002400992700001901016700002001035856003701055 2009 eng d00aQuantum Phase Transitions and Continuous Observation of Spinor Dynamics in an Antiferromagnetic Condensate 0 aQuantum Phase Transitions and Continuous Observation of Spinor D c2009/3/230 v1023 a Condensates of spin-1 sodium display rich spin dynamics due to the antiferromagnetic nature of the interactions in this system. We use Faraday rotation spectroscopy to make a continuous and minimally destructive measurement of the dynamics over multiple spin oscillations on a single evolving condensate. This method provides a sharp signature to locate a magnetically tuned separatrix in phase space which depends on the net magnetization. We also observe a phase transition from a two- to a three-component condensate at a low but finite temperature using a Stern-Gerlach imaging technique. This transition should be preserved as a zero-temperature quantum phase transition. 1 aLiu, Yingmei1 aJung, Sebastian1 aMaxwell, Stephen, E.1 aTurner, Lincoln, D.1 aTiesinga, Eite1 aLett, Paul., D. uhttp://arxiv.org/abs/0902.3189v101661nas a2200217 4500008004100000245007400041210006900115260001400184300001400198490000600212520102000218100001701238700002301255700002501278700002201303700002101325700001901346700002301365700001801388856003701406 2008 eng d00aAnyonic interferometry and protected memories in atomic spin lattices0 aAnyonic interferometry and protected memories in atomic spin lat c2008/4/20 a482 - 4880 v43 a Strongly correlated quantum systems can exhibit exotic behavior called topological order which is characterized by non-local correlations that depend on the system topology. Such systems can exhibit remarkable phenomena such as quasi-particles with anyonic statistics and have been proposed as candidates for naturally fault-tolerant quantum computation. Despite these remarkable properties, anyons have never been observed in nature directly. Here we describe how to unambiguously detect and characterize such states in recently proposed spin lattice realizations using ultra-cold atoms or molecules trapped in an optical lattice. We propose an experimentally feasible technique to access non-local degrees of freedom by performing global operations on trapped spins mediated by an optical cavity mode. We show how to reliably read and write topologically protected quantum memory using an atomic or photonic qubit. Furthermore, our technique can be used to probe statistics and dynamics of anyonic excitations. 1 aJiang, Liang1 aBrennen, Gavin, K.1 aGorshkov, Alexey, V.1 aHammerer, Klemens1 aHafezi, Mohammad1 aDemler, Eugene1 aLukin, Mikhail, D.1 aZoller, Peter uhttp://arxiv.org/abs/0711.1365v101381nas a2200145 4500008004100000245007000041210006900111260001400180490000700194520093200201100002301133700001901156700002301175856003701198 2008 eng d00aAvoided crossings between bound states of ultracold Cesium dimers0 aAvoided crossings between bound states of ultracold Cesium dimer c2008/11/50 v783 a We present an efficient new computational method for calculating the binding energies of the bound states of ultracold alkali-metal dimers in the presence of magnetic fields. The method is based on propagation of coupled differential equations and does not use a basis set for the interatomic distance coordinate. It is much more efficient than the previous method based on a radial basis set and allows many more spin channels to be included. This is particularly important in the vicinity of avoided crossings between bound states. We characterize a number of different avoided crossings in Cs_2 and compare our converged calculations with experimental results. Small but significant discrepancies are observed in both crossing strengths and level positions, especially for levels with l symmetry (rotational angular momentum L=8). The discrepancies should allow the development of improved potential models in the future. 1 aHutson, Jeremy, M.1 aTiesinga, Eite1 aJulienne, Paul, S. uhttp://arxiv.org/abs/0806.2583v101409nas a2200193 4500008004100000245006800041210006800109260001400177490000800191520083700199100001701036700002501053700001601078700002001094700002201114700001901136700002301155856003701178 2008 eng d00aCoherence of an optically illuminated single nuclear spin qubit0 aCoherence of an optically illuminated single nuclear spin qubit c2008/2/190 v1003 aWe investigate the coherence properties of individual nuclear spin quantum bits in diamond [Dutt et al., Science, 316, 1312 (2007)] when a proximal electronic spin associated with a nitrogen-vacancy (NV) center is being interrogated by optical radiation. The resulting nuclear spin dynamics are governed by time-dependent hyperfine interaction associated with rapid electronic transitions, which can be described by a spin-fluctuator model. We show that due to a process analogous to motional averaging in nuclear magnetic resonance, the nuclear spin coherence can be preserved after a large number of optical excitation cycles. Our theoretical analysis is in good agreement with experimental results. It indicates a novel approach that could potentially isolate the nuclear spin system completely from the electronic environment. 1 aJiang, Liang1 aDutt, M., V. Gurudev1 aTogan, Emre1 aChildress, Lily1 aCappellaro, Paola1 aTaylor, J., M.1 aLukin, Mikhail, D. uhttp://arxiv.org/abs/0707.1341v201158nas a2200169 4500008004100000245006700041210006700108260001300175490000800188520065200196100002500848700001700873700002000890700001800910700002300928856003700951 2008 eng d00aCoherent Quantum Optical Control with Subwavelength Resolution0 aCoherent Quantum Optical Control with Subwavelength Resolution c2008/3/70 v1003 a We suggest a new method for quantum optical control with nanoscale resolution. Our method allows for coherent far-field manipulation of individual quantum systems with spatial selectivity that is not limited by the wavelength of radiation and can, in principle, approach a few nanometers. The selectivity is enabled by the nonlinear atomic response, under the conditions of Electromagnetically Induced Transparency, to a control beam with intensity vanishing at a certain location. Practical performance of this technique and its potential applications to quantum information science with cold atoms, ions, and solid-state qubits are discussed. 1 aGorshkov, Alexey, V.1 aJiang, Liang1 aGreiner, Markus1 aZoller, Peter1 aLukin, Mikhail, D. uhttp://arxiv.org/abs/0706.3879v201463nas a2200145 4500008004100000245007500041210006900116260001500185300001200200490000600212520100100218100002001219700002401239856005401263 2008 eng d00aEstimating Jones polynomials is a complete problem for one clean qubit0 aEstimating Jones polynomials is a complete problem for one clean c2008/09/01 a681-7140 v83 a

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

1 aShor, Peter, W.1 aJordan, Stephen, P. uhttp://dl.acm.org/citation.cfm?id=2017011.201701201032nas a2200181 4500008004100000245003700041210003700078260001500115300001100130490000700141520058000148100001800728700001700746700001800763700002000781700001200801856003700813 2008 eng d00aExistence of Universal Entangler0 aExistence of Universal Entangler c2008/01/01 a0121030 v493 a A gate is called entangler if it transforms some (pure) product states to entangled states. A universal entangler is a gate which transforms all product states to entangled states. In practice, a universal entangler is a very powerful device for generating entanglements, and thus provides important physical resources for accomplishing many tasks in quantum computing and quantum information. This Letter demonstrates that a universal entangler always exists except for a degenerated case. Nevertheless, the problem how to find a universal entangler remains open. 1 aChen, Jianxin1 aDuan, Runyao1 aJi, Zhengfeng1 aYing, Mingsheng1 aYu, Jun uhttp://arxiv.org/abs/0704.1473v201345nas a2200109 4500008004100000245009200041210006900133260001500202520095700217100002401174856003701198 2008 eng d00aFast quantum algorithms for approximating some irreducible representations of groups 0 aFast quantum algorithms for approximating some irreducible repre c2008/11/043 a We consider the quantum complexity of estimating matrix elements of unitary irreducible representations of groups. For several finite groups including the symmetric group, quantum Fourier transforms yield efficient solutions to this problem. Furthermore, quantum Schur transforms yield efficient solutions for certain irreducible representations of the unitary group. Beyond this, we obtain poly(n)-time quantum algorithms for approximating matrix elements from all the irreducible representations of the alternating group A_n, and all the irreducible representations of polynomial highest weight of U(n), SU(n), and SO(n). These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters. 1 aJordan, Stephen, P. uhttp://arxiv.org/abs/0811.0562v201250nas a2200229 4500008004100000245006800041210006700109260001400176300001400190490000600204520061800210100001900828700001900847700001800866700001400884700001500898700001900913700001500932700001800947700001800965856003700983 2008 eng d00aHigh-sensitivity diamond magnetometer with nanoscale resolution0 aHighsensitivity diamond magnetometer with nanoscale resolution c2008/9/14 a810 - 8160 v43 aWe present a novel approach to the detection of weak magnetic fields that takes advantage of recently developed techniques for the coherent control of solid-state electron spin quantum bits. Specifically, we investigate a magnetic sensor based on Nitrogen-Vacancy centers in room-temperature diamond. We discuss two important applications of this technique: a nanoscale magnetometer that could potentially detect precession of single nuclear spins and an optical magnetic field imager combining spatial resolution ranging from micrometers to millimeters with a sensitivity approaching few femtotesla/Hz$^{1/2}$. 1 aTaylor, J., M.1 aCappellaro, P.1 aChildress, L.1 aJiang, L.1 aBudker, D.1 aHemmer, P., R.1 aYacoby, A.1 aWalsworth, R.1 aLukin, M., D. uhttp://arxiv.org/abs/0805.1367v101152nas a2200133 4500008004100000245004500041210004500086260001400131490000700145520078700152100002400939700001800963856003700981 2008 eng d00aPerturbative Gadgets at Arbitrary Orders0 aPerturbative Gadgets at Arbitrary Orders c2008/6/190 v773 a Adiabatic quantum algorithms are often most easily formulated using many-body interactions. However, experimentally available interactions are generally two-body. In 2004, Kempe, Kitaev, and Regev introduced perturbative gadgets, by which arbitrary three-body effective interactions can be obtained using Hamiltonians consisting only of two-body interactions. These three-body effective interactions arise from the third order in perturbation theory. Since their introduction, perturbative gadgets have become a standard tool in the theory of quantum computation. Here we construct generalized gadgets so that one can directly obtain arbitrary k-body effective interactions from two-body Hamiltonians. These effective interactions arise from the kth order in perturbation theory. 1 aJordan, Stephen, P.1 aFarhi, Edward uhttp://arxiv.org/abs/0802.1874v401766nas a2200181 4500008004100000245008100041210006900122260001500191300001800206490000800224520121000232100001701442700002401459700002001483700002001503700002401523856003701547 2008 eng d00aPolynomial-time quantum algorithm for the simulation of chemical dynamics 0 aPolynomialtime quantum algorithm for the simulation of chemical  c2008/11/24 a18681 - 186860 v1053 a The computational cost of exact methods for quantum simulation using classical computers grows exponentially with system size. As a consequence, these techniques can only be applied to small systems. By contrast, we demonstrate that quantum computers could exactly simulate chemical reactions in polynomial time. Our algorithm uses the split-operator approach and explicitly simulates all electron-nuclear and inter-electronic interactions in quadratic time. Surprisingly, this treatment is not only more accurate than the Born-Oppenheimer approximation, but faster and more efficient as well, for all reactions with more than about four atoms. This is the case even though the entire electronic wavefunction is propagated on a grid with appropriately short timesteps. Although the preparation and measurement of arbitrary states on a quantum computer is inefficient, here we demonstrate how to prepare states of chemical interest efficiently. We also show how to efficiently obtain chemically relevant observables, such as state-to-state transition probabilities and thermal reaction rates. Quantum computers using these techniques could outperform current classical computers with one hundred qubits. 1 aKassal, Ivan1 aJordan, Stephen, P.1 aLove, Peter, J.1 aMohseni, Masoud1 aAspuru-Guzik, Alán uhttp://arxiv.org/abs/0801.2986v301534nas a2200109 4500008004100000245004900041210004900090260001500139520120900154100002401363856003701387 2008 eng d00aQuantum Computation Beyond the Circuit Model0 aQuantum Computation Beyond the Circuit Model c2008/09/133 a The quantum circuit model is the most widely used model of quantum computation. It provides both a framework for formulating quantum algorithms and an architecture for the physical construction of quantum computers. However, several other models of quantum computation exist which provide useful alternative frameworks for both discovering new quantum algorithms and devising new physical implementations of quantum computers. In this thesis, I first present necessary background material for a general physics audience and discuss existing models of quantum computation. Then, I present three results relating to various models of quantum computation: a scheme for improving the intrinsic fault tolerance of adiabatic quantum computers using quantum error detecting codes, a proof that a certain problem of estimating Jones polynomials is complete for the one clean qubit complexity class, and a generalization of perturbative gadgets which allows k-body interactions to be directly simulated using 2-body interactions. Lastly, I discuss general principles regarding quantum computation that I learned in the course of my research, and using these principles I propose directions for future research. 1 aJordan, Stephen, P. uhttp://arxiv.org/abs/0809.2307v101063nas a2200145 4500008004100000245005700041210005500098260001300153490000800166520064500174100001900819700001900838700002300857856003700880 2008 eng d00aTwo-body transients in coupled atomic-molecular BECs0 aTwobody transients in coupled atomicmolecular BECs c2008/3/30 v1003 a We discuss the dynamics of an atomic Bose-Einstein condensate when pairs of atoms are converted into molecules by single-color photoassociation. Three main regimes are found and it is shown that they can be understood on the basis of time-dependent two-body theory. In particular, the so-called rogue dissociation regime [Phys. Rev. Lett., 88, 090403 (2002)], which has a density-dependent limit on the photoassociation rate, is identified with a transient regime of the two-atom dynamics exhibiting universal properties. Finally, we illustrate how these regimes could be explored by photoassociating condensates of alkaline-earth atoms. 1 aNaidon, Pascal1 aTiesinga, Eite1 aJulienne, Paul, S. uhttp://arxiv.org/abs/0707.2963v201051nas a2200133 4500008004100000245010600041210006900147260001500216520058800231100001900819700001900838700002300857856003700880 2007 eng d00aCoherent, adiabatic and dissociation regimes in coupled atomic-molecular Bose-Einstein condensates 0 aCoherent adiabatic and dissociation regimes in coupled atomicmol c2007/11/023 a We discuss the dynamics of a Bose-Einstein condensate of atoms which is suddenly coupled to a condensate of molecules by an optical or magnetic Feshbach resonance. Three limiting regimes are found and can be understood from the transient dynamics occuring for each pair of atoms. This transient dynamics can be summarised into a time-dependent shift and broadening of the molecular state. A simple Gross-Pitaevskii picture including this shift and broadening is proposed to describe the system in the three regimes. Finally, we suggest how to explore these regimes experimentally. 1 aNaidon, Pascal1 aTiesinga, Eite1 aJulienne, Paul, S. uhttp://arxiv.org/abs/0711.0397v201036nas a2200169 4500008004100000245009800041210006900139260001500208300001200223490000600235520049500241100001900736700001900755700002600774700002300800856004300823 2007 eng d00aEffective-range description of a Bose gas under strong one- or two-dimensional confinement 0 aEffectiverange description of a Bose gas under strong one or two c2007/01/29 a19 - 190 v93 a We point out that theories describing s-wave collisions of bosonic atoms confined in one- or two-dimensional geometries can be extended to much tighter confinements than previously thought. This is achieved by replacing the scattering length by an energy-dependent scattering length which was already introduced for the calculation of energy levels under 3D confinement. This replacement accurately predicts the position of confinement-induced resonances in strongly confined geometries. 1 aNaidon, Pascal1 aTiesinga, Eite1 aMitchell, William, F.1 aJulienne, Paul, S. uhttp://arxiv.org/abs/physics/0607140v201388nas a2200145 4500008004100000245009200041210006900133260001300202490000700215520092500222100001401147700001901161700001801180856004401198 2007 eng d00aA fast and robust approach to long-distance quantum communication with atomic ensembles0 afast and robust approach to longdistance quantum communication w c2007/7/20 v763 aQuantum repeaters create long-distance entanglement between quantum systems while overcoming difficulties such as the attenuation of single photons in a fiber. Recently, an implementation of a repeater protocol based on single qubits in atomic ensembles and linear optics has been proposed [Nature 414, 413 (2001)]. Motivated by rapid experimental progress towards implementing that protocol, here we develop a more efficient scheme compatible with active purification of arbitrary errors. Using similar resources as the earlier protocol, our approach intrinsically purifies leakage out of the logical subspace and all errors within the logical subspace, leading to greatly improved performance in the presence of experimental inefficiencies. Our analysis indicates that our scheme could generate approximately one pair per 3 minutes over 1280 km distance with fidelity (F>78%) sufficient to violate Bell's inequality. 1 aJiang, L.1 aTaylor, J., M.1 aLukin, M., D. uhttp://arxiv.org/abs/quant-ph/0609236v300857nas a2200145 4500008004100000245003400041210002900075260001500104520048200119100001800601700001800619700001700637700002000654856003700674 2007 eng d00aThe LU-LC conjecture is false0 aLULC conjecture is false c2007/09/093 a 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. 1 aJi, Zhengfeng1 aChen, Jianxin1 aWei, Zhaohui1 aYing, Mingsheng uhttp://arxiv.org/abs/0709.1266v201375nas a2200181 4500008004100000245008800041210006900129260001400198490000700212520082100219100001901040700001801059700002001077700001501097700001901112700001801131856004401149 2007 eng d00aRelaxation, dephasing, and quantum control of electron spins in double quantum dots0 aRelaxation dephasing and quantum control of electron spins in do c2007/7/130 v763 aRecent experiments have demonstrated quantum manipulation of two-electron spin states in double quantum dots using electrically controlled exchange interactions. Here, we present a detailed theory for electron spin dynamics in two-electron double dot systems that was used to guide these experiments and analyze experimental results. The theory treats both charge and spin degrees of freedom on an equal basis. Specifically, we analyze the relaxation and dephasing mechanisms that are relevant to experiments and discuss practical approaches for quantum control of two-electron system. We show that both charge and spin dephasing play important roles in the dynamics of the two-spin system, but neither represents a fundamental limit for electrical control of spin degrees of freedom in semiconductor quantum bits. 1 aTaylor, J., M.1 aPetta, J., R.1 aJohnson, A., C.1 aYacoby, A.1 aMarcus, C., M.1 aLukin, M., D. uhttp://arxiv.org/abs/cond-mat/0602470v201177nas a2200145 4500008004100000245006100041210006100102260001500163490000700178520074000185100002400925700001800949700002000967856004400987 2006 eng d00aError correcting codes for adiabatic quantum computation0 aError correcting codes for adiabatic quantum computation c2006/11/140 v743 a Recently, there has been growing interest in using adiabatic quantum computation as an architecture for experimentally realizable quantum computers. One of the reasons for this is the idea that the energy gap should provide some inherent resistance to noise. It is now known that universal quantum computation can be achieved adiabatically using 2-local Hamiltonians. The energy gap in these Hamiltonians scales as an inverse polynomial in the problem size. Here we present stabilizer codes which can be used to produce a constant energy gap against 1-local and 2-local noise. The corresponding fault-tolerant universal Hamiltonians are 4-local and 6-local respectively, which is the optimal result achievable within this framework. 1 aJordan, Stephen, P.1 aFarhi, Edward1 aShor, Peter, W. uhttp://arxiv.org/abs/quant-ph/0512170v300806nas a2200121 4500008004100000245006100041210006100102260001400163490000700177520043200184100002400616856004400640 2005 eng d00aFast quantum algorithm for numerical gradient estimation0 aFast quantum algorithm for numerical gradient estimation c2005/7/280 v953 a Given a blackbox for f, a smooth real scalar function of d real variables, one wants to estimate the gradient of f at a given point with n bits of precision. On a classical computer this requires a minimum of d+1 blackbox queries, whereas on a quantum computer it requires only one query regardless of d. The number of bits of precision to which f must be evaluated matches the classical requirement in the limit of large n. 1 aJordan, Stephen, P. uhttp://arxiv.org/abs/quant-ph/0405146v201042nas a2200157 4500008004100000245006600041210006500107260001500172490000700187520057000194100001200764700001900776700002300795700002300818856004300841 2005 eng d00aMultichannel quantum-defect theory for slow atomic collisions0 aMultichannel quantumdefect theory for slow atomic collisions c2005/10/280 v723 a We present a multichannel quantum-defect theory for slow atomic collisions that takes advantages of the analytic solutions for the long-range potential, and both the energy and the angular-momentum insensitivities of the short-range parameters. The theory provides an accurate and complete account of scattering processes, including shape and Feshbach resonances, in terms of a few parameters such as the singlet and the triplet scattering lengths. As an example, results for $^{23}$Na-$^{23}$Na scattering are presented and compared close-coupling calculations. 1 aGao, Bo1 aTiesinga, Eite1 aWilliams, Carl, J.1 aJulienne, Paul, S. uhttp://arxiv.org/abs/physics/0508060v101196nas a2200217 4500008004100000245005900041210005800100260001500158490000700173520059700180100001100777700001200788700002300800700001800823700001700841700001900858700001700877700002100894700001900915856004400934 2005 eng d00aSodium Bose-Einstein Condensates in an Optical Lattice0 aSodium BoseEinstein Condensates in an Optical Lattice c2005/10/100 v723 a The phase transition from a superfluid to a Mott insulator has been observed in a $^{23}$Na Bose-Einstein condensate. A dye laser detuned $\approx 5$nm red of the Na $3^2$S$ \to 3^2$P$_{1/2}$ transition was used to form the three dimensional optical lattice. The heating effects of the small detuning as well as the three-body decay processes constrained the timescale of the experiment. Certain lattice detunings were found to induce a large loss of atoms. These loss features were shown to be due to photoassociation of atoms to vibrational levels in the Na$_2$ $(1) ^3\Sigma_g^+$ state. 1 aXu, K.1 aLiu, Y.1 aAbo-Shaeer, J., R.1 aMukaiyama, T.1 aChin, J., K.1 aMiller, D., E.1 aKetterle, W.1 aJones, Kevin, M.1 aTiesinga, Eite uhttp://arxiv.org/abs/cond-mat/0507288v101059nas a2200145 4500008004100000245006200041210006100103260001400164490000700178520062000185100002200805700001900827700002300846856004400869 2005 eng d00aSpontaneous dissociation of long-range Feshbach molecules0 aSpontaneous dissociation of longrange Feshbach molecules c2005/1/180 v943 a We study the spontaneous dissociation of diatomic molecules produced in cold atomic gases via magnetically tunable Feshbach resonances. We provide a universal formula for the lifetime of these molecules that relates their decay to the scattering length and the loss rate constant for inelastic spin relaxation. Our universal treatment as well as our exact coupled channels calculations for $^{85}$Rb dimers predict a suppression of the decay over several orders of magnitude when the scattering length is increased. Our predictions are in good agreement with recent measurements of the lifetime of $^{85}$Rb$_2$. 1 aKoehler, Thorsten1 aTiesinga, Eite1 aJulienne, Paul, S. uhttp://arxiv.org/abs/cond-mat/0408387v202281nas a2200181 4500008004100000245009200041210006900133260001500202300001600217490000700233520170600240100002101946700002201967700002401989700001902013700002302032856004402055 2004 eng d00aAdiabatic association of ultracold molecules via magnetic field tunable interactions 0 aAdiabatic association of ultracold molecules via magnetic field  c2004/09/14 a3457 - 35000 v373 a We consider in detail the situation of applying a time dependent external magnetic field to a 87Rb atomic Bose-Einstein condensate held in a harmonic trap, in order to adiabatically sweep the interatomic interactions across a Feshbach resonance to produce diatomic molecules. To this end, we introduce a minimal two-body Hamiltonian depending on just five measurable parameters of a Feshbach resonance, which accurately determines all low energy binary scattering observables, in particular, the molecular conversion efficiency of just two atoms. Based on this description of the microscopic collision phenomena, we use the many-body theory of T. Koehler and K. Burnett [Phys. Rev. A 65, 033601 (2002)] to study the efficiency of the association of molecules in a 87Rb Bose-Einstein condensate during a linear passage of the magnetic field strength across the 100 mT Feshbach resonance. We explore different, experimentally accessible, parameter regimes, and compare the predictions of Landau-Zener, configuration interaction, and two level mean field calculations with those of the microscopic many-body approach. Our comparative studies reveal a remarkable insensitivity of the molecular conversion efficiency with respect to both the details of the microscopic binary collision physics and the coherent nature of the Bose-Einstein condensed gas, provided that the magnetic field strength is varied linearly. We provide the reasons for this universality of the molecular production achieved by linear ramps of the magnetic field strength, and identify the Landau-Zener coefficient determined by F.H. Mies et al. [Phys. Rev. A 61, 022721 (2000)] as the main parameter that controls the efficiency. 1 aGoral, Krzysztof1 aKoehler, Thorsten1 aGardiner, Simon, A.1 aTiesinga, Eite1 aJulienne, Paul, S. uhttp://arxiv.org/abs/cond-mat/0312178v501322nas a2200169 4500008004100000245007000041210006900111260001400180490000700194520079400201100002300995700002301018700002601041700001901067700002301086856004301109 2003 eng d00aUltracold collision properties of metastable alkaline-earth atoms0 aUltracold collision properties of metastable alkalineearth atoms c2003/2/130 v903 a Ultra-cold collisions of spin-polarized 24Mg,40Ca, and 88Sr in the metastable 3P2 excited state are investigated. We calculate the long-range interaction potentials and estimate the scattering length and the collisional loss rate as a function of magnetic field. The estimates are based on molecular potentials between 3P2 alkaline-earth atoms obtained from ab initio atomic and molecular structure calculations. The scattering lengths show resonance behavior due to the appearance of a molecular bound state in a purely long-range interaction potential and are positive for magnetic fields below 50 mT. A loss-rate model shows that losses should be smallest near zero magnetic field and for fields slightly larger than the resonance field, where the scattering length is also positive. 1 aDerevianko, Andrei1 aPorsev, Sergey, G.1 aKotochigova, Svetlana1 aTiesinga, Eite1 aJulienne, Paul, S. uhttp://arxiv.org/abs/physics/0210076v1