01754nas a2200169 4500008004100000245008800041210006900129260001400198520119900212100002201411700002301433700001901456700002901475700002201504700002101526856003701547 2024 eng d00aEfficient and practical Hamiltonian simulation from time-dependent product formulas0 aEfficient and practical Hamiltonian simulation from timedependen c3/13/20243 a

In this work we propose an approach for implementing time-evolution of a quantum system using product formulas. The quantum algorithms we develop have provably better scaling (in terms of gate complexity and circuit depth) than a naive application of well-known Trotter formulas, for systems where the evolution is determined by a Hamiltonian with different energy scales (i.e., one part is "large" and another part is "small"). Our algorithms generate a decomposition of the evolution operator into a product of simple unitaries that are directly implementable on a quantum computer. Although the theoretical scaling is suboptimal compared with state-of-the-art algorithms (e.g., quantum signal processing), the performance of the algorithms we propose is highly competitive in practice. We illustrate this via extensive numerical simulations for several models. For instance, in the strong-field regime of the 1D transverse-field Ising model, our algorithms achieve an improvement of one order of magnitude in both the system size and evolution time that can be simulated with a fixed budget of 1000 arbitrary 2-qubit gates, compared with standard Trotter formulas.

1 aBosse, Jan, Lukas1 aChilds, Andrew, M.1 aDerby, Charles1 aGambetta, Filippo, Maria1 aMontanaro, Ashley1 aSantos, Raul, A. uhttps://arxiv.org/abs/2403.0872901355nas a2200181 4500008004100000245008400041210006900125260001400194520077500208100001800983700002301001700002401024700001601048700002401064700002501088700002301113856003701136 2024 eng d00aEfficiently verifiable quantum advantage on near-term analog quantum simulators0 aEfficiently verifiable quantum advantage on nearterm analog quan c3/13/20243 a

Existing schemes for demonstrating quantum computational advantage are subject to various practical restrictions, including the hardness of verification and challenges in experimental implementation. Meanwhile, analog quantum simulators have been realized in many experiments to study novel physics. In this work, we propose a quantum advantage protocol based on single-step Feynman-Kitaev verification of an analog quantum simulation, in which the verifier need only run an O(λ2)-time classical computation, and the prover need only prepare O(1) samples of a history state and perform O(λ2) single-qubit measurements, for a security parameter λ. We also propose a near-term feasible strategy for honest provers and discuss potential experimental realizations.

1 aLiu, Zhenning1 aDevulapalli, Dhruv1 aHangleiter, Dominik1 aLiu, Yi-Kai1 aKollár, Alicia, J.1 aGorshkov, Alexey, V.1 aChilds, Andrew, M. uhttps://arxiv.org/abs/2403.0819501134nas a2200133 4500008004100000245002800041210002800069260001400097520078800111100002100899700002100920700002200941856003700963 2024 eng d00aEncoding Majorana codes0 aEncoding Majorana codes c2/12/20243 a

To implement a quantum error correction protocol, we first need a scheme to prepare our state in the correct subspace of the code, and this can be done using a unitary encoding circuit. Majorana codes are special since any gates that transform such codes must preserve fermionic parity. In this paper, we present an algorithm that uses the stabilizer matrix to compute unitary encoding circuits for Majorana codes. We present two approaches, both of which use a version of Gaussian elimination with row operations replaced with elementary fermionic Clifford operations. One approach uses an additional ancilla mode and works for all Majorana stabilizer codes, while the second approach does not use ancilla but does not work if the total parity is inside the stabilizer group.

1 aMudassar, Maryam1 aChien, Riley, W.1 aGottesman, Daniel uhttps://arxiv.org/abs/2402.0782901739nas a2200121 4500008004100000245004000041210004000081260001300121520140700134100001701541700002201558856003701580 2024 eng d00aError Correction in Dynamical Codes0 aError Correction in Dynamical Codes c3/7/20243 a

We ask what is the general framework for a quantum error correcting code that is defined by a sequence of measurements. Recently, there has been much interest in Floquet codes and space-time codes. In this work, we define and study the distance of a dynamical code. This is a subtle concept and difficult to determine: At any given time, the system will be in a subspace which forms a quantum error-correcting code with a given distance, but the full error correction capability of that code may not be available due to the schedule of measurements associated with the code. We address this challenge by developing an algorithm that tracks information we have learned about the error syndromes through the protocol and put that together to determine the distance of a dynamical code, in a non-fault-tolerant context. We use the tools developed for the algorithm to analyze the initialization and masking properties of a generic Floquet code. Further, we look at properties of dynamical codes under the constraint of geometric locality with a view to understand whether the fundamental limitations on logical gates and code parameters imposed by geometric locality for traditional codes can be surpassed in the dynamical paradigm. We find that codes with a limited number of long range connectivity will not allow non-Clifford gates to be implemented with finite depth circuits in the 2D setting.

1 aFu, Xiaozhen1 aGottesman, Daniel uhttps://arxiv.org/abs/2403.0416301817nas a2200181 4500008004100000245006100041210006100102260001400163520125300177100003201430700001901462700002201481700002201503700002001525700002801545700002501573856003701598 2024 eng d00aEstimation of Hamiltonian parameters from thermal states0 aEstimation of Hamiltonian parameters from thermal states c1/18/20243 a

We upper- and lower-bound the optimal precision with which one can estimate an unknown Hamiltonian parameter via measurements of Gibbs thermal states with a known temperature. The bounds depend on the uncertainty in the Hamiltonian term that contains the parameter and on the term's degree of noncommutativity with the full Hamiltonian: higher uncertainty and commuting operators lead to better precision. We apply the bounds to show that there exist entangled thermal states such that the parameter can be estimated with an error that decreases faster than 1/n−−√, beating the standard quantum limit. This result governs Hamiltonians where an unknown scalar parameter (e.g. a component of a magnetic field) is coupled locally and identically to n qubit sensors. In the high-temperature regime, our bounds allow for pinpointing the optimal estimation error, up to a constant prefactor. Our bounds generalize to joint estimations of multiple parameters. In this setting, we recover the high-temperature sample scaling derived previously via techniques based on quantum state discrimination and coding theory. In an application, we show that noncommuting conserved quantities hinder the estimation of chemical potentials.

1 aGarcía-Pintos, Luis, Pedro1 aBharti, Kishor1 aBringewatt, Jacob1 aDehghani, Hossein1 aEhrenberg, Adam1 aHalpern, Nicole, Yunger1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2401.1034301833nas a2200145 4500008004100000245008700041210006900128260001400197520137500211100001601586700001501602700001801617700001501635856003701650 2024 eng d00aExpanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding0 aExpanding HardwareEfficiently Manipulable Hilbert Space via Hami c1/16/20243 a

Many promising quantum applications depend on the efficient quantum simulation of an exponentially large sparse Hamiltonian, a task known as sparse Hamiltonian simulation, which is fundamentally important in quantum computation. Although several theoretically appealing quantum algorithms have been proposed for this task, they typically require a black-box query model of the sparse Hamiltonian, rendering them impractical for near-term implementation on quantum devices.
In this paper, we propose a technique named Hamiltonian embedding. This technique simulates a desired sparse Hamiltonian by embedding it into the evolution of a larger and more structured quantum system, allowing for more efficient simulation through hardware-efficient operations. We conduct a systematic study of this new technique and demonstrate significant savings in computational resources for implementing prominent quantum applications. As a result, we can now experimentally realize quantum walks on complicated graphs (e.g., binary trees, glued-tree graphs), quantum spatial search, and the simulation of real-space Schrödinger equations on current trapped-ion and neutral-atom platforms. Given the fundamental role of Hamiltonian evolution in the design of quantum algorithms, our technique markedly expands the horizon of implementable quantum advantages in the NISQ era.

1 aLeng, Jiaqi1 aLi, Joseph1 aPeng, Yuxiang1 aWu, Xiaodi uhttps://arxiv.org/abs/2401.0855001794nas a2200157 4500008004100000245010100041210006900142260001400211520126400225100002001489700002201509700001901531700002401550700002501574856003701599 2024 eng d00aExperimental roadmap for optimal state transfer and entanglement generation in power-law systems0 aExperimental roadmap for optimal state transfer and entanglement c2/12/20243 a

Experimental systems with power-law interactions have recently garnered interest as promising platforms for quantum information processing. Such systems are capable of spreading entanglement superballistically and achieving an asymptotic speed-up over locally interacting systems. Recently, protocols developed by Eldredge et al. [Phys. Rev. Lett. 119, 170503 (2017)] and Tran et al. [Phys. Rev. X 11, 031016 (2021)] for the task of transferring a quantum state between distant particles quickly were shown to be optimal and saturate theoretical bounds. However, the implementation of these protocols in physical systems with long-range interactions remains to be fully realized. In this work, we provide an experimental roadmap towards realizing fast state-transfer protocols in three classes of atomic and molecular systems with dipolar interactions: polar molecules composed of alkali-metal dimers, neutral atoms in excited Rydberg states, and atoms with strong magnetic moments (e.g. dysprosium). As a guide to near-term experimental implementation, we numerically evaluate the tradeoffs between the two protocols for small system sizes and develop methods to address potential crosstalk errors that may arise during the execution of the protocols.

1 aGuo, Andrew, Y.1 aYoung, Jeremy, T.1 aBelyansky, Ron1 aBienias, Przemyslaw1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2402.0797401506nas a2200157 4500008004100000245005800041210005700099260001400156520104400170100002001214700001801234700002101252700002001273700001801293856003701311 2023 eng d00aEffect of non-unital noise on random circuit sampling0 aEffect of nonunital noise on random circuit sampling c6/28/20233 a

In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical non-unital noise sources with constant noise rates. We show that even in the presence of unital sources like the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates — meaning it is never too "flat" — regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As consequences, our results have interesting algorithmic implications on both the hardness and easiness of noisy random circuit sampling, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results.

1 aFefferman, Bill1 aGhosh, Soumik1 aGullans, Michael1 aKuroiwa, Kohdai1 aSharma, Kunal uhttps://arxiv.org/abs/2306.1665902358nas a2200145 4500008004100000245007400041210006900115260001400184520188700198100002002085700002002105700002802125700002202153856003702175 2023 eng d00aEfficient learning of ground & thermal states within phases of matter0 aEfficient learning of ground thermal states within phases of mat c1/30/20233 a

We consider two related tasks: (a) estimating a parameterisation of a given Gibbs state and expectation values of Lipschitz observables on this state; and (b) learning the expectation values of local observables within a thermal or quantum phase of matter. In both cases, we wish to minimise the number of samples we use to learn these properties to a given precision.
For the first task, we develop new techniques to learn parameterisations of classes of systems, including quantum Gibbs states of non-commuting Hamiltonians with exponential decay of correlations and the approximate Markov property. We show it is possible to infer the expectation values of all extensive properties of the state from a number of copies that not only scales polylogarithmically with the system size, but polynomially in the observable's locality -- an exponential improvement. This set of properties includes expected values of quasi-local observables and entropies.  For the second task, we develop efficient algorithms for learning observables in a phase of matter of a quantum system. By exploiting the locality of the Hamiltonian, we show that M local observables can be learned with probability 1−δ to precision ϵ with using only N=O(log(Mδ)epolylog(ϵ−1)) samples -- an exponential improvement on the precision over previous bounds. Our results apply to both families of ground states of Hamiltonians displaying local topological quantum order, and thermal phases of matter with exponential decay of correlations. In addition, our sample complexity applies to the worse case setting whereas previous results only applied on average.
Furthermore, we develop tools of independent interest, such as robust shadow tomography algorithms, Gibbs approximations to ground states, and generalisations of transportation cost inequalities for Gibbs states.

1 aOnorati, Emilio1 aRouzé, Cambyse1 aFrança, Daniel, Stilck1 aWatson, James, D. uhttps://arxiv.org/abs/2301.1294601302nas a2200133 4500008004100000245005800041210005800099260001300157520089200170100002101062700002701083700002101110856003701131 2023 eng d00aError Mitigation Thresholds in Noisy Quantum Circuits0 aError Mitigation Thresholds in Noisy Quantum Circuits c2/8/20233 a

Extracting useful information from noisy near-term quantum simulations requires error mitigation strategies. A broad class of these strategies rely on precise characterization of the noise source. We study the performance of such strategies when the noise is imperfectly characterized. We adapt an Imry-Ma argument to predict the existence of an error mitigation threshold for random spatially local circuits in spatial dimensions D≥2: characterization disorder below the threshold rate allows for error mitigation up to times that scale with the number of qubits. For one-dimensional circuits, by contrast, mitigation fails at an O(1) time for any imperfection in the characterization of disorder. We discuss implications for tests of quantum computational advantage, fault-tolerant probes of measurement-induced phase transitions, and quantum algorithms in near-term devices.

1 aNiroula, Pradeep1 aGopalakrishnan, Sarang1 aGullans, Michael uhttps://arxiv.org/abs/2302.0427802172nas a2200133 4500008004100000245008500041210006900126260001500195520173200210100002401942700001701966700001801983856003702001 2023 eng d00aEvaluating the security of CRYSTALS-Dilithium in the quantum random oracle model0 aEvaluating the security of CRYSTALSDilithium in the quantum rand c12/17/20233 a

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

1 aJackson, Kelsey, A.1 aMiller, Carl1 aWang, Daochen uhttps://arxiv.org/abs/2312.1661901229nas a2200157 4500008004100000245007900041210006900120260001300189520074400202100001900946700001700965700001300982700002100995700001801016856003701034 2023 eng d00aEver more optimized simulations of fermionic systems on a quantum computer0 aEver more optimized simulations of fermionic systems on a quantu c3/6/20233 a

Despite using a novel model of computation, quantum computers break down programs into elementary gates. Among such gates, entangling gates are the most expensive. In the context of fermionic simulations, we develop a suite of compilation and optimization techniques that massively reduce the entangling-gate counts. We exploit the well-studied non-quantum optimization algorithms to achieve up to 24\% savings over the state of the art for several small-molecule simulations, with no loss of accuracy or hidden costs. Our methodologies straightforwardly generalize to wider classes of near-term simulations of the ground state of a fermionic system or real-time simulations probing dynamical properties of a fermionic system. 

1 aWang, Qingfeng1 aCian, Ze-Pei1 aLi, Ming1 aMarkov, Igor, L.1 aNam, Yunseong uhttps://arxiv.org/abs/2303.0346001881nas a2200193 4500008004100000245007300041210006900114260001400183490000600197520129800203100002001501700002201521700002101543700001601564700001801580700002401598700002801622856003701650 2023 eng d00aExperimental Observation of Thermalization with Noncommuting Charges0 aExperimental Observation of Thermalization with Noncommuting Cha c4/28/20230 v43 a

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

