01684nas a2200157 4500008004100000245006700041210006700108260001400175520120000189100001601389700002201405700002001427700001701447700002501464856003701489 2024 eng d00aAverage Rényi Entanglement Entropy in Gaussian Boson Sampling0 aAverage Rényi Entanglement Entropy in Gaussian Boson Sampling c3/27/20243 a

Recently, many experiments have been conducted with the goal of demonstrating a quantum advantage over classical computation. One popular framework for these experiments is Gaussian Boson Sampling, where quadratic photonic input states are interfered via a linear optical unitary and subsequently measured in the Fock basis. In this work, we study the modal entanglement of the output states in this framework just before the measurement stage. Specifically, we compute Page curves as measured by various Rényi-α entropies, where the Page curve describes the entanglement between two partitioned groups of output modes averaged over all linear optical unitaries. We derive these formulas for α=1 (i.e. the von Neumann entropy), and, more generally, for all positive integer α, in the asymptotic limit of infinite number of modes and for input states that are composed of single-mode-squeezed-vacuum state with equal squeezing strength. We then analyze the limiting behaviors when the squeezing is small and large. Having determined the averages, we then explicitly calculate the Rényi-α variance for integers α>1, and we are able to show that these entropies are weakly typical.

1 aYoum, Jason1 aIosue, Joseph, T.1 aEhrenberg, Adam1 aWang, Yu-Xin1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2403.1889001455nas a2200169 4500008004100000245007100041210006900112260001300181300001100194490000700205520093300212100002201145700001801167700002101185700002301206856005601229 2024 eng d00aContinuous-Variable Quantum State Designs: Theory and Applications0 aContinuousVariable Quantum State Designs Theory and Applications c2/8/2024 a0110130 v143 a

We generalize the notion of quantum state designs to infinite-dimensional spaces. We first prove that, under the definition of continuous-variable (CV) state t-designs from [Blume-Kohout et al., Commun. Math. Phys. 326, 755 (2014)], no state designs exist for t≥2. Similarly, we prove that no CV unitary t-designs exist for t≥2. We propose an alternative definition for CV state designs, which we call rigged t-designs, and provide explicit constructions for t = 2. As an application of rigged designs, we develop a design-based shadow-tomography protocol for CV states. Using energy-constrained versions of rigged designs, we define an average fidelity for CV quantum channels and relate this fidelity to the CV entanglement fidelity. As an additional result of independent interest, we establish a connection between torus 2-designs and complete sets of mutually unbiased bases.

1 aIosue, Joseph, T.1 aSharma, Kunal1 aGullans, Michael1 aAlbert, Victor, V. uhttps://link.aps.org/doi/10.1103/PhysRevX.14.01101301621nas a2200157 4500008004100000245006100041210005700102260001400159520113900173100002001312700002201332700002301354700002401377700002501401856003701426 2024 eng d00aThe Second Moment of Hafnians in Gaussian Boson Sampling0 aSecond Moment of Hafnians in Gaussian Boson Sampling c3/20/20243 a

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

1 aEhrenberg, Adam1 aIosue, Joseph, T.1 aDeshpande, Abhinav1 aHangleiter, Dominik1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2403.1387802278nas a2200205 4500008004100000245008100041210006900122260001400191520163500205100001701840700002101857700002801878700002001906700001501926700002301941700002201964700002501986700002402011856003702035 2023 eng d00aLattice quantum chromodynamics at large isospin density: 6144 pions in a box0 aLattice quantum chromodynamics at large isospin density 6144 pio c7/27/20233 a

We present an algorithm to compute correlation functions for systems with the quantum numbers of many identical mesons from lattice quantum chromodynamics (QCD). The algorithm is numerically stable and allows for the computation of n-pion correlation functions for n∈{1,…,N} using a single N×N matrix decomposition, improving on previous algorithms. We apply the algorithm to calculations of correlation functions with up to 6144 π+s using two ensembles of gauge field configurations generated with quark masses corresponding to a pion mass mπ=170 MeV and spacetime volumes of (4.43×8.8) fm4 and (5.83×11.6) fm4. We also discuss statistical techniques for the analysis of such systems, in which the correlation functions vary over many orders of magnitude. In particular, we observe that the many-pion correlation functions are well approximated by log-normal distributions, allowing the extraction of the energies of these systems. Using these energies, the large-isospin-density, zero-baryon-density region of the QCD phase diagram is explored. A peak is observed in the energy density at an isospin chemical potential μI∼1.5mπ, signalling the transition into a Bose-Einstein condensed phase. The isentropic speed of sound in the medium is seen to exceed the ideal-gas (conformal) limit (c2s≤1/3) over a wide range of chemical potential before falling towards the asymptotic expectation at μI∼15mπ. These, and other thermodynamic observables, indicate that the isospin chemical potential must be large for the system to be well described by an ideal gas or perturbative QCD.

1 aAbbott, Ryan1 aDetmold, William1 aRomero-López, Fernando1 aDavoudi, Zohreh1 aIlla, Marc1 aParreño, Assumpta1 aPerry, Robert, J.1 aShanahan, Phiala, E.1 aWagman, Michael, L. uhttps://arxiv.org/abs/2307.1501402055nas a2200241 4500008004100000245005300041210005200094260001300146490000800159520125800167653002701425653004201452653003901494653003101533653004701564653005201611100002201663700002101685700002201706700002001728700002801748856003701776 2023 eng d00aNon-Abelian eigenstate thermalization hypothesis0 aNonAbelian eigenstate thermalization hypothesis c4/6/20230 v1303 a

