02111nas a2200133 4500008004100000245009200041210006900133260001300202520166000215100002001875700002201895700002301917856003701940 2024 eng d00aScattering wave packets of hadrons in gauge theories: Preparation on a quantum computer0 aScattering wave packets of hadrons in gauge theories Preparation c2/1/20243 a

Quantum simulation holds promise of enabling a complete description of high-energy scattering processes rooted in gauge theories of the Standard Model. A first step in such simulations is preparation of interacting hadronic wave packets. To create the wave packets, one typically resorts to adiabatic evolution to bridge between wave packets in the free theory and those in the interacting theory, rendering the simulation resource intensive. In this work, we construct a wave-packet creation operator directly in the interacting theory to circumvent adiabatic evolution, taking advantage of resource-efficient schemes for ground-state preparation, such as variational quantum eigensolvers. By means of an ansatz for bound mesonic excitations in confining gauge theories, which is subsequently optimized using classical or quantum methods, we show that interacting mesonic wave packets can be created efficiently and accurately using digital quantum algorithms that we develop. Specifically, we obtain high-fidelity mesonic wave packets in the Z2 and U(1) lattice gauge theories coupled to fermionic matter in 1+1 dimensions. Our method is applicable to both perturbative and non-perturbative regimes of couplings. The wave-packet creation circuit for the case of the Z2 lattice gauge theory is built and implemented on the Quantinuum H1-1 trapped-ion quantum computer using 13 qubits and up to 308 entangling gates. The fidelities agree well with classical benchmark calculations after employing a simple symmetry-based noise-mitigation technique. This work serves as a step toward quantum computing scattering processes in quantum chromodynamics.

1 aDavoudi, Zohreh1 aHsieh, Chung-Chun1 aKadam, Saurabh, V. uhttps://arxiv.org/abs/2402.0084001621nas a2200157 4500008004100000245006100041210005700102260001400159520113900173100002001312700002201332700002301354700002401377700002501401856003701426 2024 eng d00aThe Second Moment of Hafnians in Gaussian Boson Sampling0 aSecond Moment of Hafnians in Gaussian Boson Sampling c3/20/20243 a

Gaussian Boson Sampling is a popular method for experimental demonstrations of quantum advantage, but many subtleties remain in fully understanding its theoretical underpinnings. An important component in the theoretical arguments for approximate average-case hardness of sampling is anticoncentration, which is a second-moment property of the output probabilities. In Gaussian Boson Sampling these are given by hafnians of generalized circular orthogonal ensemble matrices. In a companion work [arXiv:2312.08433], we develop a graph-theoretic method to study these moments and use it to identify a transition in anticoncentration. In this work, we find a recursive expression for the second moment using these graph-theoretic techniques. While we have not been able to solve this recursion by hand, we are able to solve it numerically exactly, which we do up to Fock sector 2n=80. We further derive new analytical results about the second moment. These results allow us to pinpoint the transition in anticoncentration and furthermore yield the expected linear cross-entropy benchmarking score for an ideal (error-free) device.

1 aEhrenberg, Adam1 aIosue, Joseph, T.1 aDeshpande, Abhinav1 aHangleiter, Dominik1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2403.1387802266nas a2200265 4500008004100000245005900041210005900100260001400159520150200173100002901675700001801704700002501722700002001747700002501767700001901792700002001811700001201831700001601843700002201859700001301881700002401894700002001918700002501938856003701963 2024 eng d00aSimulating Meson Scattering on Spin Quantum Simulators0 aSimulating Meson Scattering on Spin Quantum Simulators c3/11/20243 a

Studying high-energy collisions of composite particles, such as hadrons and nuclei, is an outstanding goal for quantum simulators. However, preparation of hadronic wave packets has posed a significant challenge, due to the complexity of hadrons and the precise structure of wave packets. This has limited demonstrations of hadron scattering on quantum simulators to date. Observations of confinement and composite excitations in quantum spin systems have opened up the possibility to explore scattering dynamics in spin models. In this article, we develop two methods to create entangled spin states corresponding to wave packets of composite particles in analog quantum simulators of Ising spin Hamiltonians. One wave-packet preparation method uses the blockade effect enabled by beyond-nearest-neighbor Ising spin interactions. The other method utilizes a quantum-bus-mediated exchange, such as the native spin-phonon coupling in trapped-ion arrays. With a focus on trapped-ion simulators, we numerically benchmark both methods and show that high-fidelity wave packets can be achieved in near-term experiments. We numerically study scattering of wave packets for experimentally realizable parameters in the Ising model and find inelastic-scattering regimes, corresponding to particle production in the scattering event, with prominent and distinct experimental signals. Our proposal, therefore, demonstrates the potential of observing inelastic scattering in near-term quantum simulators.

1 aBennewitz, Elizabeth, R.1 aWare, Brayden1 aSchuckert, Alexander1 aLerose, Alessio1 aSurace, Federica, M.1 aBelyansky, Ron1 aMorong, William1 aLuo, De1 aDe, Arinjoy1 aCollins, Kate, S.1 aKatz, Or1 aMonroe, Christopher1 aDavoudi, Zohreh1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2403.0706102177nas a2200181 4500008004100000022001400041245009400055210006900149260001500218300001600233490000600249520163700255100001801892700001701910700001601927700001501943856003701958 2024 eng d a2475-142100aSimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog Compilation0 aSimuQ A Framework for Programming Quantum Hamiltonian Simulation c11/19/2023 a2425–24550 v83 a

Quantum Hamiltonian simulation, which simulates the evolution of quantum systems and probes quantum phenomena, is one of the most promising applications of quantum computing. Recent experimental results suggest that Hamiltonian-oriented analog quantum simulation would be advantageous over circuit-oriented digital quantum simulation in the Noisy Intermediate-Scale Quantum (NISQ) machine era. However, programming analog quantum simulators is much more challenging due to the lack of a unified interface between hardware and software. In this paper, we design and implement SimuQ, the first framework for quantum Hamiltonian simulation that supports Hamiltonian programming and pulse-level compilation to heterogeneous analog quantum simulators. Specifically, in SimuQ, front-end users specify the target quantum system with Hamiltonian Modeling Language, and the Hamiltonian-level programmability of analog quantum simulators is specified through a new abstraction called the abstract analog instruction set (AAIS) and programmed in AAIS Specification Language by hardware providers. Through a solver-based compilation, SimuQ generates executable pulse schedules for real devices to simulate the evolution of desired quantum systems, which is demonstrated on superconducting (IBM), neutral-atom (QuEra), and trapped-ion (IonQ) quantum devices. Moreover, we demonstrate the advantages of exposing the Hamiltonian-level programmability of devices with native operations or interaction-based gates and establish a small benchmark of quantum simulation to evaluate SimuQ's compiler with the above analog quantum simulators.

1 aPeng, Yuxiang1 aYoung, Jacob1 aLiu, Pengyu1 aWu, Xiaodi uhttps://arxiv.org/abs/2303.0277502486nas a2200241 4500008004100000245013000041210006900171260001300240520172500253100001701978700001501995700002202010700002002032700002002052700001502072700002002087700001902107700001802126700001502144700002502159700002302184856003702207 2024 eng d00aStrong interactions between integrated microresonators and alkali atomic vapors: towards single-atom, single-photon operation0 aStrong interactions between integrated microresonators and alkal c4/5/20243 a

Cavity quantum electrodynamics (cQED), the interaction of a two-level system with a high quality factor (Q) cavity, is a foundational building block in different architectures for quantum computation, communication, and metrology. The strong interaction between the atom and the cavity enables single photon operation which is required for quantum gates and sources. Cold atoms, quantum dots, and color centers in crystals are amongst the systems that have shown single photon operations, but they require significant physical infrastructure. Atomic vapors, on the other hand, require limited experimental infrastructure and are hence much easier to deploy outside a laboratory, but they produce an ensemble of moving atoms that results in short interaction times involving multiple atoms, which can hamper quantum operations. A solution to this issue can be found in nanophotonic cavities, where light-matter interaction is enhanced and the volume of operation is small, so that fast single-atom, single-photon operations are enabled. In this work, we study the interaction of an atomically-clad microring resonator (ACMRR) with different-sized ensembles of Rb atoms. We demonstrate strong coupling between an ensemble of ~50 atoms interacting with a high-quality factor (Q > 4 x 10^5) ACMRR, yielding a many-atom cooperativity C ~ 5.5. We continue to observe signatures of atom-photon interaction for a few (< 3) atoms, for which we observe saturation at the level of one intracavity photon. Further development of our platform, which includes integrated thermo-optic heaters to enable cavity tuning and stabilization, should enable the observation of interactions between single photons and single atoms.

1 aZektzer, Roy1 aLu, Xiyuan1 aHoang, Khoi, Tuan1 aShrestha, Rahul1 aAustin, Sharoon1 aZhou, Feng1 aChanana, Ashish1 aHolland, Glenn1 aWestly, Daron1 aLett, Paul1 aGorshkov, Alexey, V.1 aSrinivasan, Kartik uhttps://arxiv.org/abs/2404.0437202031nas a2200121 4500008004100000245006200041210006200103260001500165520165100180100001701831700002401848856003701872 2023 eng d00aSecret extraction attacks against obfuscated IQP circuits0 aSecret extraction attacks against obfuscated IQP circuits c12/15/20233 a

Quantum computing devices can now perform sampling tasks which, according to complexity-theoretic and numerical evidence, are beyond the reach of classical computers. This raises the question of how one can efficiently verify that a quantum computer operating in this regime works as intended. In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of so-called IQP circuits, and challenges a prover to execute it on a quantum computer. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test that accepts samples from a correct quantum implementation. It was conjectured that extracting the secret from the challenge problem is NP-hard, so that the ability to pass the test constitutes strong evidence that the prover possesses a quantum device and that it works as claimed. Unfortunately, about a decade later, Kahanamoku-Meyer found an efficient classical secret extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol. Their IQP Stabilizer Scheme has been explicitly designed to circumvent the known weakness. They also suggested that the original construction can be made secure by adjusting the problem parameters. In this work, we develop a number of secret extraction attacks which are effective against both new approaches in a wide range of problem parameters. The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum supremacy thus remains open.

1 aGross, David1 aHangleiter, Dominik uhttps://arxiv.org/abs/2312.1015601331nas a2200157 4500008004100000245004000041210003900081260001400120300001100134490000800145520091900153100002301072700002101095700002001116856003701136 2023 eng d00aSelf-dual quasiperiodic percolation0 aSelfdual quasiperiodic percolation c2/27/2023 a0241370 v1073 a

How does the percolation transition behave in the absence of quenched randomness? To address this question, we study two nonrandom self-dual quasiperiodic models of square-lattice bond percolation. In both models, the critical point has emergent discrete scale invariance, but none of the additional emergent conformal symmetry of critical random percolation. From the discrete sequences of critical clusters, we find fractal dimensions of Df=1.911943(1) and Df=1.707234(40) for the two models, significantly different from Df=91/48=1.89583... of random percolation. The critical exponents ν, determined through a numerical study of cluster sizes and wrapping probabilities on a torus, are also well below the ν=4/3 of random percolation. While these new models do not appear to belong to a universality class, they demonstrate how the removal of randomness can fundamentally change the critical behavior.

1 aSommers, Grace, M.1 aGullans, Michael1 aHuse, David, A. uhttps://arxiv.org/abs/2206.1129001610nas a2200157 4500008004100000245005000041210005000091260001300141490000800154520116900162100002401331700001901355700001901374700002201393856003701415 2023 eng d00aShadow process tomography of quantum channels0 aShadow process tomography of quantum channels c4/4/20230 v1073 a

Quantum process tomography is a critical capability for building quantum computers, enabling quantum networks, and understanding quantum sensors. Like quantum state tomography, the process tomography of an arbitrary quantum channel requires a number of measurements that scale exponentially in the number of quantum bits affected. However, the recent field of shadow tomography, applied to quantum states, has demonstrated the ability to extract key information about a state with only polynomially many measurements. In this work, we apply the concepts of shadow state tomography to the challenge of characterizing quantum processes. We make use of the Choi isomorphism to directly apply rigorous bounds from shadow state tomography to shadow process tomography, and we find additional bounds on the number of measurements that are unique to process tomography. Our results, which include algorithms for implementing shadow process tomography enable new techniques including evaluation of channel concatenation and the application of channels to shadows of quantum states. This provides a dramatic improvement for understanding large-scale quantum systems.

1 aKunjummen, Jonathan1 aTran, Minh, C.1 aCarney, Daniel1 aTaylor, Jacob, M. uhttps://arxiv.org/abs/2110.0362901741nas a2200181 4500008004100000245006600041210006300107260001300170520118700183100001801370700002301388700002401411700002101435700002001456700002501476700002101501856003701522 2023 eng d00aA sharp phase transition in linear cross-entropy benchmarking0 asharp phase transition in linear crossentropy benchmarking c5/8/20233 a

Demonstrations of quantum computational advantage and benchmarks of quantum processors via quantum random circuit sampling are based on evaluating the linear cross-entropy benchmark (XEB). A key question in the theory of XEB is whether it approximates the fidelity of the quantum state preparation. Previous works have shown that the XEB generically approximates the fidelity in a regime where the noise rate per qudit ε satisfies εN≪1 for a system of N qudits and that this approximation breaks down at large noise rates. Here, we show that the breakdown of XEB as a fidelity proxy occurs as a sharp phase transition at a critical value of εN that depends on the circuit architecture and properties of the two-qubit gates, including in particular their entangling power. We study the phase transition using a mapping of average two-copy quantities to statistical mechanics models in random quantum circuit architectures with full or one-dimensional connectivity. We explain the phase transition behavior in terms of spectral properties of the transfer matrix of the statistical mechanics model and identify two-qubit gate sets that exhibit the largest noise robustness.

1 aWare, Brayden1 aDeshpande, Abhinav1 aHangleiter, Dominik1 aNiroula, Pradeep1 aFefferman, Bill1 aGorshkov, Alexey, V.1 aGullans, Michael uhttps://arxiv.org/abs/2305.0495402012nas a2200145 4500008004100000245008500041210006900126260001300195520155500208100001801763700001701781700001601798700001501814856003701829 2023 eng d00aSimuQ: A Domain-Specific Language For Quantum Simulation With Analog Compilation0 aSimuQ A DomainSpecific Language For Quantum Simulation With Anal c3/5/20233 a

Hamiltonian simulation is one of the most promising applications of quantum computing. Recent experimental results suggest that continuous-time analog quantum simulation would be advantageous over gate-based digital quantum simulation in the Noisy Intermediate-Size Quantum (NISQ) machine era. However, programming such analog quantum simulators is much more challenging due to the lack of a unified interface between hardware and software, and the only few known examples are all hardware-specific. In this paper, we design and implement SimuQ, the first domain-specific language for Hamiltonian simulation that supports pulse-level compilation to heterogeneous analog quantum simulators. Specifically, in SimuQ, front-end users will specify the target Hamiltonian evolution with a Hamiltonian modeling language, and the programmability of analog simulators is specified through a new abstraction called the abstract analog instruction set by hardware providers. Through a solver-based compilation, SimuQ will generate the pulse-level instruction schedule on the target analog simulator for the desired Hamiltonian evolution, which has been demonstrated on pulse-controlled superconducting (Qiskit Pulse) and neutral-atom (QuEra Bloqade) quantum systems, as well as on normal circuit-based digital quantum machines. Moreover, we also demonstrate the advantage of analog compilation over digital compilation on IBM machines, the use of SimuQ for resource estimation for hypothetical machines, and a scalability test of SimuQ's compilation.

1 aPeng, Yuxiang1 aYoung, Jacob1 aLiu, Pengyu1 aWu, Xiaodi uhttps://arxiv.org/abs/2303.0277501491nas a2200181 4500008004100000245008400041210006900125260001400194520089300208100003001101700002701131700003001158700002101188700001801209700002401227700002101251856003701272 2023 eng d00aSpin-selective strong light-matter coupling in a 2D hole gas-microcavity system0 aSpinselective strong lightmatter coupling in a 2D hole gasmicroc c2/12/20233 a

The interplay between time-reversal symmetry breaking and strong light-matter coupling in 2D gases brings intriguing aspects to polariton physics. This combination can lead to polarization/spin selective light-matter interaction in the strong coupling regime. In this work, we report such a selective strong light-matter interaction by harnessing a 2D gas in the quantum Hall regime coupled to a microcavity. Specifically, we demonstrate circular-polarization dependence of the vacuum Rabi splitting, as a function of magnetic field and hole density. We provide a quantitative understanding of the phenomenon by modeling the coupling of optical transitions between Landau levels to the microcavity. This method introduces a control tool over the spin degree of freedom in polaritonic semiconductor systems, paving the way for new experimental possibilities in light-matter hybrids.