1 aKranzl, Florian1 aLasek, Aleksander1 aJoshi, Manoj, K.1 aKalev, Amir1 aBlatt, Rainer1 aRoos, Christian, F.1 aHalpern, Nicole, Yunger uhttps://arxiv.org/abs/2202.0465202428nas a2200217 4500008004100000245010600041210006900147260001400216520171900230653004301949653002701992653002902019653003102048100001702079700001502096700001302111700001702124700001602141700001602157856003702173 2022 eng d00aEfficient and practical quantum compiler towards multi-qubit systems with deep reinforcement learning0 aEfficient and practical quantum compiler towards multiqubit syst c4/14/20223 a

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

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

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

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

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

1 aAn, Dong1 aFang, Di1 aJordan, Stephen1 aLiu, Jin-Peng1 aLow, Guang, Hao1 aWang, Jiasu uhttps://arxiv.org/abs/2205.0114101455nas a2200205 4500008004100000245006000041210005900101260001500160520078600175653002100961653002700982653003501009653003001044653003101074653005201105100001601157700002501173700001401198856003701212 2022 eng d00aError-correcting codes for fermionic quantum simulation0 aErrorcorrecting codes for fermionic quantum simulation c10/16/20223 a

We provide ways to simulate fermions by qubits on 2d lattices using Z2 gauge theories (stabilizer codes). By studying the symplectic automorphisms of the Pauli module over the Laurent polynomial ring, we develop a systematic way to increase the code distances of stabilizer codes. We identify a family of stabilizer codes that can be used to simulate fermions with code distances of d=2,3,4,5,6,7 such that any ⌊d−12⌋-qubit error can be corrected. In particular, we demonstrate three stabilizer codes with code distances of d=3, d=4, and d=5, respectively, with all stabilizers and logical operators shown explicitly. The syndromes for all Pauli errors are provided. Finally, we introduce a syndrome-matching method to compute code distances numerically.

10aFOS: Mathematics10aFOS: Physical sciences10aMathematical Physics (math-ph)10aQuantum Algebra (math.QA)10aQuantum Physics (quant-ph)10aStrongly Correlated Electrons (cond-mat.str-el)1 aChen, Yu-An1 aGorshkov, Alexey, V.1 aXu, Yijia uhttps://arxiv.org/abs/2210.0841101880nas a2200133 4500008004100000245008500041210006900126260001500195520144100210100001701651700002101668700002001689856003701709 2022 eng d00aEstimating gate complexities for the site-by-site preparation of fermionic vacua0 aEstimating gate complexities for the sitebysite preparation of f c07/04/20223 a

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

1 aSewell, Troy1 aBapat, Aniruddha1 aJordan, Stephen uhttps://arxiv.org/abs/2207.0169202202nas a2200145 4500008004100000245009100041210006900132260001400201490000800215520174200223100001501965700001601980700002301996856003702019 2022 eng d00aEuler-obstructed Cooper pairing: Nodal superconductivity and hinge Majorana zero modes0 aEulerobstructed Cooper pairing Nodal superconductivity and hinge c3/29/20220 v1053 a

Since the proposal of monopole Cooper pairing in [Phys. Rev. Lett. 120, 067003 (2018)], considerable research efforts have been dedicated to the study of Cooper pairing order parameters constrained (or obstructed) by the nontrivial normal-state band topology at Fermi surfaces in 3D systems. In the current work, we generalize the topologically obstructed pairings between Chern states (like the monopole Cooper pairing) by proposing Euler obstructed Cooper pairing in 3D systems. The Euler obstructed Cooper pairing widely exists between two Fermi surfaces with nontrivial band topology characterized by nonzero Euler numbers; such Fermi surfaces can exist in 3D PT-protected spinless-Dirac/nodal-line semimetals with negligible spin-orbit coupling, where PT is the space-time inversion symmetry. An Euler obstructed pairing channel must have pairing nodes on the pairing-relevant Fermi surfaces, and the total winding number of the pairing nodes is determined by the sum or difference of the Euler numbers on the Fermi surfaces. In particular, we find that when the normal state is time-reversal invariant and the pairing is weak, a sufficiently-dominant Euler obstructed pairing channel with zero total momentum leads to nodal superconductivity. If the Fermi surface splitting is small, the resultant nodal superconductor hosts hinge Majorana zero modes. The possible dominance of the Euler obstructed pairing channel near the superconducting transition and the robustness of the hinge Majorana zero modes against disorder are explicitly demonstrated using effective or tight-binding models. Our work presents the first class of higher-order nodal superconductivity originating from the topologically obstructed Cooper pairing.

1 aYu, Jiabin1 aChen, Yu-An1 aSarma, Sankar, Das uhttps://arxiv.org/abs/2109.0268501498nas a2200301 4500008004100000245006800041210006800109260001400177520060600191653002700797653004400824653003100868100001700899700001600916700002500932700001800957700001300975700001800988700001901006700002101025700001401046700002201060700001601082700001901098700001801117700002401135856003701159 2022 eng d00aExperimental Implementation of an Efficient Test of Quantumness0 aExperimental Implementation of an Efficient Test of Quantumness c9/28/20223 a

A test of quantumness is a protocol where a classical user issues challenges to a quantum device to determine if it exhibits non-classical behavior, under certain cryptographic assumptions. Recent attempts to implement such tests on current quantum computers rely on either interactive challenges with efficient verification, or non-interactive challenges with inefficient (exponential time) verification. In this paper, we execute an efficient non-interactive test of quantumness on an ion-trap quantum computer. Our results significantly exceed the bound for a classical device's success.

10aFOS: Physical sciences10aOther Condensed Matter (cond-mat.other)10aQuantum Physics (quant-ph)1 aLewis, Laura1 aZhu, Daiwei1 aGheorghiu, Alexandru1 aNoel, Crystal1 aKatz, Or1 aHarraz, Bahaa1 aWang, Qingfeng1 aRisinger, Andrew1 aFeng, Lei1 aBiswas, Debopriyo1 aEgan, Laird1 aVidick, Thomas1 aCetina, Marko1 aMonroe, Christopher uhttps://arxiv.org/abs/2209.1431602003nas a2200217 4500008004100000245007300041210006900114260001300183520129800196653002701494653003101521653004701552100002001599700002201619700002101641700001601662700001801678700002401696700002801720856003701748 2022 eng d00aExperimental observation of thermalisation with noncommuting charges0 aExperimental observation of thermalisation with noncommuting cha c2/9/20223 a

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

10aFOS: Physical sciences10aQuantum Physics (quant-ph)10aStatistical Mechanics (cond-mat.stat-mech)1 aKranzl, Florian1 aLasek, Aleksander1 aJoshi, Manoj, K.1 aKalev, Amir1 aBlatt, Rainer1 aRoos, Christian, F.1 aHalpern, Nicole, Yunger uhttps://arxiv.org/abs/2202.0465201745nas a2200181 4500008004100000245009400041210006900135260001500204300001100219490000800230520117000238100002401408700001901432700002801451700002601479700002101505856003701526 2022 eng d00aExperimentally Measuring Rolling and Sliding in Three-Dimensional Dense Granular Packings0 aExperimentally Measuring Rolling and Sliding in ThreeDimensional c06/18/2022 a0480010 v1293 a

We experimentally measure a three-dimensional (3D) granular system’s reversibility under cyclic compression. We image the grains using a refractive-index-matched fluid, then analyze the images using the artificial intelligence of variational autoencoders. These techniques allow us to track all the grains’ translations and 3D rotations with accuracy sufficient to infer sliding and rolling displacements. Our observations reveal unique roles played by 3D rotational motions in granular flows. We find that rotations and contact-point motion dominate the dynamics in the bulk, far from the perturbation’s source. Furthermore, we determine that 3D rotations are irreversible under cyclic compression. Consequently, contact-point sliding, which is dissipative, accumulates throughout the cycle. Using numerical simulations whose accuracy our experiment supports, we discover that much of the dissipation occurs in the bulk, where grains rotate more than they translate. Our observations suggest that the analysis of 3D rotations is needed for understanding granular materials’ unique and powerful ability to absorb and dissipate energy.

1 aBenson, Zackery, A.1 aPeshkov, Anton1 aHalpern, Nicole, Yunger1 aRichardson, Derek, C.1 aLosert, Wolfgang uhttps://arxiv.org/abs/2108.1197501749nas a2200169 4500008004100000245009500041210006900136260001400205520115200219653002701371653003101398653005201429100001701481700002101498700002301519856003701542 2022 eng d00aExtracting Wilson loop operators and fractional statistics from a single bulk ground state0 aExtracting Wilson loop operators and fractional statistics from  c9/28/20223 a

An essential aspect of topological phases of matter is the existence of Wilson loop operators that keep the ground state subspace invariant. Here we present and implement an unbiased numerical optimization scheme to systematically find the Wilson loop operators given a single ground state wave function of a gapped Hamiltonian on a disk. We then show how these Wilson loop operators can be cut and glued through further optimization to give operators that can create, move, and annihilate anyon excitations. We subsequently use these operators to determine the braiding statistics and topological twists of the anyons, yielding a way to fully extract topological order from a single wave function. We apply our method to the ground state of the perturbed toric code and doubled semion models with a magnetic field that is up to a half of the critical value. From a contemporary perspective, this can be thought of as a machine learning approach to discover emergent 1-form symmetries of a ground state wave function. From an application perspective, our approach can be relevant to find Wilson loop operators in current quantum simulators.

10aFOS: Physical sciences10aQuantum Physics (quant-ph)10aStrongly Correlated Electrons (cond-mat.str-el)1 aCian, Ze-Pei1 aHafezi, Mohammad1 aBarkeshli, Maissam uhttps://arxiv.org/abs/2209.1430201381nas a2200205 4500008004100000245004900041210004700090260001400137520077400151100002000925700001900945700001500964700002400979700001901003700001901022700002301041700001501064700001301079856008301092 2021 eng d00aEasyPQC: Verifying Post-Quantum Cryptography0 aEasyPQC Verifying PostQuantum Cryptography c9/20/20213 a

EasyCrypt is a formal verification tool used extensively for formalizing concrete security proofs of cryptographic constructions. However, the EasyCrypt formal logics consider only classical attackers, which means that post-quantum security proofs cannot be formalized and machine-checked with this tool. In this paper we prove that a natural extension of the EasyCrypt core logics permits capturing a wide class of post-quantum cryptography proofs, settling a question raised by (Unruh, POPL 2019). Leveraging our positive result, we implement EasyPQC, an extension of EasyCrypt for post-quantum security proofs, and use EasyPQC to verify post-quantum security of three classic constructions: PRF-based MAC, Full Domain Hash and GPV08 identity-based encryption.

1 aBarbosa, Manuel1 aBarthe, Gilles1 aFan, Xiong1 aGrégoire, Benjamin1 aHung, Shih-Han1 aKatz, Jonathan1 aStrub, Pierre-Yves1 aWu, Xiaodi1 aZhou, Li uhttps://quics.umd.edu/publications/easypqc-verifying-post-quantum-cryptography02034nas a2200181 4500008004100000245008100041210006900122260001300191490000800204520146900212100001801681700002501699700002001724700002301744700002501767700002301792856003701815 2021 eng d00aEfficient quantum algorithm for dissipative nonlinear differential equations0 aEfficient quantum algorithm for dissipative nonlinear differenti c3/1/20210 v1183 a

While there has been extensive previous work on efficient quantum algorithms for linear differential equations, analogous progress for nonlinear differential equations has been severely limited due to the linearity of quantum mechanics. Despite this obstacle, we develop a quantum algorithm for initial value problems described by dissipative quadratic n-dimensional ordinary differential equations. Assuming R<1, where R is a parameter characterizing the ratio of the nonlinearity to the linear dissipation, this algorithm has complexity T2poly(logT,logn)/ϵ, where T is the evolution time and ϵ is the allowed error in the output quantum state. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. We achieve this improvement using the method of Carleman linearization, for which we give an improved convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for R≥2–√. Finally, we discuss potential applications of this approach to problems arising in biology as well as in fluid and plasma dynamics.

1 aLiu, Jin-Peng1 aKolden, Herman, Øie1 aKrovi, Hari, K.1 aLoureiro, Nuno, F.1 aTrivisa, Konstantina1 aChilds, Andrew, M. uhttps://arxiv.org/abs/2011.0318502114nas a2200181 4500008004100000245005300041210005300094260001500147490000600162520160200168100002201770700002601792700001801818700001801836700001901854700002201873856003701895 2021 eng d00aEfficient quantum measurement of Pauli operators0 aEfficient quantum measurement of Pauli operators c01/19/20210 v53 a

Estimating the expectation value of an observable is a fundamental task in quantum computation. Unfortunately, it is often impossible to obtain such estimates directly, as the computer is restricted to measuring in a fixed computational basis. One common solution splits the observable into a weighted sum of Pauli operators and measures each separately, at the cost of many measurements. An improved version first groups mutually commuting Pauli operators together and then measures all operators within each group simultaneously. The effectiveness of this depends on two factors. First, to enable simultaneous measurement, circuits are required to rotate each group to the computational basis. In our work, we present two efficient circuit constructions that suitably rotate any group of k commuting n-qubit Pauli operators using at most kn−k(k+1)/2 and O(kn/logk) two-qubit gates respectively. Second, metrics that justifiably measure the effectiveness of a grouping are required. In our work, we propose two natural metrics that operate under the assumption that measurements are distributed optimally among groups. Motivated by our new metrics, we introduce SORTED INSERTION, a grouping strategy that is explicitly aware of the weighting of each Pauli operator in the observable. Our methods are numerically illustrated in the context of the Variational Quantum Eigensolver, where the observables in question are molecular Hamiltonians. As measured by our metrics, SORTED INSERTION outperforms four conventional greedy colouring algorithms that seek the minimum number of groups.

1 aCrawford, Ophelia1 avan Straaten, Barnaby1 aWang, Daochen1 aParks, Thomas1 aCampbell, Earl1 aBrierley, Stephen uhttps://arxiv.org/abs/1908.0694201622nas a2200145 4500008004100000245008500041210006900126260001400195520114800209100002201357700002101379700002101400700001801421856003701439 2021 eng d00aEfficient quantum programming using EASE gates on a trapped-ion quantum computer0 aEfficient quantum programming using EASE gates on a trappedion q c7/15/20213 a