The eigenstate thermalization hypothesis (ETH) explains why chaotic quantum many-body systems thermalize internally if the Hamiltonian lacks symmetries. If the Hamiltonian conserves one quantity ("charge"), the ETH implies thermalization within a charge sector -- in a microcanonical subspace. But quantum systems can have charges that fail to commute with each other and so share no eigenbasis; microcanonical subspaces may not exist. Furthermore, the Hamiltonian will have degeneracies, so the ETH need not imply thermalization. We adapt the ETH to noncommuting charges by positing a non-Abelian ETH and invoking the approximate microcanonical subspace introduced in quantum thermodynamics. Illustrating with SU(2) symmetry, we apply the non-Abelian ETH in calculating local observables' time-averaged and thermal expectation values. In many cases, we prove, the time average thermalizes. However, we also find cases in which, under a physically reasonable assumption, the time average converges to the thermal average unusually slowly as a function of the global-system size. This work extends the ETH, a cornerstone of many-body physics, to noncommuting charges, recently a subject of intense activity in quantum thermodynamics.

10aFOS: Physical sciences10aHigh Energy Physics - Theory (hep-th)10aQuantum Gases (cond-mat.quant-gas)10aQuantum Physics (quant-ph)10aStatistical Mechanics (cond-mat.stat-mech)10aStrongly Correlated Electrons (cond-mat.str-el)1 aMurthy, Chaitanya1 aBabakhani, Arman1 aIniguez, Fernando1 aSrednicki, Mark1 aHalpern, Nicole, Yunger uhttps://arxiv.org/abs/2206.0531002008nas a2200181 4500008004100000245005800041210005800099260001400157300000900171490000600180520148900186100002201675700002001697700002401717700002301741700002501764856003701789 2023 eng d00aPage curves and typical entanglement in linear optics0 aPage curves and typical entanglement in linear optics c5/18/2023 a10170 v73 a

Bosonic Gaussian states are a special class of quantum states in an infinite dimensional Hilbert space that are relevant to universal continuous-variable quantum computation as well as to near-term quantum sampling tasks such as Gaussian Boson Sampling. In this work, we study entanglement within a set of squeezed modes that have been evolved by a random linear optical unitary. We first derive formulas that are asymptotically exact in the number of modes for the Rényi-2 Page curve (the average Rényi-2 entropy of a subsystem of a pure bosonic Gaussian state) and the corresponding Page correction (the average information of the subsystem) in certain squeezing regimes. We then prove various results on the typicality of entanglement as measured by the Rényi-2 entropy by studying its variance. Using the aforementioned results for the Rényi-2 entropy, we upper and lower bound the von Neumann entropy Page curve and prove certain regimes of entanglement typicality as measured by the von Neumann entropy. Our main proofs make use of a symmetry property obeyed by the average and the variance of the entropy that dramatically simplifies the averaging over unitaries. In this light, we propose future research directions where this symmetry might also be exploited. We conclude by discussing potential applications of our results and their generalizations to Gaussian Boson Sampling and to illuminating the relationship between entanglement and computational complexity.

1 aIosue, Joseph, T.1 aEhrenberg, Adam1 aHangleiter, Dominik1 aDeshpande, Abhinav1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2209.0683801855nas a2200145 4500008004100000245007300041210006900114260001500183520138800198100002201586700001901608700002001627700002501647856003701672 2023 eng d00aProjective toric designs, difference sets, and quantum state designs0 aProjective toric designs difference sets and quantum state desig c11/22/20233 a

Trigonometric cubature rules of degree t are sets of points on the torus over which sums reproduce integrals of degree t monomials over the full torus. They can be thought of as t-designs on the torus. Motivated by the projective structure of quantum mechanics, we develop the notion of t-designs on the projective torus, which, surprisingly, have a much more restricted structure than their counterparts on full tori. We provide various constructions of these projective toric designs and prove some bounds on their size and characterizations of their structure. We draw connections between projective toric designs and a diverse set of mathematical objects, including difference and Sidon sets from the field of additive combinatorics, symmetric, informationally complete positive operator valued measures (SIC-POVMs) and complete sets of mutually unbiased bases (MUBs) (which are conjectured to relate to finite projective geometry) from quantum information theory, and crystal ball sequences of certain root lattices. Using these connections, we prove bounds on the maximal size of dense Btmodm sets. We also use projective toric designs to construct families of quantum state designs. Finally, we discuss many open questions about the properties of these projective toric designs and how they relate to other questions in number theory, geometry, and quantum information.

1 aIosue, Joseph, T.1 aMooney, T., C.1 aEhrenberg, Adam1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2311.1347901025nas a2200145 4500008004100000245002800041210002800069260001400097520064400111100002200755700002200777700002000799700002300819856003700842 2023 eng d00aQuantum spherical codes0 aQuantum spherical codes c12/7/20233 a

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

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

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

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

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

1 aIyer, Vishnu1 aJain, Siddhartha1 aKovacs-Deak, Matt1 aKumar, Vinayak, M.1 aSchaeffer, Luke1 aWang, Daochen1 aWhitmeyer, Michael uarXiv:2310.0800401909nas a2200157 4500008004100000245006300041210006300104260001500167520141800182100002001600700002201620700002301642700002401665700002501689856003701714 2023 eng d00aTransition of Anticoncentration in Gaussian Boson Sampling0 aTransition of Anticoncentration in Gaussian Boson Sampling c12/13/20233 a

Gaussian Boson Sampling is a promising method for experimental demonstrations of quantum advantage because it is easier to implement than other comparable schemes. While most of the properties of Gaussian Boson Sampling are understood to the same degree as for these other schemes, we understand relatively little about the statistical properties of its output distribution. The most relevant statistical property, from the perspective of demonstrating quantum advantage, is the anticoncentration of the output distribution as measured by its second moment. The degree of anticoncentration features in arguments for the complexity-theoretic hardness of Gaussian Boson Sampling, and it is also important to know when using cross-entropy benchmarking to verify experimental performance. In this work, we develop a graph-theoretic framework for analyzing the moments of the Gaussian Boson Sampling distribution. Using this framework, we show that Gaussian Boson Sampling undergoes a transition in anticoncentration as a function of the number of modes that are initially squeezed compared to the number of photons measured at the end of the circuit. When the number of initially squeezed modes scales sufficiently slowly with the number of photons, there is a lack of anticoncentration. However, if the number of initially squeezed modes scales quickly enough, the output probabilities anticoncentrate weakly.