1 aSuarez-Forero, Daniel, G.1 aSession, Deric, Weston1 aMehrabad, Mahmoud, Jalali1 aKnuppel, Patrick1 aFaelt, Stefan1 aWegscheider, Werner1 aHafezi, Mohammad uhttps://arxiv.org/abs/2302.0602301752nas 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.1347801289nas a2200169 4500008004100000245004100041210004100082260001400123520084200137100002300979700001601002700001801018700001201036700001701048700001701065856003701082 2023 eng d00aStreaming quantum state purification0 aStreaming quantum state purification c9/28/20233 a

Quantum state purification is the task of recovering a nearly pure copy of an unknown pure quantum state using multiple noisy copies of the state. This basic task has applications to quantum communication over noisy channels and quantum computation with imperfect devices, but has only been studied previously for the case of qubits. We derive an efficient purification procedure based on the swap test for qudits of any dimension, starting with any initial error parameter. Treating the initial error parameter and the dimension as constants, we show that our procedure has sample complexity asymptotically optimal in the final error parameter. Our protocol has a simple recursive structure that can be applied when the states are provided one at a time in a streaming fashion, requiring only a small quantum memory to implement.

1 aChilds, Andrew, M.1 aFu, Honghao1 aLeung, Debbie1 aLi, Zhi1 aOzols, Maris1 aVyas, Vedang uhttps://arxiv.org/abs/2309.1638701475nas a2200121 4500008004100000245003200041210003200073260001400105520115600119100001901275700002201294856003701316 2023 eng d00aStrongly incoherent gravity0 aStrongly incoherent gravity c1/20/20233 a

While most fundamental interactions in nature are known to be mediated by quantized fields, the possibility has been raised that gravity may behave differently. Making this concept precise enough to test requires consistent models. Here we construct an explicit example of a theory where a non-entangling version of an arbitrary two-body potential V(r) arises from local measurements and feedback forces. While a variety of such theories exist, our construction causes particularly strong decoherence compared to more subtle approaches. Regardless, expectation values of observables obey the usual classical dynamics, while the interaction generates no entanglement. Applied to the Newtonian potential, this produces a non-relativistic model of gravity with fundamental loss of unitarity. The model contains a pair of free parameters, a substantial range of which is not excluded by observations to date. As an alternative to testing entanglement properties, we show that the entire remaining parameter space can be tested by looking for loss of quantum coherence in small systems like atom interferometers coupled to oscillating source masses.

1 aCarney, Daniel1 aTaylor, Jacob, M. uhttps://arxiv.org/abs/2301.0837801519nas a2200133 4500008004100000245008200041210006900123260001500192520106200207100002601269700003001295700002301325856003701348 2023 eng d00aSubsystem CSS codes, a tighter stabilizer-to-CSS mapping, and Goursat's Lemma0 aSubsystem CSS codes a tighter stabilizertoCSS mapping and Goursa c11/29/20233 a

The CSS code construction is a powerful framework used to express features of a quantum code in terms of a pair of underlying classical codes. Its subsystem extension allows for similar expressions, but the general case has not been fully explored. Extending previous work of Aly et. al. [quant-ph/0610153], we determine subsystem CSS code parameters, express codewords, and develop a Steane-type decoder using only data from the two underlying classical codes. We show that any subsystem stabilizer code can be ``doubled'' to yield a subsystem CSS code with twice the number of physical, logical, and gauge qudits and up to twice the code distance. This mapping preserves locality and is tighter than the Majorana-based mapping of Bravyi, Leemhuis, and Terhal [New J. Phys. 12 083039 (2010)]. Using Goursat's Lemma, we show that every subsystem stabilizer code can be constructed from two nested subsystem CSS codes satisfying certain constraints, and we characterize subsystem stabilizer codes based on the nested codes' properties.

1 aLiu, Michael, Liaofan1 aTantivasadakarn, Nathanan1 aAlbert, Victor, V. uhttps://arxiv.org/abs/2311.1800302177nas a2200181 4500008004100000245007300041210006900114260001400183490000600197520165000203100001501853700001801868700001701886700002001903700001601923700001901939856003701958 2023 eng d00aSymphony: Expressive Secure Multiparty Computation with Coordination0 aSymphony Expressive Secure Multiparty Computation with Coordinat c2/20/20230 v73 a