Parallel operations in conventional computing have proven to be an essential tool for efficient and practical computation, and the story is not different for quantum computing. Indeed, there exists a large body of works that study advantages of parallel implementations of quantum gates for efficient quantum circuit implementations. Here, we focus on the recently invented efficient, arbitrary, simultaneously entangling (EASE) gates, available on a trapped-ion quantum computer. Leveraging its flexibility in selecting arbitrary pairs of qubits to be coupled with any degrees of entanglement, all in parallel, we show a n-qubit Clifford circuit can be implemented using 6log(n) EASE gates, a n-qubit multiply-controlled NOT gate can be implemented using 3n/2 EASE gates, and a n-qubit permutation can be implemented using six EASE gates. We discuss their implications to near-term quantum chemistry simulations and the state of the art pattern matching algorithm. Given Clifford + multiply-controlled NOT gates form a universal gate set for quantum computing, our results imply efficient quantum computation by EASE gates, in general.

1 aGrzesiak, Nikodem1 aMaksymov, Andrii1 aNiroula, Pradeep1 aNam, Yunseong uhttps://arxiv.org/abs/2107.0759101255nas a2200169 4500008004100000245007000041210006900111260001400180300000800194490000600202520075000208100002500958700001300983700003200996700002001028856003701048 2021 eng d00aEnergy storage and coherence in closed and open quantum batteries0 aEnergy storage and coherence in closed and open quantum batterie c7/15/2021 a5050 v53 a

We study the role of coherence in closed and open quantum batteries. We obtain upper bounds to the work performed or energy exchanged by both closed and open quantum batteries in terms of coherence. Specifically, we show that the energy storage can be bounded by the Hilbert-Schmidt coherence of the density matrix in the spectral basis of the unitary operator that encodes the evolution of the battery. We also show that an analogous bound can be obtained in terms of the battery's Hamiltonian coherence in the basis of the unitary operator by evaluating their commutator. We apply these bounds to a 4-state quantum system and the anisotropic XY Ising model in the closed system case, and the Spin-Boson model in the open case. 

1 aCaravelli, Francesco1 aYan, Bin1 aGarcía-Pintos, Luis, Pedro1 aHamma, Alioscia uhttps://arxiv.org/abs/2012.1502601588nas a2200241 4500008004100000022001400041245008300055210006900138260001400207300001100221490000600232520086600238100002401104700002201128700002101150700001801171700002801189700001401217700002401231700002301255700002101278856004701299 2021 eng d a2058-956500aEntangled quantum cellular automata, physical complexity, and Goldilocks rules0 aEntangled quantum cellular automata physical complexity and Gold c9/29/2021 a0450170 v63 a

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

1 aHillberry, Logan, E1 aJones, Matthew, T1 aVargas, David, L1 aRall, Patrick1 aHalpern, Nicole, Yunger1 aBao, Ning1 aNotarnicola, Simone1 aMontangero, Simone1 aCarr, Lincoln, D uhttp://dx.doi.org/10.1088/2058-9565/ac1c4101366nas a2200121 4500008004100000245008100041210006900122260001400191520095400205100002701159700002101186856003701207 2021 eng d00aEntanglement and purification transitions in non-Hermitian quantum mechanics0 aEntanglement and purification transitions in nonHermitian quantu c12/2/20203 a

A quantum system subject to continuous measurement and post-selection evolves according to a non-Hermitian Hamiltonian. We show that, as one increases the rate of post-selection, this non-Hermitian Hamiltonian undergoes a spectral phase transition. On one side of this phase transition (for weak post-selection) an initially mixed density matrix remains mixed at all times, and an initially unentangled state develops volume-law entanglement; on the other side, an arbitrary initial state approaches a unique pure state with low entanglement. We identify this transition with an exceptional point in the spectrum of the non-Hermitian Hamiltonian, at which PT symmetry is spontaneously broken. We characterize the transition as well as the nontrivial steady state that emerges at late times in the mixed phase using exact diagonalization and an approximate, analytically tractable mean-field theory; these methods yield consistent conclusions.

1 aGopalakrishnan, Sarang1 aGullans, Michael uhttps://arxiv.org/abs/2012.0143502215nas a2200169 4500008004100000245006400041210006300105260001300168490000700181520171100188100002101899700002101920700002701941700002001968700002001988856003702008 2021 eng d00aEntanglement Phase Transitions in Measurement-Only Dynamics0 aEntanglement Phase Transitions in MeasurementOnly Dynamics c1/2/20210 v113 a

Unitary circuits subject to repeated projective measurements can undergo an entanglement phase transition (EPT) as a function of the measurement rate. This transition is generally understood in terms of a competition between the scrambling effects of unitary dynamics and the disentangling effects of measurements. We find that, surprisingly, EPTs are possible even in the absence of scrambling unitary dynamics, where they are best understood as arising from measurements alone. This motivates us to introduce \emph{measurement-only models}, in which the "scrambling" and "un-scrambling" effects driving the EPT are fundamentally intertwined and cannot be attributed to physically distinct processes. This represents a novel form of an EPT, conceptually distinct from that in hybrid unitary-projective circuits. We explore the entanglement phase diagrams, critical points, and quantum code properties of some of these measurement-only models. We find that the principle driving the EPTs in these models is \emph{frustration}, or mutual incompatibility, of the measurements. Suprisingly, an entangling (volume-law) phase is the generic outcome when measuring sufficiently long but still local (≳3-body) operators. We identify a class of exceptions to this behavior ("bipartite ensembles") which cannot sustain an entangling phase, but display dual area-law phases, possibly with different kinds of quantum order, separated by self-dual critical points. Finally, we introduce a measure of information spreading in dynamics with measurements and use it to demonstrate the emergence of a statistical light-cone, despite the non-locality inherent to quantum measurements.

1 aIppoliti, Matteo1 aGullans, Michael1 aGopalakrishnan, Sarang1 aHuse, David, A.1 aKhemani, Vedika uhttps://arxiv.org/abs/2004.0956001608nas a2200145 4500008004100000245006400041210006400105260001400169520115800183100002201341700002401363700001801387700002001405856003701425 2021 eng d00aEstimating distinguishability measures on quantum computers0 aEstimating distinguishability measures on quantum computers c8/18/20213 a

The performance of a quantum information processing protocol is ultimately judged by distinguishability measures that quantify how distinguishable the actual result of the protocol is from the ideal case. The most prominent distinguishability measures are those based on the fidelity and trace distance, due to their physical interpretations. In this paper, we propose and review several algorithms for estimating distinguishability measures based on trace distance and fidelity, and we evaluate their performance using simulators of quantum computers. The algorithms can be used for distinguishing quantum states, channels, and strategies (the last also known in the literature as "quantum combs"). The fidelity-based algorithms offer novel physical interpretations of these distinguishability measures in terms of the maximum probability with which a single prover (or competing provers) can convince a verifier to accept the outcome of an associated computation. We simulate these algorithms by using a variational approach with parameterized quantum circuits and find that they converge well for the examples that we consider. 

1 aAgarwal, Rochisha1 aRethinasamy, Soorya1 aSharma, Kunal1 aWilde, Mark, M. uhttps://arxiv.org/abs/2108.0840601306nas a2200121 4500008004100000245007000041210006900111260001500180520091800195100001601113700001801129856003701147 2021 eng d00aExactly Solvable Lattice Hamiltonians and Gravitational Anomalies0 aExactly Solvable Lattice Hamiltonians and Gravitational Anomalie c10/27/20213 a

We construct infinitely many new exactly solvable local commuting projector lattice Hamiltonian models for general bosonic beyond group cohomology invertible topological phases of order two and four in any spacetime dimensions, whose boundaries are characterized by gravitational anomalies. Examples include the beyond group cohomology invertible phase without symmetry in (4+1)D that has an anomalous boundary Z2 topological order with fermionic particle and fermionic loop excitations that have mutual π statistics. We argue that this construction gives a new non-trivial quantum cellular automaton (QCA) in (4+1)D of order two. We also present an explicit construction of gapped symmetric boundary state for the bosonic beyond group cohomology invertible phase with unitary Z2 symmetry in (4+1)D. We discuss new quantum phase transitions protected by different invertible phases across the transitions.

1 aChen, Yu-An1 aHsin, Po-Shen uhttps://arxiv.org/abs/2110.1464402180nas a2200181 4500008004100000245003100041210003100072260001200103520171100115100001901826700001301845700001701858700001701875700001701892700001501909700001901924856005501943 2021 eng d00aExpanding the VOQC Toolkit0 aExpanding the VOQC Toolkit c06/20213 a

voqc [Hietala et al. 2021b] (pronounced “vox”) is a compiler for quantum circuits, in the style of
tools like Qiskit [Aleksandrowicz et al. 2019], tket [Cambridge Quantum Computing Ltd 2019],
Quilc [Rigetti Computing 2019], and Cirq [Developers 2021]. What makes voqc different from these
tools is that it has been formally verified in the Coq proof assistant [Coq Development Team 2019].
voqc source programs are expressed in sqir, a simple quantum intermediate representation, which
has a precise mathematical semantics. We use Gallina, Coq’s programming language, to implement
voqc transformations over sqir programs, and use Coq to prove the source program’s semantics
are preserved. We then extract these Gallina definitions to OCaml, and compile the OCaml code to
a library that can operate on standard-formatted circuits.
voqc, and sqir, were built to be general-purpose. For example, while we originally designed sqir
for use in verified optimizations, we subsequently found sqir could also be suitable for writing, and
proving correct, source programs [Hietala et al. 2021a]. We have continued to develop the voqc
codebase to expand its reach and utility.
In this abstract, we present new extensions to voqc as an illustration of its flexibility. These
include support for calling voqc transformations from Python, added support for new gate sets
and optimizations, and the extension of our notion of correctness to include mapping-preservation,
which allows us to apply optimizations after mapping, reducing the cost introduced by making a
program conform to hardware constraints.

1 aHietala, Kesha1 aLi, Liyi1 aGaur, Akshaj1 aGreen, Aaron1 aRand, Robert1 aWu, Xiaodi1 aHicks, Michael uhttp://rand.cs.uchicago.edu/files/planqc_2021c.pdf00984nas a2200133 4500008004100000245005500041210005100096260001400147520059000161100002600751700001700777700001900794856003700813 2021 eng d00aAn explicit vector algorithm for high-girth MaxCut0 aexplicit vector algorithm for highgirth MaxCut c8/27/20213 a

We give an approximation algorithm for MaxCut and provide guarantees on the average fraction of edges cut on d-regular graphs of girth ≥2k. For every d≥3 and k≥4, our approximation guarantees are better than those of all other classical and quantum algorithms known to the authors. Our algorithm constructs an explicit vector solution to the standard semidefinite relaxation of MaxCut and applies hyperplane rounding. It may be viewed as a simplification of the previously best known technique, which approximates Gaussian wave processes on the infinite d-regular tree.

1 aThompson, Jessica, K.1 aParekh, Ojas1 aMarwaha, Kunal uhttps://arxiv.org/abs/2108.1247701856nas a2200121 4500008004100000245005700041210005700098260001400155520150000169100001301669700001501682856003701697 2021 eng d00aExploiting anticommutation in Hamiltonian simulation0 aExploiting anticommutation in Hamiltonian simulation c3/14/20213 a

Quantum computing can efficiently simulate Hamiltonian dynamics of many-body quantum physics, a task that is generally intractable with classical computers. The hardness lies at the ubiquitous anti-commutative relations of quantum operators, in corresponding with the notorious negative sign problem in classical simulation. Intuitively, Hamiltonians with more commutative terms are also easier to simulate on a quantum computer, and anti-commutative relations generally cause more errors, such as in the product formula method. Here, we theoretically explore the role of anti-commutative relation in Hamiltonian simulation. We find that, contrary to our intuition, anti-commutative relations could also reduce the hardness of Hamiltonian simulation. Specifically, Hamiltonians with mutually anti-commutative terms are easy to simulate, as what happens with ones consisting of mutually commutative terms. Such a property is further utilized to reduce the algorithmic error or the gate complexity in the truncated Taylor series quantum algorithm for general problems. Moreover, we propose two modified linear combinations of unitaries methods tailored for Hamiltonians with different degrees of anti-commutation. We numerically verify that the proposed methods exploiting anti-commutative relations could significantly improve the simulation accuracy of electronic Hamiltonians. Our work sheds light on the roles of commutative and anti-commutative relations in simulating quantum systems.

1 aZhao, Qi1 aYuan, Xiao uhttps://arxiv.org/abs/2103.0798801673nas a2200145 4500008004100000245006300041210006300104260001400167300001600181490000800197520125000205100001601455700001501471856004101486 2021 eng d00aExponentially Many Local Minima in Quantum Neural Networks0 aExponentially Many Local Minima in Quantum Neural Networks c10/5/2021 a12144-121550 v1393 a

Quantum Neural Networks (QNNs), or the so-called variational quantum circuits, are important quantum applications both because of their similar promises as classical neural networks and because of the feasibility of their implementation on near-term intermediate-size noisy quantum machines (NISQ). However, the training task of QNNs is challenging and much less understood. We conduct a quantitative investigation on the landscape of loss functions of QNNs and identify a class of simple yet extremely hard QNN instances for training. Specifically, we show for typical under-parameterized QNNs, there exists a dataset that induces a loss function with the number of spurious local minima depending exponentially on the number of parameters. Moreover, we show the optimality of our construction by providing an almost matching upper bound on such dependence. While local minima in classical neural networks are due to non-linear activations, in quantum neural networks local minima appear as a result of the quantum interference phenomenon. Finally, we empirically confirm that our constructions can indeed be hard instances in practice with typical gradient-based optimizers, which demonstrates the practical value of our findings. 

1 aYou, Xuchen1 aWu, Xiaodi uhttps://arxiv.org/pdf/2110.02479.pdf01710nas a2200121 4500008004100000245011300041210006900154260001400223520127200237100002201509700002001531856003701551 2020 eng d00aEffective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians0 aEffective gaps are not effective quasipolynomial classical simul c4/21/20203 a

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

1 aBringewatt, Jacob1 aJarret, Michael uhttps://arxiv.org/abs/2004.0868101938nas a2200145 4500008004100000245007300041210006900114260001300183490000600196520143200202100001801634700001601652700001901668856010501687 2020 eng d00aEfficient randomness certification by quantum probability estimation0 aEfficient randomness certification by quantum probability estima c1/7/20200 v23 a