1 aEhrenberg, Adam1 aIosue, Joseph, T.1 aDeshpande, Abhinav1 aHangleiter, Dominik1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2312.0843302524nas a2200193 4500008004100000245007700041210006900118260001400187520188800201653004302089653002702132653003102159653003302190100001602223700001602239700001902255700001902274856003702293 2022 eng d00aArline Benchmarks: Automated Benchmarking Platform for Quantum Compilers0 aArline Benchmarks Automated Benchmarking Platform for Quantum Co c3/28/20223 a

Efficient compilation of quantum algorithms is vital in the era of Noisy Intermediate-Scale Quantum (NISQ) devices. While multiple open-source quantum compilation and circuit optimization frameworks are available, e.g. IBM Qiskit, CQC Tket, Google Cirq, Rigetti Quilc, PyZX, their relative performance is not always clear to a quantum programmer. The growth of complexity and diversity of quantum circuit compilation algorithms creates a demand for a dedicated tool for cross-benchmarking and profiling of inner workflow of the quantum compilation stack. We present an open-source software package, Arline Benchmarks, that is designed to perform automated benchmarking of quantum compilers with the focus on NISQ applications. The name "Arline" was given in honour of Arline Greenbaum Feynman, the first wife of Richard Feynman, the pioneer of quantum computing. We compared several quantum compilation frameworks based on a set of important metrics such as post-optimization gate counts, circuit depth, hardware-dependent circuit cost function, compiler run time etc. with a detailed analysis of metrics for each compilation stage. We performed a variety of compiler tests for random circuits and structured quantum algorithms (VQE, Trotter decomposition, Grover search, Option Pricing via Amplitude Estimation) for several popular quantum hardware architectures. Leveraging cross-platform functionality of Arline, we propose a concept of composite compilation pipeline that combines compiler-specific circuit optimization subroutines in a single compilation stack and finds an optimized sequence of compilation passes. By providing detailed insights into the compilation flow of quantum compilers, Arline Benchmarks offers a valuable toolkit for quantum computing researchers and software developers to gain additional insights into compilers' characteristics.

10aFOS: Computer and information sciences10aFOS: Physical sciences10aQuantum Physics (quant-ph)10aSoftware Engineering (cs.SE)1 aKharkov, Y.1 aIvanova, A.1 aMikhantiev, E.1 aKotelnikov, A. uhttps://arxiv.org/abs/2202.1402502013nas a2200277 4500008004100000245008100041210006900122260001300191300001300204490000600217520120300223100002301426700001801449700002001467700002101487700002001508700002001528700001701548700002101565700001401586700001701600700002401617700002001641700001501661856005901676 2022 eng d00aQuantum computational advantage via high-dimensional Gaussian boson sampling0 aQuantum computational advantage via highdimensional Gaussian bos c1/5/2022 aeabi78940 v83 a

A programmable quantum computer based on fiber optics outperforms classical computers with a high level of confidence. Photonics is a promising platform for demonstrating a quantum computational advantage (QCA) by outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing proposals and demonstrations face challenges. Experimentally, current implementations of Gaussian boson sampling (GBS) lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make progress in improving both the theoretical evidence and experimental prospects. We provide evidence for the hardness of GBS, comparable to the strongest theoretical proposals for QCA. We also propose a QCA architecture we call high-dimensional GBS, which is programmable and can be implemented with low loss using few optical components. We show that particular algorithms for simulating GBS are outperformed by high-dimensional GBS experiments at modest system sizes. This work thus opens the path to demonstrating QCA with programmable photonic processors.

1 aDeshpande, Abhinav1 aMehta, Arthur1 aVincent, Trevor1 aQuesada, Nicolas1 aHinsche, Marcel1 aIoannou, Marios1 aMadsen, Lars1 aLavoie, Jonathan1 aQi, Haoyu1 aEisert, Jens1 aHangleiter, Dominik1 aFefferman, Bill1 aDhand, Ish uhttps://www.science.org/doi/abs/10.1126/sciadv.abi789401622nas a2200193 4500008004100000245008300041210006900124260001400193520097000207653002701177653005201204100002101256700003001277700002001307700002501327700002101352700001801373856003701391 2022 eng d00aQuantum Many-Body Scars from Einstein-Podolsky-Rosen States in Bilayer Systems0 aQuantum ManyBody Scars from EinsteinPodolskyRosen States in Bila c9/12/20223 a

Quantum many-body scar states are special eigenstates of nonintegrable models with distinctive entanglement features that give rise to infinitely long-lived coherent dynamics under quantum quenches from certain initial states. We elaborate on a construction of quantum many-body scar states in which they emerge from Einstein-Podolsky-Rosen (EPR) states in systems with two layers, wherein the two layers are maximally entangled. We apply this construction to spin systems as well as systems of itinerant fermions and bosons and demonstrate how symmetries can be harnessed to enhance its versatility. We show that several well-known examples of quantum many-body scars, including the tower of states in the spin-1 XY model and the η-pairing states in the Fermi-Hubbard model, can be understood within this formalism. We also demonstrate how an {\it infinite} tower of many-body scar states can emerge in bilayer Bose-Hubbard models with charge conservation.