Context: Secure Multiparty Computation (MPC) refers to a family of cryptographic techniques where mutually untrusting parties may compute functions of their private inputs while revealing only the function output. Inquiry: It can be hard to program MPCs correctly and efficiently using existing languages and frameworks, especially when they require coordinating disparate computational roles. How can we make this easier? Approach: We present Symphony, a new functional programming language for MPCs among two or more parties. Symphony starts from the single-instruction, multiple-data (SIMD) semantics of prior MPC languages, in which each party carries out symmetric responsibilities, and generalizes it using constructs that can coordinate many parties. Symphony introduces **first-class shares** and **first-class party sets** to provide unmatched language-level expressive power with high efficiency. Knowledge: Developing a core formal language called λ-Symphony, we prove that the intuitive, generalized SIMD view of a program coincides with its actual distributed semantics. Thus the programmer can reason about her programs by reading them from top to bottom, even though in reality the program runs in a coordinated fashion, distributed across many machines. We implemented a prototype interpreter for Symphony leveraging multiple cryptographic backends. With it we wrote a variety of MPC programs, finding that Symphony can express optimized protocols that other languages cannot, and that in general Symphony programs operate efficiently. [ full abstract at https://doi.org/10.22152/programming-journal.org/2023/7/14 ] 

1 aSweet, Ian1 aDarais, David1 aHeath, David1 aHarris, William1 aEstes, Ryan1 aHicks, Michael uhttps://arxiv.org/abs/2302.1007601949nas a2200193 4500008004100000245005300041210005200094260001500146520133800161653004301499653002701542653003101569653002901600653003101629100001801660700002001678700002001698856003701718 2022 eng d00aSample-optimal classical shadows for pure states0 aSampleoptimal classical shadows for pure states c11/21/20223 a

We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state ρ in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate Tr(Oρ) for any Hermitian observable O to within additive error ϵ provided Tr(O2)≤B and ∥O∥=1. Our main result applies to the joint measurement setting, where we show Θ~(B−−√ϵ−1+ϵ−2) samples of ρ are necessary and sufficient to succeed with high probability. The upper bound is a quadratic improvement on the previous best sample complexity known for this problem. For the lower bound, we see that the bottleneck is not how fast we can learn the state but rather how much any classical description of ρ can be compressed for observable estimation. In the independent measurement setting, we show that O(Bd−−−√ϵ−1+ϵ−2) samples suffice. Notably, this implies that the random Clifford measurements algorithm of Huang, Kueng, and Preskill, which is sample-optimal for mixed states, is not optimal for pure states. Interestingly, our result also uses the same random Clifford measurements but employs a different estimator.

10aFOS: Computer and information sciences10aFOS: Physical sciences10aInformation Theory (cs.IT)10aMachine Learning (cs.LG)10aQuantum Physics (quant-ph)1 aGrier, Daniel1 aPashayan, Hakop1 aSchaeffer, Luke uhttps://arxiv.org/abs/2211.1181001923nas a2200241 4500008004100000245007300041210006900114260001400183520110600197653004301303653002701346653002901373653003901402653003101441653005201472100002001524700002801544700001501572700002401587700001601611700001701627856003701644 2022 eng d00aScalably learning quantum many-body Hamiltonians from dynamical data0 aScalably learning quantum manybody Hamiltonians from dynamical d c9/28/20223 a

The physics of a closed quantum mechanical system is governed by its Hamiltonian. However, in most practical situations, this Hamiltonian is not precisely known, and ultimately all there is are data obtained from measurements on the system. In this work, we introduce a highly scalable, data-driven approach to learning families of interacting many-body Hamiltonians from dynamical data, by bringing together techniques from gradient-based optimization from machine learning with efficient quantum state representations in terms of tensor networks. Our approach is highly practical, experimentally friendly, and intrinsically scalable to allow for system sizes of above 100 spins. In particular, we demonstrate on synthetic data that the algorithm works even if one is restricted to one simple initial state, a small number of single-qubit observables, and time evolution up to relatively short times. For the concrete example of the one-dimensional Heisenberg model our algorithm exhibits an error constant in the system size and scaling as the inverse square root of the size of the data set.

10aFOS: Computer and information sciences10aFOS: Physical sciences10aMachine Learning (cs.LG)10aQuantum Gases (cond-mat.quant-gas)10aQuantum Physics (quant-ph)10aStrongly Correlated Electrons (cond-mat.str-el)1 aWilde, Frederik1 aKshetrimayum, Augustine1 aRoth, Ingo1 aHangleiter, Dominik1 aSweke, Ryan1 aEisert, Jens uhttps://arxiv.org/abs/2209.1432801649nas a2200193 4500008004100000245007500041210006900116260001300185490000600198520110000204100001401304700001301318700001701331700001301348700002101361700001801382700001801400856003701418 2022 eng d00aA scheme to create and verify scalable entanglement in optical lattice0 ascheme to create and verify scalable entanglement in optical lat c9/4/20220 v83 a

To achieve scalable quantum information processing, great efforts have been devoted to the creation of large-scale entangled states in various physical systems. Ultracold atom in optical lattice is considered as one of the promising platforms due to its feasible initialization and parallel manipulation. In this work, we propose an efficient scheme to generate and characterize global entanglement in the optical lattice. With only two-layer quantum circuits, the generation utilizes two-qubit entangling gates based on the superexchange interaction in double wells. The parallelism of these operations enables the generation to be fast and scalable. To verify the entanglement of this non-stabilizer state, we mainly design three complementary detection protocols which are less resource-consuming compared to the full tomography. In particular, one just needs two homogenous local measurement settings to identify the entanglement property. Our entanglement generation and verification protocols provide the foundation for the further quantum information processing in optical lattice.

1 aZhou, You1 aXiao, Bo1 aDa Li, Meng-1 aZhao, Qi1 aYuan, Zhen-Sheng1 aMa, Xiongfeng1 aPan, Jian-Wei uhttps://arxiv.org/abs/2209.0153102029nas a2200325 4500008004100000245006700041210006500108260001400173520109100187653003701278653002701315653003101342100001701373700001201390700002301402700001901425700001901444700001501463700001201478700002001490700001801510700001701528700002001545700001901565700001901584700002201603700001901625700002201644856003701666 2022 eng d00aSelf-Testing of a Single Quantum System: Theory and Experiment0 aSelfTesting of a Single Quantum System Theory and Experiment c3/17/20223 a

Certifying individual quantum devices with minimal assumptions is crucial for the development of quantum technologies. Here, we investigate how to leverage single-system contextuality to realize self-testing. We develop a robust self-testing protocol based on the simplest contextuality witness for the simplest contextual quantum system, the Klyachko-Can-Binicioğlu-Shumovsky (KCBS) inequality for the qutrit. We establish a lower bound on the fidelity of the state and the measurements (to an ideal configuration) as a function of the value of the witness under a pragmatic assumption on the measurements we call the KCBS orthogonality condition. We apply the method in an experiment with randomly chosen measurements on a single trapped 40Ca+ and near-perfect detection efficiency. The observed statistics allow us to self-test the system and provide the first experimental demonstration of quantum self-testing of a single system. Further, we quantify and report that deviations from our assumptions are minimal, an aspect previously overlooked by contextuality experiments.

10aAtomic Physics (physics.atom-ph)10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aHu, Xiao-Min1 aXie, Yi1 aArora, Atul, Singh1 aAi, Ming-Zhong1 aBharti, Kishor1 aZhang, Jie1 aWu, Wei1 aChen, Ping-Xing1 aCui, Jin-Ming1 aLiu, Bi-Heng1 aHuang, Yun-Feng1 aLi, Chuan-Feng1 aGuo, Guang-Can1 aRoland, Jérémie1 aCabello, Adán1 aKwek, Leong-Chuan uhttps://arxiv.org/abs/2203.0900301587nas 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.0730901867nas a2200205 4500008004100000245006500041210006500106260001500171520119000186653003701376653004301413653002701456653003101483100001801514700002301532700002401555700002501579700002001604856003701624 2022 eng d00aSharp complexity phase transitions generated by entanglement0 aSharp complexity phase transitions generated by entanglement c12/20/20223 a

Entanglement is one of the physical properties of quantum systems responsible for the computational hardness of simulating quantum systems. But while the runtime of specific algorithms, notably tensor network algorithms, explicitly depends on the amount of entanglement in the system, it is unknown whether this connection runs deeper and entanglement can also cause inherent, algorithm-independent complexity. In this work, we quantitatively connect the entanglement present in certain quantum systems to the computational complexity of simulating those systems. Moreover, we completely characterize the entanglement and complexity as a function of a system parameter. Specifically, we consider the task of simulating single-qubit measurements of k--regular graph states on n qubits. We show that, as the regularity parameter is increased from 1 to n−1, there is a sharp transition from an easy regime with low entanglement to a hard regime with high entanglement at k=3, and a transition back to easy and low entanglement at k=n−3. As a key technical result, we prove a duality for the simulation complexity of regular graph states between low and high regularity.

10aComputational Complexity (cs.CC)10aFOS: Computer and information sciences10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aGhosh, Soumik1 aDeshpande, Abhinav1 aHangleiter, Dominik1 aGorshkov, Alexey, V.1 aFefferman, Bill uhttps://arxiv.org/abs/2212.1058201610nas a2200157 4500008004100000245005700041210005600098260001400154520112700168100002001295700002301315700002901338700002301367700002501390856003701415 2022 eng d00aSimulation Complexity of Many-Body Localized Systems0 aSimulation Complexity of ManyBody Localized Systems c5/25/20223 a

We use complexity theory to rigorously investigate the difficulty of classically simulating evolution under many-body localized (MBL) Hamiltonians. Using the defining feature that MBL systems have a complete set of quasilocal integrals of motion (LIOMs), we demonstrate a transition in the classical complexity of simulating such systems as a function of evolution time. On one side, we construct a quasipolynomial-time tensor-network-inspired algorithm for strong simulation of 1D MBL systems (i.e., calculating the expectation value of arbitrary products of local observables) evolved for any time polynomial in the system size. On the other side, we prove that even weak simulation, i.e. sampling, becomes formally hard after an exponentially long evolution time, assuming widely believed conjectures in complexity theory. Finally, using the consequences of our classical simulation results, we also show that the quantum circuit complexity for MBL systems is sublinear in evolution time. This result is a counterpart to a recent proof that the complexity of random quantum circuits grows linearly in time. 

1 aEhrenberg, Adam1 aDeshpande, Abhinav1 aBaldwin, Christopher, L.1 aAbanin, Dmitry, A.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2205.1296701457nas a2200157 4500008004100000245003100041210003100072260001500103490000800118520103500126653002701161653003101188100002201219700002101241856003701262 2022 eng d00aSimultaneous Stoquasticity0 aSimultaneous Stoquasticity c06/09/20220 v1053 a

Stoquastic Hamiltonians play a role in the computational complexity of the local Hamiltonian problem as well as the study of classical simulability. In particular, stoquastic Hamiltonians can be straightforwardly simulated using Monte Carlo techniques. We address the question of whether two or more Hamiltonians may be made simultaneously stoquastic via a unitary transformation. This question has important implications for the complexity of simulating quantum annealing where quantum advantage is related to the stoquasticity of the Hamiltonians involved in the anneal. We find that for almost all problems no such unitary exists and show that the problem of determining the existence of such a unitary is equivalent to identifying if there is a solution to a system of polynomial (in)equalities in the matrix elements of the initial and transformed Hamiltonians. Solving such a system of equations is NP-hard. We highlight a geometric understanding of this problem in terms of a collection of generalized Bloch vectors.

10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aBringewatt, Jacob1 aBrady, Lucas, T. uhttps://arxiv.org/abs/2202.0886302255nas a2200205 4500008004100000245005300041210005000094260001300144520167300157100002001830700002001850700002301870700002101893700001601914700002401930700002501954700001701979700001601996856003702012 2022 eng d00aA single T-gate makes distribution learning hard0 asingle Tgate makes distribution learning hard c7/7/20223 a

The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits form a particularly interesting class of distributions, of key importance both to quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we provide an extensive characterization of the learnability of the output distributions of local quantum circuits. Our first result yields insight into the relationship between the efficient learnability and the efficient simulatability of these distributions. Specifically, we prove that the density modelling problem associated with Clifford circuits can be efficiently solved, while for depth d=nΩ(1) circuits the injection of a single T-gate into the circuit renders this problem hard. This result shows that efficient simulatability does not imply efficient learnability. Our second set of results provides insight into the potential and limitations of quantum generative modelling algorithms. We first show that the generative modelling problem associated with depth d=nΩ(1) local quantum circuits is hard for any learning algorithm, classical or quantum. As a consequence, one cannot use a quantum algorithm to gain a practical advantage for this task. We then show that, for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth d=ω(log(n)) Clifford circuits is hard. This result places limitations on the applicability of near-term hybrid quantum-classical generative modelling algorithms.

1 aHinsche, Marcel1 aIoannou, Marios1 aNietner, Alexander1 aHaferkamp, Jonas1 aQuek, Yihui1 aHangleiter, Dominik1 aSeifert, Jean-Pierre1 aEisert, Jens1 aSweke, Ryan uhttps://arxiv.org/abs/2207.0314001392nas a2200229 4500008004100000245008100041210006900122260001400191520061400205653002700819653005300846653004900899653003100948100001900979700001700998700001901015700002001034700002401054700002501078700002201103856003701125 2022 eng d00aSnowmass 2021 White Paper: Tabletop experiments for infrared quantum gravity0 aSnowmass 2021 White Paper Tabletop experiments for infrared quan c3/22/20223 a

Progress in the quantum readout and control of mechanical devices from single atoms to large masses may enable a first generation of experiments probing the gravitational interaction in the quantum regime, conceivably within the next decade. In this Snowmass whitepaper, we briefly outline the possibilities and challenges facing the realization of these experiments. In particular, we emphasize the need for detailed theories of modifications to the usual effective QFT of gravitons in the infrared regime E/L3≪mPl/ℓ3Pl in which these experiments operate, and relations to possible UV completions.

10aFOS: Physical sciences10aGeneral Relativity and Quantum Cosmology (gr-qc)10aHigh Energy Physics - Phenomenology (hep-ph)10aQuantum Physics (quant-ph)1 aCarney, Daniel1 aChen, Yanbei1 aGeraci, Andrew1 aMüller, Holger1 aPanda, Cristian, D.1 aStamp, Philip, C. E.1 aTaylor, Jacob, M. uhttps://arxiv.org/abs/2203.1184602149nas a2200457 4500008004100000245005300041210005200094260001400146520077300160653005700933653002700990653004601017653004901063100003401112700002201146700002101168700001901189700001901208700002201227700001901249700002201268700002501290700001901315700001701334700001901351700002101370700002101391700001801412700001401430700002701444700002201471700002201493700001601515700002001531700001701551700002501568700002201593700001401615700002501629856003701654 2022 eng d00aSnowmass 2021 White Paper: The Windchime Project0 aSnowmass 2021 White Paper The Windchime Project c3/14/20223 a

The absence of clear signals from particle dark matter in direct detection experiments motivates new approaches in disparate regions of viable parameter space. In this Snowmass white paper, we outline the Windchime project, a program to build a large array of quantum-enhanced mechanical sensors. The ultimate aim is to build a detector capable of searching for Planck mass-scale dark matter purely through its gravitational coupling to ordinary matter. In the shorter term, we aim to search for a number of other physics targets, especially some ultralight dark matter candidates. Here, we discuss the basic design, open R&D challenges and opportunities, current experimental efforts, and both short- and long-term physics targets of the Windchime project.

10aCosmology and Nongalactic Astrophysics (astro-ph.CO)10aFOS: Physical sciences10aHigh Energy Physics - Experiment (hep-ex)10aHigh Energy Physics - Phenomenology (hep-ph)1 aCollaboration, The, Windchime1 aAttanasio, Alaina1 aBhave, Sunil, A.1 aBlanco, Carlos1 aCarney, Daniel1 aDemarteau, Marcel1 aElshimy, Bahaa1 aFebbraro, Michael1 aFeldman, Matthew, A.1 aGhosh, Sohitri1 aHickin, Abby1 aHong, Seongjin1 aLang, Rafael, F.1 aLawrie, Benjamin1 aLi, Shengchao1 aLiu, Zhen1 aMaldonado, Juan, P. A.1 aMarvinney, Claire1 aOo, Hein, Zay Yar1 aPai, Yun-Yi1 aPooser, Raphael1 aQin, Juehang1 aSparmann, Tobias, J.1 aTaylor, Jacob, M.1 aTian, Hao1 aTunnell, Christopher uhttps://arxiv.org/abs/2203.0724202034nas a2200217 4500008004100000245004900041210004900090260001300139520129000152653006101442653002701503653004201530653004701572653005201619100001901671700002001690700002901710700002101739700001901760856003701779 2022 eng d00aSpectral Form Factor of a Quantum Spin Glass0 aSpectral Form Factor of a Quantum Spin Glass c4/4/20223 a

It is widely expected that systems which fully thermalize are chaotic in the sense of exhibiting random-matrix statistics of their energy level spacings, whereas integrable systems exhibit Poissonian statistics. In this paper, we investigate a third class: spin glasses. These systems are partially chaotic but do not achieve full thermalization due to large free energy barriers. We examine the level spacing statistics of a canonical infinite-range quantum spin glass, the quantum p-spherical model, using an analytic path integral approach. We find statistics consistent with a direct sum of independent random matrices, and show that the number of such matrices is equal to the number of distinct metastable configurations -- the exponential of the spin glass "complexity" as obtained from the quantum Thouless-Anderson-Palmer equations. We also consider the statistical properties of the complexity itself and identify a set of contributions to the path integral which suggest a Poissonian distribution for the number of metastable configurations. Our results show that level spacing statistics can probe the ergodicity-breaking in quantum spin glasses and provide a way to generalize the notion of spin glass complexity beyond models with a semi-classical limit.

10aDisordered Systems and Neural Networks (cond-mat.dis-nn)10aFOS: Physical sciences10aHigh Energy Physics - Theory (hep-th)10aStatistical Mechanics (cond-mat.stat-mech)10aStrongly Correlated Electrons (cond-mat.str-el)1 aWiner, Michael1 aBarney, Richard1 aBaldwin, Christopher, L.1 aGalitski, Victor1 aSwingle, Brian uhttps://arxiv.org/abs/2203.1275302774nas a2200241 4500008004100000245009900041210006900140260001100209520197600220100001902196700001702215700001802232700001602250700001602266700001702282700002202299700001702321700001802338700001802356700001702374700002102391856012002412 2022 eng d00aStatus Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process0 aStatus Report on the Third Round of the NIST PostQuantum Cryptog c7/20223 a

The National Institute of Standards and Technology is in the process of selecting publickey cryptographic algorithms through a public, competition-like process. The new publickey cryptography standards will specify additional digital signature, public-key encryption, and key-establishment algorithms to augment Federal Information Processing Standard (FIPS) 186-4, Digital Signature Standard (DSS), as well as NIST Special Publication (SP) 800-56A Revision 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800-56B Revision 2, Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography. It is intended that these algorithms will be capable of protecting sensitive information well into the foreseeable future, including after the advent of quantum computers.

This report describes the evaluation and selection process of the NIST Post-Quantum Cryptography Standardization process third-round candidates based on public feedback and internal review. The report summarizes each of the 15 third-round candidate algorithms and identifies those selected for standardization, as well as those that will continue to be evaluated in a fourth round of analysis. The public-key encryption and key-establishment algorithm that will be standardized is CRYSTALS–KYBER. The digital signatures that will be standardized are CRYSTALS–Dilithium, FALCON, and SPHINCS+. While there are multiple signature algorithms selected, NIST recommends CRYSTALS–Dilithium as the primary algorithm to be implemented. In addition, four of the alternate key-establishment candidate algorithms will advance to a fourth round of evaluation: BIKE, Classic McEliece, HQC, and SIKE. These candidates are still being considered for future standardization. NIST will also issue a new Call for Proposals for public-key digital signature algorithms to augment and diversify its signature portfolio.

1 aAlagic, Gorjan1 aApon, Daniel1 aCooper, David1 aDang, Quynh1 aDang, Thinh1 aKelsey, John1 aLichtinger, Jacob1 aMiller, Carl1 aMoody, Dustin1 aPeralta, Rene1 aPerlner, Ray1 aRobinson, Angela uhttps://quics.umd.edu/publications/status-report-third-round-nist-post-quantum-cryptography-standardization-process01834nas a2200157 4500008004100000245007600041210006900117260001400186520133100200100002901531700001601560700002501576700002101601700001701622856003701639 2021 eng d00aSingularities in nearly-uniform 1D condensates due to quantum diffusion0 aSingularities in nearlyuniform 1D condensates due to quantum dif c3/10/20213 a

Dissipative systems can often exhibit wavelength-dependent loss rates. One prominent example is Rydberg polaritons formed by electromagnetically-induced transparency, which have long been a leading candidate for studying the physics of interacting photons and also hold promise as a platform for quantum information. In this system, dissipation is in the form of quantum diffusion, i.e., proportional to k2 (k being the wavevector) and vanishing at long wavelengths as k→0. Here, we show that one-dimensional condensates subject to this type of loss are unstable to long-wavelength density fluctuations in an unusual manner: after a prolonged period in which the condensate appears to relax to a uniform state, local depleted regions quickly form and spread ballistically throughout the system. We connect this behavior to the leading-order equation for the nearly-uniform condensate -- a dispersive analogue to the Kardar-Parisi-Zhang (KPZ) equation -- which develops singularities in finite time. Furthermore, we show that the wavefronts of the depleted regions are described by purely dissipative solitons within a pair of hydrodynamic equations, with no counterpart in lossless condensates. We close by discussing conditions under which such singularities and the resulting solitons can be physically realized.

1 aBaldwin, Christopher, L.1 aBienias, P.1 aGorshkov, Alexey, V.1 aGullans, Michael1 aMaghrebi, M. uhttps://arxiv.org/abs/2103.0629301449nas 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.1209601130nas a2200169 4500008004100000245006700041210006500108260001400173520060600187100001900793700002400812700002100836700001900857700002200876700002500898856003700923 2021 eng d00aSpin-Wave Quantum Computing with Atoms in a Single-Mode Cavity0 aSpinWave Quantum Computing with Atoms in a SingleMode Cavity c9/30/20213 a

We present a method for network-capable quantum computing that relies on holographic spin-wave excitations stored collectively in ensembles of qubits. We construct an orthogonal basis of spin waves in a one-dimensional array and show that high-fidelity universal linear controllability can be achieved using only phase shifts, applied in both momentum and position space. Neither single-site addressability nor high single-qubit cooperativity is required, and the spin waves can be read out with high efficiency into a single cavity mode for quantum computing and networking applications. 

1 aCox, Kevin, C.1 aBienias, Przemyslaw1 aMeyer, David, H.1 aKunz, Paul, D.1 aFahey, Donald, P.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2109.1525201315nas a2200145 4500008004100000245007600041210006900117260001400186520084500200100002201045700002701067700002001094700001801114856003701132 2021 eng d00aSubdiffusive hydrodynamics of nearly-integrable anisotropic spin chains0 aSubdiffusive hydrodynamics of nearlyintegrable anisotropic spin  c9/27/20213 a

We address spin transport in the easy-axis Heisenberg spin chain subject to integrability-breaking perturbations. We find that spin transport is subdiffusive with dynamical exponent z=4 up to a timescale that is parametrically long in the anisotropy. In the limit of infinite anisotropy, transport is subdiffusive at all times; for large finite anisotropy, one eventually recovers diffusion at late times, but with a diffusion constant independent of the strength of the integrability breaking perturbation. We provide numerical evidence for these findings, and explain them by adapting the generalized hydrodynamics framework to nearly integrable dynamics. Our results show that the diffusion constant of near-integrable interacting spin chains is not generically a continuous function of the integrability-breaking parameter. 

1 aDe Nardis, Jacopo1 aGopalakrishnan, Sarang1 aVasseur, Romain1 aWare, Brayden uhttps://arxiv.org/abs/2109.1325101688nas a2200133 4500008004100000245005300041210005200094260001500146520129100161100002301452700002301475700001901498856003701517 2021 eng d00aSurface code compilation via edge-disjoint paths0 aSurface code compilation via edgedisjoint paths c10/21/20213 a

We provide an efficient algorithm to compile quantum circuits for fault-tolerant execution. We target surface codes, which form a 2D grid of logical qubits with nearest-neighbor logical operations. Embedding an input circuit's qubits in surface codes can result in long-range two-qubit operations across the grid. We show how to prepare many long-range Bell pairs on qubits connected by edge-disjoint paths of ancillas in constant depth which can be used to perform these long-range operations. This forms one core part of our Edge-Disjoint Paths Compilation (EDPC) algorithm, by easily performing parallel long-range Clifford operations in constant depth. It also allows us to establish a connection between surface code compilation and several well-studied edge-disjoint paths problems. Similar techniques allow us to perform non-Clifford single-qubit rotations far from magic state distillation factories. In this case, we can easily find the maximum set of paths by a max-flow reduction, which forms the other major part of our EDPC algorithm. We compare EDPC to other compilation approaches including a SWAP-based algorithm, and find significantly improved performance for circuits built from parallel CNOTs, and for circuits which implement the multi-controlled X gate.

1 aBeverland, Michael1 aKliuchnikov, Vadym1 aSchoute, Eddie uhttps://arxiv.org/abs/2110.1149301359nas a2200157 4500008004100000245003200041210003200073260001400105520093200119100002001051700002001071700002701091700002201118700002401140856003701164 2021 eng d00aSynchronous Values of Games0 aSynchronous Values of Games c9/29/20213 a

We study synchronous values of games, especially synchronous games. It is known that a synchronous game has a perfect strategy if and only if it has a perfect synchronous strategy. However, we give examples of synchronous games, in particular graph colouring games, with synchronous value that is strictly smaller than their ordinary value. Thus, the optimal strategy for a synchronous game need not be synchronous. We derive a formula for the synchronous value of an XOR game as an optimization problem over a spectrahedron involving a matrix related to the cost matrix. We give an example of a game such that the synchronous value of repeated products of the game is strictly increasing. We show that the synchronous quantum bias of the XOR of two XOR games is not multiplicative. Finally, we derive geometric and algebraic conditions that a set of projections that yields the synchronous value of a game must satisfy.

1 aHelton, William1 aMousavi, Hamoon1 aNezhadi, Seyed, Sajjad1 aPaulsen, Vern, I.1 aRussell, Travis, B. uhttps://arxiv.org/abs/2109.1474102222nas a2200169 4500008004100000245010800041210006900149260001400218520167700232100001801909700001901927700001701946700001901963700001501982700001801997856003702015 2020 eng d00aSampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning0 aSamplingbased sublinear lowrank matrix arithmetic framework for  c6/18/20203 a

We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang's breakthrough quantum-inspired algorithm for recommendation systems [STOC'19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén et al. [STOC'19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all recent results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: ℓ2-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.

1 aChia, Nai-Hui1 aGilyen, Andras1 aLi, Tongyang1 aLin, Han-Hsuan1 aTang, Ewin1 aWang, Chunhao uhttps://arxiv.org/abs/1910.0615101697nas a2200181 4500008004100000245007000041210006900111260001400180490000800194520115900202100002301361700001501384700001901399700002001418700001901438700002101457856003701478 2020 eng d00aSearch for composite dark matter with optically levitated sensors0 aSearch for composite dark matter with optically levitated sensor c11/2/20200 v1253 a

Results are reported from a search for a class of composite dark matter models with feeble, long-range interactions with normal matter. We search for impulses arising from passing dark matter particles by monitoring the mechanical motion of an optically levitated nanogram mass over the course of several days. Assuming such particles constitute the dominant component of dark matter, this search places upper limits on their interaction with neutrons of αn≤1.2×10−7 at 95\% confidence for dark matter masses between 1--10 TeV and mediator masses mφ≤0.1 eV. Due to the large enhancement of the cross-section for dark matter to coherently scatter from a nanogram mass (∼1029 times that for a single neutron) and the ability to detect momentum transfers as small as ∼200 MeV/c, these results provide sensitivity to certain classes of composite dark matter models that substantially exceeds existing searches, including those employing kg-scale or ton-scale targets. Extensions of these techniques can enable directionally-sensitive searches for a broad class of previously inaccessible heavy dark matter candidates. 

1 aMonteiro, Fernando1 aAfek, Gadi1 aCarney, Daniel1 aKrnjaic, Gordan1 aWang, Jiaxiang1 aMoore, David, C. uhttps://arxiv.org/abs/2007.1206702382nas a2200145 4500008004100000245007400041210006900115260001500184520192100199100001902120700002402139700001902163700001702182856003702199 2020 eng d00aSecure Quantum Two-Party Computation: Impossibility and Constructions0 aSecure Quantum TwoParty Computation Impossibility and Constructi c10/15/20203 a

Secure two-party computation considers the problem of two parties computing a joint function of their private inputs without revealing anything beyond the output of the computation. In this work, we take the first steps towards understanding the setting in which the two parties want to evaluate a joint quantum functionality while using only a classical channel between them. Our first result indicates that it is in general impossible to realize a two-party quantum functionality against malicious adversaries with black-box simulation, relying only on classical channels. The negative result stems from reducing the existence of a black-box simulator to an extractor for classical proof of quantum knowledge, which in turn leads to violation of the quantum no-cloning. Next, we introduce the notion of oblivious quantum function evaluation (OQFE). An OQFE is a two-party quantum cryptographic primitive with one fully classical party (Alice) whose input is (a classical description of a) quantum unitary, U, and a quantum party (Bob) whose input is a quantum state, ψ. In particular, Alice receives a classical output corresponding to the measurement of U(ψ) while Bob receives no output. In OQFE, Bob remains oblivious to Alice's input, while Alice learns nothing about ψ more than what can be learned from the output. We present two constructions, one secure against semi-honest parties and the other against malicious parties. Due to the no-go result mentioned above, we consider what is arguably the best possible notion obtainable in our model concerning malicious adversaries: one-sided simulation security. Our protocol relies on the assumption of injective homomorphic trapdoor OWFs, which in turn rely on the LWE problem. As a result, we put forward a first, simple and modular, construction of one-sided quantum two-party computation and quantum oblivious transfer over classical networks.

1 aCiamp, Michele1 aCojocaru, Alexandru1 aKashefi, Elham1 aMantri, Atul uhttps://arxiv.org/abs/2010.0792502441nas a2200181 4500008004100000245007300041210006900114260001300183520187800196100002702074700002402101700001902125700001902144700002202163700001702185700002002202856003702222 2020 eng d00aSecurity Limitations of Classical-Client Delegated Quantum Computing0 aSecurity Limitations of ClassicalClient Delegated Quantum Comput c7/3/20203 a

Secure delegated quantum computing allows a computationally weak client to outsource an arbitrary quantum computation to an untrusted quantum server in a privacy-preserving manner. One of the promising candidates to achieve classical delegation of quantum computation is classical-client remote state preparation (RSPCC), where a client remotely prepares a quantum state using a classical channel. However, the privacy loss incurred by employing RSPCC as a sub-module is unclear.
In this work, we investigate this question using the Constructive Cryptography framework by Maurer and Renner (ICS'11). We first identify the goal of RSPCC as the construction of ideal RSP resources from classical channels and then reveal the security limitations of using RSPCC. First, we uncover a fundamental relationship between constructing ideal RSP resources (from classical channels) and the task of cloning quantum states. Any classically constructed ideal RSP resource must leak to the server the full classical description (possibly in an encoded form) of the generated quantum state, even if we target computational security only. As a consequence, we find that the realization of common RSP resources, without weakening their guarantees drastically, is impossible due to the no-cloning theorem. Second, the above result does not rule out that a specific RSPCC protocol can replace the quantum channel at least in some contexts, such as the Universal Blind Quantum Computing (UBQC) protocol of Broadbent et al. (FOCS '09). However, we show that the resulting UBQC protocol cannot maintain its proven composable security as soon as RSPCC is used as a subroutine. Third, we show that replacing the quantum channel of the above UBQC protocol by the RSPCC protocol QFactory of Cojocaru et al. (Asiacrypt '19), preserves the weaker, game-based, security of UBQC.

1 aBadertscher, Christian1 aCojocaru, Alexandru1 aColisson, Léo1 aKashefi, Elham1 aLeichtle, Dominik1 aMantri, Atul1 aWallden, Petros uhttps://arxiv.org/abs/2007.0166801772nas a2200169 4500008004100000245006700041210006600108260001300174490000800187520126400195100002001459700001901479700002301498700002501521700001901546856003701565 2020 eng d00aSignaling and Scrambling with Strongly Long-Range Interactions0 aSignaling and Scrambling with Strongly LongRange Interactions c7/8/20200 v1023 a

Strongly long-range interacting quantum systems---those with interactions decaying as a power-law 1/rα in the distance r on a D-dimensional lattice for α≤D---have received significant interest in recent years. They are present in leading experimental platforms for quantum computation and simulation, as well as in theoretical models of quantum information scrambling and fast entanglement creation. Since no notion of locality is expected in such systems, a general understanding of their dynamics is lacking. As a first step towards rectifying this problem, we prove two new Lieb-Robinson-type bounds that constrain the time for signaling and scrambling in strongly long-range interacting systems, for which no tight bounds were previously known. Our first bound applies to systems mappable to free-particle Hamiltonians with long-range hopping, and is saturable for α≤D/2. Our second bound pertains to generic long-range interacting spin Hamiltonians, and leads to a tight lower bound for the signaling time to extensive subsets of the system for all α<D. This result also lower-bounds the scrambling time, and suggests a path towards achieving a tight scrambling bound that can prove the long-standing fast scrambling conjecture. 

1 aGuo, Andrew, Y.1 aTran, Minh, C.1 aChilds, Andrew, M.1 aGorshkov, Alexey, V.1 aGong, Zhe-Xuan uhttps://arxiv.org/abs/1906.0266201053nas a2200121 4500008004100000245007400041210006900115260001300184520066700197100001600864700001400880856003700894 2020 eng d00aSimulating Hamiltonian Dynamics with an Off-diagonal Series Expansion0 aSimulating Hamiltonian Dynamics with an Offdiagonal Series Expan c6/3/20203 a

We propose an efficient quantum algorithm for simulating the dynamics of general Hamiltonian systems. Our technique is based on a power series expansion of the time-evolution operator in its off-diagonal terms. The expansion decouples the dynamics due to the diagonal component of the Hamiltonian from the dynamics generated by its off-diagonal part, which we encode using the linear combination of unitaries technique. Our method has an optimal dependence on the desired precision and, as we illustrate, generally requires considerably fewer resources than the current state-of-the-art. We provide an analysis of resource costs for several sample models.

1 aKalev, Amir1 aHen, Itay uhttps://arxiv.org/abs/2006.0253901588nas a2200157 4500008004100000245006600041210006600107260001400173490000800187520113200195100001701327700001701344700001701361700001501378856003701393 2020 eng d00aSimulating large quantum circuits on a small quantum computer0 aSimulating large quantum circuits on a small quantum computer c12/8/20200 v1253 a

Limited quantum memory is one of the most important constraints for near-term quantum devices. Understanding whether a small quantum computer can simulate a larger quantum system, or execute an algorithm requiring more qubits than available, is both of theoretical and practical importance. In this Letter, we introduce cluster parameters K and d of a quantum circuit. The tensor network of such a circuit can be decomposed into clusters of size at most d with at most K qubits of inter-cluster quantum communication. Our main result is a simulation scheme of any (K,d)-clustered quantum circuit on a d-qubit machine in time roughly 2O(K). An important application of our result is the simulation of clustered quantum systems---such as large molecules---that can be partitioned into multiple significantly smaller clusters with weak interactions among them. Another potential application is quantum optimization: we demonstrate numerically that variational quantum eigensolvers can still perform well when restricted to clustered circuits, thus making it feasible to study large quantum systems on small quantum devices.

1 aPeng, Tianyi1 aHarrow, Aram1 aOzols, Maris1 aWu, Xiaodi uhttps://arxiv.org/abs/1904.0010201875nas a2200145 4500008004100000245004100041210003900082260001300121520148600134100001801620700002201638700001301660700001901673856003701692 2020 eng d00aA Sparse Model of Quantum Holography0 aSparse Model of Quantum Holography c8/5/20203 a

We study a sparse version of the Sachdev-Ye-Kitaev (SYK) model defined on random hypergraphs constructed either by a random pruning procedure or by randomly sampling regular hypergraphs. The resulting model has a new parameter, k, defined as the ratio of the number of terms in the Hamiltonian to the number of degrees of freedom, with the sparse limit corresponding to the thermodynamic limit at fixed k. We argue that this sparse SYK model recovers the interesting global physics of ordinary SYK even when k is of order unity. In particular, at low temperature the model exhibits a gravitational sector which is maximally chaotic. Our argument proceeds by constructing a path integral for the sparse model which reproduces the conventional SYK path integral plus gapped fluctuations. The sparsity of the model permits larger scale numerical calculations than previously possible, the results of which are consistent with the path integral analysis. Additionally, we show that the sparsity of the model considerably reduces the cost of quantum simulation algorithms. This makes the sparse SYK model the most efficient currently known route to simulate a holographic model of quantum gravity. We also define and study a sparse supersymmetric SYK model, with similar conclusions to the non-supersymmetric case. Looking forward, we argue that the class of models considered here constitute an interesting and relatively unexplored sparse frontier in quantum many-body physics.

1 aXu, Shenglong1 aSusskind, Leonard1 aSu, Yuan1 aSwingle, Brian uhttps://arxiv.org/abs/2008.0230301597nas a2200145 4500008004100000245003200041210003100073260001400104520121600118100001901334700002901353700001501382700001701397856003701414 2020 eng d00aSpin-Mediated Mott Excitons0 aSpinMediated Mott Excitons c4/22/20203 a

Motivated by recent experiments on Mott insulators, in both iridates and ultracold atoms, we theoretically study the effects of magnetic order on the Mott-Hubbard excitons. In particular, we focus on spin-mediated doublon-holon pairing in Hubbard materials. We use several complementary theoretical techniques: mean-field theory to describe the spin degrees of freedom, the self-consistent Born approximation to characterize individual charge excitations across the Hubbard gap, and the Bethe-Salpeter equation to identify bound states of doublons and holons. The binding energy of the Hubbard exciton is found to increase with increasing the N{é}el order parameter, while the exciton mass decreases. We observe that these trends rely significantly on the retardation of the effective interaction, and require consideration of multiple effects from changing the magnetic order. Our results are consistent with the key qualitative trends observed in recent experiments on iridates. Moreover, the findings could have direct implications on ultracold atom Mott insulators, where the Hubbard model is the exact description of the system and the microscopic degrees of freedom can be directly accessed. 

1 aHuang, T., -S.1 aBaldwin, Christopher, L.1 aHafezi, M.1 aGalitski, V. uhttps://arxiv.org/abs/2004.1082503206nas a2200253 4500008004100000245010000041210006900141260001200210520236500222100001902587700002702606700001702633700001802650700001602668700001702684700001602701700001702717700001802734700001802752700001702770700002102787700002302808856012102831 2020 eng d00aStatus Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process0 aStatus Report on the Second Round of the NIST PostQuantum Crypto c07/20203 a

The National Institute of Standards and Technology is in the process of selecting one or more public-key cryptographic algorithms through a public, competition-like process. The new public-key cryptography standards will specify one or more additional digital signatures, public-key encryption, and key-establishment algorithms to augment Federal Information Processing Standard (FIPS) 186-4, Digital Signature Standard (DSS), as well as NIST Special Publication (SP) 800-56A Revision 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800-56B Revision 2, Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography. It is intended that these algorithms will be capable of protecting sensitive information well into the foreseeable future, including after the advent of quantum computers.

The NIST Post-Quantum Cryptography Standardization Process began in 2017 with 69 candidate algorithms that met both the minimum acceptance criteria and submission requirements. The first round lasted until January 2019, during which candidate algorithms were evaluated based on their security, performance, and other characteristics. NIST selected 26 algorithms to advance to the second round for more analysis. This report describes the evaluation and selection process, based on public feedback and internal review, of the second-round candidates. The report summarizes the 26 second-round candidate algorithms and identifies those selected to move forward to the third round of the competition. The third-round finalist public-key encryption and key-establishment algorithms are Classic McEliece, CRYSTALS-KYBER, NTRU, and SABER. The third-round finalists for digital signatures are CRYSTALS-DILITHIUM, FALCON, and Rainbow. These finalists will be considered for standardization at the end of the third round. In addition, eight alternate candidate algorithms will also advance to the third round: BIKE, FrodoKEM, HQC, NTRU Prime, SIKE, GeMSS, Picnic, and SPHINCS+. These additional candidates are still being considered for standardization, although this is unlikely to occur at the end of the third round. NIST hopes that the announcement of these finalists and additional candidates will serve to focus the cryptographic community’s attention during the next round.

1 aAlagic, Gorjan1 aAlperin-Sheriff, Jacob1 aApon, Daniel1 aCooper, David1 aDang, Quynh1 aKelsey, John1 aLiu, Yi-Kai1 aMiller, Carl1 aMoody, Dustin1 aPeralta, Rene1 aPerlner, Ray1 aRobinson, Angela1 aSmith-Tone, Daniel uhttps://quics.umd.edu/publications/status-report-second-round-nist-post-quantum-cryptography-standardization-process01030nas a2200157 4500008004100000245006700041210006700108260001400175520054300189100001900732700002900751700001700780700001900797700001900816856003700835 2020 eng d00aStudying viral populations with tools from quantum spin chains0 aStudying viral populations with tools from quantum spin chains c3/24/20203 a

We study Eigen's model of quasi-species, characterized by sequences that replicate with a specified fitness and mutate independently at single sites. The evolution of the population vector in time is then closely related to that of quantum spins in imaginary time. We employ multiple perspectives and tools from interacting quantum systems to examine growth and collapse of realistic viral populations, specifically certain HIV proteins. All approaches used, including the simplest perturbation theory, give consistent results.

1 aShivam, Saumya1 aBaldwin, Christopher, L.1 aBarton, John1 aKardar, Mehran1 aSondhi, S., L. uhttps://arxiv.org/abs/2003.1066801601nas a2200145 4500008004100000245007200041210006900113260001500182520114400197100001701341700001801358700002701376700001501403856003701418 2020 eng d00aSublinear classical and quantum algorithms for general matrix games0 aSublinear classical and quantum algorithms for general matrix ga c12/11/20203 a

We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix A∈Rn×d, sublinear algorithms for the matrix game minx∈Xmaxy∈Yy⊤Ax were previously known only for two special cases: (1) Y being the ℓ1-norm unit ball, and (2) X being either the ℓ1- or the ℓ2-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed q∈(1,2], we solve the matrix game where X is a ℓq-norm unit ball within additive error ε in time O~((n+d)/ε2). We also provide a corresponding sublinear quantum algorithm that solves the same task in time O~((n−−√+d−−√)poly(1/ε)) with a quadratic improvement in both n and d. Both our classical and quantum algorithms are optimal in the dimension parameters n and d up to poly-logarithmic factors. Finally, we propose sublinear classical and quantum algorithms for the approximate Carathéodory problem and the ℓq-margin support vector machines as applications.

1 aLi, Tongyang1 aWang, Chunhao1 aChakrabarti, Shouvanik1 aWu, Xiaodi uhttps://arxiv.org/abs/2012.0651901555nas a2200169 4500008004100000245005500041210005300096260001400149520105800163100002201221700002301243700001901266700002401285700002101309700001801330856003701348 2020 eng d00aSymmetries, graph properties, and quantum speedups0 aSymmetries graph properties and quantum speedups c6/23/20203 a

Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup?
In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups.
In contrast, in the adjacency list model for bounded-degree graphs (where graph symmetry is manifested differently), we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).

1 aBen-David, Shalev1 aChilds, Andrew, M.1 aGilyen, Andras1 aKretschmer, William1 aPodder, Supartha1 aWang, Daochen uhttps://arxiv.org/abs/2006.1276001648nas a2200193 4500008004100000245006700041210006700108260001300175300001100188490000800199520108700207100001601294700001901310700002201329700001801351700002301369700002501392856003701417 2020 eng d00aSymmetry breaking and error correction in open quantum systems0 aSymmetry breaking and error correction in open quantum systems c8/6/2020 a2404050 v1253 a

Symmetry-breaking transitions are a well-understood phenomenon of closed quantum systems in quantum optics, condensed matter, and high energy physics. However, symmetry breaking in open systems is less thoroughly understood, in part due to the richer steady-state and symmetry structure that such systems possess. For the prototypical open system---a Lindbladian---a unitary symmetry can be imposed in a "weak" or a "strong" way. We characterize the possible Zn symmetry breaking transitions for both cases. In the case of Z2, a weak-symmetry-broken phase guarantees at most a classical bit steady-state structure, while a strong-symmetry-broken phase admits a partially-protected steady-state qubit. Viewing photonic cat qubits through the lens of strong-symmetry breaking, we show how to dynamically recover the logical information after any gap-preserving strong-symmetric error; such recovery becomes perfect exponentially quickly in the number of photons. Our study forges a connection between driven-dissipative phase transitions and error correctio

1 aLieu, Simon1 aBelyansky, Ron1 aYoung, Jeremy, T.1 aLundgren, Rex1 aAlbert, Victor, V.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2008.0281601611nas a2200205 4500008004100000245008100041210006900122260001500191490000800206520098000214100001701194700001601211700002401227700002201251700002501273700002401298700002101322700002501343856003701368 2019 eng d00aScale-Invariant Continuous Entanglement Renormalization of a Chern Insulator0 aScaleInvariant Continuous Entanglement Renormalization of a Cher c03/27/20190 v1223 a

The multi-scale entanglement renormalization ansatz (MERA) postulates the existence of quantum circuits that renormalize entanglement in real space at different length scales. Chern insulators, however, cannot have scale-invariant discrete MERA circuits with finite bond dimension. In this Letter, we show that the continuous MERA (cMERA), a modified version of MERA adapted for field theories, possesses a fixed point wavefunction with nonzero Chern number. Additionally, it is well known that reversed MERA circuits can be used to prepare quantum states efficiently in time that scales logarithmically with the size of the system. However, state preparation via MERA typically requires the advent of a full-fledged universal quantum computer. In this Letter, we demonstrate that our cMERA circuit can potentially be realized in existing analog quantum computers, i.e., an ultracold atomic Fermi gas in an optical lattice with light-induced spin-orbit coupling. 

1 aChu, Su-Kuan1 aZhu, Guanyu1 aGarrison, James, R.1 aEldredge, Zachary1 aCuriel, Ana, Valdés1 aBienias, Przemyslaw1 aSpielman, I., B.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1807.1148600941nas a2200109 4500008004100000245005400041210005400095260001500149520061200164100001800776856003700794 2019 eng d00aSimulating quantum circuits by classical circuits0 aSimulating quantum circuits by classical circuits c04/10/20193 a

In a recent breakthrough, Bravyi, Gosset and König (BGK) [Science, 2018] proved that "simulating" constant depth quantum circuits takes classical circuits Ω(logn) depth. In our paper, we first formalise their notion of simulation, which we call "possibilistic simulation". Then, from well-known results, we deduce that their circuits can be simulated in depth O(log2n). Separately, we construct explicit classical circuits that can simulate any depth-d quantum circuit with Clifford and t T-gates in depth O(d+t). Our classical circuits use {NOT, AND, OR} gates of fan-in ≤2.

1 aWang, Daochen uhttps://arxiv.org/abs/1904.0528201623nas 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.0350501664nas a2200157 4500008004100000245006600041210006200107260001500169520119400184100001801378700001901396700001701415700001901432700001801451856003701469 2019 eng d00aThe Speed of Quantum Information Spreading in Chaotic Systems0 aSpeed of Quantum Information Spreading in Chaotic Systems c08/19/20193 a

We present a general theory of quantum information propagation in chaotic quantum many-body systems. The generic expectation in such systems is that quantum information does not propagate in localized form; instead, it tends to spread out and scramble into a form that is inaccessible to local measurements. To characterize this spreading, we define an information speed via a quench-type experiment and derive a general formula for it as a function of the entanglement density of the initial state. As the entanglement density varies from zero to one, the information speed varies from the entanglement speed to the butterfly speed. We verify that the formula holds both for a quantum chaotic spin chain and in field theories with an AdS/CFT gravity dual. For the second case, we study in detail the dynamics of entanglement in two-sided Vaidya-AdS-Reissner-Nordstrom black branes. We also show that, with an appropriate decoding process, quantum information can be construed as moving at the information speed, and, in the case of AdS/CFT, we show that a locally detectable signal propagates at the information speed in a spatially local variant of the traversable wormhole setup.

1 aCouch, Josiah1 aEccles, Stefan1 aNguyen, Phuc1 aSwingle, Brian1 aXu, Shenglong uhttps://arxiv.org/abs/1908.0699301408nas a2200133 4500008004100000245008000041210006900121260001500190520097500205100001901180700001901199700001901218856003701237 2019 eng d00aStatistical Privacy in Distributed Average Consensus on Bounded Real Inputs0 aStatistical Privacy in Distributed Average Consensus on Bounded  c03/20/20193 a

This paper proposes a privacy protocol for distributed average consensus algorithms on bounded real-valued inputs that guarantees statistical privacy of honest agents' inputs against colluding (passive adversarial) agents, if the set of colluding agents is not a vertex cut in the underlying communication network. This implies that privacy of agents' inputs is preserved against t number of arbitrary colluding agents if the connectivity of the communication network is at least (t+1). A similar privacy protocol has been proposed for the case of bounded integral inputs in our previous paper~\cite{gupta2018information}. However, many applications of distributed consensus concerning distributed control or state estimation deal with real-valued inputs. Thus, in this paper we propose an extension of the privacy protocol in~\cite{gupta2018information}, for bounded real-valued agents' inputs, where bounds are known apriori to all the agents. 

1 aGupta, Nirupam1 aKatz, Jonathan1 aChopra, Nikhil uhttps://arxiv.org/abs/1903.0931502754nas a2200229 4500008004100000245009900041210006900140520205300209100001902262700002402281700001302305700001502318700001302333700001702346700001402363700001602377700001602393700001702409700001902426700001602445856006302461 2019 eng d00aStatus Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process0 aStatus Report on the First Round of the NIST PostQuantum Cryptog3 a

The National Institute of Standards and Technology is in the process of selecting one or more
public-key cryptographic algorithms through a public competition-like process. The new publickey cryptography standards will specify one or more additional digital signature, public-key
encryption, and key-establishment algorithms to augment FIPS 186-4, Digital Signature Standard
(DSS), as well as special publications SP 800-56A Revision 2, Recommendation for Pair-Wise
Key Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800-56B,
Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization. It is
intended that these algorithms will be capable of protecting sensitive information well into the
foreseeable future, including after the advent of quantum computers.
In November 2017, 82 candidate algorithms were submitted to NIST for consideration. Among
these, 69 met both the minimum acceptance criteria and our submission requirements, and were
accepted as First-Round Candidates on Dec. 20, 2017, marking the beginning of the First Round
of the NIST Post-Quantum Cryptography Standardization Process. This report describes the
evaluation criteria and selection process, based on public feedback and internal review of the
first-round candidates, and summarizes the 26 candidate algorithms announced on January 30,
2019 for moving forward to the second round of the competition. The 17 Second-Round
Candidate public-key encryption and key-establishment algorithms are BIKE, Classic McEliece,
CRYSTALS-KYBER, FrodoKEM, HQC, LAC, LEDAcrypt (merger of LEDAkem/LEDApkc),
NewHope, NTRU (merger of NTRUEncrypt/NTRU-HRSS-KEM), NTRU Prime, NTS-KEM,
ROLLO (merger of LAKE/LOCKER/Ouroboros-R), Round5 (merger of Hila5/Round2), RQC,
SABER, SIKE, and Three Bears. The 9 Second-Round Candidates for digital signatures are
CRYSTALS-DILITHIUM, FALCON, GeMSS, LUOV, MQDSS, Picnic, qTESLA, Rainbow,
and SPHINCS+.

1 aAlagic, Gorjan1 aAlperin-Sheriff, J.1 aApon, D.1 aCooper, D.1 aDang, Q.1 aMiller, Carl1 aMoody, D.1 aPeralta, R.1 aPerlner, R.1 aRobinson, A.1 aSmith-Tone, D.1 aLiu, Yi-Kai uhttps://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8240.pdf01473nas a2200157 4500008004100000245008200041210006900123260001500192300001400207490000700221520099100228100001701219700002701236700001501263856003701278 2019 eng d00aSublinear quantum algorithms for training linear and kernel-based classifiers0 aSublinear quantum algorithms for training linear and kernelbased c04/03/2019 a3815-38240 v973 a

We investigate quantum algorithms for classification, a fundamental problem in machine learning, with provable guarantees. Given n d-dimensional data points, the state-of-the-art (and optimal) classical algorithm for training classifiers with constant margin runs in O~(n+d) time. We design sublinear quantum algorithms for the same task running in O~(n−−√+d−−√) time, a quadratic improvement in both n and d. Moreover, our algorithms use the standard quantization of the classical input and generate the same classical output, suggesting minimal overheads when used as subroutines for end-to-end applications. We also demonstrate a tight lower bound (up to poly-log factors) and discuss the possibility of implementation on near-term quantum machines. As a side result, we also give sublinear quantum algorithms for approximating the equilibria of n-dimensional matrix zero-sum games with optimal complexity Θ~(n−−√). 

1 aLi, Tongyang1 aChakrabarti, Shouvanik1 aWu, Xiaodi uhttps://arxiv.org/abs/1904.0227601302nas a2200121 4500008004100000245008600041210006900127520089100196100001901087700001801106700001901124856003701143 2018 eng d00aScrambling dynamics across a thermalization-localization quantum phase transition0 aScrambling dynamics across a thermalizationlocalization quantum 3 a

We study quantum information scrambling, specifically the growth of Heisenberg operators, in large disordered spin chains using matrix product operator dynamics to scan across the thermalization-localization quantum phase transition. We observe ballistic operator growth for weak disorder, and a sharp transition to a phase with sub-ballistic operator spreading. The critical disorder strength for the ballistic to sub-ballistic transition is well below the many body localization phase transition, as determined from finite size scaling of energy eigenstate entanglement entropy in small chains. In contrast, we find that the operator dynamics is not very sensitive to the actual eigenstate localization transition. These data are discussed in the context of a universal form for the growing operator shape and substantiated with a simple phenomenological model of rare regions.

1 aSahu, Subhayan1 aXu, Shenglong1 aSwingle, Brian uhttps://arxiv.org/abs/1807.0608601174nas a2200109 4500008004100000245007300041210006900114520080600183100001900989700001901008856003701027 2018 eng d00aA semiclassical theory of phase-space dynamics of interacting bosons0 asemiclassical theory of phasespace dynamics of interacting boson3 a

We study the phase-space representation of dynamics of bosons in the semiclassical regime where the occupation number of the modes is large. To this end, we employ the van Vleck-Gutzwiller propagator to obtain an approximation for the Green's function of the Wigner distribution. The semiclassical analysis incorporates interference of classical paths and reduces to the truncated Wigner approximation (TWA) when the interference is ignored. Furthermore, we identify the Ehrenfest time after which the TWA fails. As a case study, we consider a single-mode quantum nonlinear oscillator, which displays collapse and revival of observables. We analytically show that the interference of classical paths leads to revivals, an effect that is not reproduced by the TWA or a perturbative analysis.

1 aMathew, Ranchu1 aTiesinga, Eite uhttps://arxiv.org/abs/1803.0512201238nas a2200157 4500008004100000245005100041210005000092520077600142100001600918700002100934700002200955700001800977700002300995700002501018856003701043 2018 eng d00aSingle-photon bound states in atomic ensembles0 aSinglephoton bound states in atomic ensembles3 a

We illustrate the existence of single-excitation bound states for propagating photons interacting with N two-level atoms. These bound states can be calculated from an effective spin model, and their existence relies on dissipation in the system. The appearance of these bound states is in a one-to-one correspondence with zeros in the single-photon transmission and with divergent bunching in the second-order photon-photon correlation function. We also formulate a dissipative version of Levinson's theorem for this system by looking at the relation between the number of bound states and the winding number of the transmission phases. This theorem allows a direct experimental measurement of the number of bound states using the measured transmission phases.

1 aWang, Yidan1 aGullans, Michael1 aBrowaeys, Antoine1 aPorto, J., V.1 aChang, Darrick, E.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1809.0114701204nas a2200181 4500008004100000245007100041210006900112260001500181490000800196520064500204100002700849700001900876700001900895700002700914700002000941700002500961856003600986 2018 eng d00aSpectrum estimation of density operators with alkaline-earth atoms0 aSpectrum estimation of density operators with alkalineearth atom c2018/01/090 v1203 a

We show that Ramsey spectroscopy of fermionic alkaline-earth atoms in a square-well trap provides an efficient and accurate estimate for the eigenspectrum of a density matrix whose n copies are stored in the nuclear spins of n such atoms. This spectrum estimation is enabled by the high symmetry of the interaction Hamiltonian, dictated, in turn, by the decoupling of the nuclear spin from the electrons and by the shape of the square-well trap. Practical performance of this procedure and its potential applications to quantum computing, quantum simulation, and time-keeping with alkalineearth atoms are discussed.

1 aBeverland, Michael, E.1 aHaah, Jeongwan1 aAlagic, Gorjan1 aCampbell, Gretchen, K.1 aRey, Ana, Maria1 aGorshkov, Alexey, V. uhttp://arxiv.org/abs/1608.0204502029nas a2200205 4500008004100000245009100041210006900132490000900201520141200210100001901622700002001641700001801661700001701679700002001696700002001716700001601736700001701752700001701769856003701786 2018 eng d00aA spinor Bose-Einstein condensate phase-sensitive amplifier for SU(1,1) interferometry0 aspinor BoseEinstein condensate phasesensitive amplifier for SU110 vA 983 a

The SU(1,1) interferometer was originally conceived as a Mach-Zehnder interferometer with the beam-splitters replaced by parametric amplifiers. The parametric amplifiers produce states with correlations that result in enhanced phase sensitivity. F=1 spinor Bose-Einstein condensates (BECs) can serve as the parametric amplifiers for an atomic version of such an interferometer by collisionally producing entangled pairs of ⟨F=1,m=±1| atoms. We simulate the effect of single and double-sided seeding of the inputs to the amplifier using the truncated-Wigner approximation. We find that single-sided seeding degrades the performance of the interferometer exactly at the phase the unseeded interferometer should operate the best. Double-sided seeding results in a phase-sensitive amplifier, where the maximal sensitivity is a function of the phase relationship between the input states of the amplifier. In both single and double-sided seeding we find there exists an optimal phase shift that achieves sensitivity beyond the standard quantum limit. Experimentally, we demonstrate a spinor phase-sensitive amplifier using a BEC of 23Na in an optical dipole trap. This configuration could be used as an input to such an interferometer. We are able to control the initial phase of the double-seeded amplifier, and demonstrate sensitivity to initial population fractions as small as 0.1\%. 

1 aWrubel, J., P.1 aSchwettmann, A.1 aFahey, D., P.1 aGlassman, Z.1 aPechkis, H., K.1 aGriffin, P., F.1 aBarnett, R.1 aTiesinga, E.1 aLett, P., D. uhttps://arxiv.org/abs/1807.0667601897nas a2200109 4500008004100000245010200041210006900143520150500212100001701717700001601734856003701750 2018 eng d00aStationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits0 aStationary Phase Method in Discrete Wigner Functions and Classic3 a

We apply the periodized stationary phase method to discrete Wigner functions of systems with odd prime dimension using results from p-adic number theory. We derive the Wigner-Weyl-Moyal (WWM) formalism with higher order ℏ corrections representing contextual corrections to non-contextual Clifford operations. We apply this formalism to a subset of unitaries that include diagonal gates such as the π8 gates. We characterize the stationary phase critical points as a quantum resource injecting contextuality and show that this resource allows for the replacement of the p2t points that represent t magic state Wigner functions on p-dimensional qudits by ≤pt points. We find that the π8 gate introduces the smallest higher order ℏ correction possible, requiring the lowest number of additional critical points compared to the Clifford gates. We then establish a relationship between the stabilizer rank of states and the number of critical points necessary to treat them in the WWM formalism. This allows us to exploit the stabilizer rank decomposition of two qutrit π8 gates to develop a classical strong simulation of a single qutrit marginal on t qutrit π8 gates that are followed by Clifford evolution, and show that this only requires calculating 3t2+1 critical points corresponding to Gauss sums. This outperforms the best alternative qutrit algorithm (based on Wigner negativity and scaling as ∼30.8t for 10−2 precision) for any number of π8 gates to full precision.

1 aKocia, Lucas1 aLove, Peter uhttps://arxiv.org/abs/1810.0362201396nas a2200157 4500008004100000245006600041210006600107260001500173300001100188490000600199520092600205100002601131700001901157700002501176856003701201 2018 eng d00aStructure of Correlated Worldline Theories of Quantum Gravity0 aStructure of Correlated Worldline Theories of Quantum Gravity c2018/06/21 a0840520 vD3 a

We consider the general form of "Correlated Worldline" (CWL) theories of quantum gravity. We show that one can have 2 different kinds of CWL theory, in which the generating functional is written as either a sum or a product over multiple copies of the coupled matter and gravitational fields. In both versions, the paths in a functional formulation are correlated via gravity itself, causing a breakdown of the superposition principle; however, the product form survives consistency tests not satisfied by the summed form. To better understand the structure of these two theories, we show how to perform diagrammatic expansions in the gravitational coupling for each version of CWL theory, using particle propagation and scalar fields as examples. We explicitly calculate contributions to 2-point and 4-point functions, again for each version of the theory, up to 2nd-order in the gravitational coupling.

1 aBarvinsky, Andrei, O.1 aCarney, Daniel1 aStamp, Philip, C. E. uhttps://arxiv.org/abs/1806.0804310586nas a2200301 4500008004100000245007200041210006900113520978200182100001609964700001609980700001909996700001810015700001610033700002210049700001510071700001310086700001210099700001610111700001210127700001410139700001510153700001710168700001610185700001610201700001310217700001710230856003710247 2018 eng d00aStudy of radon reduction in gases for rare event search experiments0 aStudy of radon reduction in gases for rare event search experime3 a

The noble elements, argon and xenon, are frequently employed as the target and event detector for weakly interacting particles such as neutrinos and Dark Matter. For such rare processes, background radiation must be carefully minimized. Radon provides one of the most significant contaminants since it is an inevitable product of trace amounts of natural uranium. To design a purification system for reducing such contamination, the adsorption characteristics of radon in nitrogen, argon, and xenon carrier gases on various types of charcoals with different adsorbing properties and intrinsic radioactive purities have been studied in the temperature range of 190-295 K at flow rates of 0.5 and 2 standard liters per minute. Essential performance parameters for the various charcoals include the average breakthrough times (τ), dynamic adsorption coefficients (ka) and the number of theoretical stages (n). It is shown that the ka-values for radon in nitrogen, argon, and xenon increase as the temperature of the charcoal traps decreases, and that they are significantly larger in nitrogen and argon than in xenon gas due to adsorption saturation effects. It is found that, unlike in xenon, the dynamic adsorption coefficients for radon in nitrogen and argon strictly obey the Arrhenius law. The experimental results strongly indicate that nitric acid etched Saratech is the best candidate among all used charcoal brands. It allows reducing total radon concentration in the LZ liquid Xe detector to meet the ultimate goal in the search for Dark Matter.

1 aPushkin, K.1 aAkerlof, C.1 aAnbajagane, D.1 aArmstrong, J.1 aArthurs, M.1 aBringewatt, Jacob1 aEdberg, T.1 aHall, C.1 aLei, M.1 aRaymond, R.1 aReh, M.1 aSaini, D.1 aSander, A.1 aSchaefer, J.1 aSeymour, D.1 aSwanson, N.1 aWang, Y.1 aLorenzon, W. uhttps://arxiv.org/abs/1805.1130601846nas a2200169 4500008004100000245006600041210006500107520131000172100001701482700001801499700002801517700002501545700002201570700002301592700002401615856003701639 2018 eng d00aStudying community development: a network analytical approach0 aStudying community development a network analytical approach3 a

Research shows that community plays a central role in learning, and strong community engages students and aids in student persistence. Thus, understanding the function and structure of communities in learning environments is essential to education. We use social network analysis to explore the community dynamics of students in a pre-matriculation, two-week summer program. Unlike previous network analysis studies in PER, we build our networks from classroom video that has been coded for student interactions using labeled, directed ties. We define 3 types of interaction: on task interactions (regarding the assigned task), on topic interactions (having to do with science, technology, engineering, and mathematics (STEM)), and off topic interactions (unrelated to the assignment or STEM). To study the development of community in this program, we analyze the shift in conversation topicality over the course of the program. Conversations are more on-task toward the end of the program and we propose that this conversational shift represents a change in student membership within their forming community. 

1 aHass, C., A.1 aGenz, Florian1 aKustusch, Mary, Bridget1 aOuime, Pierre-P., A.1 aPomian, Katarzyna1 aSayre, Eleanor, C.1 aZwolak, Justyna, P. uhttps://arxiv.org/abs/1808.0819301318nas a2200121 4500008004100000245004000041210004000081520097600121100002101097700002201118700001901140856003701159 2018 eng d00aSubsystem Complexity and Holography0 aSubsystem Complexity and Holography3 a

We study circuit complexity for spatial regions in holographic field theories. We study analogues based on the entanglement wedge of the bulk quantities appearing in the "complexity = volume" and "complexity = action" conjectures. We calculate these quantities for one exterior region of an eternal static neutral or charged black hole in general dimensions, dual to a thermal state on one boundary with or without chemical potential respectively, as well as for a shock wave geometry. We then define several analogues of circuit complexity for mixed states, and use tensor networks to gain intuition about them. We find a promising qualitative match between the holographic action and what we call the purification complexity, the minimum number of gates required to prepare an arbitrary purification of the given mixed state. On the other hand, the holographic volume does not appear to match any of our definitions of mixed-state complexity.

1 aAgón, Cesar, A.1 aHeadrick, Matthew1 aSwingle, Brian uhttps://arxiv.org/abs/1804.0156102412nas a2200145 4500008004100000245006200041210006100103260001500164300001400179520194800193100002102141700002402162700002202186856005802208 2017 eng d00aSequential measurements, disturbance and property testing0 aSequential measurements disturbance and property testing c2017/01/01 a1598-16113 a

We describe two procedures which, given access to one copy of a quantum state and a sequence of two-outcome measurements, can distinguish between the case that at least one of the measurements accepts the state with high probability, and the case that all of the measurements have low probability of acceptance. The measurements cannot simply be tried in sequence, because early measurements may disturb the state being tested. One procedure is based on a variant of Marriott-Watrous amplification. The other procedure is based on the use of a test for this disturbance, which is applied with low probability. We find a number of applications. First, quantum query complexity separations in the property testing model for testing isomorphism of functions under group actions. We give quantum algorithms for testing isomorphism, linear isomorphism and affine isomorphism of boolean functions which use exponentially fewer queries than is possible classically, and a quantum algorithm for testing graph isomorphism which uses polynomially fewer queries than the best algorithm known. Second, testing properties of quantum states and operations. We show that any finite property of quantum states can be tested using a number of copies of the state which is logarithmic in the size of the property, and give a test for genuine multipartite entanglement of states of n qubits that uses O(n) copies of the state. Third, correcting an error in a result of Aaronson on de-Merlinizing quantum protocols. This result claimed that, in any one-way quantum communication protocol where two parties are assisted by an all-powerful but untrusted third party, the third party can be removed with only a modest increase in the communication cost. We give a corrected proof of a key technical lemma required for Aaronson's result.

1 aHarrow, Aram, W.1 aLin, Cedric, Yen-Yu1 aMontanaro, Ashley uhttp://epubs.siam.org/doi/10.1137/1.9781611974782.10501977nas a2200121 4500008004100000245009300041210006900134260001500203520155900218100001901777700002201796856003701818 2017 eng d00aShorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations0 aShorter stabilizer circuits via Bruhat decomposition and quantum c2017/05/253 a

In this paper we improve the layered implementation of arbitrary stabilizer circuits introduced by Aaronson and Gottesman in Phys. Rev. A 70(052328), 2004: to implement a general stabilizer circuit, we reduce their 11-stage computation -HC-P-C-P-C-H-P-C-P-C- over the gate set consisting of Hadamard, Controlled-NOT, and Phase gates, into a 7-stage computation of the form -C-CZ-P-H-P-CZ-C-. We show arguments in support of using -CZ- stages over the -C- stages: not only the use of -CZ- stages allows a shorter layered expression, but -CZ- stages are simpler and appear to be easier to implement compared to the -C- stages. Based on this decomposition, we develop a twoqubit gate depth-(14n−4) implementation of stabilizer circuits over the gate library {H, P, CNOT}, executable in the LNN architecture, improving best previously known depth-25n circuit, also executable in the LNN architecture. Our constructions rely on Bruhat decomposition of the symplectic group and on folding arbitrarily long sequences of the form (-P-C-) m into a 3-stage computation -P-CZ-C-. Our results include the reduction of the 11-stage decomposition -H-C-P-C-P-C-H-P-C-P-C- into a 9-stage decomposition of the form -C-P-C-P-H-C-P-C-P-. This reduction is based on the Bruhat decomposition of the symplectic group. This result also implies a new normal form for stabilizer circuits. We show that a circuit in this normal form is optimal in the number of Hadamard gates used. We also show that the normal form has an asymptotically optimal number of parameters.

1 aMaslov, Dmitri1 aRoetteler, Martin uhttps://arxiv.org/abs/1705.0917602019nas a2200217 4500008004100000245006500041210006300106260001500169300001100184490000600195520137300201100001601574700002501590700002101615700002701636700002601663700001801689700001601707700002301723856005501746 2017 eng d00aSimultaneous, Full Characterization of a Single-Photon State0 aSimultaneous Full Characterization of a SinglePhoton State c2017/11/15 a0410360 v73 a

As single-photon sources become more mature and are used more often in quantum information, communications, and measurement applications, their characterization becomes more important. Singlephoton-like light is often characterized by its brightness, as well as two quantum properties: the suppression of multiphoton content and the photon indistinguishability. While it is desirable to obtain these quantities from a single measurement, currently two or more measurements are required. Here, we show that using two-photon (n ¼ 2) number-resolving detectors, one can completely characterize single-photon-like states in a single measurement, where previously two or more measurements were necessary. We simultaneously determine the brightness, the suppression of multiphoton states, the indistinguishability, and the statistical distribution of Fock states to third order for a quantum light source. We find n ≥ 3 number-resolving detectors provide no additional advantage in the single-photon characterization. The new method extracts more information per experimental trial than a conventional measurement for all input states and is particularly more efficient for statistical mixtures of photon states. Thus, using this n ¼ 2, number-resolving detector scheme will provide advantages in a variety of quantum optics measurements and systems.

1 aThomay, Tim1 aPolyakov, Sergey, V.1 aGazzano, Olivier1 aGoldschmidt, Elizabeth1 aEldredge, Zachary, D.1 aHuber, Tobias1 aLoo, Vivien1 aSolomon, Glenn, S. uhttps://link.aps.org/doi/10.1103/PhysRevX.7.04103601534nas a2200169 4500008004100000245006200041210005800103260001500161490000800176520102300184100002301207700002201230700002301252700002501275700002701300856003701327 2017 eng d00aA solvable family of driven-dissipative many-body systems0 asolvable family of drivendissipative manybody systems c2017/11/100 v1193 a

Exactly solvable models have played an important role in establishing the sophisticated modern understanding of equilibrium many-body physics. And conversely, the relative scarcity of solutions for non-equilibrium models greatly limits our understanding of systems away from thermal equilibrium. We study a family of nonequilibrium models, some of which can be viewed as dissipative analogues of the transverse-field Ising model, in that an effectively classical Hamiltonian is frustrated by dissipative processes that drive the system toward states that do not commute with the Hamiltonian. Surprisingly, a broad and experimentally relevant subset of these models can be solved efficiently in any number of spatial dimensions. We leverage these solutions to prove a no-go theorem on steady-state phase transitions in a many-body model that can be realized naturally with Rydberg atoms or trapped ions, and to compute the effects of decoherence on a canonical trapped-ion-based quantum computation architecture.

1 aFoss-Feig, Michael1 aYoung, Jeremy, T.1 aAlbert, Victor, V.1 aGorshkov, Alexey, V.1 aMaghrebi, Mohammad, F. uhttps://arxiv.org/abs/1703.0462603676nas 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.0901401811nas a2200145 4500008004100000245009400041210006900135260001500204520133900219100001901558700001601577700001601593700001901609856003701628 2017 eng d00aSuper-polynomial and exponential improvements for quantum-enhanced reinforcement learning0 aSuperpolynomial and exponential improvements for quantumenhanced c2017/12/123 a

Recent work on quantum machine learning has demonstrated that quantum computers can offer dramatic improvements over classical devices for data mining, prediction and classification. However, less is known about the advantages using quantum computers may bring in the more general setting of reinforcement learning, where learning is achieved via interaction with a task environment that provides occasional rewards. Reinforcement learning can incorporate data-analysis-oriented learning settings as special cases, but also includes more complex situations where, e.g., reinforcing feedback is delayed. In a few recent works, Grover-type amplification has been utilized to construct quantum agents that achieve up-to-quadratic improvements in learning efficiency. These encouraging results have left open the key question of whether super-polynomial improvements in learning times are possible for genuine reinforcement learning problems, that is problems that go beyond the other more restricted learning paradigms. In this work, we provide a family of such genuine reinforcement learning tasks. We construct quantum-enhanced learners which learn super-polynomially, and even exponentially faster than any classical reinforcement learning model, and we discuss the potential impact our results may have on future technologies.

1 aDunjko, Vedran1 aLiu, Yi-Kai1 aWu, Xingyao1 aTaylor, J., M. uhttps://arxiv.org/abs/1710.1116001444nas a2200169 4500008004100000245006100041210006000102260001500162300001100177490000700188520092700195100002201122700001801144700001901162700002501181856006801206 2016 eng d00aSelf-organization of atoms coupled to a chiral reservoir0 aSelforganization of atoms coupled to a chiral reservoir c2016/11/29 a0538550 v943 a

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

1 aEldredge, Zachary1 aSolano, Pablo1 aChang, Darrick1 aGorshkov, Alexey, V. uhttp://journals.aps.org/pra/abstract/10.1103/PhysRevA.94.05385501512nas a2200157 4500008004100000245008700041210006900128260001500197300001100212490000700223520099300230100002501223700001401248700001901262856007301281 2016 eng d00aSerialized Quantum Error Correction Protocol for High-Bandwidth Quantum Repeaters0 aSerialized Quantum Error Correction Protocol for HighBandwidth Q c2016/09/02 a0930080 v183 a

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

1 aGlaudell, Andrew, N.1 aWaks, Edo1 aTaylor, J., M. uhttp://iopscience.iop.org/article/10.1088/1367-2630/18/9/093008/meta01372nas a2200181 4500008004100000245007800041210006900119260001500188300001100203490000800214520084100222100002101063700001601084700001701100700001801117700001901135856003601154 2016 eng d00aSisyphus Thermalization of Photons in a Cavity-Coupled Double Quantum Dot0 aSisyphus Thermalization of Photons in a CavityCoupled Double Qua c2016/07/25 a0568010 v1173 a

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

1 aGullans, Michael1 aStehlik, J.1 aLiu, Y., -Y.1 aPetta, J., R.1 aTaylor, J., M. uhttp://arxiv.org/abs/1512.0124821161nas a2200205 45000080041000000200022000410220014000632450069000772100068001462600015002143000016002294900007002455202053400252100002020786700002420806700002420830700002220854700002520876856005420901 2016 eng d a978-3-95977-013-2 a1868-896900aSpace-Efficient Error Reduction for Unitary Quantum Computations0 aSpaceEfficient Error Reduction for Unitary Quantum Computations c2016/04/27 a14:1--14:140 v553 a

This paper develops general space-efficient methods for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness c and soundnesss, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most 2p, the most space-efficient method known requires extra workspace of O(plog1cs) qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper presents error-reduction methods for unitary quantum computations (i.e., computations without intermediate measurements) that require extra workspace of just O(logpcs) qubits. This in particular gives the first methods of strong amplification for logarithmic-space unitary quantum computations with two-sided bounded error. This also leads to a number of consequences in complexity theory, such as the uselessness of quantum witnesses in bounded-error logarithmic-space unitary quantum computations, the PSPACE upper bound for QMA with exponentially-small completeness-soundness gap, and strong amplification for matchgate computations.

1 aFefferman, Bill1 aKobayashi, Hirotada1 aLin, Cedric, Yen-Yu1 aMorimae, Tomoyuki1 aNishimura, Harumichi uhttp://drops.dagstuhl.de/opus/volltexte/2016/629709346nas a2200181 4500008004100000245005500041210005400096260001500150520881500165100001908980700001608999700002309015700002409038700002009062700002009082700002509102856003709127 2016 eng d00aSteady-state superradiance with Rydberg polaritons0 aSteadystate superradiance with Rydberg polaritons c2016/11/023 a

A steady-state superradiant laser can be used to generate ultranarrow-linewidth light, and thus has important applications in the fields of quantum information and precision metrology. However, the light produced by such a laser is still essentially classical. Here, we show that the introduction of a Rydberg medium into a cavity containing atoms with a narrow optical transition can lead to the steady-state superradiant emission of ultranarrow-linewidth nonclassical light. The cavity nonlinearity induced by the Rydberg medium strongly modifies the superradiance threshold, and leads to a Mollow triplet in the cavity output spectrumthis behavior can be understood as an unusual analogue of resonance fluorescence. The cavity output spectrum has an extremely sharp central peak, with a linewidth that can be far narrower than that of a classical superradiant laser. This unprecedented spectral sharpness, together with the nonclassical nature of the light, could lead to new applications in which spectrally pure quantum light is desired.

1 aGong, Zhe-Xuan1 aXu, Minghui1 aFoss-Feig, Michael1 aThompson, James, K.1 aRey, Ana, Maria1 aHolland, Murray1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1611.0079701465nas 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 a2200157 4500008004100000245008800041210006900129260001500198300001100213490000700224520127000231100001801501700001501519700001901534856003601553 2016 eng d00aSudden-quench dynamics of Bardeen-Cooper-Schrieffer states in deep optical lattices0 aSuddenquench dynamics of BardeenCooperSchrieffer states in deep  c2016/08/05 a0236070 v943 a

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

1 aNuske, Marlon1 aMathey, L.1 aTiesinga, Eite uhttp://arxiv.org/abs/1602.0097901945nas 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.09149v201150nas a2200193 4500008004100000245004800041210004800089260001500137300001400152490000800166520063700174100001700811700001600828700001600844700002100860700001900881700001800900856003800918 2015 eng d00aSemiconductor double quantum dot micromaser0 aSemiconductor double quantum dot micromaser c2015/01/15 a285 - 2870 v3473 a The coherent generation of light, from masers to lasers, relies upon the specific structure of the individual emitters that lead to gain. Devices operating as lasers in the few-emitter limit provide opportunities for understanding quantum coherent phenomena, from THz sources to quantum communication. Here we demonstrate a maser that is driven by single electron tunneling events. Semiconductor double quantum dots (DQDs) serve as a gain medium and are placed inside of a high quality factor microwave cavity. We verify maser action by comparing the statistics of the emitted microwave field above and below the maser threshold. 1 aLiu, Y., -Y.1 aStehlik, J.1 aEichler, C.1 aGullans, Michael1 aTaylor, J., M.1 aPetta, J., R. uhttp://arxiv.org/abs/1507.06359v101120nas a2200181 4500008004100000245006700041210006700108260001500175300001100190490000800201520058500209100002300794700002300817700001900840700001900859700002300878856003700901 2015 eng d00aSimulating Hamiltonian dynamics with a truncated Taylor series0 aSimulating Hamiltonian dynamics with a truncated Taylor series c2015/03/03 a0905020 v1143 a We describe a simple, efficient method for simulating Hamiltonian dynamics on a quantum computer by approximating the truncated Taylor series of the evolution operator. Our method can simulate the time evolution of a wide variety of physical systems. As in another recent algorithm, the cost of our method depends only logarithmically on the inverse of the desired precision, which is optimal. However, we simplify the algorithm and its analysis by using a method for implementing linear combinations of unitary operations to directly apply the truncated Taylor series. 1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aCleve, Richard1 aKothari, Robin1 aSomma, Rolando, D. uhttp://arxiv.org/abs/1412.4687v101278nas a2200205 4500008004100000245009000041210006900131260001400200490000700214520065300221100001600874700001300890700002000903700002700923700002100950700001800971700002500989700002101014856003701035 2014 eng d00aScattering resonances and bound states for strongly interacting Rydberg polaritons 0 aScattering resonances and bound states for strongly interacting  c2014/11/30 v903 a We provide a theoretical framework describing slow-light polaritons interacting via atomic Rydberg states. We use a diagrammatic method to analytically derive the scattering properties of two polaritons. We identify parameter regimes where polariton-polariton interactions are repulsive. Furthermore, in the regime of attractive interactions, we identify multiple two-polariton bound states, calculate their dispersion, and study the resulting scattering resonances. Finally, the two-particle scattering properties allow us to derive the effective low-energy many-body Hamiltonian. This theoretical platform is applicable to ongoing experiments. 1 aBienias, P.1 aChoi, S.1 aFirstenberg, O.1 aMaghrebi, Mohammad, F.1 aGullans, Michael1 aLukin, M., D.1 aGorshkov, Alexey, V.1 aBüchler, H., P. uhttp://arxiv.org/abs/1402.7333v101619nas a2200133 4500008004100000245007600041210006900117260001500186300001000201490001200211520120900223100001601432856003701448 2014 eng d00aSingle-shot security for one-time memories in the isolated qubits model0 aSingleshot security for onetime memories in the isolated qubits  c2014/02/01 a19-360 vPart II3 a One-time memories (OTM's) are simple, tamper-resistant cryptographic devices, which can be used to implement sophisticated functionalities such as one-time programs. Can one construct OTM's whose security follows from some physical principle? This is not possible in a fully-classical world, or in a fully-quantum world, but there is evidence that OTM's can be built using "isolated qubits" -- qubits that cannot be entangled, but can be accessed using adaptive sequences of single-qubit measurements. Here we present new constructions for OTM's using isolated qubits, which improve on previous work in several respects: they achieve a stronger "single-shot" security guarantee, which is stated in terms of the (smoothed) min-entropy; they are proven secure against adversaries who can perform arbitrary local operations and classical communication (LOCC); and they are efficiently implementable. These results use Wiesner's idea of conjugate coding, combined with error-correcting codes that approach the capacity of the q-ary symmetric channel, and a high-order entropic uncertainty relation, which was originally developed for cryptography in the bounded quantum storage model. 1 aLiu, Yi-Kai uhttp://arxiv.org/abs/1402.0049v201146nas a2200133 4500008004100000245007200041210006900113260001400182490000700196520073500203100002300938700001400961856003700975 2014 eng d00aSpatial search by continuous-time quantum walks on crystal lattices0 aSpatial search by continuoustime quantum walks on crystal lattic c2014/5/300 v893 a We consider the problem of searching a general $d$-dimensional lattice of $N$ vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behaviour near a Dirac point, we develop algorithms that solve the problem in a time of $O(\sqrt N)$ for $d>2$ and $O(\sqrt N \log N)$ in $d=2$. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory. 1 aChilds, Andrew, M.1 aGe, Yimin uhttp://arxiv.org/abs/1403.2676v201304nas 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.3530v201136nas a2200145 4500008004100000245005800041210005600099260001300155490000700168520070900175100002700884700002300911700001900934856003700953 2013 eng d00aA Scattering Approach to the Dynamical Casimir Effect0 aScattering Approach to the Dynamical Casimir Effect c2013/1/70 v873 a We develop a unified scattering approach to dynamical Casimir problems which can be applied to both accelerating boundaries, as well as dispersive objects in relative motion. A general (trace) formula is derived for the radiation from accelerating boundaries. Applications are provided for objects with different shapes in various dimensions, and undergoing rotational or linear motion. Within this framework, photon generation is discussed in the context of a modulated optical mirror. For dispersive objects, we find general results solely in terms of the scattering matrix. Specifically, we discuss the vacuum friction on a rotating object, and the friction on an atom moving parallel to a surface. 1 aMaghrebi, Mohammad, F.1 aGolestanian, Ramin1 aKardar, Mehran uhttp://arxiv.org/abs/1210.1842v201244nas a2200241 4500008004100000245008400041210006900125260001300194300001400207490000600221520055700227100001600784700001300800700001900813700002100832700002000853700001900873700002300892700001100915700002000926700001900946856003700965 2013 eng d00aSelf-Consistent Measurement and State Tomography of an Exchange-Only Spin Qubit0 aSelfConsistent Measurement and State Tomography of an ExchangeOn c2013/9/1 a654 - 6590 v83 aWe report initialization, complete electrical control, and single-shot readout of an exchange-only spin qubit. Full control via the exchange interaction is fast, yielding a demonstrated 75 qubit rotations in under 2 ns. Measurement and state tomography are performed using a maximum-likelihood estimator method, allowing decoherence, leakage out of the qubit state space, and measurement fidelity to be quantified. The methods developed here are generally applicable to systems with state leakage, noisy measurements, and non-orthogonal control axes. 1 aMedford, J.1 aBeil, J.1 aTaylor, J., M.1 aBartlett, S., D.1 aDoherty, A., C.1 aRashba, E., I.1 aDiVincenzo, D., P.1 aLu, H.1 aGossard, A., C.1 aMarcus, C., M. uhttp://arxiv.org/abs/1302.1933v101034nas a2200169 4500008004100000245005800041210005700099260001500156490000800171520053900179100002100718700001800739700002300757700002900780700001800809856003700827 2013 eng d00aSingle-photon nonlinear optics with graphene plasmons0 aSinglephoton nonlinear optics with graphene plasmons c2013/12/110 v1113 a We show that it is possible to realize significant nonlinear optical interactions at the few photon level in graphene nanostructures. Our approach takes advantage of the electric field enhancement associated with the strong confinement of graphene plasmons and the large intrinsic nonlinearity of graphene. Such a system could provide a powerful platform for quantum nonlinear optical control of light. As an example, we consider an integrated optical device that exploits this large nonlinearity to realize a single photon switch. 1 aGullans, Michael1 aChang, D., E.1 aKoppens, F., H. L.1 ade Abajo, F., J. García1 aLukin, M., D. uhttp://arxiv.org/abs/1309.2651v301731nas a2200145 4500008004100000245007000041210006900111260001300180490000700193520128300200100002401483700002201507700001901529856003701548 2013 eng d00aSoliton dynamics of an atomic spinor condensate on a Ring Lattice0 aSoliton dynamics of an atomic spinor condensate on a Ring Lattic c2013/3/60 v873 a We study the dynamics of macroscopically-coherent matter waves of an ultra-cold atomic spin-one or spinor condensate on a ring lattice of six sites and demonstrate a novel type of spatio-temporal internal Josephson effect. Using a discrete solitary mode of uncoupled spin components as an initial condition, the time evolution of this many-body system is found to be characterized by two dominant frequencies leading to quasiperiodic dynamics at various sites. The dynamics of spatially-averaged and spin-averaged degrees of freedom, however, is periodic enabling an unique identification of the two frequencies. By increasing the spin-dependent atom-atom interaction strength we observe a resonance state, where the ratio of the two frequencies is a characteristic integer multiple and the spin-and-spatial degrees of freedom oscillate in "unison". Crucially, this resonant state is found to signal the onset to chaotic dynamics characterized by a broad band spectrum. In a ferromagnetic spinor condensate with attractive spin-dependent interactions, the resonance is accompanied by a transition from oscillatory- to rotational-type dynamics as the time evolution of the relative phase of the matter wave of the individual spin projections changes from bounded to unbounded. 1 aSatija, Indubala, I1 aPando, Carlos, L.1 aTiesinga, Eite uhttp://arxiv.org/abs/1301.5851v101428nas a2200193 4500008004100000245006800041210006700109260001300176490000800189520085100197100002401048700002501072700002201097700002201119700001801141700001901159700001901178856003701197 2013 eng d00aSpinor dynamics in an antiferromagnetic spin-1 thermal Bose gas0 aSpinor dynamics in an antiferromagnetic spin1 thermal Bose gas c2013/7/90 v1113 a We present experimental observations of coherent spin-population oscillations in a cold thermal, Bose gas of spin-1 sodium-23 atoms. The population oscillations in a multi-spatial-mode thermal gas have the same behavior as those observed in a single-spatial-mode antiferromagnetic spinor Bose Einstein condensate. We demonstrate this by showing that the two situations are described by the same dynamical equations, with a factor of two change in the spin-dependent interaction coefficient, which results from the change to particles with distinguishable momentum states in the thermal gas. We compare this theory to the measured spin population evolution after times up to a few hundreds of ms, finding quantitative agreement with the amplitude and period. We also measure the damping time of the oscillations as a function of magnetic field. 1 aPechkis, Hyewon, K.1 aWrubel, Jonathan, P.1 aSchwettmann, Arne1 aGriffin, Paul, F.1 aBarnett, Ryan1 aTiesinga, Eite1 aLett, Paul, D. uhttp://arxiv.org/abs/1306.4255v101999nas 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.7020v201927nas 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.2864v101472nas a2200217 4500008004100000245004000041210003900081260001500120300001100135490000800146520090500154100001701059700001901076700001801095700001701113700001601130700001601146700001601162700001701178856005901195 2012 eng d00aSpace-Time Crystals of Trapped Ions0 aSpaceTime Crystals of Trapped Ions c2012/10/19 a1630010 v1093 aSpontaneous symmetry breaking can lead to the formation of time crystals, as well as spatial crystals. Here we propose a space-time crystal of trapped ions and a method to realize it experimentally by confining ions in a ring-shaped trapping potential with a static magnetic field. The ions spontaneously form a spatial ring crystal due to Coulomb repulsion. This ion crystal can rotate persistently at the lowest quantum energy state in magnetic fields with fractional fluxes. The persistent rotation of trapped ions produces the temporal order, leading to the formation of a space-time crystal. We show that these space-time crystals are robust for direct experimental observation. We also study the effects of finite temperatures on the persistent rotation. The proposed space-time crystals of trapped ions provide a new dimension for exploring many-body physics and emerging properties of matter.1 aLi, Tongcang1 aGong, Zhe-Xuan1 aYin, Zhang-Qi1 aQuan, H., T.1 aYin, Xiaobo1 aZhang, Peng1 aDuan, L.-M.1 aZhang, Xiang uhttp://link.aps.org/doi/10.1103/PhysRevLett.109.16300101932nas a2200169 4500008004100000245005700041210005500098260001500153300001200168520144400180100002701624700002101651700001601672700002101688700001601709856003701725 2012 eng d00aA Spectral Algorithm for Latent Dirichlet Allocation0 aSpectral Algorithm for Latent Dirichlet Allocation c2012/04/30 a193-2143 a The problem of topic modeling can be seen as a generalization of the clustering problem, in that it posits that observations are generated due to multiple latent factors (e.g., the words in each document are generated as a mixture of several active topics, as opposed to just one). This increased representational power comes at the cost of a more challenging unsupervised learning problem of estimating the topic probability vectors (the distributions over words for each topic), when only the words are observed and the corresponding topics are hidden. We provide a simple and efficient learning procedure that is guaranteed to recover the parameters for a wide class of mixture models, including the popular latent Dirichlet allocation (LDA) model. For LDA, the procedure correctly recovers both the topic probability vectors and the prior over the topics, using only trigram statistics (i.e., third order moments, which may be estimated with documents containing just three words). The method, termed Excess Correlation Analysis (ECA), is based on a spectral decomposition of low order moments (third and fourth order) via two singular value decompositions (SVDs). Moreover, the algorithm is scalable since the SVD operations are carried out on $k\times k$ matrices, where $k$ is the number of latent factors (e.g. the number of topics), rather than in the $d$-dimensional observed space (typically $d \gg k$). 1 aAnandkumar, Animashree1 aFoster, Dean, P.1 aHsu, Daniel1 aKakade, Sham, M.1 aLiu, Yi-Kai uhttp://arxiv.org/abs/1204.6703v400969nas 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.1485v201233nas a2200157 4500008004100000245006500041210006300106260001400169490000800183520075800191100002300949700002200972700002400994700002001018856003701038 2012 eng d00aSteady-state many-body entanglement of hot reactive fermions0 aSteadystate manybody entanglement of hot reactive fermions c2012/12/40 v1093 a Entanglement is typically created via systematic intervention in the time evolution of an initially unentangled state, which can be achieved by coherent control, carefully tailored non-demolition measurements, or dissipation in the presence of properly engineered reservoirs. In this paper we show that two-component Fermi gases at ~\mu K temperatures naturally evolve, in the presence of reactive two-body collisions, into states with highly entangled (Dicke-type) spin wavefunctions. The entanglement is a steady-state property that emerges---without any intervention---from uncorrelated initial states, and could be used to improve the accuracy of spectroscopy in experiments with fermionic alkaline earth atoms or fermionic groundstate molecules. 1 aFoss-Feig, Michael1 aDaley, Andrew, J.1 aThompson, James, K.1 aRey, Ana, Maria uhttp://arxiv.org/abs/1207.4741v101009nas a2200157 4500008004100000020002200041245009100063210006900154260001500223300001200238520050600250100001600756700001900772700002300791856003700814 2012 eng d a978-1-4503-1115-100aSuper-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure0 aSuperPolynomial Quantum Speedups for Boolean Evaluation Trees wi c2012/01/08 a249-2653 a We give a quantum algorithm for evaluating a class of boolean formulas (such as NAND trees and 3-majority trees) on a restricted set of inputs. Due to the structure of the allowed inputs, our algorithm can evaluate a depth $n$ tree using $O(n^{2+\log\omega})$ queries, where $\omega$ is independent of $n$ and depends only on the type of subformulas within the tree. We also prove a classical lower bound of $n^{\Omega(\log\log n)}$ queries, thus showing a (small) super-polynomial speed-up. 1 aZhan, Bohua1 aKimmel, Shelby1 aHassidim, Avinatan uhttp://arxiv.org/abs/1101.0796v301279nas 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.1722v101533nas a2200133 4500008004100000245006700041210006700108300001200175490000700187520106700194100001901261700002301280856009601303 2011 eng d00aSpectral Concentration of Positive Functions on Compact Groups0 aSpectral Concentration of Positive Functions on Compact Groups a355-3730 v173 a

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

1 aAlagic, Gorjan1 aRussell, Alexander uhttps://quics.umd.edu/publications/spectral-concentration-positive-functions-compact-groups01707nas a2200145 4500008004100000245006800041210006800109260001300177490000700190520125600197100002601453700002501479700002001504856003701524 2011 eng d00aSpectroscopy of dipolar fermions in 2D pancakes and 3D lattices0 aSpectroscopy of dipolar fermions in 2D pancakes and 3D lattices c2011/9/60 v843 a Motivated by ongoing measurements at JILA, we calculate the recoil-free spectra of dipolar interacting fermions, for example ultracold heteronuclear molecules, in a one-dimensional lattice of two-dimensional pancakes, spectroscopically probing transitions between different internal (e.g., rotational) states. We additionally incorporate p-wave interactions and losses, which are important for reactive molecules such as KRb. Moreover, we consider other sources of spectral broadening: interaction-induced quasiparticle lifetimes and the different polarizabilities of the different rotational states used for the spectroscopy. Although our main focus is molecules, some of the calculations are also useful for optical lattice atomic clocks. For example, understanding the p-wave shifts between identical fermions and small dipolar interactions coming from the excited clock state are necessary to reach future precision goals. Finally, we consider the spectra in a deep 3D lattice and show how they give a great deal of information about static correlation functions, including \textit{all} the moments of the density correlations between nearby sites. The range of correlations measurable depends on spectroscopic resolution and the dipole moment. 1 aHazzard, Kaden, R. A.1 aGorshkov, Alexey, V.1 aRey, Ana, Maria uhttp://arxiv.org/abs/1106.1718v100466nas a2200133 4500008004100000245009500041210006900136300001100205490000700216100002000223700002500243700001400268856005000282 2011 eng d00aSpectroscopy of dipolar fermions in layered two-dimensional and three-dimensional lattices0 aSpectroscopy of dipolar fermions in layered twodimensional and t a0336080 v841 aHazzard, K, R A1 aGorshkov, Alexey, V.1 aRey, A, M uhttp://link.aps.org/abstract/PRA/v84/e033608/01195nas a2200157 4500008004100000245009000041210006900131260001500200300001600215490000700231520070200238100002100940700001800961700002100979856003701000 2011 eng d00aSuperactivation of the Asymptotic Zero-Error Classical Capacity of a Quantum Channel0 aSuperactivation of the Asymptotic ZeroError Classical Capacity o c2011/12/01 a8114 - 81260 v573 a The zero-error classical capacity of a quantum channel is the asymptotic rate at which it can be used to send classical bits perfectly, so that they can be decoded with zero probability of error. We show that there exist pairs of quantum channels, neither of which individually have any zero-error capacity whatsoever (even if arbitrarily many uses of the channels are available), but such that access to even a single copy of both channels allows classical information to be sent perfectly reliably. In other words, we prove that the zero-error classical capacity can be superactivated. This result is the first example of superactivation of a classical capacity of a quantum channel. 1 aCubitt, Toby, S.1 aChen, Jianxin1 aHarrow, Aram, W. uhttp://arxiv.org/abs/0906.2547v301304nas a2200145 4500008004100000245006900041210006900110260001300179490000700192520086300199100001801062700002201080700001901102856003701121 2011 eng d00aSuperradiance of cold atoms coupled to a superconducting circuit0 aSuperradiance of cold atoms coupled to a superconducting circuit c2011/6/60 v833 a We investigate superradiance of an ensemble of atoms coupled to an integrated superconducting LC-circuit. Particular attention is paid to the effect of inhomogeneous coupling constants. Combining perturbation theory in the inhomogeneity and numerical simulations we show that inhomogeneous coupling constants can significantly affect the superradiant relaxation process. Incomplete relaxation terminating in "dark states" can occur, from which the only escape is through individual spontaneous emission on a much longer time scale. The relaxation dynamics can be significantly accelerated or retarded, depending on the distribution of the coupling constants. On the technical side, we also generalize the previously known propagator of superradiance for identical couplings in the completely symmetric sector to the full exponentially large Hilbert space. 1 aBraun, Daniel1 aHoffman, Jonathan1 aTiesinga, Eite uhttp://arxiv.org/abs/1101.5300v101041nas a2200121 4500008004100000245006000041210006000101260001500161520066400176100002300840700001900863856003700882 2010 eng d00aSimulating sparse Hamiltonians with star decompositions0 aSimulating sparse Hamiltonians with star decompositions c2010/03/183 a We present an efficient algorithm for simulating the time evolution due to a sparse Hamiltonian. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian H acts for time t, this algorithm uses (d^2(d+log* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which scales like (d^4(log* N)||Ht||)^{1+o(1)}. To achieve this, we decompose a general sparse Hamiltonian into a small sum of Hamiltonians whose graphs of non-zero entries have the property that every connected component is a star, and efficiently simulate each of these pieces. 1 aChilds, Andrew, M.1 aKothari, Robin uhttp://arxiv.org/abs/1003.3683v200539nas a2200133 4500008004100000245014600041210006900187300000900256490000700265100001900272700002500291700001600316856007300332 2009 eng d00aSlow light propagation and amplification via electromagnetically induced transparency and four-wave mixing in an optically dense atomic vapor0 aSlow light propagation and amplification via electromagnetically a19160 v561 aPhillips, N, B1 aGorshkov, Alexey, V.1 aNovikova, I uhttp://www.informaworld.com/smpp/content db=all content=a91354540500566nas a2200181 4500008004100000245008800041210006900129300001100198490000800209100002500217700001200242700001500254700001500269700001400284700001600298700001900314856005100333 2008 eng d00aSuppression of Inelastic Collisions Between Polar Molecules With a Repulsive Shield0 aSuppression of Inelastic Collisions Between Polar Molecules With a0732010 v1011 aGorshkov, Alexey, V.1 aRabl, P1 aPupillo, G1 aMicheli, A1 aZoller, P1 aLukin, M, D1 aBüchler, H, P uhttp://link.aps.org/abstract/PRL/v101/e073201/01734nas a2200229 4500008004100000245006500041210006500106260001500171520102700186100002301213700002501236700002601261700002201287700002001309700002101329700002501350700003001375700002301405700001901428700002001447856003701467 2007 eng d00aSignatures of incoherence in a quantum information processor0 aSignatures of incoherence in a quantum information processor c2007/05/243 a Incoherent noise is manifest in measurements of expectation values when the underlying ensemble evolves under a classical distribution of unitary processes. While many incoherent processes appear decoherent, there are important differences. The distribution functions underlying incoherent processes are either static or slowly varying with respect to control operations and so the errors introduced by these distributions are refocusable. The observation and control of incoherence in small Hilbert spaces is well known. Here we explore incoherence during an entangling operation, such as is relevant in quantum information processing. As expected, it is more difficult to separate incoherence and decoherence over such processes. However, by studying the fidelity decay under a cyclic entangling map we are able to identify distinctive experimental signatures of incoherence. This result is demonstrated both through numerical simulations and experimentally in a three qubit nuclear magnetic resonance implementation. 1 aHenry, Michael, K.1 aGorshkov, Alexey, V.1 aWeinstein, Yaakov, S.1 aCappellaro, Paola1 aEmerson, Joseph1 aBoulant, Nicolas1 aHodges, Jonathan, S.1 aRamanathan, Chandrasekhar1 aHavel, Timothy, F.1 aMartinez, Rudy1 aCory, David, G. uhttp://arxiv.org/abs/0705.3666v201118nas a2200145 4500008004100000245008400041210006900125260001500194300001400209490000700223520066000230100001900890700001900909856004400928 2007 eng d00aSimple scheme for implementing the Deutsch-Jozsa algorithm in thermal cavity 0 aSimple scheme for implementing the DeutschJozsa algorithm in the c2007/01/05 a155 - 1610 v403 a We present a simple scheme to implement the Deutsch-Jozsa algorithm based on two-atom interaction in a thermal cavity. The photon-number-dependent parts in the evolution operator are canceled with the strong resonant classical field added. As a result, our scheme is immune to thermal field, and does not require the cavity to remain in the vacuum state throughout the procedure. Besides, large detuning between the atoms and the cavity is not necessary neither, leading to potential speed up of quantum operation. Finally, we show by numerical simulation that the proposed scheme is equal to demonstrate the Deutsch-Jozsa algorithm with high fidelity. 1 aYang, Wen-Xing1 aGong, Zhe-Xuan uhttp://arxiv.org/abs/quant-ph/0611225v201428nas a2200181 4500008004100000245008400041210006900125260001500194300001600209490000700225520086200232100002301094700001901117700002001136700002301156700002301179856004401202 2005 eng d00aScalable register initialization for quantum computing in an optical lattice 0 aScalable register initialization for quantum computing in an opt c2005/06/14 a1687 - 16940 v383 a The Mott insulator state created by loading an atomic Bose-Einstein condensate (BEC) into an optical lattice may be used as a means to prepare a register of atomic qubits in a quantum computer. Such architecture requires a lattice commensurately filled with atoms, which corresponds to the insulator state only in the limit of zero inter-well tunneling. We show that a lattice with spatial inhomogeneity created by a quadratic magnetic trapping potential can be used to isolate a subspace in the center which is impervious to hole-hoping. Components of the wavefunction with more than one atom in any well can be projected out by selective measurement on a molecular photo-associative transition. Maintaining the molecular coupling induces a quantum Zeno effect that can sustain a commensurately filled register for the duration of a quantum computation. 1 aBrennen, Gavin, K.1 aPupillo, Guido1 aRey, Ana, Maria1 aClark, Charles, W.1 aWilliams, Carl, J. uhttp://arxiv.org/abs/quant-ph/0312069v101196nas 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/0507288v101053nas a2200181 4500008004100000245007400041210006900115260001400184490000700198520052300205100001900728700001300747700001500760700001500775700001900790700001800809856004400827 2005 eng d00aSolid-state circuit for spin entanglement generation and purification0 aSolidstate circuit for spin entanglement generation and purifica c2005/6/150 v943 aWe show how realistic charge manipulation and measurement techniques, combined with the exchange interaction, allow for the robust generation and purification of four-particle spin entangled states in electrically controlled semiconductor quantum dots. The generated states are immunized to the dominant sources of noise via a dynamical decoherence-free subspace; all additional errors are corrected by a purification protocol. This approach may find application in quantum computation, communication, and metrology. 1 aTaylor, J., M.1 aDür, W.1 aZoller, P.1 aYacoby, A.1 aMarcus, C., M.1 aLukin, M., D. uhttp://arxiv.org/abs/cond-mat/0503255v201059nas 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/0408387v201168nas a2200133 4500008004100000245004200041210004200083260001400125520078800139100001900927700002200946700002300968856004300991 2005 eng d00aStrong Fourier Sampling Fails over Gn0 aStrong Fourier Sampling Fails over Gn c11/7/20053 a

We present a negative result regarding the hidden subgroup problem on the powers Gn of a fixed group G. Under a condition on the base group G, we prove that strong Fourier sampling cannot distinguish some subgroups of Gn. Since strong sampling is in fact the optimal measurement on a coset state, this shows that we have no hope of efficiently solving the hidden subgroup problem over these groups with separable measurements on coset states (that is, using any polynomial number of single-register coset state experiments). Base groups satisfying our condition include all nonabelian simple groups. We apply our results to show that there exist uniform families of nilpotent groups whose normal series factors have constant size and yet are immune to strong Fourier sampling.

1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://arxiv.org/abs/quant-ph/051105401546nas a2200181 4500008004100000245007100041210006900112260001500181300001600196490000700212520099700219100001901216700002001235700001901255700002301274700002301297856004401320 2004 eng d00aScalable quantum computation in systems with Bose-Hubbard dynamics0 aScalable quantum computation in systems with BoseHubbard dynamic c2004/02/15 a2395 - 24040 v513 a Several proposals for quantum computation utilize a lattice type architecture with qubits trapped by a periodic potential. For systems undergoing many body interactions described by the Bose-Hubbard Hamiltonian, the ground state of the system carries number fluctuations that scale with the number of qubits. This process degrades the initialization of the quantum computer register and can introduce errors during error correction. In an earlier manuscript we proposed a solution to this problem tailored to the loading of cold atoms into an optical lattice via the Mott Insulator phase transition. It was shown that by adding an inhomogeneity to the lattice and performing a continuous measurement, the unit filled state suitable for a quantum computer register can be maintained. Here, we give a more rigorous derivation of the register fidelity in homogeneous and inhomogeneous lattices and provide evidence that the protocol is effective in the finite temperature regime. 1 aPupillo, Guido1 aRey, Ana, Maria1 aBrennen, Gavin1 aWilliams, Carl, J.1 aClark, Charles, W. uhttp://arxiv.org/abs/quant-ph/0403052v200967nas a2200133 4500008004100000245004200041210004200083260001500125490000700140520059600147100002300743700002300766856004400789 2004 eng d00aSpatial search and the Dirac equation0 aSpatial search and the Dirac equation c2004/10/190 v703 a We consider the problem of searching a d-dimensional lattice of N sites for a single marked location. We present a Hamiltonian that solves this problem in time of order sqrt(N) for d>2 and of order sqrt(N) log(N) in the critical dimension d=2. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of d=4), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom. 1 aChilds, Andrew, M.1 aGoldstone, Jeffrey uhttp://arxiv.org/abs/quant-ph/0405120v101263nas a2200133 4500008004100000245003500041210003500076260001400111490000700125520090700132100002301039700002301062856004401085 2004 eng d00aSpatial search by quantum walk0 aSpatial search by quantum walk c2004/8/230 v703 a Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of N items laid out in d spatial dimensions can be searched in time of order sqrt(N) for d>2, and in time of order sqrt(N) poly(log N) for d=2. We consider an alternative search algorithm based on a continuous time quantum walk on a graph. The case of the complete graph gives the continuous time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that sqrt(N) speedup can also be achieved on the hypercube. We show that full sqrt(N) speedup can be achieved on a d-dimensional periodic lattice for d>4. In d=4, the quantum walk search algorithm takes time of order sqrt(N) poly(log N), and in d<4, the algorithm does not provide substantial speedup. 1 aChilds, Andrew, M.1 aGoldstone, Jeffrey uhttp://arxiv.org/abs/quant-ph/0306054v200953nas a2200109 4500008004100000245004000041210004000081260001500121520064000136100002300776856004400799 2001 eng d00aSecure assisted quantum computation0 aSecure assisted quantum computation c2001/11/073 a Suppose Alice wants to perform some computation that could be done quickly on a quantum computer, but she cannot do universal quantum computation. Bob can do universal quantum computation and claims he is willing to help, but Alice wants to be sure that Bob cannot learn her input, the result of her calculation, or perhaps even the function she is trying to compute. We describe a simple, efficient protocol by which Bob can help Alice perform the computation, but there is no way for him to learn anything about it. We also discuss techniques for Alice to detect whether Bob is honestly helping her or if he is introducing errors. 1 aChilds, Andrew, M. uhttp://arxiv.org/abs/quant-ph/0111046v200513nas a2200121 4500008004100000245007000041210006800111260001400179490000700193520013500200100001200335856004400347 2001 eng d00aSecure key distribution via pre- and post-selected quantum states0 aSecure key distribution via pre and postselected quantum states c2001/2/140 v633 a A quantum key distribution scheme whose security depends on the features of pre- and post-selected quantum states is described. 1 aBub, J. uhttp://arxiv.org/abs/quant-ph/0006086v300436nas a2200121 4500008004100000245006600041210006600107300001200173490000800185100001500193700001700208856008900225 1996 eng d00aSpecial eigenforms on the sphere bundle of a Finsler manifold0 aSpecial eigenforms on the sphere bundle of a Finsler manifold a67–780 v1961 aBao, David1 aLackey, Brad uhttps://quics.umd.edu/publications/special-eigenforms-sphere-bundle-finsler-manifold