For practical applications of quantum randomness generation, it is important to certify and further produce a fixed block of fresh random bits with as few trials as possible. Consequently, protocols with high finite-data efficiency are preferred. To yield such protocols with respect to quantum side information, we develop quantum probability estimation. Our approach is applicable to device-independent as well as device-dependent scenarios, and it generalizes techniques from previous works [Miller and Shi, SIAM J. Comput. 46, 1304 (2017); Arnon-Friedman et al., Nat. Commun. 9, 459 (2018)]. Quantum probability estimation can adapt to changing experimental conditions, allows stopping the experiment as soon as the prespecified randomness goal is achieved, and can tolerate imperfect knowledge of the input distribution. Moreover, the randomness rate achieved at constant error is asymptotically optimal. For the device-independent scenario, our approach certifies the amount of randomness available in experimental results without first searching for relations between randomness and violations of fixed Bell inequalities. We implement quantum probability estimation for device-independent randomness generation in the CHSH Bell-test configuration, and we show significant improvements in finite-data efficiency, particularly at small Bell violations which are typical in current photonic loophole-free Bell tests.

1 aZhang, Yanbao1 aFu, Honghao1 aKnill, Emanuel uhttps://quics.umd.edu/publications/efficient-randomness-certification-quantum-probability-estimation01901nas a2200157 4500008004100000245006300041210006300104260001300167300001200180490001000192520138200202100001901584700002201603700002301625856009501648 2020 eng d00aEfficient Simulation of Random States and Random Unitaries0 aEfficient Simulation of Random States and Random Unitaries c5/1/2020 a759-7870 v121073 a

We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access.

This problem has previously only been considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known that t-designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined in a recent work of Ji, Liu, and Song; unfortunately, no provably secure construction is known for PRUs.

In our setting, we are concerned with unbounded adversaries. Nonetheless, we are able to give stateful quantum algorithms which simulate the ideal object in both settings of interest. In the case of Haar-random states, our simulator is polynomial-time, has negligible error, and can also simulate verification and reflection through the simulated state. This yields an immediate application to quantum money: a money scheme which is information-theoretically unforgeable and untraceable. In the case of Haar-random unitaries, our simulator takes polynomial space, but simulates both forward and inverse access with zero error.

These results can be seen as the first significant steps in developing a theory of lazy sampling for random quantum objects.

1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander uhttps://quics.umd.edu/publications/efficient-simulation-random-states-and-random-unitaries01893nas a2200145 4500008004100000245006300041210006300104260001300167490000800180520147500188100001401663700002001677700001301697856003701710 2020 eng d00aEfficiently computable bounds for magic state distillation0 aEfficiently computable bounds for magic state distillation c3/6/20200 v1243 a

Magic state manipulation is a crucial component in the leading approaches to realizing scalable, fault-tolerant, and universal quantum computation. Related to magic state manipulation is the resource theory of magic states, for which one of the goals is to characterize and quantify quantum "magic." In this paper, we introduce the family of thauma measures to quantify the amount of magic in a quantum state, and we exploit this family of measures to address several open questions in the resource theory of magic states. As a first application, we use the min-thauma to bound the regularized relative entropy of magic. As a consequence of this bound, we find that two classes of states with maximal mana, a previously established magic measure, cannot be interconverted in the asymptotic regime at a rate equal to one. This result resolves a basic question in the resource theory of magic states and reveals a fundamental difference between the resource theory of magic states and other resource theories such as entanglement and coherence. As a second application, we establish the hypothesis testing thauma as an efficiently computable benchmark for the one-shot distillable magic, which in turn leads to a variety of bounds on the rate at which magic can be distilled, as well as on the overhead of magic state distillation. Finally, we prove that the max-thauma can outperform mana in benchmarking the efficiency of magic state distillation. 

1 aWang, Xin1 aWilde, Mark, M.1 aSu, Yuan uhttps://arxiv.org/abs/1812.1014501493nas a2200193 4500008004100000245007800041210006900119260001400188490000600202520090100208100002201109700001401131700002101145700002401166700002301190700002401213700002501237856003701262 2020 eng d00aEntanglement Bounds on the Performance of Quantum Computing Architectures0 aEntanglement Bounds on the Performance of Quantum Computing Arch c9/22/20200 v23 a

There are many possible architectures for future quantum computers that designers will need to choose between. However, the process of evaluating a particular connectivity graph's performance as a quantum architecture can be difficult. In this paper, we establish a connection between a quantity known as the isoperimetric number and a lower bound on the time required to create highly entangled states. The metric we propose counts resources based on the use of two-qubit unitary operations, while allowing for arbitrarily fast measurements and classical feedback. We describe how these results can be applied to the evaluation of the hierarchical architecture proposed in Phys. Rev. A 98, 062328 (2018). We also show that the time-complexity bound we place on the creation of highly-entangled states can be saturated up to a multiplicative factor logarithmic in the number of qubits.

1 aEldredge, Zachary1 aZhou, Leo1 aBapat, Aniruddha1 aGarrison, James, R.1 aDeshpande, Abhinav1 aChong, Frederic, T.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1908.0480201656nas a2200157 4500008004100000245008100041210006900122260001500191520114900206100002801355700001701383700001801400700002201418700002101440856003701461 2020 eng d00aEntanglement entropy scaling transition under competing monitoring protocols0 aEntanglement entropy scaling transition under competing monitori c08/19/20203 a

Dissipation generally leads to the decoherence of a quantum state. In contrast, numerous recent proposals have illustrated that dissipation can also be tailored to stabilize many-body entangled quantum states. While the focus of these works has been primarily on engineering the non-equilibrium steady state, we investigate the build-up of entanglement in the quantum trajectories. Specifically, we analyze the competition between two different dissipation channels arising from two incompatible continuous monitoring protocols. The first protocol locks the phase of neighboring sites upon registering a quantum jump, thereby generating a long-range entanglement through the system, while the second one destroys the coherence via dephasing mechanism. By studying the unraveling of stochastic quantum trajectories associated with the continuous monitoring protocols, we present a transition for the scaling of the averaged trajectory entanglement entropies, from critical scaling to area-law behavior. Our work provides novel insights into the occurrence of a measurement-induced phase transition within a continuous monitoring protocol.

1 aVan Regemortel, Mathias1 aCian, Ze-Pei1 aSeif, Alireza1 aDehghani, Hossein1 aHafezi, Mohammad uhttps://arxiv.org/abs/2008.0861901709nas a2200205 4500008004100000245006400041210006200105260001400167490000800181520108400189100002401273700002101297700002301318700002801341700003001369700002401399700001801423700002501441856003701466 2020 eng d00aExotic photonic molecules via Lennard-Jones-like potentials0 aExotic photonic molecules via LennardJoneslike potentials c9/19/20200 v1253 a

Ultracold systems offer an unprecedented level of control of interactions between atoms. An important challenge is to achieve a similar level of control of the interactions between photons. Towards this goal, we propose a realization of a novel Lennard-Jones-like potential between photons coupled to the Rydberg states via electromagnetically induced transparency (EIT). This potential is achieved by tuning Rydberg states to a F{ö}rster resonance with other Rydberg states. We consider few-body problems in 1D and 2D geometries and show the existence of self-bound clusters ("molecules") of photons. We demonstrate that for a few-body problem, the multi-body interactions have a significant impact on the geometry of the molecular ground state. This leads to phenomena without counterparts in conventional systems: For example, three photons in 2D preferentially arrange themselves in a line-configuration rather than in an equilateral-triangle configuration. Our result opens a new avenue for studies of many-body phenomena with strongly interacting photons.

1 aBienias, Przemyslaw1 aGullans, Michael1 aKalinowski, Marcin1 aCraddock, Alexander, N.1 aOrnelas-Huerta, Dalia, P.1 aRolston, Steven, L.1 aPorto, J., V.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2003.0786401465nas a2200265 4500008004100000245006700041210006500108260001500173490000800188520070100196100001800897700002200915700002500937700002400962700002500986700001801011700002101029700002001050700002501070700001601095700001701111700001501128700001901143856003701162 2020 eng d00aExperimental Low-Latency Device-Independent Quantum Randomness0 aExperimental LowLatency DeviceIndependent Quantum Randomness c12/24/20190 v1243 a

Applications of randomness such as private key generation and public randomness beacons require small blocks of certified random bits on demand. Device-independent quantum random number generators can produce such random bits, but existing quantum-proof protocols and loophole-free implementations suffer from high latency, requiring many hours to produce any random bits. We demonstrate device-independent quantum randomness generation from a loophole-free Bell test with a more efficient quantum-proof protocol, obtaining multiple blocks of 512 bits with an average experiment time of less than 5 min per block and with certified error bounded by 2−64≈5.42×10−20.

1 aZhang, Yanbao1 aShalm, Lynden, K.1 aBienfang, Joshua, C.1 aStevens, Martin, J.1 aMazurek, Michael, D.1 aNam, Sae, Woo1 aAbellán, Carlos1 aAmaya, Waldimar1 aMitchell, Morgan, W.1 aFu, Honghao1 aMiller, Carl1 aMink, Alan1 aKnill, Emanuel uhttps://arxiv.org/abs/1812.0778601260nas a2200133 4500008004100000245006500041210006000106260001400166520085200180100001901032700001901051700001901070856003701089 2020 eng d00aAn exponential ramp in the quadratic Sachdev-Ye-Kitaev model0 aexponential ramp in the quadratic SachdevYeKitaev model c6/26/20203 a

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

1 aWiner, Michael1 aJian, Shao-Kai1 aSwingle, Brian uhttps://arxiv.org/abs/2006.1515201930nas a2200133 4500008004100000245008000041210006900121260001400190520148400204100002801688700002701716700001601743856003701759 2019 eng d00aEquilibration to the non-Abelian thermal state in quantum many-body physics0 aEquilibration to the nonAbelian thermal state in quantum manybod c6/21/20193 a

In statistical mechanics, a small system exchanges conserved charges---heat, particles, electric charge, etc.---with a bath. The small system thermalizes to the canonical ensemble, or the grand canonical ensemble, etc., depending on the charges. The charges are usually represented by operators assumed to commute with each other. This assumption was removed within quantum-information-theoretic (QI-theoretic) thermodynamics recently. The small system's long-time state was dubbed "the non-Abelian thermal state (NATS)." We propose an experimental protocol for observing a system thermalize to the NATS. We illustrate with a chain of spins, a subset of which form the system of interest. The conserved charges manifest as spin components. Heisenberg interactions push the charges between the system and the effective bath, the rest of the chain. We predict long-time expectation values, extending the NATS theory from abstract idealization to finite systems that thermalize with finite couplings for finite times. Numerical simulations support the analytics: The system thermalizes to the NATS, rather than to the canonical prediction. Our proposal can be implemented with ultracold atoms, nitrogen-vacancy centers, trapped ions, quantum dots, and perhaps nuclear magnetic resonance. This work introduces noncommuting charges from QI-theoretic thermodynamics into quantum many-body physics: atomic, molecular, and optical physics and condensed matter. 

1 aHalpern, Nicole, Yunger1 aBeverland, Michael, E.1 aKalev, Amir uhttps://arxiv.org/abs/1906.0922701662nas a2200217 4500008004100000245004200041210004000083260001500123300001200138490000600150520105500156100002101211700002201232700002101254700002201275700002301297700001601320700001901336700001601355856007301371 2018 eng d00aElectro-mechano-optical NMR detection0 aElectromechanooptical NMR detection c2018/02/01 a152-1580 v53 a

Signal reception of nuclear magnetic resonance (NMR) usually relies on electrical amplification of the electromotive force caused by nuclear induction. Here, we report up-conversion of a radio-frequency NMR signal to an optical regime using a high-stress silicon nitride membrane that interfaces the electrical detection circuit and an optical cavity through the electro-mechanical and the opto-mechanical couplings. This enables optical NMR detection without sacrificing the versatility of the traditional nuclear induction approach. While the signal-to-noise ratio is currently limited by the Brownian motion of the membrane as well as additional technical noise, we find it can exceed that of the conventional electrical schemes by increasing the electro-mechanical coupling strength. The electro-mechano-optical NMR detection presented here can even be combined with the laser cooling technique applied to nuclear spins.

1 aTakeda, Kazuyuki1 aNagasaka, Kentaro1 aNoguchi, Atsushi1 aYamazaki, Rekishu1 aNakamura, Yasunobu1 aIwase, Eiji1 aTaylor, J., M.1 aUsami, Koji uhttps://www.osapublishing.org/optica/abstract.cfm?uri=optica-5-2-15202284nas a2200145 4500008004100000245007200041210006900113260001500182520181800197100001802015700002302033700001902056700002602075856003702101 2018 eng d00aElectro-optomechanical equivalent circuits for quantum transduction0 aElectrooptomechanical equivalent circuits for quantum transducti c2018/10/153 a

Using the techniques of optomechanics, a high-Q mechanical oscillator may serve as a link between electromagnetic modes of vastly different frequencies. This approach has successfully been exploited for the frequency conversion of classical signals and has the potential of performing quantum state transfer between superconducting circuitry and a traveling optical signal. Such transducers are often operated in a linear regime, where the hybrid system can be described using linear response theory based on the Heisenberg-Langevin equations. While mathematically straightforward to solve, this approach yields little intuition about the dynamics of the hybrid system to aid the optimization of the transducer. As an analysis and design tool for such electro-optomechanical transducers, we introduce an equivalent circuit formalism, where the entire transducer is represented by an electrical circuit. Thereby we integrate the transduction functionality of optomechanical (OM) systems into the toolbox of electrical engineering allowing the use of its well-established design techniques. This unifying impedance description can be applied both for static (DC) and harmonically varying (AC) drive fields, accommodates arbitrary linear circuits, and is not restricted to the resolved-sideband regime. Furthermore, by establishing the quantized input/output formalism for the equivalent circuit, we obtain the scattering matrix for linear transducers using circuit analysis, and thereby have a complete quantum mechanical characterization of the transducer. Hence, this mapping of the entire transducer to the language of electrical engineering both sheds light on how the transducer performs and can at the same time be used to optimize its performance by aiding the design of a suitable electrical circuit.

1 aZeuthen, Emil1 aSchliesser, Albert1 aTaylor, J., M.1 aSørensen, Anders, S. uhttps://arxiv.org/abs/1710.1013601867nas a2200157 4500008004100000245008200041210006900123260001500192300001100207490000600218520138400224100001701608700002201625700002501647856003701672 2018 eng d00aEnergy-level statistics in strongly disordered systems with power-law hopping0 aEnergylevel statistics in strongly disordered systems with power c2018/07/16 a0142010 vB3 a