10aFOS: Physical sciences10aStrongly Correlated Electrons (cond-mat.str-el)1 aWildeboer, Julia1 aLanglett, Christopher, M.1 aYang, Zhi-Cheng1 aGorshkov, Alexey, V.1 aIadecola, Thomas1 aXu, Shenglong uhttps://arxiv.org/abs/2209.0552702255nas a2200205 4500008004100000245005300041210005000094260001300144520167300157100002001830700002001850700002301870700002101893700001601914700002401930700002501954700001701979700001601996856003702012 2022 eng d00aA single T-gate makes distribution learning hard0 asingle Tgate makes distribution learning hard c7/7/20223 a

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

1 aHinsche, Marcel1 aIoannou, Marios1 aNietner, Alexander1 aHaferkamp, Jonas1 aQuek, Yihui1 aHangleiter, Dominik1 aSeifert, Jean-Pierre1 aEisert, Jens1 aSweke, Ryan uhttps://arxiv.org/abs/2207.0314002215nas 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.0956002430nas a2200205 4500008004100000245007100041210006900112260001500181520180900196100002002005700002002025700002302045700002102068700001602089700002402105700002502129700001702154700001602171856003702187 2021 eng d00aLearnability of the output distributions of local quantum circuits0 aLearnability of the output distributions of local quantum circui c10/11/20213 a

There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable in the statistical query model, i.e., when given query access to empirical expectation values of bounded functions over the sample space. This immediately implies the hardness, for both quantum and classical algorithms, of learning from statistical queries the output distributions of local quantum circuits using any gate set which includes the Clifford group. As many practical generative modelling algorithms use statistical queries -- including those for training quantum circuit Born machines -- our result is broadly applicable and strongly limits the possibility of a meaningful quantum advantage for learning the output distributions of local quantum circuits. As a positive result, we show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable by a classical learner. Our results are equally applicable to the problems of learning an algorithm for generating samples from the target distribution (generative modelling) and learning an algorithm for evaluating its probabilities (density modelling). They provide the first rigorous insights into the learnability of output distributions of local quantum circuits from the probabilistic modelling perspective. 

1 aHinsche, Marcel1 aIoannou, Marios1 aNietner, Alexander1 aHaferkamp, Jonas1 aQuek, Yihui1 aHangleiter, Dominik1 aSeifert, Jean-Pierre1 aEisert, Jens1 aSweke, Ryan uhttps://arxiv.org/abs/2110.0551702003nas a2200253 4500008004100000245008100041210006900122260001400191520125700205100002301462700001801485700002001503700002101523700002001544700002001564700001701584700002101601700001401622700001701636700002401653700002001677700001501697856003701712 2021 eng d00aQuantum Computational Supremacy via High-Dimensional Gaussian Boson Sampling0 aQuantum Computational Supremacy via HighDimensional Gaussian Bos c2/24/20213 a

Photonics is a promising platform for demonstrating quantum computational supremacy (QCS) by convincingly outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing photonics proposals and demonstrations face significant hurdles. Experimentally, current implementations of Gaussian boson sampling lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make significant progress in improving both the theoretical evidence and experimental prospects. On the theory side, we provide strong evidence for the hardness of Gaussian boson sampling, placing it on par with the strongest theoretical proposals for QCS. On the experimental side, we propose a new QCS architecture, high-dimensional Gaussian boson sampling, which is programmable and can be implemented with low loss rates using few optical components. We show that particular classical algorithms for simulating GBS are vastly outperformed by high-dimensional Gaussian boson sampling experiments at modest system sizes. This work thus opens the path to demonstrating QCS with programmable photonic processors.

1 aDeshpande, Abhinav1 aMehta, Arthur1 aVincent, Trevor1 aQuesada, Nicolas1 aHinsche, Marcel1 aIoannou, Marios1 aMadsen, Lars1 aLavoie, Jonathan1 aQi, Haoyu1 aEisert, Jens1 aHangleiter, Dominik1 aFefferman, Bill1 aDhand, Ish uhttps://arxiv.org/abs/2102.1247401512nas a2200217 4500008004100000245007100041210006900112260001400181490000700195520085300202100002801055700002301083700001901106700001901125700002201144700002401166700002501190700002101215700002101236856003701257 2021 eng d00aQuench Dynamics of a Fermi Gas with Strong Long-Range Interactions0 aQuench Dynamics of a Fermi Gas with Strong LongRange Interaction c5/24/20210 v113 a

We induce strong non-local interactions in a 2D Fermi gas in an optical lattice using Rydberg dressing. The system is approximately described by a t−V model on a square lattice where the fermions experience isotropic nearest-neighbor interactions and are free to hop only along one direction. We measure the interactions using many-body Ramsey interferometry and study the lifetime of the gas in the presence of tunneling, finding that tunneling does not reduce the lifetime. To probe the interplay of non-local interactions with tunneling, we investigate the short-time relaxation dynamics of charge density waves in the gas. We find that strong nearest-neighbor interactions slow down the relaxation. Our work opens the door for quantum simulations of systems with strong non-local interactions such as extended Fermi-Hubbard models.

1 aGuardado-Sanchez, Elmer1 aSpar, Benjamin, M.1 aSchauss, Peter1 aBelyansky, Ron1 aYoung, Jeremy, T.1 aBienias, Przemyslaw1 aGorshkov, Alexey, V.1 aIadecola, Thomas1 aBakr, Waseem, S. uhttps://arxiv.org/abs/2010.0587101565nas a2200169 4500008004100000245004300041210004200084260001400126520108300140100003001223700002001253700002101273700002501294700002101319700001801340856003701358 2021 eng d00aRainbow Scars: From Area to Volume Law0 aRainbow Scars From Area to Volume Law c7/12/20213 a

Quantum many-body scars (QMBS) constitute a new quantum dynamical regime in which rare "scarred" eigenstates mediate weak ergodicity breaking. One open question is to understand the most general setting in which these states arise. In this work, we develop a generic construction that embeds a new class of QMBS, rainbow scars, into the spectrum of an arbitrary Hamiltonian. Unlike other examples of QMBS, rainbow scars display extensive bipartite entanglement entropy while retaining a simple entanglement structure. Specifically, the entanglement scaling is volume-law for a random bipartition, while scaling for a fine-tuned bipartition is sub-extensive. When internal symmetries are present, the construction leads to multiple, and even towers of rainbow scars revealed through distinctive non-thermal dynamics. To this end, we provide an experimental road map for realizing rainbow scar states in a Rydberg-atom quantum simulator, leading to coherent oscillations distinct from the strictly sub-volume-law QMBS previously realized in the same system. 

1 aLanglett, Christopher, M.1 aYang, Zhi-Cheng1 aWildeboer, Julia1 aGorshkov, Alexey, V.1 aIadecola, Thomas1 aXu, Shenglong uhttps://arxiv.org/abs/2107.0341601383nas a2200157 4500008004100000245005600041210005500097260001400152490000800166520093200174100002001106700001601126700002501142700002101167856003701188 2020 eng d00aHilbert-Space Fragmentation from Strict Confinement0 aHilbertSpace Fragmentation from Strict Confinement c5/22/20200 v1243 a

We study one-dimensional spin-1/2 models in which strict confinement of Ising domain walls leads to the fragmentation of Hilbert space into exponentially many disconnected subspaces. Whereas most of the previous works emphasize dipole moment conservation as an essential ingredient for such fragmentation, we instead require two commuting U(1) conserved quantities associated with the total domain-wall number and the total magnetization. The latter arises naturally from the confinement of domain walls. Remarkably, while some connected components of the Hilbert space thermalize, others are integrable by Bethe ansatz. We further demonstrate how this Hilbert-space fragmentation pattern arises perturbatively in the confining limit of Z2 gauge theory coupled to fermionic matter, leading to a hierarchy of time scales for motion of the fermions. This model can be realized experimentally in two complementary settings.

1 aYang, Zhi-Cheng1 aLiu, Fangli1 aGorshkov, Alexey, V.1 aIadecola, Thomas uhttps://arxiv.org/abs/1912.0430001427nas a2200157 4500008004100000245007300041210006900114260001400183520092900197100001601126700002001142700002401162700002101186700002501207856003701232 2020 eng d00aLocalization and criticality in antiblockaded 2D Rydberg atom arrays0 aLocalization and criticality in antiblockaded 2D Rydberg atom ar c12/7/20203 a

Controllable Rydberg atom arrays have provided new insights into fundamental properties of quantum matter both in and out of equilibrium. In this work, we study the effect of experimentally relevant positional disorder on Rydberg atoms trapped in a 2D square lattice under anti-blockade (facilitation) conditions. We show that the facilitation conditions lead the connectivity graph of a particular subspace of the full Hilbert space to form a 2D Lieb lattice, which features a singular flat band. Remarkably, we find three distinct regimes as the disorder strength is varied: a critical regime, a delocalized but nonergodic regime, and a regime with a disorder-induced flat band. The critical regime's existence depends crucially upon the singular flat band in our model, and is absent in any 1D array or ladder system. We propose to use quench dynamics to probe the three different regimes experimentally. 

1 aLiu, Fangli1 aYang, Zhi-Cheng1 aBienias, Przemyslaw1 aIadecola, Thomas1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2012.0394601854nas a2200193 4500008004100000245008800041210006900129260001400198520128100212100001501493700001701508700001501525700001601540700001701556700001401573700001901587700001701606856003701623 2020 eng d00aProbing XY phase transitions in a Josephson junction array with tunable frustration0 aProbing XY phase transitions in a Josephson junction array with  c1/22/20203 a

The seminal theoretical works of Berezinskii, Kosterlitz, and Thouless presented a new paradigm for phase transitions in condensed matter that are driven by topological excitations. These transitions have been extensively studied in the context of two-dimensional XY models -- coupled compasses -- and have generated interest in the context of quantum simulation. Here, we use a circuit quantum-electrodynamics architecture to study the critical behavior of engineered XY models through their dynamical response. In particular, we examine not only the unfrustrated case but also the fully-frustrated case which leads to enhanced degeneracy associated with the spin rotational [U(1)] and discrete chiral (Z2) symmetries. The nature of the transition in the frustrated case has posed a challenge for theoretical studies while direct experimental probes remain elusive. Here we identify the transition temperatures for both the unfrustrated and fully-frustrated XY models by probing a Josephson junction array close to equilibrium using weak microwave excitations and measuring the temperature dependence of the effective damping obtained from the complex reflection coefficient. We argue that our probing technique is primarily sensitive to the dynamics of the U(1) part.

1 aCosmic, R.1 aKawabata, K.1 aAshida, Y.1 aIkegami, H.1 aFurukawa, S.1 aPatil, P.1 aTaylor, J., M.1 aNakamura, Y. uhttps://arxiv.org/abs/2001.0787701814nas a2200169 4500008004100000245006700041210006600108260001400174490000800188520130400196100001701500700002201517700002401539700002501563700001901588856003701607 2019 eng d00aProbing ground-state phase transitions through quench dynamics0 aProbing groundstate phase transitions through quench dynamics c9/11/20190 v1233 a

The study of quantum phase transitions requires the preparation of a many-body system near its ground state, a challenging task for many experimental systems. The measurement of quench dynamics, on the other hand, is now a routine practice in most cold atom platforms. Here we show that quintessential ingredients of quantum phase transitions can be probed directly with quench dynamics in integrable and nearly integrable systems. As a paradigmatic example, we study global quench dynamics in a transverse-field Ising model with either short-range or long-range interactions. When the model is integrable, we discover a new dynamical critical point with a non-analytic signature in the short-range correlators. The location of the dynamical critical point matches that of the quantum critical point and can be identified using a finite-time scaling method. We extend this scaling picture to systems near integrability and demonstrate the continued existence of a dynamical critical point detectable at prethermal time scales. Therefore, our method can be used to approximately locate the quantum critical point. The scaling method is also relevant to experiments with finite time and system size, and our predictions are testable in near-term experiments with trapped ions and Rydberg atoms.