Motivated by neutral excitations in disordered electronic materials and systems of trapped ultracold particles with long-range interactions, we study energy-level statistics of quasiparticles with the power-law hopping Hamiltonian ∝1/rα in a strong random potential. In solid-state systems such quasiparticles, which are exemplified by neutral dipolar excitations, lead to long-range correlations of local observables and may dominate energy transport. Focussing on the excitations in disordered electronic systems, we compute the energy-level correlation function R2(ω) in a finite system in the limit of sufficiently strong disorder. At small energy differences the correlations exhibit Wigner-Dyson statistics. In particular, in the limit of very strong disorder the energy-level correlation function is given by R2(ω,V)=A3ωωV for small frequencies ω≪ωV and R2(ω,V)=1−(α−d)A1(ωVω)dα−A2(ωVω)2 for large frequencies ω≫ωV, where ωV∝V−αd is the characteristic matrix element of excitation hopping in a system of volume V, and A1, A2 and A3 are coefficient of order unity which depend on the shape of the system. The energy-level correlation function, which we study, allows for a direct experimental observation, for example, by measuring the correlations of the ac conductance of the system at different frequencies.

1 aTitum, Paraj1 aQuito, Victor, L.1 aSyzranov, Sergey, V. uhttps://arxiv.org/abs/1803.1117801648nas a2200169 4500008004100000245006500041210006400106260001500170300000700185520110300192100001701295700002101312700002601333700002501359700001901384856007501403 2018 eng d00aEntanglement of purification: from spin chains to holography0 aEntanglement of purification from spin chains to holography c2018/01/22 a983 a

Purification is a powerful technique in quantum physics whereby a mixed quantum state is extended to a pure state on a larger system. This process is not unique, and in systems composed of many degrees of freedom, one natural purification is the one with minimal entanglement. Here we study the entropy of the minimally entangled purification, called the entanglement of purification, in three model systems: an Ising spin chain, conformal field theories holographically dual to Einstein gravity, and random stabilizer tensor networks. We conjecture values for the entanglement of purification in all these models, and we support our conjectures with a variety of numerical and analytical results. We find that such minimally entangled purifications have a number of applications, from enhancing entanglement-based tensor network methods for describing mixed states to elucidating novel aspects of the emergence of geometry from entanglement in the AdS/CFT correspondence.

1 aNguyen, Phuc1 aDevakul, Trithep1 aHalbasch, Matthew, G.1 aZaletel, Michael, P.1 aSwingle, Brian uhttps://link.springer.com/article/10.1007%2FJHEP01%282018%29098#citeas06978nas a2200109 4500008004100000245009100041210006900132520659600201100001406797700002006811856003706831 2018 eng d00aExact entanglement cost of quantum states and channels under PPT-preserving operations0 aExact entanglement cost of quantum states and channels under PPT3 a

This paper establishes single-letter formulas for the exact entanglement cost of generating bipartite quantum states and simulating quantum channels under free quantum operations that completely preserve positivity of the partial transpose (PPT). First, we establish that the exact entanglement cost of any bipartite quantum state under PPT-preserving operations is given by a single-letter formula, here called the κ-entanglement of a quantum state. This formula is calculable by a semidefinite program, thus allowing for an efficiently computable solution for general quantum states. Notably, this is the first time that an entanglement measure for general bipartite states has been proven not only to possess a direct operational meaning but also to be efficiently computable, thus solving a question that has remained open since the inception of entanglement theory over two decades ago. Next, we introduce and solve the exact entanglement cost for simulating quantum channels in both the parallel and sequential settings, along with the assistance of free PPT-preserving operations. The entanglement cost in both cases is given by the same single-letter formula and is equal to the largest κ-entanglement that can be shared by the sender and receiver of the channel. It is also efficiently computable by a semidefinite program. 

1 aWang, Xin1 aWilde, Mark, M. uhttps://arxiv.org/abs/1809.0959202638nas a2200265 4500008004100000245009500041210006900136260001500205300001200220490000800232520186000240100002102100700001902121700001802140700001802158700001502176700002002191700001902211700001602230700002502246700001802271700002402289700002202313856003702335 2018 eng d00aExperimentally Generated Randomness Certified by the Impossibility of Superluminal Signals0 aExperimentally Generated Randomness Certified by the Impossibili c2018/04/11 a223-2260 v5563 a

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

1 aBierhorst, Peter1 aKnill, Emanuel1 aGlancy, Scott1 aZhang, Yanbao1 aMink, Alan1 aJordan, Stephen1 aRommal, Andrea1 aLiu, Yi-Kai1 aChristensen, Bradley1 aNam, Sae, Woo1 aStevens, Martin, J.1 aShalm, Lynden, K. uhttps://arxiv.org/abs/1803.0621901217nas a2200169 4500008004100000245006400041210006200105260001500167300001100182490000800193520070900201100001900910700002300929700003300952700002500985856003701010 2017 eng d00a{E}ntanglement area laws for long-range interacting systems0 aE ntanglement area laws for longrange interacting systems c2017/07/31 a0505010 v1193 a

We prove that the entanglement entropy of any state evolved under an arbitrary 1/rα long-range-interacting D-dimensional lattice spin Hamiltonian cannot change faster than a rate proportional to the boundary area for any α > D + 1. We also prove that for any α > 2D + 2, the ground state of such a Hamiltonian satisfies the entanglement area law if it can be transformed along a gapped adiabatic path into a ground state known to satisfy the area law. These results significantly generalize their existing counterparts for short-range interacting systems, and are useful for identifying dynamical phase transitions and quantum phase transitions in the presence of long-range interactions.

1 aGong, Zhe-Xuan1 aFoss-Feig, Michael1 aBrandão, Fernando, G. S. L.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1702.0536801309nas a2200133 4500008004100000245008000041210006900121260001500190300001300205490000700218520089600225100001801121856003601139 2017 eng d00aEfficient quantum algorithms for analyzing large sparse electrical networks0 aEfficient quantum algorithms for analyzing large sparse electric c2017/07/21 a987-10260 v173 a

Analyzing large sparse electrical networks is a fundamental task in physics, electrical engineering and computer science. We propose two classes of quantum algorithms for this task. The first class is based on solving linear systems, and the second class is based on using quantum walks. These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time poly(d, c,log(N),1/λ,1/ε), where N is the number of vertices in the network, d is the maximum unweighted degree of the vertices, c is the ratio of largest to smallest edge resistance, λ is the spectral gap of the normalized Laplacian of the network, and ε is the accuracy. Furthermore, we show that the polynomial dependence on 1/λ is necessary. This implies that our algorithms are optimal up to polynomial factors and cannot be signficantly improved.

1 aWang, Guoming uhttps://arxiv.org/abs/1311.185101386nas a2200145 4500008004100000245006200041210006200103260001500165300001200180490000700192520096400199100002301163700001701186856003701203 2017 eng d00aEfficient simulation of sparse Markovian quantum dynamics0 aEfficient simulation of sparse Markovian quantum dynamics c2017/09/01 a901-9470 v173 a

Quantum algorithms for simulating Hamiltonian dynamics have been extensively developed, but there has been much less work on quantum algorithms for simulating the dynamics of open quantum systems. We give the first efficient quantum algorithms for simulating Markovian quantum dynamics generated by Lindbladians that are not necessarily local. We introduce two approaches to simulating sparse Lindbladians. First, we show how to simulate Lindbladians that act within small invariant subspaces using a quantum algorithm to implement sparse Stinespring isometries. Second, we develop a method for simulating sparse Lindblad operators by concatenating a sequence of short-time evolutions. We also show limitations on Lindbladian simulation by proving a no-fast-forwarding theorem for simulating sparse Lindbladians in a black-box model.

1 aChilds, Andrew, M.1 aLi, Tongyang uhttps://arxiv.org/abs/1611.0554301805nas a2200217 4500008004100000245005000041210005000091260001500141300001100156490000800167520121700175100002101392700001401413700002401427700001801451700002001469700001701489700002501506700001901531856003701550 2017 eng d00aEfimov States of Strongly Interacting Photons0 aEfimov States of Strongly Interacting Photons c2017/12/04 a2336010 v1193 a

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

1 aGullans, Michael1 aDiehl, S.1 aRittenhouse, S., T.1 aRuzic, B., P.1 aD'Incao, J., P.1 aJulienne, P.1 aGorshkov, Alexey, V.1 aTaylor, J., M. uhttps://arxiv.org/abs/1709.0195501103nas a2200109 4500008004100000245008300041210006900124260001500193520073100208100001700939856003700956 2017 eng d00aAn Elementary Proof of Private Random Number Generation from Bell Inequalities0 aElementary Proof of Private Random Number Generation from Bell I c2017/07/203 a

The field of device-independent quantum cryptography has seen enormous success in the past several years, including security proofs for key distribution and random number generation that account for arbitrary imperfections in the devices used. Full security proofs in the field so far are long and technically deep. In this paper we show that the concept of the mirror adversary can be used to simplify device-independent proofs. We give a short proof that any bipartite Bell violation can be used to generate private random numbers. The proof is based on elementary techniques and is self-contained.

1 aMiller, Carl uhttps://arxiv.org/abs/1707.0659702145nas a2200205 4500008004100000245005800041210005700099260001500156300001100171490000700182520152100189100002301710700002101733700002201754700002101776700002501797700002101822700002701843856006901870 2017 eng d00aEmergent equilibrium in many-body optical bistability0 aEmergent equilibrium in manybody optical bistability c2017/04/17 a0438260 v953 a

Many-body systems constructed of quantum-optical building blocks can now be realized in experimental platforms ranging from exciton-polariton fluids to ultracold gases of Rydberg atoms, establishing a fascinating interface between traditional many-body physics and the driven-dissipative, non-equilibrium setting of cavity-QED. At this interface, the standard techniques and intuitions of both fields are called into question, obscuring issues as fundamental as the role of fluctuations, dimensionality, and symmetry on the nature of collective behavior and phase transitions. Here, we study the driven-dissipative Bose-Hubbard model, a minimal description of numerous atomic, optical, and solid-state systems in which particle loss is countered by coherent driving. Despite being a lattice version of optical bistability---a foundational and patently non-equilibrium model of cavity-QED---the steady state possesses an emergent equilibrium description in terms of a classical Ising model. We establish this picture by identifying a limit in which the quantum dynamics is asymptotically equivalent to non-equilibrium Langevin equations, which support a phase transition described by model A of the Hohenberg-Halperin classification. Numerical simulations of the Langevin equations corroborate this picture, producing results consistent with the behavior of a finite-temperature Ising model.

1 aFoss-Feig, Michael1 aNiroula, Pradeep1 aYoung, Jeremy, T.1 aHafezi, Mohammad1 aGorshkov, Alexey, V.1 aWilson, Ryan, M.1 aMaghrebi, Mohammad, F. uhttps://journals.aps.org/pra/abstract/10.1103/PhysRevA.95.04382602354nas a2200157 4500008004100000245007000041210006900111520185900180100001902039700002002058700002402078700001802102700001902120700002002139856003702159 2017 eng d00aEntanglement Wedge Reconstruction via Universal Recovery Channels0 aEntanglement Wedge Reconstruction via Universal Recovery Channel3 a

We apply and extend the theory of universal recovery channels from quantum information theory to address the problem of entanglement wedge reconstruction in AdS/CFT. It has recently been proposed that any low-energy local bulk operators in a CFT boundary region's entanglement wedge can be reconstructed on that boundary region itself. Existing work arguing for this proposal relies on algebraic consequences of the exact equivalence between bulk and boundary relative entropies, namely the theory of operator algebra quantum error correction. However, bulk and boundary relative entropies are only approximately equal in bulk effective field theory, and in similar situations it is known that predictions from exact entropic equalities can be qualitatively incorrect. The framework of universal recovery channels provides a robust demonstration of the entanglement wedge reconstruction conjecture in addition to new physical insights. Most notably, we find that a bulk operator acting in a given boundary region's entanglement wedge can be expressed as the response of the boundary region's modular Hamiltonian to a perturbation of the bulk state in the direction of the bulk operator. This formula can be interpreted as a noncommutative version of Bayes' rule that attempts to undo the noise induced by restricting to only a portion of the boundary, and has an integral representation in terms of modular flows. To reach these conclusions, we extend the theory of universal recovery channels to finite-dimensional operator algebras and demonstrate that recovery channels approximately preserve the multiplicative structure of the operator algebra

1 aCotler, Jordan1 aHayden, Patrick1 aPenington, Geoffrey1 aSalton, Grant1 aSwingle, Brian1 aWalter, Michael uhttps://arxiv.org/abs/1704.0583902985nas a2200157 4500008004100000245004900041210004900090260001500139300001100154490000700165520255000172100002002722700002302742700002502765856003702790 2017 eng d00aExact sampling hardness of Ising spin models0 aExact sampling hardness of Ising spin models c2017/09/14 a0323240 v963 a

We study the complexity of classically sampling from the output distribution of an Ising spin model, which can be implemented naturally in a variety of atomic, molecular, and optical systems. In particular, we construct a specific example of an Ising Hamiltonian that, after time evolution starting from a trivial initial state, produces a particular output configuration with probability very nearly proportional to the square of the permanent of a matrix with arbitrary integer entries. In a similar spirit to boson sampling, the ability to sample classically from the probability distribution induced by time evolution under this Hamiltonian would imply unlikely complexity theoretic consequences, suggesting that the dynamics of such a spin model cannot be efficiently simulated with a classical computer. Physical Ising spin systems capable of achieving problem-size instances (i.e., qubit numbers) large enough so that classical sampling of the output distribution is classically difficult in practice may be achievable in the near future. Unlike boson sampling, our current results only imply hardness of exact classical sampling, leaving open the important question of whether a much stronger approximate-sampling hardness result holds in this context. The latter is most likely necessary to enable a convincing experimental demonstration of quantum supremacy. As referenced in a recent paper [A. Bouland, L. Mancinska, and X. Zhang, in Proceedings of the 31st Conference on Computational Complexity (CCC 2016), Leibniz International Proceedings in Informatics (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2016)], our result completes the sampling hardness classification of two-qubit commuting Hamiltonians.

1 aFefferman, Bill1 aFoss-Feig, Michael1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1701.0316701311nas a2200157 4500008004100000245004900041210004900090260001500139490000700154520083300161100002100994700002501015700002001040700002501060856006801085 2017 eng d00aExactly soluble model of boundary degeneracy0 aExactly soluble model of boundary degeneracy c2017/01/250 v953 a

We investigate the topological degeneracy that can be realized in Abelian fractional quantum spin Hall states with multiply connected gapped boundaries. Such a topological degeneracy (also dubbed as "boundary degeneracy") does not require superconducting proximity effect and can be created by simply applying a depletion gate to the quantum spin Hall material and using a generic spin-mixing term (e.g., due to backscattering) to gap out the edge modes. We construct an exactly soluble microscopic model manifesting this topological degeneracy and solve it using the recently developed technique [S. Ganeshan and M. Levin, Phys. Rev. B 93, 075118 (2016)]. The corresponding string operators spanning this degeneracy are explicitly calculated. It is argued that the proposed scheme is experimentally reasonable.

1 aGaneshan, Sriram1 aGorshkov, Alexey, V.1 aGurarie, Victor1 aGalitski, Victor, M. uhttp://journals.aps.org/prb/abstract/10.1103/PhysRevB.95.04530901709nas a2200229 4500008004100000245006700041210006700108250000700175260001500182300001400197490000800211520106700219100001601286700001901302700002201321700001601343700001601359700002101375700001501396700002401411856004401435 2017 eng d00aExperimental Comparison of Two Quantum Computing Architectures0 aExperimental Comparison of Two Quantum Computing Architectures a13 c2017/03/21 a3305-33100 v1143 a

We run a selection of algorithms on two state-of-the-art 5-qubit quantum computers that are based on different technology platforms. One is a publicly accessible superconducting transmon device [1] with limited connectivity, and the other is a fully connected trapped-ion system [2]. Even though the two systems have different native quantum interactions, both can be programmed in a way that is blind to the underlying hardware, thus allowing the first comparison of identical quantum algorithms between different physical systems. We show that quantum algorithms and circuits that employ more connectivity clearly benefit from a better connected system of qubits. While the quantum systems here are not yet large enough to eclipse classical computers, this experiment exposes critical factors of scaling quantum computers, such as qubit connectivity and gate expressivity. In addition, the results suggest that co-designing particular quantum applications with the hardware itself will be paramount in successfully using quantum computers in the future.

1 aLinke, N.M.1 aMaslov, Dmitri1 aRoetteler, Martin1 aDebnath, S.1 aFiggatt, C.1 aLandsman, K., A.1 aWright, K.1 aMonroe, Christopher uhttp://www.pnas.org/content/114/13/330501121nas a2200169 4500008004100000245007000041210006900111260001500180300001100195490000800206520058700214100002200801700001900823700001900842700001700861856007300878 2017 eng d00aExperimental demonstration of cheap and accurate phase estimation0 aExperimental demonstration of cheap and accurate phase estimatio c2017/05/12 a1905020 v1183 a

We demonstrate experimental implementation of robust phase estimation (RPE) to learn the phases of X and Y rotations on a trapped Yb+ ion qubit. We estimate these phases with uncertainties less than 4 · 10−4 radians using as few as 176 total experimental samples per phase, and our estimates exhibit Heisenberg scaling. Unlike standard phase estimation protocols, RPE neither assumes perfect state preparation and measurement, nor requires access to ancillae. We cross-validate the results of RPE with the more resource-intensive protocol of gate set tomography.

1 aRudinger, Kenneth1 aKimmel, Shelby1 aLobser, Daniel1 aMaunz, Peter uhttps://journals.aps.org/prl/abstract/10.1103/PhysRevLett.118.19050201341nas a2200193 4500008004100000245007600041210006900117260001500186300001100201490000800212520075400220100002200974700001800996700002001014700001401034700002001048700001901068856006001087 2017 eng d00aExperimental Study of Optimal Measurements for Quantum State Tomography0 aExperimental Study of Optimal Measurements for Quantum State Tom c2017/10/13 a1504010 v1193 a

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

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

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

1 aBierhorst, Peter1 aKnill, Emanuel1 aGlancy, Scott1 aMink, Alan1 aJordan, Stephen, P.1 aRommal, Andrea1 aLiu, Yi-Kai1 aChristensen, Bradley1 aNam, Sae, Woo1 aShalm, Lynden, K. uhttps://arxiv.org/abs/1702.05178#01775nas a2200133 4500008004100000245007500041210006900116520134900185100001901534700001601553700001601569700001901585856003701604 2017 eng d00aExponential improvements for quantum-accessible reinforcement learning0 aExponential improvements for quantumaccessible reinforcement lea3 a

Quantum computers can offer dramatic improvements over classical devices for data analysis tasks such as prediction and classification. However, less is known about the advantages that quantum computers may bring in the setting of reinforcement learning, where learning is achieved via interaction with a task environment. Here, we consider a special case of reinforcement learning, where the task environment allows quantum access. In addition, we impose certain "naturalness" conditions on the task environment, which rule out the kinds of oracle problems that are studied in quantum query complexity (and for which quantum speedups are well-known). Within this framework of quantum-accessible reinforcement learning environments, we demonstrate that quantum agents can achieve exponential improvements in learning efficiency, surpassing previous results that showed only quadratic improvements. A key step in the proof is to construct task environments that encode well-known oracle problems, such as Simon's problem and Recursive Fourier Sampling, while satisfying the above "naturalness" conditions for reinforcement learning. Our results suggest that quantum agents may perform well in certain game-playing scenarios, where the game has recursive structure, and the agent can learn by playing against itself

1 aDunjko, Vedran1 aLiu, Yi-Kai1 aWu, Xingyao1 aTaylor, J., M. uhttps://arxiv.org/abs/1710.1116002582nas a2200169 4500008004100000245010100041210006900142260001500211520202200226100003302248700001602281700001702297700002402314700002202338700001502360856003702375 2017 eng d00aExponential Quantum Speed-ups for Semidefinite Programming with Applications to Quantum Learning0 aExponential Quantum Speedups for Semidefinite Programming with A c2017/10/063 a

We give semidefinite program (SDP) quantum solvers with an exponential speed-up over classical ones. Specifically, we consider SDP instances with m constraint matrices of dimension n, each of rank at most r, and assume that the input matrices of the SDP are given as quantum states (after a suitable normalization). Then we show there is a quantum algorithm that solves the SDP feasibility problem with accuracy ǫ by using √ m log m · poly(log n,r, ǫ −1 ) quantum gates. The dependence on n provides an exponential improvement over the work of Brand ˜ao and Svore [6] and the work of van Apeldoorn et al. [23], and demonstrates an exponential quantum speed-up when m and r are small. We apply the SDP solver to the problem of learning a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state ρ, we show we can find in time √ m log m · poly(log n,r, ǫ −1 ) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as ρ on the m measurements up to error ǫ. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes’ principle. As in previous work, we obtain our algorithm by “quantizing” classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension based on the techniques developed in quantum principal component analysis, which could be of independent interest. Our quantum SDP solver is different from previous ones in the following two aspects: (1) it follows from a zero-sum game approach of Hazan [11] of solving SDPs rather than the primal-dual approach by Arora and Kale [5]; and (2) it does not rely on any sparsity assumption of the input matrices.

1 aBrandão, Fernando, G. S. L.1 aKalev, Amir1 aLi, Tongyang1 aLin, Cedric, Yen-Yu1 aSvore, Krysta, M.1 aWu, Xiaodi uhttps://arxiv.org/abs/1710.0258101600nas a2200145 4500008004100000245005700041210005700098260001500155490000800170520117800178100002101356700002401377700001601401856003701417 2017 eng d00aExtracting entanglement geometry from quantum states0 aExtracting entanglement geometry from quantum states c2017/10/060 v1193 a

Tensor networks impose a notion of geometry on the entanglement of a quantum system. In some cases, this geometry is found to reproduce key properties of holographic dualities, and subsequently much work has focused on using tensor networks as tractable models for holographic dualities. Conventionally, the structure of the network - and hence the geometry - is largely fixed a priori by the choice of tensor network ansatz. Here, we evade this restriction and describe an unbiased approach that allows us to extract the appropriate geometry from a given quantum state. We develop an algorithm that iteratively finds a unitary circuit that transforms a given quantum state into an unentangled product state. We then analyze the structure of the resulting unitary circuits. In the case of non-interacting, critical systems in one dimension, we recover signatures of scale invariance in the unitary network, and we show that appropriately defined geodesic paths between physical degrees of freedom exhibit known properties of a hyperbolic geometry.

1 aHyatt, Katharine1 aGarrison, James, R.1 aBauer, Bela uhttps://arxiv.org/abs/1704.0197401360nas a2200181 4500008004100000022001400041245007000055210006900125260001500194520081800209100001801027700001901045700001801064700001301082700001901095700001601114856004801130 2017 eng d a1871-409900aExtreme learning machines for regression based on V-matrix method0 aExtreme learning machines for regression based on Vmatrix method c2017/06/103 a

This paper studies the joint effect of V-matrix, a recently proposed framework for statistical inferences, and extreme learning machine (ELM) on regression problems. First of all, a novel algorithm is proposed to efficiently evaluate the V-matrix. Secondly, a novel weighted ELM algorithm called V-ELM is proposed based on the explicit kernel mapping of ELM and the V-matrix method. Though V-matrix method could capture the geometrical structure of training data, it tends to assign a higher weight to instance with smaller input value. In order to avoid this bias, a novel method called VI-ELM is proposed by minimizing both the regression error and the V-matrix weighted error simultaneously. Finally, experiment results on 12 real world benchmark datasets show the effectiveness of our proposed methods.

1 aYang, Zhiyong1 aZhang, Taohong1 aLu, Jingcheng1 aSu, Yuan1 aZhang, Dezheng1 aDuan, Yaowu uhttp://dx.doi.org/10.1007/s11571-017-9444-201280nas a2200205 4500008004100000245005000041210005000091260001500141300001100156490000800167520073000175100002100905700002100926700001300947700001900960700001600979700001800995700002501013856003601038 2016 eng d00aEffective Field Theory for Rydberg Polaritons0 aEffective Field Theory for Rydberg Polaritons c2016/09/09 a1136010 v1173 a

We study non-perturbative effects in N-body scattering of Rydberg polaritons using effective field theory (EFT). We develop an EFT in one dimension and show how a suitably long medium can be used to prepare shallow N-body bound states. We then derive the effective N-body interaction potential for Rydberg polaritons and the associated N-body contact force that arises in the EFT. We use the contact force to find the leading order corrections to the binding energy of the N-body bound states and determine the photon number at which the EFT description breaks down. We find good agreement throughout between the predictions of EFT and numerical simulations of the exact two and three photon wavefunction transmission.

1 aGullans, Michael1 aThompson, J., D.1 aWang, Y.1 aLiang, Q., -Y.1 aVuletic, V.1 aLukin, M., D.1 aGorshkov, Alexey, V. uhttp://arxiv.org/abs/1605.0565101507nas a2200145 4500008004100000245007200041210006900113260001500182520103700197100002301234700001901257700002501276700002301301856003701324 2016 eng d00aEntanglement and spin-squeezing without infinite-range interactions0 aEntanglement and spinsqueezing without infiniterange interaction c2016/12/223 a

Infinite-range interactions are known to facilitate the production of highly entangled states with applications in quantum information and metrology. However, many experimental systems have interactions that decay with distance, and the achievable benefits in this context are much less clear. Combining recent exact solutions with a controlled expansion in the system size, we analyze quench dynamics in Ising models with power-law (1/r α ) interactions in D dimensions, thereby expanding the understanding of spin squeezing into a broad and experimentally relevant context. In spatially homogeneous systems, we show that for small α the scaling of squeezing with system size is identical to the infinite-range (α = 0) case. This indifference to the interaction range persists up to a critical value α = 2D/3, above which squeezing degrades continuously. Boundaryinduced inhomogeneities present in most experimental systems modify this picture, but it nevertheless remains qualitatively correct for finite-sized systems.

1 aFoss-Feig, Michael1 aGong, Zhe-Xuan1 aGorshkov, Alexey, V.1 aClark, Charles, W. uhttps://arxiv.org/abs/1612.0780501399nas a2200157 4500008004100000245008400041210006900125260001500194300001100209490000700220520091600227100001801143700001901161700001401180856004701194 2016 eng d00aEntangling distant resonant exchange qubits via circuit quantum electrodynamics0 aEntangling distant resonant exchange qubits via circuit quantum  c2016/11/16 a2054210 v943 a

We investigate a hybrid quantum system consisting of spatially separated resonant exchange qubits, defined in three-electron semiconductor triple quantum dots, that are coupled via a superconducting transmission line resonator. Drawing on methods from circuit quantum electrodynamics and Hartmann-Hahn double resonance techniques, we analyze three specific approaches for implementing resonator-mediated two-qubit entangling gates in both dispersive and resonant regimes of interaction. We calculate entangling gate fidelities as well as the rate of relaxation via phonons for resonant exchange qubits in silicon triple dots and show that such an implementation is particularly well-suited to achieving the strong coupling regime. Our approach combines the favorable coherence properties of encoded spin qubits in silicon with the rapid and robust long-range entanglement provided by circuit QED systems.

1 aSrinivasa, V.1 aTaylor, J., M.1 aTahan, C. uhttps://doi.org/10.1103/PhysRevB.94.20542101724nas a2200181 4500008004100000245005800041210005800099260001500157520121100172100001801383700001801401700002101419700001601440700001601456700001801472700001501490856003701505 2016 eng d00aExperimental demonstration of quantum fault tolerance0 aExperimental demonstration of quantum fault tolerance c2016/11/213 a

Quantum computers will eventually reach a size at which quantum error correction (QEC) becomes imperative. In order to make quantum information robust to errors introduced by qubit imperfections and flawed control operations, QEC protocols encode a logical qubit in multiple physical qubits. This redundancy allows the extraction of error syndromes and the subsequent correction or detection of errors without destroying the logical state itself through direct measurement. While several experiments have shown a reduction of high intrinsic or artificially introduced errors in logical qubits, fault-tolerant encoding of a logical qubit has never been demonstrated. Here we show the encoding and syndrome measurement of a fault-tolerant logical qubit via an error detection protocol on four physical qubits, represented by trapped atomic ions. This demonstrates for the first time the robustness of a fault-tolerant qubit to imperfections in the very operations used to encode it. This advantage persists in the face of large added error rates and experimental calibration errors.