1 aTitum, Paraj1 aIosue, Joseph, T.1 aGarrison, James, R.1 aGorshkov, Alexey, V.1 aGong, Zhe-Xuan uhttps://arxiv.org/abs/1809.0637701709nas a2200241 4500008004100000245007100041210006900112260001500181520103600196100001501232700002101247700001801268700001801286700002501304700001301329700001401342700001201356700001501368700001701383700001401400700001601414856003701430 2019 eng d00aProgrammable Quantum Simulations of Spin Systems with Trapped Ions0 aProgrammable Quantum Simulations of Spin Systems with Trapped Io c12/17/20193 a

Laser-cooled and trapped atomic ions form an ideal standard for the simulation of interacting quantum spin models. Effective spins are represented by appropriate internal energy levels within each ion, and the spins can be measured with near-perfect efficiency using state-dependent fluorescence techniques. By applying optical fields that exert optical dipole forces on the ions, their Coulomb interaction can be modulated in ways that give rise to long-range and tunable spin-spin interactions that can be reconfigured by shaping the spectrum and pattern of the laser fields. Here we review the theoretical mapping of atomic ions to interacting spin systems, the experimental preparation of complex equilibrium states, and the study of dynamical processes of this many-body interacting quantum system. The use of such quantum simulators for studying spin models may inform our understanding of exotic quantum materials and shed light on interacting quantum systems that cannot be modeled with conventional computers. 

1 aMonroe, C.1 aCampbell, W., C.1 aDuan, L., -M.1 aGong, Z., -X.1 aGorshkov, Alexey, V.1 aHess, P.1 aIslam, R.1 aKim, K.1 aPagano, G.1 aRicherme, P.1 aSenko, C.1 aYao, N., Y. uhttps://arxiv.org/abs/1912.0784501718nas a2200169 4500008004100000245008800041210006900129260001500198520118200213100001501395700002001410700001701430700002201447700001901469700002301488856003701511 2018 eng d00aCircuit QED-based measurement of vortex lattice order in a Josephson junction array0 aCircuit QEDbased measurement of vortex lattice order in a Joseph c2018/03/123 a

Superconductivity provides a canonical example of a quantum phase of matter. When superconducting islands are connected by Josephson junctions in a lattice, the low temperature state of the system can map to the celebrated XY model and its associated universality classes. This has been used to experimentally implement realizations of Mott insulator and Berezinskii--Kosterlitz--Thouless (BKT) transitions to vortex dynamics analogous to those in type-II superconductors. When an external magnetic field is added, the effective spins of the XY model become frustrated, leading to the formation of topological defects (vortices). Here we observe the many-body dynamics of such an array, including frustration, via its coupling to a superconducting microwave cavity. We take the design of the transmon qubit, but replace the single junction between two antenna pads with the complete array. This allows us to probe the system at 10 mK with minimal self-heating by using weak coherent states at the single (microwave) photon level to probe the resonance frequency of the cavity. We observe signatures of ordered vortex lattice at rational flux fillings of the array. 

1 aCosmic, R.1 aIkegami, Hiroki1 aLin, Zhirong1 aInomata, Kunihiro1 aTaylor, J., M.1 aNakamura, Yasunobu uhttps://arxiv.org/abs/1803.0411301662nas 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-15201552nas a2200181 4500008004100000245007900041210006900120260001500189300001100204490000700215520101200222100002101234700001901255700001901274700001901293700002101312856003701333 2017 eng d00aHigh-Order Multipole Radiation from Quantum Hall States in Dirac Materials0 aHighOrder Multipole Radiation from Quantum Hall States in Dirac  c2017/06/30 a2354390 v953 a

Topological states can exhibit electronic coherence on macroscopic length scales. When the coherence length exceeds the wavelength of light, one can expect new phenomena to occur in the optical response of these states. We theoretically characterize this limit for integer quantum Hall states in two-dimensional Dirac materials. We find that the radiation from the bulk is dominated by dipole emission, whose spectral properties vary with the local disorder potential. On the other hand, the radiation from the edge is characterized by large multipole moments in the far-field associated with the efficient transfer of angular momentum from the electrons into the scattered light. These results demonstrate that high-order multipole transitions are a necessary component for the optical spectroscopy and control of quantum Hall and related topological states in electronic systems.

1 aGullans, Michael1 aTaylor, J., M.1 aImamoglu, Atac1 aGhaemi, Pouyan1 aHafezi, Mohammad uhttps://arxiv.org/abs/1701.0346402646nas a2200241 4500008004100000245008200041210006900123260001500192520190700207100002902114700002302143700001802166700002302184700001502207700002002222700002702242700002402269700001902293700002002312700001702332700001802349856003702367 2017 eng d00aOn the readiness of quantum optimization machines for industrial applications0 areadiness of quantum optimization machines for industrial applic c2017/08/313 a