1 aLinke, N., M.1 aGutierrez, M.1 aLandsman, K., A.1 aFiggatt, C.1 aDebnath, S.1 aBrown, K., R.1 aMonroe, C. uhttps://arxiv.org/abs/1611.0694602567nas a2200145 4500008004100000245007800041210006900119260001500188520211000203100001802313700002002331700001702351700001602368856003702384 2016 eng d00aExponential Separation of Quantum Communication and Classical Information0 aExponential Separation of Quantum Communication and Classical In c2016/11/283 a
We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. The function we use to present such a separation is the Symmetric k-ary Pointer Jumping function introduced by Rao and Sinha [ECCC TR15-057], whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence of round-elimination arguments, allowing us to simplify further the approach of Rao and Sinha. 
As another application of the techniques that we develop, we give a simple proof for an optimal trade-off between Alice's and Bob's communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/exp(O(b)) bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.
 
 
1 aAnshu, Anurag1 aTouchette, Dave1 aYao, Penghui1 aYu, Nengkun uhttps://arxiv.org/abs/1611.0894601233nas a2200145 4500008004100000245009700041210006900138260001500207300001100222490000800233520076600241100002701007700001601034856003701050 2015 eng d00aEntanglement entropy of dispersive media from thermodynamic entropy in one higher dimension0 aEntanglement entropy of dispersive media from thermodynamic entr c2015/04/16 a1516020 v1143 a A dispersive medium becomes entangled with zero-point fluctuations in the vacuum. We consider an arbitrary array of material bodies weakly interacting with a quantum field and compute the quantum mutual information between them. It is shown that the mutual information in D dimensions can be mapped to classical thermodynamic entropy in D+1 dimensions. As a specific example, we compute the mutual information both analytically and numerically for a range of separation distances between two bodies in D=2 dimensions and find a logarithmic correction to the area law at short separations. A key advantage of our method is that it allows the strong subadditivity property---notoriously difficult to prove for quantum systems---to be easily verified. 1 aMaghrebi, Mohammad, F.1 aReid, Homer uhttp://arxiv.org/abs/1412.5613v202223nas a2200193 4500008004100000245007100041210006900112260001500181300001200196490000800208520166400216100002001880700001901900700002301919700001701942700001601959700001801975856003601993 2015 eng d00aEntangling two transportable neutral atoms via local spin exchange0 aEntangling two transportable neutral atoms via local spin exchan c2015/11/02 a208-2110 v5273 a To advance quantum information science a constant pursuit is the search for physical systems that meet the stringent requirements for creating and preserving quantum entanglement. In atomic physics, robust two-qubit entanglement is typically achieved by strong, long-range interactions in the form of Coulomb interactions between ions or dipolar interactions between Rydberg atoms. While these interactions allow fast gates, atoms subject to these interactions must overcome the associated coupling to the environment and cross-talk among qubits. Local interactions, such as those requiring significant wavefunction overlap, can alleviate these detrimental effects yet present a new challenge: To distribute entanglement, qubits must be transported, merged for interaction, and then isolated for storage and subsequent operations. Here we show how, via a mobile optical tweezer, it is possible to prepare and locally entangle two ultracold neutral atoms, and then separate them while preserving their entanglement. While ultracold neutral atom experiments have measured dynamics consistent with spin entanglement, we are now able to demonstrate two-particle coherence via application of a local gradient and parity measurements; this new entanglement-verification protocol could be applied to arbitrary spin-entangled states of spatially-separated atoms. The local entangling operation is achieved via ultracold spin-exchange interactions, and quantum tunneling is used to combine and separate atoms. Our toolset provides a framework for dynamically entangling remote qubits via local operations within a large-scale quantum register. 1 aKaufman, A., M.1 aLester, B., J.1 aFoss-Feig, Michael1 aWall, M., L.1 aRey, A., M.1 aRegal, C., A. uhttp://arxiv.org/abs/1507.0558600594nas a2200145 4500008004100000245009000041210006900131260001500200100001700215700002900232700002300261700002000284700002600304856011800330 2014 eng d00a"Einstein and Bohr Meet Alice and Bob', Logic and Science Facing the New Technologies0 aEinstein and Bohr Meet Alice and Bob Logic and Science Facing th c2014/01/011 aBub, Jeffrey1 aSchroeder-Heister, Peter1 aHeinzmann, Gerhard1 aHodges, Wilfrid1 aBour, Pierre, Edouard uhttps://quics.umd.edu/publications/einstein-and-bohr-meet-alice-and-bob-logic-and-science-facing-new-technologies02001nas a2200181 4500008004100000020002200041245007600063210006900139260001500208300001200223520144000235100002301675700002301698700001901721700001901740700002301759856003701782 2014 eng d a978-1-4503-2710-700aExponential improvement in precision for simulating sparse Hamiltonians0 aExponential improvement in precision for simulating sparse Hamil c2014/05/31 a283-2923 a We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a $d$-sparse Hamiltonian $H$ acting on $n$ qubits can be simulated for time $t$ with precision $\epsilon$ using $O\big(\tau \frac{\log(\tau/\epsilon)}{\log\log(\tau/\epsilon)}\big)$ queries and $O\big(\tau \frac{\log^2(\tau/\epsilon)}{\log\log(\tau/\epsilon)}n\big)$ additional 2-qubit gates, where $\tau = d^2 \|{H}\|_{\max} t$. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error. 1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aCleve, Richard1 aKothari, Robin1 aSomma, Rolando, D. uhttp://arxiv.org/abs/1312.1414v201231nas a2200145 4500008004100000245014400041210006900185260001500254300001100269490000700280520070100287100002100988700002101009856005501030 2014 eng d00aExtended order parameter and conjugate field for the dynamic phase transition in a Ginzburg-Landau mean-field model in an oscillating field0 aExtended order parameter and conjugate field for the dynamic pha c2014/02/12 a0221140 v893 aWe present numerical evidence for an extended order parameter and conjugate field for the dynamic phase transition in a Ginzburg-Landau mean-field model driven by an oscillating field. The order parameter, previously taken to be the time-averaged magnetization, comprises the deviations of the Fourier components of the magnetization from their values at the critical period. The conjugate field, previously taken to be the time-averaged magnetic field, comprises the even Fourier components of the field. The scaling exponents β and δ associated with the extended order parameter and conjugate field are shown numerically to be consistent with their values in the equilibrium mean-field model.1 aRobb, Daniel, T.1 aOstrander, Aaron uhttp://link.aps.org/doi/10.1103/PhysRevE.89.02211401395nas a2200169 4500008004100000245006500041210006500106260001500171300001000186490000700196520090400203100002301107700001901130700001701149700002201166856003701188 2013 eng d00aEasy and hard functions for the Boolean hidden shift problem0 aEasy and hard functions for the Boolean hidden shift problem c2013/04/16 a50-790 v223 a We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact one-query algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state; its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem. 1 aChilds, Andrew, M.1 aKothari, Robin1 aOzols, Maris1 aRoetteler, Martin uhttp://arxiv.org/abs/1304.4642v101124nas a2200145 4500008004100000245007500041210006900116260001400185490000800199520068100207100001900888700001800907700001600925856003700941 2013 eng d00aElectrically-protected resonant exchange qubits in triple quantum dots0 aElectricallyprotected resonant exchange qubits in triple quantum c2013/7/310 v1113 aWe present a modulated microwave approach for quantum computing with qubits comprising three spins in a triple quantum dot. This approach includes single- and two-qubit gates that are protected against low-frequency electrical noise, due to an operating point with a narrowband response to high frequency electric fields. Furthermore, existing double quantum dot advances, including robust preparation and measurement via spin-to-charge conversion, are immediately applicable to the new qubit. Finally, the electric dipole terms implicit in the high frequency coupling enable strong coupling with superconducting microwave resonators, leading to more robust two-qubit gates. 1 aTaylor, J., M.1 aSrinivasa, V.1 aMedford, J. uhttp://arxiv.org/abs/1304.3407v201475nas a2200145 4500008004100000022001400041245007300055210006900128260001500197300001200212490000600224520104100230100001701271856004101288 2013 eng d a1551-305X00aEvasiveness of Graph Properties and Topological Fixed-Point Theorems0 aEvasiveness of Graph Properties and Topological FixedPoint Theor c2013/05/16 a337-4150 v73 a

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

1 aMiller, Carl uhttp://dx.doi.org/10.1561/040000005501243nas a2200181 4500008004100000245012700041210006900168260001400237490000700251520064800258100002100906700001900927700001700946700001500963700002200978700002401000856003701024 2013 eng d00aExperimental Performance of a Quantum Simulator: Optimizing Adiabatic Evolution and Identifying Many-Body Ground States 0 aExperimental Performance of a Quantum Simulator Optimizing Adiab c2013/7/310 v883 a We use local adiabatic evolution to experimentally create and determine the ground state spin ordering of a fully-connected Ising model with up to 14 spins. Local adiabatic evolution -- in which the system evolution rate is a function of the instantaneous energy gap -- is found to maximize the ground state probability compared with other adiabatic methods while only requiring knowledge of the lowest $\sim N$ of the $2^N$ Hamiltonian eigenvalues. We also demonstrate that the ground state ordering can be experimentally identified as the most probable of all possible spin configurations, even when the evolution is highly non-adiabatic. 1 aRicherme, Philip1 aSenko, Crystal1 aSmith, Jacob1 aLee, Aaron1 aKorenblit, Simcha1 aMonroe, Christopher uhttp://arxiv.org/abs/1305.2253v102074nas a2200157 4500008004100000245008100041210006900122260001500191490000700206520159700213100001501810700002001825700001901845700001501864856003701879 2012 eng d00aThe equilibrium states of open quantum systems in the strong coupling regime0 aequilibrium states of open quantum systems in the strong couplin c2012/12/260 v863 aIn this work we investigate the late-time stationary states of open quantum systems coupled to a thermal reservoir in the strong coupling regime. In general such systems do not necessarily relax to a Boltzmann distribution if the coupling to the thermal reservoir is non-vanishing or equivalently if the relaxation timescales are finite. Using a variety of non-equilibrium formalisms valid for non-Markovian processes, we show that starting from a product state of the closed system = system + environment, with the environment in its thermal state, the open system which results from coarse graining the environment will evolve towards an equilibrium state at late-times. This state can be expressed as the reduced state of the closed system thermal state at the temperature of the environment. For a linear (harmonic) system and environment, which is exactly solvable, we are able to show in a rigorous way that all multi-time correlations of the open system evolve towards those of the closed system thermal state. Multi-time correlations are especially relevant in the non-Markovian regime, since they cannot be generated by the dynamics of the single-time correlations. For more general systems, which cannot be exactly solved, we are able to provide a general proof that all single-time correlations of the open system evolve to those of the closed system thermal state, to first order in the relaxation rates. For the special case of a zero-temperature reservoir, we are able to explicitly construct the reduced closed system thermal state in terms of the environmental correlations. 1 aSubasi, Y.1 aFleming, C., H.1 aTaylor, J., M.1 aHu, B., L. uhttp://arxiv.org/abs/1206.2707v101007nas a2200145 4500008004100000245006100041210006000102260001500162300001000177490000700187520058600194100002700780700001700807856003700824 2011 eng d00aElectromagnetic Casimir Energies of Semi-Infinite Planes0 aElectromagnetic Casimir Energies of SemiInfinite Planes c2011/07/01 a140010 v953 a Using recently developed techniques based on scattering theory, we find the electromagnetic Casimir energy for geometries involving semi-infinite planes, a case that is of particular interest in the design of microelectromechanical devices. We obtain both approximate analytic formulae and exact results requiring only modest numerical computation. Using these results, we analyze the effects of edges and orientation on the Casimir energy. We also demonstrate the accuracy, simplicity, and utility of our approximation scheme, which is based on a multiple reflection expansion. 1 aMaghrebi, Mohammad, F.1 aGraham, Noah uhttp://arxiv.org/abs/1102.1486v101232nas a2200157 4500008004100000245005300041210005300094260001500147490000800162520078900170100001800959700002100977700002100998700001801019856003701037 2011 eng d00aEntanglement can completely defeat quantum noise0 aEntanglement can completely defeat quantum noise c2011/12/150 v1073 a We describe two quantum channels that individually cannot send any information, even classical, without some chance of decoding error. But together a single use of each channel can send quantum information perfectly reliably. This proves that the zero-error classical capacity exhibits superactivation, the extreme form of the superadditivity phenomenon in which entangled inputs allow communication over zero capacity channels. But our result is stronger still, as it even allows zero-error quantum communication when the two channels are combined. Thus our result shows a new remarkable way in which entanglement across two systems can be used to resist noise, in this case perfectly. We also show a new form of superactivation by entanglement shared between sender and receiver. 1 aChen, Jianxin1 aCubitt, Toby, S.1 aHarrow, Aram, W.1 aSmith, Graeme uhttp://arxiv.org/abs/1109.0540v101014nas a2200157 4500008004100000245004500041210004500086260001500131300001000146490000700156520059200163100002700755700001800782700001900800856003700819 2011 eng d00aEntropic force of polymers on a cone tip0 aEntropic force of polymers on a cone tip c2011/12/01 a660020 v963 a We consider polymers attached to the tip of a cone, and the resulting force due to entropy loss on approaching a plate (or another cone). At separations shorter than the polymer radius of gyration R_g, the only relevant length scale is the tip-plate (or tip-tip) separation h, and the entropic force is given by F=A kT/h. The universal amplitude A can be related to (geometry dependent) correlation exponents of long polymers. We compute A for phantom polymers, and for self-avoiding (including star) polymers by epsilon-expansion, as well as by numerical simulations in 3 dimensions. 1 aMaghrebi, Mohammad, F.1 aKantor, Yacov1 aKardar, Mehran uhttp://arxiv.org/abs/1109.5658v201192nas a2200133 4500008004100000245005800041210005800099260001500157520078600172100002900958700001600987700001801003856003701021 2010 eng d00aEfficient Direct Tomography for Matrix Product States0 aEfficient Direct Tomography for Matrix Product States c2010/02/243 a In this note, we describe a method for reconstructing matrix product states from a small number of efficiently-implementable measurements. Our method is exponentially faster than standard tomography, and it can also be used to certify that the unknown state is an MPS. The basic idea is to use local unitary operations to measure in the Schmidt basis, giving direct access to the MPS representation. This compares favorably with recently and independently proposed methods that recover the MPS tensors by performing a variational minimization, which is computationally intractable in certain cases. Our method also has the advantage of recovering any MPS, while other approaches were limited to special classes of states that exclude important examples such as GHZ and W states. 1 aLandon-Cardinal, Olivier1 aLiu, Yi-Kai1 aPoulin, David uhttp://arxiv.org/abs/1002.4632v101775nas a2200229 4500008004100000245003900041210003900080260001500119300000800134490000600142520116900148100001901317700002301336700002401359700001701383700002601400700001901426700002901445700001601474700001801490856003701508 2010 eng d00aEfficient quantum state tomography0 aEfficient quantum state tomography c2010/12/21 a1490 v13 a Quantum state tomography, the ability to deduce the state of a quantum system from measured data, is the gold standard for verification and benchmarking of quantum devices. It has been realized in systems with few components, but for larger systems it becomes infeasible because the number of quantum measurements and the amount of computation required to process them grows exponentially in the system size. Here we show that we can do exponentially better than direct state tomography for a wide range of quantum states, in particular those that are well approximated by a matrix product state ansatz. We present two schemes for tomography in 1-D quantum systems and touch on generalizations. One scheme requires unitary operations on a constant number of subsystems, while the other requires only local measurements together with more elaborate post-processing. Both schemes rely only on a linear number of experimental operations and classical postprocessing that is polynomial in the system size. A further strength of the methods is that the accuracy of the reconstructed states can be rigorously certified without any a priori assumptions. 1 aCramer, Marcus1 aPlenio, Martin, B.1 aFlammia, Steven, T.1 aGross, David1 aBartlett, Stephen, D.1 aSomma, Rolando1 aLandon-Cardinal, Olivier1 aLiu, Yi-Kai1 aPoulin, David uhttp://arxiv.org/abs/1101.4366v107538nas a2200145 4500008004100000022001400041245006900055210006600124260001500190300001200205490000600217520708300223100001707306856006907323 2010 eng d a1937-065200aAn Euler–Poincaré bound for equicharacteristic étale sheaves0 aEuler–Poincaré bound for equicharacteristic étale sheaves c2010/01/14 a21 - 450 v43 a

The Grothendieck–Ogg–Shafarevich formula expresses the Euler characteristic of an étale sheaf on a characteristic-p curve in terms of local data. The purpose of this paper is to prove an equicharacteristic version of this formula (a bound, rather than an equality). This follows work of R. Pink.

The basis for the proof of this result is the characteristic-p Riemann–Hilbert correspondence, which is a functorial relationship between two different types of sheaves on a characteristic-p scheme. In the paper we prove a one-dimensional version of this correspondence, considering both local and global settings.

1 aMiller, Carl uhttp://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.648.358401162nas a2200133 4500008004100000245006200041210006200103260001400165490000700179520076300186100002400949700001800973856003700991 2009 eng d00aEfficient quantum circuits for arbitrary sparse unitaries0 aEfficient quantum circuits for arbitrary sparse unitaries c2009/12/10 v803 a Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided it has at most polynomially many nonzero entries in any row or column, and these entries are efficiently computable. One can formulate a model of computation based on the composition of sparse unitaries which includes the quantum Turing machine model, the quantum circuit model, anyonic models, permutational quantum computation, and discrete time quantum walks as special cases. Thus we obtain a simple unified proof that these models are all contained in BQP. Furthermore our general method for implementing sparse unitaries simplifies several existing quantum algorithms. 1 aJordan, Stephen, P.1 aWocjan, Pawel uhttp://arxiv.org/abs/0904.2211v201422nas a2200145 4500008004100000245005900041210005900100260001500159520097700174100002201151700002401173700001801197700002401215856003701239 2009 eng d00aEfficient quantum processing of ideals in finite rings0 aEfficient quantum processing of ideals in finite rings c2009/07/313 a Suppose we are given black-box access to a finite ring R, and a list of generators for an ideal I in R. We show how to find an additive basis representation for I in poly(log |R|) time. This generalizes a recent quantum algorithm of Arvind et al. which finds a basis representation for R itself. We then show that our algorithm is a useful primitive allowing quantum computers to rapidly solve a wide variety of problems regarding finite rings. In particular we show how to test whether two ideals are identical, find their intersection, find their quotient, prove whether a given ring element belongs to a given ideal, prove whether a given element is a unit, and if so find its inverse, find the additive and multiplicative identities, compute the order of an ideal, solve linear equations over rings, decide whether an ideal is maximal, find annihilators, and test the injectivity and surjectivity of ring homomorphisms. These problems appear to be hard classically. 1 aWocjan, Pawel, M.1 aJordan, Stephen, P.1 aAhmadi, Hamed1 aBrennan, Joseph, P. uhttp://arxiv.org/abs/0908.0022v101370nas a2200157 4500008004100000245004700041210004700088260001400135490000700149520092300156100003001079700002101109700001901130700002601149856003701175 2009 eng d00aEntanglement Cost of Nonlocal Measurements0 aEntanglement Cost of Nonlocal Measurements c2009/7/150 v803 a For certain joint measurements on a pair of spatially separated particles, we ask how much entanglement is needed to carry out the measurement exactly. For a class of orthogonal measurements on two qubits with partially entangled eigenstates, we present upper and lower bounds on the entanglement cost. The upper bound is based on a recent result by D. Berry [Phys. Rev. A 75, 032349 (2007)]. The lower bound, based on the entanglement production capacity of the measurement, implies that for almost all measurements in the class we consider, the entanglement required to perform the measurement is strictly greater than the average entanglement of its eigenstates. On the other hand, we show that for any complete measurement in d x d dimensions that is invariant under all local Pauli operations, the cost of the measurement is exactly equal to the average entanglement of the states associated with the outcomes. 1 aBandyopadhyay, Somshubhro1 aBrassard, Gilles1 aKimmel, Shelby1 aWootters, William, K. uhttp://arxiv.org/abs/0809.2264v401125nas a2200145 4500008004100000245006500041210006500106260001500171300001200186490000600198520068700204100002400891700001800915856004600933 2009 eng d00aEstimating Jones and HOMFLY polynomials with One Clean Qubit0 aEstimating Jones and HOMFLY polynomials with One Clean Qubit c2009/03/01 a264-2890 v93 a

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

1 aJordan, Stephen, P.1 aWocjan, Pawel uhttp://dl.acm.org/citation.cfm?id=201178701191nas a2200145 4500008004100000245007100041210006900112260001400181300001600195490000700211520075200218100001900970700001900989856003701008 2008 eng d00aEfficient scheme for one-way quantum computing in thermal cavities0 aEfficient scheme for oneway quantum computing in thermal cavitie c2008/4/12 a2997 - 30040 v473 a We propose a practical scheme for one-way quantum computing based on efficient generation of 2D cluster state in thermal cavities. We achieve a controlled-phase gate that is neither sensitive to cavity decay nor to thermal field by adding a strong classical field to the two-level atoms. We show that a 2D cluster state can be generated directly by making every two atoms collide in an array of cavities, with numerically calculated parameters and appropriate operation sequence that can be easily achieved in practical Cavity QED experiments. Based on a generated cluster state in Box$^{(4)}$ configuration, we then implement Grover's search algorithm for four database elements in a very simple way as an example of one-way quantum computing. 1 aYang, Wen-Xing1 aGong, Zhe-Xuan uhttp://arxiv.org/abs/0704.2297v101463nas a2200145 4500008004100000245007500041210006900116260001500185300001200200490000600212520100100218100002001219700002401239856005401263 2008 eng d00aEstimating Jones polynomials is a complete problem for one clean qubit0 aEstimating Jones polynomials is a complete problem for one clean c2008/09/01 a681-7140 v83 a

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

1 aShor, Peter, W.1 aJordan, Stephen, P. uhttp://dl.acm.org/citation.cfm?id=2017011.201701201032nas a2200181 4500008004100000245003700041210003700078260001500115300001100130490000700141520058000148100001800728700001700746700001800763700002000781700001200801856003700813 2008 eng d00aExistence of Universal Entangler0 aExistence of Universal Entangler c2008/01/01 a0121030 v493 a A gate is called entangler if it transforms some (pure) product states to entangled states. A universal entangler is a gate which transforms all product states to entangled states. In practice, a universal entangler is a very powerful device for generating entanglements, and thus provides important physical resources for accomplishing many tasks in quantum computing and quantum information. This Letter demonstrates that a universal entangler always exists except for a degenerated case. Nevertheless, the problem how to find a universal entangler remains open. 1 aChen, Jianxin1 aDuan, Runyao1 aJi, Zhengfeng1 aYing, Mingsheng1 aYu, Jun uhttp://arxiv.org/abs/0704.1473v201036nas a2200169 4500008004100000245009800041210006900139260001500208300001200223490000600235520049500241100001900736700001900755700002600774700002300800856004300823 2007 eng d00aEffective-range description of a Bose gas under strong one- or two-dimensional confinement 0 aEffectiverange description of a Bose gas under strong one or two c2007/01/29 a19 - 190 v93 a We point out that theories describing s-wave collisions of bosonic atoms confined in one- or two-dimensional geometries can be extended to much tighter confinements than previously thought. This is achieved by replacing the scattering length by an energy-dependent scattering length which was already introduced for the calculation of energy levels under 3D confinement. This replacement accurately predicts the position of confinement-induced resonances in strongly confined geometries. 1 aNaidon, Pascal1 aTiesinga, Eite1 aMitchell, William, F.1 aJulienne, Paul, S. uhttp://arxiv.org/abs/physics/0607140v200984nas a2200145 4500008004100000245009600041210006900137260001500206520048900221100002300710700002300733700001900756700001900775856004400794 2007 eng d00aEvery NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer 0 aEvery NAND formula of size N can be evaluated in time N 12o1 on  c2007/03/023 a For every NAND formula of size N, there is a bounded-error N^{1/2+o(1)}-time quantum algorithm, based on a coined quantum walk, that evaluates this formula on a black-box input. Balanced, or ``approximately balanced,'' NAND formulas can be evaluated in O(sqrt{N}) queries, which is optimal. It follows that the (2-o(1))-th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy. 1 aChilds, Andrew, M.1 aReichardt, Ben, W.1 aSpalek, Robert1 aZhang, Shengyu uhttp://arxiv.org/abs/quant-ph/0703015v301021nas a2200109 4500008004100000245007100041210006900112260001500181520065200196100001900848856004400867 2006 eng d00aEffective error-suppression scheme for reversible quantum computer0 aEffective errorsuppression scheme for reversible quantum compute c2006/08/203 a We construct a new error-suppression scheme that makes use of the adjoint of reversible quantum algorithms. For decoherence induced errors such as depolarization, it is presented that provided the depolarization error probability is less than 1, our scheme can exponentially reduce the final output error rate to zero using a number of cycles, and the output state can be coherently sent to another stage of quantum computation process. Besides, experimental set-ups via optical approach have been proposed using Grover's search algorithm as an example. Some further discussion on the benefits and limitations of the scheme is given in the end. 1 aGong, Zhe-Xuan uhttp://arxiv.org/abs/quant-ph/0608152v401078nas a2200145 4500008004100000245006200041210006200103260001400165490000700179520063300186100001900819700002300838700002700861856004400888 2006 eng d00aEffects of finite temperature on the Mott insulator state0 aEffects of finite temperature on the Mott insulator state c2006/1/200 v733 a We investigate the effects of finite temperature on ultracold Bose atoms confined in an optical lattice plus a parabolic potential in the Mott insulator state. In particular, we analyze the temperature dependence of the density distribution of atomic pairs in the lattice, by means of exact Monte-Carlo simulations. We introduce a simple model that quantitatively accounts for the computed pair density distributions at low enough temperatures. We suggest that the temperature dependence of the atomic pair statistics may be used to estimate the system's temperature at energies of the order of the atoms' interaction energy. 1 aPupillo, Guido1 aWilliams, Carl, J.1 aProkof'ev, Nikolay, V. uhttp://arxiv.org/abs/cond-mat/0407075v301177nas a2200145 4500008004100000245006100041210006100102260001500163490000700178520074000185100002400925700001800949700002000967856004400987 2006 eng d00aError correcting codes for adiabatic quantum computation0 aError correcting codes for adiabatic quantum computation c2006/11/140 v743 a Recently, there has been growing interest in using adiabatic quantum computation as an architecture for experimentally realizable quantum computers. One of the reasons for this is the idea that the energy gap should provide some inherent resistance to noise. It is now known that universal quantum computation can be achieved adiabatically using 2-local Hamiltonians. The energy gap in these Hamiltonians scales as an inverse polynomial in the problem size. Here we present stabilizer codes which can be used to produce a constant energy gap against 1-local and 2-local noise. The corresponding fault-tolerant universal Hamiltonians are 4-local and 6-local respectively, which is the optimal result achievable within this framework. 1 aJordan, Stephen, P.1 aFarhi, Edward1 aShor, Peter, W. uhttp://arxiv.org/abs/quant-ph/0512170v306219nas a2200145 4500008004100000022001300041245011100054210006900165260001500234300001400249490000700263520571500270100001705985856007106002 2005 eng d a0040938300aExponential iterated integrals and the relative solvable completion of the fundamental group of a manifold0 aExponential iterated integrals and the relative solvable complet c2005/03/01 a351 - 3730 v443 a

We develop a class of integrals on a manifold M called exponential iterated integrals  , an extension of K.T. Chen's iterated integrals. It is shown that the matrix entries of any upper triangular representation of π1(M,x) can be expressed via these new integrals. The ring of exponential iterated integrals contains the coordinate rings for a class of universal representations, called the relative solvable completions   of π1(M,x). We consider exponential iterated integrals in the particular case of fibered knot complements, where the fundamental group always has a faithful relative solvable completion.

1 aMiller, Carl uhttp://www.sciencedirect.com/science/article/pii/S004093830400079501113nas a2200169 4500008004100000245005200041210005200093260001500145520061800160100002300778700001900801700001900820700001800839700001700857700002500874856004400899 2002 eng d00aExponential algorithmic speedup by quantum walk0 aExponential algorithmic speedup by quantum walk c2002/09/243 a We construct an oracular (i.e., black box) problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our oracular setting. We then show how this quantum walk can be used to solve our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve this problem with high probability in subexponential time. 1 aChilds, Andrew, M.1 aCleve, Richard1 aDeotto, Enrico1 aFarhi, Edward1 aGutmann, Sam1 aSpielman, Daniel, A. uhttp://arxiv.org/abs/quant-ph/0209131v201212nas a2200145 4500008004100000245007400041210006900115260001400184490000700198520074500205100002300950700002400973700002500997856004401022 2001 eng d00aExact sampling from non-attractive distributions using summary states0 aExact sampling from nonattractive distributions using summary st c2001/2/220 v633 a Propp and Wilson's method of coupling from the past allows one to efficiently generate exact samples from attractive statistical distributions (e.g., the ferromagnetic Ising model). This method may be generalized to non-attractive distributions by the use of summary states, as first described by Huber. Using this method, we present exact samples from a frustrated antiferromagnetic triangular Ising model and the antiferromagnetic q=3 Potts model. We discuss the advantages and limitations of the method of summary states for practical sampling, paying particular attention to the slowing down of the algorithm at low temperature. In particular, we show that such a slowing down can occur in the absence of a physical phase transition. 1 aChilds, Andrew, M.1 aPatterson, Ryan, B.1 aMacKay, David, J. C. uhttp://arxiv.org/abs/cond-mat/0005132v100814nas a2200157 4500008004100000245007600041210006900117260001500186300001200201490000600213520033500219100002300554700001800577700001700595856004400612 2001 eng d00aAn example of the difference between quantum and classical random walks0 aexample of the difference between quantum and classical random w c2002/04/01 a35 - 430 v13 a In this note, we discuss a general definition of quantum random walks on graphs and illustrate with a simple graph the possibility of very different behavior between a classical random walk and its quantum analogue. In this graph, propagation between a particular pair of nodes is exponentially faster in the quantum case. 1 aChilds, Andrew, M.1 aFarhi, Edward1 aGutmann, Sam uhttp://arxiv.org/abs/quant-ph/0103020v1