There have been multiple attempts to demonstrate that quantum annealing and, in particular, quantum annealing on quantum annealing machines, has the potential to outperform current classical optimization algorithms implemented on CMOS technologies. The benchmarking of these devices has been controversial. Initially, random spin-glass problems were used, however, these were quickly shown to be not well suited to detect any quantum speedup. Subsequently, benchmarking shifted to carefully crafted synthetic problems designed to highlight the quantum nature of the hardware while (often) ensuring that classical optimization techniques do not perform well on them. Even worse, to date a true sign of improved scaling with the number problem variables remains elusive when compared to classical optimization techniques. Here, we analyze the readiness of quantum annealing machines for real-world application problems. These are typically not random and have an underlying structure that is hard to capture in synthetic benchmarks, thus posing unexpected challenges for optimization techniques, both classical and quantum alike. We present a comprehensive computational scaling analysis of fault diagnosis in digital circuits, considering architectures beyond D-wave quantum annealers. We find that the instances generated from real data in multiplier circuits are harder than other representative random spin-glass benchmarks with a comparable number of variables. Although our results show that transverse-field quantum annealing is outperformed by state-of-the-art classical optimization algorithms, these benchmark instances are hard and small in the size of the input, therefore representing the first industrial application ideally suited for near-term quantum annealers.

1 aPerdomo-Ortiz, Alejandro1 aFeldman, Alexander1 aOzaeta, Asier1 aIsakov, Sergei, V.1 aZhu, Zheng1 aO'Gorman, Bryan1 aKatzgraber, Helmut, G.1 aDiedrich, Alexander1 aNeven, Hartmut1 ade Kleer, Johan1 aLackey, Brad1 aBiswas, Rupak uhttps://arxiv.org/abs/1708.0978002179nas a2200157 4500008004100000245010300041210006900144520165700213100002001870700001901890700001901909700001701928700002501945700001501970856003601985 2016 eng d00aMapping constrained optimization problems to quantum annealing with application to fault diagnosis0 aMapping constrained optimization problems to quantum annealing w3 aCurrent quantum annealing (QA) hardware suffers from practical limitations such as finite temperature, sparse connectivity, small qubit numbers, and control error. We propose new algorithms for mapping boolean constraint satisfaction problems (CSPs) onto QA hardware mitigating these limitations. In particular we develop a new embedding algorithm for mapping a CSP onto a hardware Ising model with a fixed sparse set of interactions, and propose two new decomposition algorithms for solving problems too large to map directly into hardware. The mapping technique is locally-structured, as hardware compatible Ising models are generated for each problem constraint, and variables appearing in different constraints are chained together using ferromagnetic couplings. In contrast, global embedding techniques generate a hardware independent Ising model for all the constraints, and then use a minor-embedding algorithm to generate a hardware compatible Ising model. We give an example of a class of CSPs for which the scaling performance of D-Wave's QA hardware using the local mapping technique is significantly better than global embedding. We validate the approach by applying D-Wave's hardware to circuit-based fault-diagnosis. For circuits that embed directly, we find that the hardware is typically able to find all solutions from a min-fault diagnosis set of size N using 1000N samples, using an annealing rate that is 25 times faster than a leading SAT-based sampling method. Further, we apply decomposition algorithms to find min-cardinality faults for circuits that are up to 5 times larger than can be solved directly on current hardware.1 aBian, Zhengbing1 aChudak, Fabian1 aIsrael, Robert1 aLackey, Brad1 aMacready, William, G1 aRoy, Aidan uhttp://arxiv.org/abs/1603.0311103037nas a2200193 4500008004100000245010200041210006900143260001500212300000700227490000600234520240900240100002002649700001902669700002602688700001702714700002502731700001502756856007202771 2016 eng d00aMapping contrained optimization problems to quantum annealing with application to fault diagnosis0 aMapping contrained optimization problems to quantum annealing wi c2016/07/28 a140 v33 a

Current quantum annealing (QA) hardware suffers from practical limitations such as finite temperature, sparse connectivity, small qubit numbers, and control error. We propose new algorithms for mapping Boolean constraint satisfaction problems (CSPs) onto QA hardware mitigating these limitations. In particular, we develop a new embedding algorithm for mapping a CSP onto a hardware Ising model with a fixed sparse set of interactions and propose two new decomposition algorithms for solving problems too large to map directly into hardware. The mapping technique is locally structured, as hardware compatible Ising models are generated for each problem constraint, and variables appearing in different constraints are chained together using ferromagnetic couplings. By contrast, global embedding techniques generate a hardware-independent Ising model for all the constraints, and then use a minor-embedding algorithm to generate a hardware compatible Ising model. We give an example of a class of CSPs for which the scaling performance of the D-Wave hardware using the local mapping technique is significantly better than global embedding. We validate the approach by applying D- Wave’s QA hardware to circuit-based fault diagnosis. For circuits that embed directly, we find that the hardware is typically able to find all solutions from a min-fault diagnosis set of size N using 1000 N samples, using an annealing rate that is 25 times faster than a leading SAT-based sampling method. Furthermore, we apply decomposition algorithms to find min-cardinality faults for circuits that are up to 5 times larger than can be solved directly on current hardware.

1 aBian, Zhengbing1 aChudak, Fabian1 aIsrael, Robert, Brian1 aLackey, Brad1 aMacready, William, G1 aRoy, Aiden uhttp://journal.frontiersin.org/article/10.3389/fict.2016.00014/full01375nas a2200193 4500008004100000245007300041210006900114260002600183300000700209490000600216520073500222100002000957700001900977700001900996700001701015700002501032700001501057856010901072 2014 eng d00aDiscrete optimization using quantum annealing on sparse Ising models0 aDiscrete optimization using quantum annealing on sparse Ising mo bFrontiersc2014/09/01 a560 v23 aThis paper discusses techniques for solving discrete optimization problems using quantum annealing. Practical issues likely to affect the computation include precision limitations, finite temperature, bounded energy range, sparse connectivity, and small numbers of qubits. To address these concerns we propose a way of finding energy representations with large classical gaps between ground and first excited states, efficient algorithms for mapping non-compatible Ising models into the hardware, and the use of decomposition methods for problems that are too large to fit in hardware. We validate the approach by describing experiments with D-Wave quantum hardware for low density parity check decoding with up to 1000 variables.1 aBian, Zhengbing1 aChudak, Fabian1 aIsrael, Robert1 aLackey, Brad1 aMacready, William, G1 aRoy, Aidan uhttps://www.quics.umd.edu/publications/discrete-optimization-using-quantum-annealing-sparse-ising-models01152nas a2200133 4500008004100000245006100041210006100102260001400163490000600177520075500183100002300938700002000961856003700981 2014 eng d00aQuantum computation of discrete logarithms in semigroups0 aQuantum computation of discrete logarithms in semigroups c2014/01/10 v83 a We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor's algorithms for period finding and discrete log as subroutines. Thus proposed cryptosystems based on the presumed hardness of discrete logarithms in semigroups are insecure against quantum attacks. In contrast, we show that some generalizations of the discrete log problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete log problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to $k \ge 2$ generators in a black-box abelian semigroup of order $N$ requires $\tilde \Theta(N^{\frac{1}{2}-\frac{1}{2k}})$ quantum queries. 1 aChilds, Andrew, M.1 aIvanyos, Gábor uhttp://arxiv.org/abs/1310.6238v201289nas a2200205 4500008004100000245007500041210006900116260001300185490000800198520067800206100002100884700001900905700002200924700001700946700001500963700001900978700002500997700002401022856003701046 2013 eng d00aQuantum Catalysis of Magnetic Phase Transitions in a Quantum Simulator0 aQuantum Catalysis of Magnetic Phase Transitions in a Quantum Sim c2013/9/50 v1113 a We control quantum fluctuations to create the ground state magnetic phases of a classical Ising model with a tunable longitudinal magnetic field using a system of 6 to 10 atomic ion spins. Due to the long-range Ising interactions, the various ground state spin configurations are separated by multiple first-order phase transitions, which in our zero temperature system cannot be driven by thermal fluctuations. We instead use a transverse magnetic field as a quantum catalyst to observe the first steps of the complete fractal devil's staircase, which emerges in the thermodynamic limit and can be mapped to a large number of many-body and energy-optimization problems. 1 aRicherme, Philip1 aSenko, Crystal1 aKorenblit, Simcha1 aSmith, Jacob1 aLee, Aaron1 aIslam, Rajibul1 aCampbell, Wesley, C.1 aMonroe, Christopher uhttp://arxiv.org/abs/1303.6983v201417nas a2200253 4500008004100000245008300041210006900124260001500193300001100208490000700219520068500226100002200911700001600933700002300949700001900972700002300991700001901014700001801033700001701051700001801068700001601086700002401102856003701126 2012 eng d00aQuantum Simulation of Spin Models on an Arbitrary Lattice with Trapped Ions 0 aQuantum Simulation of Spin Models on an Arbitrary Lattice with T c2012/09/27 a0950240 v143 a A collection of trapped atomic ions represents one of the most attractive platforms for the quantum simulation of interacting spin networks and quantum magnetism. Spin-dependent optical dipole forces applied to an ion crystal create long-range effective spin-spin interactions and allow the simulation of spin Hamiltonians that possess nontrivial phases and dynamics. Here we show how appropriate design of laser fields can provide for arbitrary multidimensional spin-spin interaction graphs even for the case of a linear spatial array of ions. This scheme uses currently existing trap technology and is scalable to levels where classical methods of simulation are intractable. 1 aKorenblit, Simcha1 aKafri, Dvir1 aCampbell, Wess, C.1 aIslam, Rajibul1 aEdwards, Emily, E.1 aGong, Zhe-Xuan1 aLin, Guin-Dar1 aDuan, Luming1 aKim, Jungsang1 aKim, Kihwan1 aMonroe, Christopher uhttp://arxiv.org/abs/1201.0776v101230nas a2200193 4500008004100000245007800041210006900119260001500188520065600203100001900859700001500878700001500893700001600908700001800924700001500942700001800957700001700975856004400992 2004 eng d00aQuantum information processing using localized ensembles of nuclear spins0 aQuantum information processing using localized ensembles of nucl c2004/07/233 aWe describe a technique for quantum information processing based on localized en sembles of nuclear spins. A qubit is identified as the presence or absence of a collective excitation of a mesoscopic ensemble of nuclear spins surrounding a single quantum dot. All single and two-qubit operations can be effected using hyperfine interactions and single-electron spin rotations, hence the proposed scheme avoids gate errors arising from entanglement between spin and orbital degrees of freedom. Ultra-long coherence times of nuclear spins suggest that this scheme could be particularly well suited for applications where long lived memory is essential. 1 aTaylor, J., M.1 aGiedke, G.1 aChrist, H.1 aParedes, B.1 aCirac, J., I.1 aZoller, P.1 aLukin, M., D.1 aImamoglu, A. uhttp://arxiv.org/abs/cond-mat/0407640v201129nas a2200145 4500008004100000245007400041210006900115260001500184490000700199520067900206100001900885700001700904700001800921856004400939 2003 eng d00aControlling a mesoscopic spin environment by quantum bit manipulation0 aControlling a mesoscopic spin environment by quantum bit manipul c2003/12/100 v913 aWe present a unified description of cooling and manipulation of a mesoscopic bath of nuclear spins via coupling to a single quantum system of electronic spin (quantum bit). We show that a bath cooled by the quantum bit rapidly saturates. Although the resulting saturated states of the spin bath (``dark states'') generally have low degrees of polarization and purity, their symmetry properties make them a valuable resource for the coherent manipulation of quantum bits. Specifically, we demonstrate that the dark states of nuclear ensembles can be used to coherently control the system-bath interaction and to provide a robust, long-lived quantum memory for qubit states. 1 aTaylor, J., M.1 aImamoglu, A.1 aLukin, M., D. uhttp://arxiv.org/abs/cond-mat/0308459v1