01254nas a2200157 4500008004100000245003300041210002900074260001400103520086100117100001300978700001400991700002201005700001701027700001501044856003701059 2024 eng d00aThe Quantum Abstract Machine0 aQuantum Abstract Machine c2/21/20243 a

This paper develops a model of quantum behavior that is intended to support the abstract yet accurate design and functional verification of quantum communication protocols. The work is motivated by the need for conceptual tools for the development of quantum-communication systems that are usable by non-specialists in quantum physics while also correctly capturing at a useful abstraction the underlying quantum phenomena. Our approach involves defining a quantum abstract machine (QAM) whose operations correspond to well-known quantum circuits; these operations, however, are given direct abstract semantics in a style similar to that of Berry's and Boudol's Chemical Abstract Machine. This paper defines the QAM's semantics and shows via examples how it may be used to model and reason about existing quantum communication protocols.

1 aLi, Liyi1 aChang, Le1 aCleaveland, Rance1 aZhu, Mingwei1 aWu, Xiaodi uhttps://arxiv.org/abs/2402.1346901285nas a2200121 4500008004100000245009700041210006900138260001400207520087200221100001901093700001401112856003701126 2024 eng d00aA Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles0 aQuantum Lifting Theorem for Constructions of Pseudorandom Genera c1/30/20243 a

We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles. We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making polynomially many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense. As a result of independent interest, we also show that any pseudo-deterministic quantum-oracle algorithm (i.e., a quantum algorithm that with high probability returns the same value on repeated executions) can be simulated by a computationally unbounded but query bounded classical-oracle algorithm with only a polynomial blowup in the number of queries. This implies as a corollary that our lifting theorem holds even for PRGs that themselves make quantum queries to the random oracle.

1 aKatz, Jonathan1 aSela, Ben uhttps://arxiv.org/abs/2401.1431901910nas a2200121 4500008004100000245008000041210006900121260001300190520150500203100002001708700002301728856003701751 2024 eng d00aQuantum One-Wayness of the Single-Round Sponge with Invertible Permutations0 aQuantum OneWayness of the SingleRound Sponge with Invertible Per c3/7/20243 a

Sponge hashing is a novel class of cryptographic hash algorithms which underlies the current international hash function standard SHA-3. In a nutshell, a sponge function takes as input a bit-stream of any length and processes it via a simple iterative procedure: it repeatedly feeds each block of the input into a so-called block function, and then produces a short digest which consists of a subset of the final output bits. While much is known about the post-quantum security of the sponge construction in the case when the block function is modeled as a random function or permutation, the case of invertible permutations, which more accurately models the construction underlying SHA-3, has so far remained a fundamental open problem.
In this work, we make new progress towards overcoming this barrier and show several results. First, we prove the "double-sided zero-search" conjecture proposed by Unruh (eprint' 2021) and show that finding zero-pairs in a random 2n-bit permutation requires at least Ω(2n/2) many queries -- and this is tight due to Grover's algorithm. At the core of our proof lies a novel "symmetrization argument" which uses insights from the theory of Young subgroups. Second, we consider more general variants of the double-sided search problem and show similar query lower bounds for them. As an application, we prove the quantum one-wayness of the single-round sponge with invertible permutations in the quantum random oracle model.

1 aCarolan, Joseph1 aPoremba, Alexander uhttps://arxiv.org/abs/2403.0474002067nas a2200169 4500008004100000245008100041210006900122260001300191520151900204100002001723700002701743700002001770700002301790700001901813700002801832856003701860 2024 eng d00aQuantum thermodynamics of nonequilibrium processes in lattice gauge theories0 aQuantum thermodynamics of nonequilibrium processes in lattice ga c4/3/20243 a

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

1 aDavoudi, Zohreh1 aJarzynski, Christopher1 aMueller, Niklas1 aOruganti, Greeshma1 aPowers, Connor1 aHalpern, Nicole, Yunger uhttps://arxiv.org/abs/2404.0296501569nas a2200169 4500008004100000245008700041210006900128260001400197520105800211100001301269700001701282700002201299700001201321700001401333700001501347856003701362 2023 eng d00aQafny: Quantum Program Verification Through Type-guided Classical Separation Logic0 aQafny Quantum Program Verification Through Typeguided Classical  c7/12/20233 a

Formal verification has been proven instrumental to ensure that quantum programs implement their specifications but often requires a significant investment of time and labor. To address this challenge, we present Qafny, an automated proof system designed for verifying quantum programs. At its core, Qafny uses a type-guided quantum proof system that translates quantum operations to classical array operations. By modeling these operations as proof rules within a classical separation logic framework, Qafny provides automated support for the reasoning process that would otherwise be tedious and time-consuming. We prove the soundness and completeness of our proof system and implement a prototype compiler that transforms Qafny programs both into the Dafny programming language and into executable quantum circuits. Using Qafny, we demonstrate how to efficiently verify prominent quantum algorithms, including quantum-walk algorithms, Grover's search algorithm, and Shor's factoring algorithm, with significantly reduced human efforts.

1 aLi, Liyi1 aZhu, Mingwei1 aCleaveland, Rance1 aLee, Yi1 aChang, Le1 aWu, Xiaodi uhttps://arxiv.org/abs/2211.0641101581nas a2200181 4500008004100000245006200041210006200103260001100165490000600176520106100182100002701243700002301270700001901293700001701312700001801329700001501347856003701362 2023 eng d00aQuantum algorithm for estimating volumes of convex bodies0 aQuantum algorithm for estimating volumes of convex bodies c4/20230 v43 a

Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an n-dimensional convex body within multiplicative error ε using O~(n3.5+n2.5/ε) queries to a membership oracle and O~(n5.5+n4.5/ε) additional arithmetic operations. For comparison, the best known classical algorithm uses O~(n4+n3/ε2) queries and O~(n6+n5/ε2) additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of "Chebyshev cooling", where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error.

1 aChakrabarti, Shouvanik1 aChilds, Andrew, M.1 aHung, Shih-Han1 aLi, Tongyang1 aWang, Chunhao1 aWu, Xiaodi uhttps://arxiv.org/abs/1908.0390301051nas a2200133 4500008004100000245010100041210006900142260001400211520060600225100001300831700002300844700001300867856003700880 2023 eng d00aQuantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters0 aQuantum algorithm for linear nonunitary dynamics with nearoptima c12/6/20233 a

We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the first time, this approach enables quantum algorithms to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters.

1 aAn, Dong1 aChilds, Andrew, M.1 aLin, Lin uhttps://arxiv.org/abs/2312.0391601818nas a2200169 4500008004100000020002200041245005100063210005100114300001600165490000800181520131000189100002301499700002101522700002501543700002401568856005601592 2023 eng d a978-3-95977-263-100aQuantum Algorithms and the Power of Forgetting0 aQuantum Algorithms and the Power of Forgetting a37:1--37:220 v2513 a

The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm [Andrew M. Childs et al., 2003]. Given the name of a special entrance vertex, a quantum walk can find another distinguished exit vertex using polynomially many queries, though without finding any particular path from entrance to exit. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from entrance to exit. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the entrance, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget the path they take to reach a solution in order to outperform classical computation.

1 aChilds, Andrew, M.1 aCoudron, Matthew1 aGilani, Amin, Shiraz1 aKalai, Yael, Tauman uhttps://drops.dagstuhl.de/opus/volltexte/2023/1754002470nas a2200169 4500008004100000245007100041210006900112260001400181520193200195100002202127700002202149700002402171700002302195700002502218700002002243856003702263 2023 eng d00aQuantum Algorithms for Simulating Nuclear Effective Field Theories0 aQuantum Algorithms for Simulating Nuclear Effective Field Theori c12/8/20233 a

Quantum computers offer the potential to simulate nuclear processes that are classically intractable. With the goal of understanding the necessary quantum resources, we employ state-of-the-art Hamiltonian-simulation methods, and conduct a thorough algorithmic analysis, to estimate the qubit and gate costs to simulate low-energy effective field theories (EFTs) of nuclear physics. In particular, within the framework of nuclear lattice EFT, we obtain simulation costs for the leading-order pionless and pionful EFTs. We consider both static pions represented by a one-pion-exchange potential between the nucleons, and dynamical pions represented by relativistic bosonic fields coupled to non-relativistic nucleons. We examine the resource costs for the tasks of time evolution and energy estimation for physically relevant scales. We account for model errors associated with truncating either long-range interactions in the one-pion-exchange EFT or the pionic Hilbert space in the dynamical-pion EFT, and for algorithmic errors associated with product-formula approximations and quantum phase estimation. Our results show that the pionless EFT is the least costly to simulate and the dynamical-pion theory is the costliest. We demonstrate how symmetries of the low-energy nuclear Hamiltonians can be utilized to obtain tighter error bounds on the simulation algorithm. By retaining the locality of nucleonic interactions when mapped to qubits, we achieve reduced circuit depth and substantial parallelization. We further develop new methods to bound the algorithmic error for classes of fermionic Hamiltonians that preserve the number of fermions, and demonstrate that reasonably tight Trotter error bounds can be achieved by explicitly computing nested commutators of Hamiltonian terms. This work highlights the importance of combining physics insights and algorithmic advancement in reducing quantum-simulation costs.

1 aWatson, James, D.1 aBringewatt, Jacob1 aShaw, Alexander, F.1 aChilds, Andrew, M.1 aGorshkov, Alexey, V.1 aDavoudi, Zohreh uhttps://arxiv.org/abs/2312.0534401354nas a2200157 4500008004100000245006100041210005900102260001400161520088700175100002301062700001601085700002301101700002001124700001501144856003701159 2023 eng d00aA quantum central path algorithm for linear optimization0 aquantum central path algorithm for linear optimization c11/7/20233 a

We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. While interior point methods follow the central path with an iterative algorithm that works with successive linearizations of the perturbed KKT conditions, we perform a single simulation working directly with the nonlinear complementarity equations. Combining our approach with iterative refinement techniques, we obtain an exact solution to a linear optimization problem involving m constraints and n variables using at most O((m+n)nnz(A)κ(M)L⋅polylog(m,n,κ(M))) elementary gates and O(nnz(A)L) classical arithmetic operations, where nnz(A) is the total number of non-zero elements found in the constraint matrix, L denotes binary input length of the problem data, and κ(M) is a condition number that depends only on the problem data.

1 aAugustino, Brandon1 aLeng, Jiaqi1 aNannicini, Giacomo1 aTerlaky, Tamás1 aWu, Xiaodi uhttps://arxiv.org/abs/2311.0397701916nas a2200169 4500008004100000245011700041210006900158260001400227520133400241100002001575700002001595700002101615700002001636700002701656700002601683856003701709 2023 eng d00aQuantum computation of dynamical quantum phase transitions and entanglement tomography in a lattice gauge theory0 aQuantum computation of dynamical quantum phase transitions and e c10/6/20233 a

Strongly-coupled gauge theories far from equilibrium may exhibit unique features that could illuminate the physics of the early universe and of hadron and ion colliders. Studying real-time phenomena has proven challenging with classical-simulation methods, but is a natural application of quantum simulation. To demonstrate this prospect, we quantum compute non-equal time correlation functions and perform entanglement tomography of non-equilibrium states of a simple lattice gauge theory, the Schwinger model, using a trapped-ion quantum computer by IonQ Inc. As an ideal target for near-term devices, a recently-predicted [Zache et al., Phys. Rev. Lett. 122, 050403 (2019)] dynamical quantum phase transition in this model is studied by preparing, quenching, and tracking the subsequent non-equilibrium dynamics in three ways: i) overlap echos signaling dynamical transitions, ii) non-equal time correlation functions with an underlying topological nature, and iii) the entanglement structure of non-equilibrium states, including entanglement Hamiltonians. These results constitute the first observation of a dynamical quantum phase transition in a lattice gauge theory on a quantum computer, and are a first step toward investigating topological phenomena in nuclear and high-energy physics using quantum technologies.

1 aMueller, Niklas1 aCarolan, Joseph1 aConnelly, Andrew1 aDavoudi, Zohreh1 aDumitrescu, Eugene, F.1 aYeter-Aydeniz, Kübra uhttps://arxiv.org/abs/2210.0308901891nas a2200145 4500008004100000245003200041210003200073260001300105520152500118100001601643700001901659700001501678700001501693856003701708 2023 eng d00aQuantum Hamiltonian Descent0 aQuantum Hamiltonian Descent c3/2/20233 a

Gradient descent is a fundamental algorithm in both theory and practice for continuous optimization. Identifying its quantum counterpart would be appealing to both theoretical and practical quantum applications. A conventional approach to quantum speedups in optimization relies on the quantum acceleration of intermediate steps of classical algorithms, while keeping the overall algorithmic trajectory and solution quality unchanged. We propose Quantum Hamiltonian Descent (QHD), which is derived from the path integral of dynamical systems referring to the continuous-time limit of classical gradient descent algorithms, as a truly quantum counterpart of classical gradient methods where the contribution from classically-prohibited trajectories can significantly boost QHD's performance for non-convex optimization. Moreover, QHD is described as a Hamiltonian evolution efficiently simulatable on both digital and analog quantum computers. By embedding the dynamics of QHD into the evolution of the so-called Quantum Ising Machine (including D-Wave and others), we empirically observe that the D-Wave-implemented QHD outperforms a selection of state-of-the-art gradient-based classical solvers and the standard quantum adiabatic algorithm, based on the time-to-solution metric, on non-convex constrained quadratic programming instances up to 75 dimensions. Finally, we propose a "three-phase picture" to explain the behavior of QHD, especially its difference from the quantum adiabatic algorithm.

1 aLeng, Jiaqi1 aHickman, Ethan1 aLi, Joseph1 aWu, Xiaodi uhttps://arxiv.org/abs/2303.0147101518nas a2200145 4500008004100000245006600041210006500107260001300172520107900185100001701264700002101281700001701302700001601319856003701335 2023 eng d00aQuantum Lego Expansion Pack: Enumerators from Tensor Networks0 aQuantum Lego Expansion Pack Enumerators from Tensor Networks c8/9/20233 a

We provide the first tensor network method for computing quantum weight enumerator polynomials in the most general form. As a corollary, if a quantum code has a known tensor network construction of its encoding map, our method produces an algorithm that computes its distance. For non-(Pauli)-stabilizer codes, this constitutes the current best algorithm for computing the code distance. For degenerate stabilizer codes, it can provide up to an exponential speed up compared to the current methods. We also introduce a few novel applications of different weight enumerators. In particular, for any code built from the quantum lego method, we use enumerators to construct its (optimal) decoders under any i.i.d. single qubit or qudit error channels and discuss their applications for computing logical error rates. As a proof of principle, we perform exact analyses of the deformed surface codes, the holographic pentagon code, and the 2d Bacon-Shor code under (biased) Pauli noise and limited instances of coherent error at sizes that are inaccessible by brute force.

1 aCao, ChunJun1 aGullans, Michael1 aLackey, Brad1 aWang, Zitao uhttps://arxiv.org/abs/2308.0515201590nas a2200217 4500008004100000245004000041210004000081260001400121520100000135100002101135700001601156700001501172700002201187700002001209700001901229700001901248700002101267700002201288700002501310856003701335 2023 eng d00aQuantum Sensing with Erasure Qubits0 aQuantum Sensing with Erasure Qubits c10/2/20233 a

The dominant noise in an "erasure qubit" is an erasure -- a type of error whose occurrence and location can be detected. Erasure qubits have potential to reduce the overhead associated with fault tolerance. To date, research on erasure qubits has primarily focused on quantum computing and quantum networking applications. Here, we consider the applicability of erasure qubits to quantum sensing and metrology. We show theoretically that, for the same level of noise, an erasure qubit acts as a more precise sensor or clock compared to its non-erasure counterpart. We experimentally demonstrate this by artificially injecting either erasure errors (in the form of atom loss) or dephasing errors into a differential optical lattice clock comparison, and observe enhanced precision in the case of erasure errors for the same injected error rate. Similar benefits of erasure qubits to sensing can be realized in other quantum platforms like Rydberg atoms and superconducting qubits

1 aNiroula, Pradeep1 aDolde, Jack1 aZheng, Xin1 aBringewatt, Jacob1 aEhrenberg, Adam1 aCox, Kevin, C.1 aThompson, Jeff1 aGullans, Michael1 aKolkowitz, Shimon1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2310.0151201207nas a2200181 4500008004100000022001400041245005100055210005000106260001300156300001400169490000600183520071300189100002500902700002000927700001800947700002300965856003700988 2023 eng d a2522-582000aQuantum Simulating Nature's Fundamental Fields0 aQuantum Simulating Natures Fundamental Fields c4/9/2024 a420–4320 v53 a

Simulating key static and dynamic properties of matter -- from creation in the Big Bang to evolution into sub-atomic and astrophysical environments -- arising from the underlying fundamental quantum fields of the Standard Model and their effective descriptions, lies beyond the capabilities of classical computation alone. Advances in quantum technologies have improved control over quantum entanglement and coherence to the point where robust simulations are anticipated to be possible in the foreseeable future. We discuss the emerging area of quantum simulations of Standard-Model physics, challenges that lie ahead, and opportunities for progress in the context of nuclear and high-energy physics.

1 aBauer, Christian, W.1 aDavoudi, Zohreh1 aKlco, Natalie1 aSavage, Martin, J. uhttps://arxiv.org/abs/2404.0629801735nas a2200145 4500008004100000245007200041210006900113260001400182490000800196520127600204100003501480700002501515700002801540856002101568 2023 eng d00aQuantum simulations of time travel can power nonclassical metrology0 aQuantum simulations of time travel can power nonclassical metrol c11/3/20230 v1313 a

We construct a metrology experiment in which the metrologist can sometimes amend her input state by simulating a closed timelike curve, a worldline that travels backward in time. The existence of closed timelike curves is hypothetical. Nevertheless, they can be simulated probabilistically by quantum-teleportation circuits. We leverage such simulations to pinpoint a counterintuitive nonclassical advantage achievable with entanglement. Our experiment echoes a common information-processing task: A metrologist must prepare probes to input into an unknown quantum interaction. The goal is to infer as much information per probe as possible. If the input is optimal, the information gained per probe can exceed any value achievable classically. The problem is that, only after the interaction does the metrologist learn which input would have been optimal. The metrologist can attempt to change her input by effectively teleporting the optimal input back in time, via entanglement manipulation. The effective time travel sometimes fails but ensures that, summed over trials, the metrologist's winnings are positive. Our Gedankenexperiment demonstrates that entanglement can generate operational advantages forbidden in classical chronology-respecting theories.

1 aArvidsson-Shukur, David, R. M.1 aMcConnell, Aidan, G.1 aHalpern, Nicole, Yunger uarXiv:2207.0766601025nas 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.0973301172nas a2200133 4500008004100000245007300041210006900114260001400183520075600197100001600953700001700969700001500986856003701001 2023 eng d00aA quantum-classical performance separation in nonconvex optimization0 aquantumclassical performance separation in nonconvex optimizatio c11/1/20233 a

In this paper, we identify a family of nonconvex continuous optimization instances, each d-dimensional instance with 2d local minima, to demonstrate a quantum-classical performance separation. Specifically, we prove that the recently proposed Quantum Hamiltonian Descent (QHD) algorithm [Leng et al., arXiv:2303.01471] is able to solve any d-dimensional instance from this family using O˜(d3) quantum queries to the function value and O˜(d4) additional 1-qubit and 2-qubit elementary quantum gates. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical optimization algorithms/solvers (including Gurobi) would require a super-polynomial time to solve such optimization instances.

1 aLeng, Jiaqi1 aZheng, Yufan1 aWu, Xiaodi uhttps://arxiv.org/abs/2311.0081101765nas a2200169 4500008004100000245008000041210006900121260001400190300001100204490000600215520126900221100001401490700001501504700001601519700002301535856003701558 2023 eng d00aQubit-Oscillator Concatenated Codes: Decoding Formalism and Code Comparison0 aQubitOscillator Concatenated Codes Decoding Formalism and Code C c6/14/2023 a0203420 v43 a

Concatenating bosonic error-correcting codes with qubit codes can substantially boost the error-correcting power of the original qubit codes. It is not clear how to concatenate optimally, given that there are several bosonic codes and concatenation schemes to choose from, including the recently discovered Gottesman-Kitaev-Preskill (GKP) – stabilizer codes [Phys. Rev. Lett. 125, 080503 (2020)] that allow protection of a logical bosonic mode from fluctuations of the conjugate variables of the mode. We develop efficient maximum-likelihood decoders for and analyze the performance of three different concatenations of codes taken from the following set: qubit stabilizer codes, analog or Gaussian stabilizer codes, GKP codes, and GKP-stabilizer codes. We benchmark decoder performance against additive Gaussian white noise, corroborating our numerics with analytical calculations. We observe that the concatenation involving GKP-stabilizer codes outperforms the more conventional concatenation of a qubit stabilizer code with a GKP code in some cases. We also propose a GKP-stabilizer code that suppresses fluctuations in both conjugate variables without extra quadrature squeezing and formulate qudit versions of GKP-stabilizer codes.

1 aXu, Yijia1 aWang, Yixu1 aKuo, En-Jui1 aAlbert, Victor, V. uhttps://arxiv.org/abs/2209.0457300782nas a2200229 4500008004100000245009900041210006900140260001500209490000700224653004300231653002100274653002700295653002900322653003900351653003100390100002300421700001700444700001800461700001800479700001800497856003700515 2022 eng d00aQuantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants0 aQuantum Algorithms for Sampling LogConcave Distributions and Est c10/12/20220 v3510aFOS: Computer and information sciences10aFOS: Mathematics10aFOS: Physical sciences10aMachine Learning (cs.LG)10aOptimization and Control (math.OC)10aQuantum Physics (quant-ph)1 aChilds, Andrew, M.1 aLi, Tongyang1 aLiu, Jin-Peng1 aWang, Chunhao1 aZhang, Ruizhe uhttps://arxiv.org/abs/2210.0653902013nas 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.abi789402089nas a2200229 4500008004100000245004500041210004500086260001500131520136900146653003701515653003801552653004301590653002701633653003101660100002301691700002401714700002101738700002501759700001701784700002101801856003701822 2022 eng d00aQuantum Depth in the Random Oracle Model0 aQuantum Depth in the Random Oracle Model c10/12/20223 a

We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, we show that the following statements hold, relative to a random oracle:
(a) BPPQNCBPP≠BQP. This refutes Jozsa's conjecture [QIP 05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson's ten semi-grand challenges in quantum computing.
(b) BPPQNC⊈QNCBPP and QNCBPP⊈BPPQNC. This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [STOC 22].

10aComputational Complexity (cs.CC)10aCryptography and Security (cs.CR)10aFOS: Computer and information sciences10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aArora, Atul, Singh1 aColadangelo, Andrea1 aCoudron, Matthew1 aGheorghiu, Alexandru1 aSingh, Uttam1 aWaldner, Hendrik uhttps://arxiv.org/abs/2210.0645401490nas a2200205 4500008004100000245003100041210003100072260001500103520088200118653004301000653004301043653002701086653003101113100002301144700001901167700002201186700002101208700001801229856003701247 2022 eng d00aQuantum divide and conquer0 aQuantum divide and conquer c10/12/20223 a

The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem of size n into smaller subproblems (say, a copies of size n/b each), along with some auxiliary work of cost Caux(n), to give a recurrence relation
C(n)≤aC(n/b)+Caux(n)
for the classical complexity C(n). We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation
CQ(n)≤a−−√CQ(n/b)+O(CauxQ(n))
that characterizes the quantum query complexity. We apply this framework to obtain near-optimal quantum query complexities for various string problems, such as (i) recognizing regular languages; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.

10aData Structures and Algorithms (cs.DS)10aFOS: Computer and information sciences10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aChilds, Andrew, M.1 aKothari, Robin1 aKovacs-Deak, Matt1 aSundaram, Aarthi1 aWang, Daochen uhttps://arxiv.org/abs/2210.0641901774nas a2200145 4500008004100000245007900041210006900120260001500189300001100204490000600215520133600221100001701557700001701574856003701591 2022 eng d00aQuantum Lego: Building Quantum Error Correction Codes from Tensor Networks0 aQuantum Lego Building Quantum Error Correction Codes from Tensor c05/11/2022 a0203320 v33 a

We introduce a flexible and graphically intuitive framework that constructs complex quantum error correction codes from simple codes or states, generalizing code concatenation. More specifically, we represent the complex code constructions as tensor networks built from the tensors of simple codes or states in a modular fashion. Using a set of local moves known as operator pushing, one can derive properties of the more complex codes, such as transversal non-Clifford gates, by tracing the flow of operators in the network. The framework endows a network geometry to any code it builds and is valid for constructing stabilizer codes as well as non-stabilizer codes over qubits and qudits. For a contractible tensor network, the sequence of contractions also constructs a decoding/encoding circuit. To highlight the framework's range of capabilities and to provide a tutorial, we lay out some examples where we glue together simple stabilizer codes to construct non-trivial codes. These examples include the toric code and its variants, a holographic code with transversal non-Clifford operators, a 3d stabilizer code, and other stabilizer codes with interesting properties. Surprisingly, we find that the surface code is equivalent to the 2d Bacon-Shor code after "dualizing" its tensor network encoding map.

1 aCao, ChunJun1 aLackey, Brad uhttps://arxiv.org/abs/2109.0815801622nas 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.0552701921nas a2200205 4500008004100000245009400041210006900135260001500204520125300219653004301472653002701515653003401542653003101576100001301607700001701620700001201637700001401649700001501663856003701678 2022 eng d00aQuantum Natural Proof: A New Perspective of Hybrid Quantum-Classical Program Verification0 aQuantum Natural Proof A New Perspective of Hybrid QuantumClassic c11/11/20223 a

Many quantum programs are assured by formal verification, but such verification is usually laborious and time-consuming. This paper proposes quantum natural proof (QNP), an automated proof system for verifying hybrid quantum-classical algorithms. Natural proofs are a subclass of proofs that are amenable to completely automated reasoning, provide sound but incomplete procedures, and capture common reasoning tactics in program verification. The core of QNP is a type-guided quantum proof system, named Qafny, which views quantum operations as some classical array operations that can be modeled as proof rules in a classical separation logic framework, suitable for automated reasoning. We proved the soundness and completeness of the Qafny proof system as well as the soundness of the proof system compilation from Qafny to Dafny. By using the QNP implementation in Dafny, automated verification can be efficiently perform for many hybrid quantum-classical algorithms, including GHZ, Shor's, Grover's, and quantum walk algorithms, which saves a great amount of human efforts. In addition, quantum programs written in Qafny can be compiled to quantum circuits so that every verified quantum program can be run on a quantum machine.

10aFOS: Computer and information sciences10aFOS: Physical sciences10aProgramming Languages (cs.PL)10aQuantum Physics (quant-ph)1 aLi, Liyi1 aZhu, Mingwei1 aLee, Yi1 aChang, Le1 aWu, Xiaodi uhttps://arxiv.org/abs/2211.0641101358nas a2200181 4500008004100000245003900041210003900080260001300119520083800132653002700970653003100997100002301028700001901051700002101070700002301091700002501114856003701139 2022 eng d00aQuantum Routing with Teleportation0 aQuantum Routing with Teleportation c4/8/20223 a

We study the problem of implementing arbitrary permutations of qubits under interaction constraints in quantum systems that allow for arbitrarily fast local operations and classical communication (LOCC). In particular, we show examples of speedups over swap-based and more general unitary routing methods by distributing entanglement and using LOCC to perform quantum teleportation. We further describe an example of an interaction graph for which teleportation gives a logarithmic speedup in the worst-case routing time over swap-based routing. We also study limits on the speedup afforded by quantum teleportation - showing an O(NlogN−−−−−−−√) upper bound on the separation in routing time for any interaction graph - and give tighter bounds for some common classes of graphs.

10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aDevulapalli, Dhruv1 aSchoute, Eddie1 aBapat, Aniruddha1 aChilds, Andrew, M.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2204.0418502845nas a2200541 4500008004100000245004700041210004700088260001300135520125300148653002701401653004401428653004901472653004201521653002901563653003101592100002501623700002001648700002101668700002501689700002001714700002201734700002001756700002001776700001801796700002101814700002101835700001601856700001801872700001501890700001901905700002101924700002401945700002201969700001801991700001902009700002002028700002402048700002402072700002302096700001902119700002002138700002202158700001802180700002102198700002602219700002102245856003702266 2022 eng d00aQuantum Simulation for High Energy Physics0 aQuantum Simulation for High Energy Physics c4/7/20223 a

It is for the first time that Quantum Simulation for High Energy Physics (HEP) is studied in the U.S. decadal particle-physics community planning, and in fact until recently, this was not considered a mainstream topic in the community. This fact speaks of a remarkable rate of growth of this subfield over the past few years, stimulated by the impressive advancements in Quantum Information Sciences (QIS) and associated technologies over the past decade, and the significant investment in this area by the government and private sectors in the U.S. and other countries. High-energy physicists have quickly identified problems of importance to our understanding of nature at the most fundamental level, from tiniest distances to cosmological extents, that are intractable with classical computers but may benefit from quantum advantage. They have initiated, and continue to carry out, a vigorous program in theory, algorithm, and hardware co-design for simulations of relevance to the HEP mission. This community whitepaper is an attempt to bring this exciting and yet challenging area of research to the spotlight, and to elaborate on what the promises, requirements, challenges, and potential solutions are over the next decade and beyond.

10aFOS: Physical sciences10aHigh Energy Physics - Lattice (hep-lat)10aHigh Energy Physics - Phenomenology (hep-ph)10aHigh Energy Physics - Theory (hep-th)10aNuclear Theory (nucl-th)10aQuantum Physics (quant-ph)1 aBauer, Christian, W.1 aDavoudi, Zohreh1 aBalantekin, Baha1 aBhattacharya, Tanmoy1 aCarena, Marcela1 ade Jong, Wibe, A.1 aDraper, Patrick1 aEl-Khadra, Aida1 aGemelke, Nate1 aHanada, Masanori1 aKharzeev, Dmitri1 aLamm, Henry1 aLi, Ying-Ying1 aLiu, Junyu1 aLukin, Mikhail1 aMeurice, Yannick1 aMonroe, Christopher1 aNachman, Benjamin1 aPagano, Guido1 aPreskill, John1 aRinaldi, Enrico1 aRoggero, Alessandro1 aSantiago, David, I.1 aSavage, Martin, J.1 aSiddiqi, Irfan1 aSiopsis, George1 aVan Zanten, David1 aWiebe, Nathan1 aYamauchi, Yukari1 aYeter-Aydeniz, Kübra1 aZorzetti, Silvia uhttps://arxiv.org/abs/2204.0338102005nas a2200181 4500008004100000245004600041210004500087260001400132300000800146490000600154520152300160100002301683700001601706700001701722700001801739700001801757856004801775 2022 eng d00aQuantum simulation of real-space dynamics0 aQuantum simulation of realspace dynamics c11/8/2022 a8600 v63 a

Quantum simulation is a prominent application of quantum computers. While there is extensive previous work on simulating finite-dimensional systems, less is known about quantum algorithms for real-space dynamics. We conduct a systematic study of such algorithms. In particular, we show that the dynamics of a d-dimensional Schrödinger equation with η particles can be simulated with gate complexity O~(ηdFpoly(log(g′/ϵ))), where ϵ is the discretization error, g′ controls the higher-order derivatives of the wave function, and F measures the time-integrated strength of the potential. Compared to the best previous results, this exponentially improves the dependence on ϵ and g′ from poly(g′/ϵ) to poly(log(g′/ϵ)) and polynomially improves the dependence on T and d, while maintaining best known performance with respect to η. For the case of Coulomb interactions, we give an algorithm using η3(d+η)Tpoly(log(ηdTg′/(Δϵ)))/Δ one- and two-qubit gates, and another using η3(4d)d/2Tpoly(log(ηdTg′/(Δϵ)))/Δ one- and two-qubit gates and QRAM operations, where T is the evolution time and the parameter Δ regulates the unbounded Coulomb interaction. We give applications to several computational problems, including faster real-space simulation of quantum chemistry, rigorous analysis of discretization error for simulation of a uniform electron gas, and a quadratic improvement to a quantum algorithm for escaping saddle points in nonconvex optimization.

1 aChilds, Andrew, M.1 aLeng, Jiaqi1 aLi, Tongyang1 aLiu, Jin-Peng1 aZhang, Chenyi uhttps://doi.org/10.22331%2Fq-2022-11-17-86001806nas a2200181 4500008004100000245007200041210006900113260001500182520123900197653002701436653003101463100002001494700001601514700001801530700001901548700002001567856003701587 2022 eng d00aQuantum state tomography via non-convex Riemannian gradient descent0 aQuantum state tomography via nonconvex Riemannian gradient desce c10/10/20223 a

The recovery of an unknown density matrix of large size requires huge computational resources. The recent Factored Gradient Descent (FGD) algorithm and its variants achieved state-of-the-art performance since they could mitigate the dimensionality barrier by utilizing some of the underlying structures of the density matrix. Despite their theoretical guarantee of a linear convergence rate, the convergence in practical scenarios is still slow because the contracting factor of the FGD algorithms depends on the condition number κ of the ground truth state. Consequently, the total number of iterations can be as large as O(κ−−√ln(1ε)) to achieve the estimation error ε. In this work, we derive a quantum state tomography scheme that improves the dependence on κ to the logarithmic scale; namely, our algorithm could achieve the approximation error ε in O(ln(1κε)) steps. The improvement comes from the application of the non-convex Riemannian gradient descent (RGD). The contracting factor in our approach is thus a universal constant that is independent of the given state. Our theoretical results of extremely fast convergence and nearly optimal error bounds are corroborated by numerical results.

10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aHsu, Ming-Chien1 aKuo, En-Jui1 aYu, Wei-Hsuan1 aCai, Jian-Feng1 aHsieh, Min-Hsiu uhttps://arxiv.org/abs/2210.0471701906nas a2200205 4500008004100000245008600041210006900127260001400196520121200210653004301422653002701465653003801492653003401530653003101564100001901595700001301614700001701627700001901644856003701663 2022 eng d00aQunity: A Unified Language for Quantum and Classical Computing (Extended Version)0 aQunity A Unified Language for Quantum and Classical Computing Ex c4/26/20223 a

We introduce Qunity, a new quantum programming language designed to treat quantum computing as a natural generalization of classical computing. Qunity presents a unified syntax where familiar programming constructs can have both quantum and classical effects. For example, one can use sum types to implement the direct sum of linear operators, exception-handling syntax to implement projective measurements, and aliasing to induce entanglement. Further, Qunity takes advantage of the overlooked BQP subroutine theorem, allowing one to construct reversible subroutines from irreversible quantum algorithms through the uncomputation of "garbage" outputs. Unlike existing languages that enable quantum aspects with separate add-ons (like a classical language with quantum gates bolted on), Qunity provides a unified syntax and a novel denotational semantics that guarantees that programs are quantum mechanically valid. We present Qunity's syntax, type system, and denotational semantics, showing how it can cleanly express several quantum algorithms. We also detail how Qunity can be compiled into a low-level qubit circuit language like OpenQASM, proving the realizability of our design.

10aFOS: Computer and information sciences10aFOS: Physical sciences10aLogic in Computer Science (cs.LO)10aProgramming Languages (cs.PL)10aQuantum Physics (quant-ph)1 aVoichick, Finn1 aLi, Liyi1 aRand, Robert1 aHicks, Michael uhttps://arxiv.org/abs/2204.1238401482nas a2200145 4500008004100000245005500041210005500096260001400151490000600165520107700171100001801248700001601266700001701282856003701299 2021 eng d00aQuantum Algorithms for Escaping from Saddle Points0 aQuantum Algorithms for Escaping from Saddle Points c8/19/20210 v53 a

We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a function f:Rn→R, our quantum algorithm outputs an ϵ-approximate second-order stationary point using O~(log2n/ϵ1.75) queries to the quantum evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical state-of-the-art algorithm by Jin et al. with O~(log6n/ϵ1.75) queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms of n and matches its complexity in terms of 1/ϵ. Our quantum algorithm is built upon two techniques: First, we replace the classical perturbations in gradient descent methods by simulating quantum wave equations, which constitutes the polynomial speedup in n for escaping from saddle points. Second, we show how to use a quantum gradient computation algorithm due to Jordan to replace the classical gradient queries by quantum evaluation queries with the same complexity. Finally, we also perform numerical experiments that support our quantum speedup.

1 aZhang, Chenyi1 aLeng, Jiaqi1 aLi, Tongyang uhttps://arxiv.org/abs/2007.1025301833nas a2200217 4500008004100000245007400041210006900115260001500184490000800199520114200207653004301349653002701392653002901419653003101448100001801479700002101497700001901518700001901537700002201556856003701578 2021 eng d00aQuantum Algorithms for Reinforcement Learning with a Generative Model0 aQuantum Algorithms for Reinforcement Learning with a Generative  c12/15/20210 v1393 a

Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. A standard way to study this question abstractly is to ask how many samples an agent needs from the environment to learn an optimal policy for a γ-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy (π∗), the optimal value function (v∗), and the optimal Q-function (q∗), assuming the algorithms can access samples from the environment in quantum superposition. This assumption is justified whenever there exists a simulator for the environment; for example, if the environment is a video game or some other program. Our quantum algorithms, inspired by value iteration, achieve quadratic speedups over the best-possible classical sample complexities in the approximation accuracy (ϵ) and two main parameters of the MDP: the effective time horizon (11−γ) and the size of the action space (A). Moreover, we show that our quantum algorithm for computing q∗ is optimal by proving a matching quantum lower bound.

10aFOS: Computer and information sciences10aFOS: Physical sciences10aMachine Learning (cs.LG)10aQuantum Physics (quant-ph)1 aWang, Daochen1 aSundaram, Aarthi1 aKothari, Robin1 aKapoor, Ashish1 aRoetteler, Martin uhttps://arxiv.org/abs/2112.0845101362nas a2200193 4500008004100000022001400041245013800055210006900193260001400262490000800276520071000284100001900994700002101013700002401034700002401058700002301082700002601105856003701131 2021 eng d a2469-993400aQuantum circuits for the realization of equivalent forms of one-dimensional discrete-time quantum walks on near-term quantum hardware0 aQuantum circuits for the realization of equivalent forms of oned c12/8/20210 v1043 a

Quantum walks are a promising framework for developing quantum algorithms and quantum simulations. They represent an important test case for the application of quantum computers. Here we present different forms of discrete-time quantum walks (DTQWs) and show their equivalence for physical realizations. Using an appropriate digital mapping of the position space on which a walker evolves to the multiqubit states of a quantum processor, we present different configurations of quantum circuits for the implementation of DTQWs in one-dimensional position space. We provide example circuits for a five-qubit processor and address scalability to higher dimensions as well as larger quantum processors.

1 aSingh, Shivani1 aAlderete, Huerta1 aBalu, Radhakrishnan1 aMonroe, Christopher1 aLinke, Norbert, M.1 aChandrashekar, C., M. uhttps://arxiv.org/abs/2001.1119702003nas 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.1247401283nas a2200169 4500008004100000245005900041210005800100260000900158300001600167490000700183520079000190100001800980700001600998700001701014700002301031856005901054 2021 eng d00aQuantum exploration algorithms for multi-armed bandits0 aQuantum exploration algorithms for multiarmed bandits c2021 a10102-101100 v353 a

 Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we show that we can find the best arm with fixed confidence using O~(∑ni=2Δ−2i−−−−−−−−√) quantum queries, where Δi represents the difference between the mean reward of the best arm and the ith-best arm. This algorithm, based on variable-time amplitude amplification and estimation, gives a quadratic speedup compared to the best possible classical result. We also prove a matching quantum lower bound (up to poly-logarithmic factors).

1 aWang, Daochen1 aYou, Xuchen1 aLi, Tongyang1 aChilds, Andrew, M. uhttps://ojs.aaai.org/index.php/AAAI/article/view/1721201239nas a2200121 4500008004100000245002800041210002800069260001500097520092800112100002301040700001701063856003701080 2021 eng d00aQuantum Lattice Sieving0 aQuantum Lattice Sieving c10/26/20213 a

Lattices are very important objects in the effort to construct cryptographic primitives that are secure against quantum attacks. A central problem in the study of lattices is that of finding the shortest non-zero vector in the lattice. Asymptotically, sieving is the best known technique for solving the shortest vector problem, however, sieving requires memory exponential in the dimension of the lattice. As a consequence, enumeration algorithms are often used in place of sieving due to their linear memory complexity, despite their super-exponential runtime. In this work, we present a heuristic quantum sieving algorithm that has memory complexity polynomial in the size of the length of the sampled vectors at the initial step of the sieve. In other words, unlike most sieving algorithms, the memory complexity of our algorithm does not depend on the number of sampled vectors at the initial step of the sieve.

1 aRodrigues, Nishant1 aLackey, Brad uhttps://arxiv.org/abs/2110.1335201237nas a2200253 4500008004100000245004100041210004100082260001300123520055200136100001900688700002400707700002100731700002000752700002700772700001800799700001600817700001700833700002000850700002100870700001900891700001300910700002300923856003700946 2021 eng d00aQuantum Machine Learning for Finance0 aQuantum Machine Learning for Finance c9/9/20213 a

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

1 aPistoia, Marco1 aAhmad, Syed, Farhan1 aAjagekar, Akshay1 aButs, Alexander1 aChakrabarti, Shouvanik1 aHerman, Dylan1 aHu, Shaohan1 aJena, Andrew1 aMinssen, Pierre1 aNiroula, Pradeep1 aRattew, Arthur1 aSun, Yue1 aYalovetzky, Romina uhttps://arxiv.org/abs/2109.0429801935nas a2200145 4500008004100000245005100041210005100092260001300143520152400156100001801680700001901698700001701717700001801734856003701752 2021 eng d00aQuantum Meets the Minimum Circuit Size Problem0 aQuantum Meets the Minimum Circuit Size Problem c8/6/20213 a

In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory---its hardness is mysterious, and a better understanding of its hardness can have surprising implications to many fields in computer science.
We first define and investigate the basic complexity-theoretic properties of minimum quantum circuit size problems for three natural objects: Boolean functions, unitaries, and quantum states. We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols). Next, we explore the relations between the three quantum MCSPs and their variants. We discover that some reductions that are not known for classical MCSP exist for quantum MCSPs for unitaries and states, e.g., search-to-decision reduction and self-reduction. Finally, we systematically generalize results known for classical MCSP to the quantum setting (including quantum cryptography, quantum learning theory, quantum circuit lower bounds, and quantum fine-grained complexity) and also find new connections to tomography and quantum gravity. Due to the fundamental differences between classical and quantum circuits, most of our results require extra care and reveal properties and phenomena unique to the quantum setting. Our findings could be of interest for future studies, and we post several open problems for further exploration along this direction.

1 aChia, Nai-Hui1 aChou, Chi-Ning1 aZhang, Jiayu1 aZhang, Ruizhe uhttps://arxiv.org/abs/2108.0317101323nas a2200145 4500008004100000020002200041245005700063210005600120260008600176520080000262100002301062700001901085700001701104856005601121 2021 eng d a978-3-95977-195-500aQuantum Query Complexity with Matrix-Vector Products0 aQuantum Query Complexity with MatrixVector Products aDagstuhl, GermanybSchloss Dagstuhl – Leibniz-Zentrum für Informatikc2/7/20213 a

We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. We show that for various problems, including computing the trace, determinant, or rank of a matrix or solving a linear system that it specifies, quantum computers do not provide an asymptotic speedup over classical computation. On the other hand, we show that for some problems, such as computing the parities of rows or columns or deciding if there are two identical rows or columns, quantum computers provide exponential speedup. We demonstrate this by showing equivalence between models that provide matrix-vector products, vector-matrix products, and vector-matrix-vector products, whereas the power of these models can vary significantly for classical computation.

1 aChilds, Andrew, M.1 aHung, Shih-Han1 aLi, Tongyang uhttps://drops.dagstuhl.de/opus/volltexte/2021/1412401245nas a2200157 4500008004100000245005700041210005600098260001400154300001500168490000800183520080000191100002300991700001901014700001701033856003701050 2021 eng d00aQuantum query complexity with matrix-vector products0 aQuantum query complexity with matrixvector products c3/14/2021 a55:1-55:190 v1983 a

We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. We show that for various problems, including computing the trace, determinant, or rank of a matrix or solving a linear system that it specifies, quantum computers do not provide an asymptotic speedup over classical computation. On the other hand, we show that for some problems, such as computing the parities of rows or columns or deciding if there are two identical rows or columns, quantum computers provide exponential speedup. We demonstrate this by showing equivalence between models that provide matrix-vector products, vector-matrix products, and vector-matrix-vector products, whereas the power of these models can vary significantly for classical computation.

1 aChilds, Andrew, M.1 aHung, Shih-Han1 aLi, Tongyang uhttps://arxiv.org/abs/2102.1134901494nas a2200181 4500008004100000245004000041210004000081260001400121490000600135520100800141100002101149700002301170700002501193700001701218700001901235700002101254856003701275 2021 eng d00aQuantum routing with fast reversals0 aQuantum routing with fast reversals c8/24/20210 v53 a

We present methods for implementing arbitrary permutations of qubits under interaction constraints. Our protocols make use of previous methods for rapidly reversing the order of qubits along a path. Given nearest-neighbor interactions on a path of length n, we show that there exists a constant ϵ≈0.034 such that the quantum routing time is at most (1−ϵ)n, whereas any swap-based protocol needs at least time n−1. This represents the first known quantum advantage over swap-based routing methods and also gives improved quantum routing times for realistic architectures such as grids. Furthermore, we show that our algorithm approaches a quantum routing time of 2n/3 in expectation for uniformly random permutations, whereas swap-based protocols require time n asymptotically. Additionally, we consider sparse permutations that route k≤n qubits and give algorithms with quantum routing time at most n/3+O(k2) on paths and at most 2r/3+O(k2) on general graphs with radius r.

1 aBapat, Aniruddha1 aChilds, Andrew, M.1 aGorshkov, Alexey, V.1 aKing, Samuel1 aSchoute, Eddie1 aShastri, Hrishee uhttps://arxiv.org/abs/2103.0326401535nas a2200181 4500008004100000022001400041245005100055210005100106260001400157490000800171520104700179100001501226700001701241700001501258700001301273700001401286856005301300 2021 eng d a1079-711400aQuantum Simulation with Hybrid Tensor Networks0 aQuantum Simulation with Hybrid Tensor Networks c8/31/20210 v1273 a

Tensor network theory and quantum simulation are respectively the key classical and quantum computing methods in understanding quantum many-body physics. Here, we introduce the framework of hybrid tensor networks with building blocks consisting of measurable quantum states and classically contractable tensors, inheriting both their distinct features in efficient representation of many-body wave functions. With the example of hybrid tree tensor networks, we demonstrate efficient quantum simulation using a quantum computer whose size is significantly smaller than the one of the target system. We numerically benchmark our method for finding the ground state of 1D and 2D spin systems of up to 8×8 and 9×8 qubits with operations only acting on 8+1 and 9+1 qubits,~respectively. Our approach sheds light on simulation of large practical problems with intermediate-scale quantum computers, with potential applications in chemistry, quantum many-body physics, quantum field theory, and quantum gravity thought experiments.

1 aYuan, Xiao1 aSun, Jinzhao1 aLiu, Junyu1 aZhao, Qi1 aZhou, You uhttp://dx.doi.org/10.1103/PhysRevLett.127.04050101351nas a2200193 4500008004100000245011700041210006900158260001400227300000800241490000600249520075900255100001301014700001701027700001801044700002201062700002001084700001601104856003701120 2021 eng d00aQuantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance0 aQuantumaccelerated multilevel Monte Carlo methods for stochastic c6/22/2021 a4810 v53 a

Inspired by recent progress in quantum algorithms for ordinary and partial differential equations, we study quantum algorithms for stochastic differential equations (SDEs). Firstly we provide a quantum algorithm that gives a quadratic speed-up for multilevel Monte Carlo methods in a general setting. As applications, we apply it to compute expection values determined by classical solutions of SDEs, with improved dependence on precision. We demonstrate the use of this algorithm in a variety of applications arising in mathematical finance, such as the Black-Scholes and Local Volatility models, and Greeks. We also provide a quantum algorithm based on sublinear binomial sampling for the binomial option pricing model with the same improvement.

1 aAn, Dong1 aLinden, Noah1 aLiu, Jin-Peng1 aMontanaro, Ashley1 aShao, Changpeng1 aWang, Jiasu uhttps://arxiv.org/abs/2012.0628301512nas 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.0587101173nas a2200157 4500008004100000245006400041210006400105260001500169490000600184520070600190100002700896700002300923700001700946700001500963856003700978 2020 eng d00aQuantum algorithms and lower bounds for convex optimization0 aQuantum algorithms and lower bounds for convex optimization c12/18/20190 v43 a

While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n-dimensional convex body using O~(n) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω~(n−−√) evaluation queries and Ω(n−−√) membership queries.

1 aChakrabarti, Shouvanik1 aChilds, Andrew, M.1 aLi, Tongyang1 aWu, Xiaodi uhttps://arxiv.org/abs/1809.0173101946nas a2200157 4500008004100000245006600041210006600107260001300173490000600186520147300192100002401665700002101689700002301710700001801733856003701751 2020 eng d00aQuantum Algorithms for Simulating the Lattice Schwinger Model0 aQuantum Algorithms for Simulating the Lattice Schwinger Model c8/5/20200 v43 a

The Schwinger model (quantum electrodynamics in 1+1 dimensions) is a testbed for the study of quantum gauge field theories. We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In particular, we perform a tight analysis of low-order Trotter formula simulations of the Schwinger model, using recently derived commutator bounds, and give upper bounds on the resources needed for simulations in both scenarios. In lattice units, we find a Schwinger model on N/2 physical sites with coupling constant x−1/2 and electric field cutoff x−1/2Λ can be simulated on a quantum computer for time 2xT using a number of T-gates or CNOTs in O˜(N3/2T3/2x−−√Λ) for fixed operator error. This scaling with the truncation Λ is better than that expected from algorithms such as qubitization or QDRIFT. Furthermore, we give scalable measurement schemes and algorithms to estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density. Finally, we bound the root-mean-square error in estimating this observable via simulation as a function of the diamond distance between the ideal and actual CNOT channels. This work provides a rigorous analysis of simulating the Schwinger model, while also providing benchmarks against which subsequent simulation algorithms can be tested. 

1 aShaw, Alexander, F.1 aLougovski, Pavel1 aStryker, Jesse, R.1 aWiebe, Nathan uhttps://arxiv.org/abs/2002.1114601928nas a2200121 4500008004100000245006200041210006200103260001500165520155100180100002001731700001801751856003701769 2020 eng d00aQuantum algorithms for the polynomial eigenvalue problems0 aQuantum algorithms for the polynomial eigenvalue problems c10/28/20203 a

Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with A,B symmetric, and B positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when B is invertible, B−1A is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when B is singular, any quantum algorithm uses at least Ω(n−−√) queries to compute the eigenvalues, where n is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.

1 aShao, Changpeng1 aLiu, Jin-Peng uhttps://arxiv.org/abs/2010.1502702525nas a2200169 4500008004100000245006600041210006200107260001400169300000700183490000600190520198300196100001902179700002002198700001702218700002302235856009702258 2020 eng d00aOn Quantum Chosen-Ciphertext Attacks and Learning with Errors0 aQuantum ChosenCiphertext Attacks and Learning with Errors c3/21/2020 a100 v43 a

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

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

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

1 aGullans, Michael1 aKrastanov, Stefan1 aHuse, David, A.1 aJiang, Liang1 aFlammia, Steven, T. uhttps://arxiv.org/abs/2010.0977501627nas a2200193 4500008004100000245002900041210002900070260001400099300001500113490000800128520112700136100002801263700002301291700002301314700001901337700002001356700002001376856003701396 2020 eng d00aQuantum Coupon Collector0 aQuantum Coupon Collector c2/18/2020 a10:1-10:170 v1583 a

We study how efficiently a k-element set S⊆[n] can be learned from a uniform superposition |S⟩ of its elements. One can think of |S⟩=∑i∈S|i⟩/|S|−−−√ as the quantum version of a uniformly random sample over S, as in the classical analysis of the ``coupon collector problem.'' We show that if k is close to n, then we can learn S using asymptotically fewer quantum samples than random samples. In particular, if there are n−k=O(1) missing elements then O(k) copies of |S⟩ suffice, in contrast to the Θ(klogk) random samples needed by a classical coupon collector. On the other hand, if n−k=Ω(k), then Ω(klogk) quantum samples are~necessary. More generally, we give tight bounds on the number of quantum samples needed for every k and n, and we give efficient quantum learning algorithms. We also give tight bounds in the model where we can additionally reflect through |S⟩. Finally, we relate coupon collection to a known example separating proper and improper PAC learning that turns out to show no separation in the quantum case.

1 aArunachalam, Srinivasan1 aBelovs, Aleksandrs1 aChilds, Andrew, M.1 aKothari, Robin1 aRosmanis, Ansis1 ade Wolf, Ronald uhttps://arxiv.org/abs/2002.0768801529nas a2200145 4500008004100000245007400041210006900115260001500184490000800199520104100207100002601248700001701274700002201291856007001313 2020 eng d00aQuantum Lifshitz criticality in a frustrated two-dimensional XY model0 aQuantum Lifshitz criticality in a frustrated twodimensional XY m c01/09/20200 v1013 a

Antiferromagnetic quantum spin systems can exhibit a transition between collinear and spiral ground states,
driven by frustration. Classically this is a smooth crossover and the crossover point is termed a Lifshitz point.
Quantum fluctuations change the nature of the transition. In particular, it has been argued previously that in the two-dimensional (2D) case a spin liquid (SL) state is developed in the vicinity of the Lifshitz point, termed a Lifshitz SL. In the present work, using a field theory approach, we solve the Lifshitz quantum phase transition problem for the 2D frustrated XY model. Specifically, we show that, unlike the SU (2) symmetric Lifshitz case, in the XY model, the SL exists only at the critical point. At zero temperature we calculate nonuniversal critical exponents in the Néel and in the spin spiral state and relate these to properties of the SL. We also solve the transition problem at a finite temperature and discuss the role of topological excitations.

1 aKharkov, Yaroslav, A.1 aOitmaa, Jaan1 aSushkov, Oleg, P. uhttps://journals.aps.org/prb/abstract/10.1103/PhysRevB.101.03511401783nas a2200169 4500008004100000245010500041210006900146260001400215490000800229520122700237100002001464700002401484700001901508700002401527700002501551856003701576 2020 eng d00aQuantum Simulation of Hyperbolic Space with Circuit Quantum Electrodynamics: From Graphs to Geometry0 aQuantum Simulation of Hyperbolic Space with Circuit Quantum Elec c9/11/20200 v1023 a

We show how quantum many-body systems on hyperbolic lattices with nearest-neighbor hopping and local interactions can be mapped onto quantum field theories in continuous negatively curved space. The underlying lattices have recently been realized experimentally with superconducting resonators and therefore allow for a table-top quantum simulation of quantum physics in curved background. Our mapping provides a computational tool to determine observables of the discrete system even for large lattices, where exact diagonalization fails. As an application and proof of principle we quantitatively reproduce the ground state energy, spectral gap, and correlation functions of the noninteracting lattice system by means of analytic formulas on the Poincaré disk, and show how conformal symmetry emerges for large lattices. This sets the stage for studying interactions and disorder on hyperbolic graphs in the future. Our analysis also reveals in which sense discrete hyperbolic lattices emulate the continuous geometry of negatively curved space and thus can be used to resolve fundamental open problems at the interface of interacting many-body systems, quantum field theory in curved space, and quantum gravity.

1 aBoettcher, Igor1 aBienias, Przemyslaw1 aBelyansky, Ron1 aKollár, Alicia, J.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1910.1231801566nas a2200157 4500008004100000245005100041210005100092260001300143520114100156100001501297700001701312700001501329700001301344700001401357856003701371 2020 eng d00aQuantum simulation with hybrid tensor networks0 aQuantum simulation with hybrid tensor networks c7/2/20203 a

Tensor network theory and quantum simulation are respectively the key classical and quantum methods in understanding many-body quantum physics. Here we show hybridization of these two seemingly independent methods, inheriting both their distinct advantageous features of efficient representations of many-body wave functions. We introduce the framework of hybrid tensor networks with building blocks consisting of measurable quantum states and classically contractable tensors. As an example, we demonstrate efficient quantum simulation with hybrid tree tensor networks that use quantum hardware whose size is significantly smaller than the one of the target system. We numerically test our method for finding the ground state of 1D and 2D spin systems of up to 8×8 and 4×3 qubits with operations only acting on 8+1 and 4+1 qubits, respectively. Our approach paves the way to the near-term quantum simulation of large practical problems with intermediate size quantum hardware, with potential applications in quantum chemistry, quantum many-body physics, quantum field theory, and quantum gravity thought experiments.

1 aYuan, Xiao1 aSun, Jinzhao1 aLiu, Junyu1 aZhao, Qi1 aZhou, You uhttps://arxiv.org/abs/2007.0095801292nas a2200145 4500008004100000245005600041210005600097260001400153300001400167490000800181520087900189100002301068700001801091856003701109 2020 eng d00aQuantum spectral methods for differential equations0 aQuantum spectral methods for differential equations c2/18/2020 a1427-14570 v3753 a

Recently developed quantum algorithms address computational challenges in numerical analysis by performing linear algebra in Hilbert space. Such algorithms can produce a quantum state proportional to the solution of a d-dimensional system of linear equations or linear differential equations with complexity poly(logd). While several of these algorithms approximate the solution to within ε with complexity poly(log(1/ε)), no such algorithm was previously known for differential equations with time-dependent coefficients. Here we develop a quantum algorithm for linear ordinary differential equations based on so-called spectral methods, an alternative to finite difference methods that approximates the solution globally. Using this approach, we give a quantum algorithm for time-dependent initial and boundary value problems with complexity poly(logd,log(1/ε)).

1 aChilds, Andrew, M.1 aLiu, Jin-Peng uhttps://arxiv.org/abs/1901.0096101551nas a2200193 4500008004100000245009300041210006900134260001300203520092900216100002101145700001901166700002201185700001601207700002401223700002401247700002601271700002301297856003701320 2020 eng d00aQuantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer0 aQuantum walks and Dirac cellular automata on a programmable trap c2/6/20203 a

The quantum walk formalism is a widely used and highly successful framework for modeling quantum systems, such as simulations of the Dirac equation, different dynamics in both the low and high energy regime, and for developing a wide range of quantum algorithms. Here we present the circuit-based implementation of a discrete-time quantum walk in position space on a five-qubit trapped-ion quantum processor. We encode the space of walker positions in particular multi-qubit states and program the system to operate with different quantum walk parameters, experimentally realizing a Dirac cellular automaton with tunable mass parameter. The quantum walk circuits and position state mapping scale favorably to a larger model and physical systems, allowing the implementation of any algorithm based on discrete-time quantum walks algorithm and the dynamics associated with the discretized version of the Dirac equation.

1 aAlderete, Huerta1 aSingh, Shivani1 aNguyen, Nhung, H.1 aZhu, Daiwei1 aBalu, Radhakrishnan1 aMonroe, Christopher1 aChandrashekar, C., M.1 aLinke, Norbert, M. uhttps://arxiv.org/abs/2002.0253702359nas a2200169 4500008004100000245007400041210006900115260001300184300001300197490001000210520178100220100001902001700002202020700002302042700001502065856010902080 2020 eng d00aQuantum-Access-Secure Message Authentication via Blind-Unforgeability0 aQuantumAccessSecure Message Authentication via BlindUnforgeabili c5/1/2020 a788-817 0 v12-173 a

Formulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of “predicting an unqueried value” when the adversary can query in quantum superposition.

We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use “partially blinded” oracle access to predict values in the blinded region. We support the proposal with a number of technical results. We begin by establishing that the notion coincides with EUF-CMA in the classical setting and go on to demonstrate that the notion is satisfied by a number of simple guiding examples, such as random functions and quantum-query-secure pseudorandom functions. We then show the suitability of blind unforgeability for supporting canonical constructions and reductions. We prove that the “hash-and-MAC” paradigm and the Lamport one-time digital signature scheme are indeed unforgeable according to the definition. To support our analysis, we additionally define and study a new variety of quantum-secure hash functions called Bernoulli-preserving.

Finally, we demonstrate that blind unforgeability is strictly stronger than a previous definition of Boneh and Zhandry [EUROCRYPT ’13, CRYPTO ’13] and resolve an open problem concerning this previous definition by constructing an explicit function family which is forgeable yet satisfies the definition.

1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander1 aSong, Fang uhttps://www.quics.umd.edu/publications/quantum-access-secure-message-authentication-blind-unforgeability02278nas a2200121 4500008004100000245012000041210006900161260001500230520183200245100002102077700002102098856003702119 2020 eng d00aQuasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits0 aQuasipolynomial Time Approximation of Output Probabilities of Co c12/10/20203 a

We present a classical algorithm that, for any 3D geometrically-local, constant-depth quantum circuit C, and any bit string x∈{0,1}n, can compute the quantity |<x|C|0⊗n>|2 to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is #P-hard to compute this same quantity to within 2−n2 additive error [Mov20]. The previous best known algorithm for this problem used O(2n1/3poly(1/ε)) time to compute probabilities to within additive error ε [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: Our algorithm has a Divide-and-Conquer structure, constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings, each creating a 3D-local circuit on at most half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from the entanglement that may exist between the different circuit "pieces" produced this way.

1 aCoble, Nolan, J.1 aCoudron, Matthew uhttps://arxiv.org/abs/2012.0546002321nas a2200121 4500008004100000245011300041210006900154260001500223520188200238100002102120700002102141856003702162 2020 eng d00aQuasi-polynomial time approximation of output probabilities of geometrically-local, shallow quantum circuits0 aQuasipolynomial time approximation of output probabilities of ge c12/10/20203 a

We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuit C acting on n qubits, and any bit string x∈{0,1}n, can compute the quantity |<x|C|0⊗n>|2 to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is #P-hard to compute this same quantity to within 2−n2 additive error [Mov20, KMM21]. The previous best known algorithm for this problem used O(2n1/3poly(1/ϵ)) time to compute probabilities to within additive error ϵ [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for this estimation task restricted to 2D circuits, which makes a novel use of 1D Matrix Product States (MPS) carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach.
Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on about half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted combination of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from entanglement that may exist between the different circuit ``pieces" produced this way.

1 aCoble, Nolan, J.1 aCoudron, Matthew uhttps://arxiv.org/abs/2012.0546001888nas a2200145 4500008004100000245004600041210004600087260001400133490000700147520150400154100001401658700002001672700001301692856003701705 2019 eng d00aQuantifying the magic of quantum channels0 aQuantifying the magic of quantum channels c10/8/20190 v213 a

To achieve universal quantum computation via general fault-tolerant schemes, stabilizer operations must be supplemented with other non-stabilizer quantum resources. Motivated by this necessity, we develop a resource theory for magic quantum channels to characterize and quantify the quantum "magic" or non-stabilizerness of noisy quantum circuits. For qudit quantum computing with odd dimension d, it is known that quantum states with non-negative Wigner function can be efficiently simulated classically. First, inspired by this observation, we introduce a resource theory based on completely positive-Wigner-preserving quantum operations as free operations, and we show that they can be efficiently simulated via a classical algorithm. Second, we introduce two efficiently computable magic measures for quantum channels, called the mana and thauma of a quantum channel. As applications, we show that these measures not only provide fundamental limits on the distillable magic of quantum channels, but they also lead to lower bounds for the task of synthesizing non-Clifford gates. Third, we propose a classical algorithm for simulating noisy quantum circuits, whose sample complexity can be quantified by the mana of a quantum channel. We further show that this algorithm can outperform another approach for simulating noisy quantum circuits, based on channel robustness. Finally, we explore the threshold of non-stabilizerness for basic quantum circuits under depolarizing noise.

1 aWang, Xin1 aWilde, Mark, M.1 aSu, Yuan uhttps://arxiv.org/abs/1903.0448301091nas a2200145 4500008004100000245005500041210005500096260001500151490000800166520066600174100002300840700002400863700002100887856003700908 2019 eng d00aQuantum Algorithm for Simulating the Wave Equation0 aQuantum Algorithm for Simulating the Wave Equation c03/24/20190 v99 3 a

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

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

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

1 aPagano, G.1 aBapat, A.1 aBecker, P.1 aCollins, K., S.1 aDe, A.1 aHess, P., W.1 aKaplan, H., B.1 aKyprianidis, A.1 aTan, W., L.1 aBaldwin, Christopher, L.1 aBrady, L., T.1 aDeshpande, A.1 aLiu, F.1 aJordan, S.1 aGorshkov, Alexey, V.1 aMonroe, C. uhttps://arxiv.org/abs/1906.0270001585nas a2200145 4500008004100000245010600041210006900147260001500216520109100231100002101322700002001343700001901363700002001382856003701402 2019 eng d00aQuantum circuit approximations and entanglement renormalization for the Dirac field in 1+1 dimensions0 aQuantum circuit approximations and entanglement renormalization  c05/21/20193 a

The multiscale entanglement renormalization ansatz describes quantum many-body states by a hierarchical entanglement structure organized by length scale. Numerically, it has been demonstrated to capture critical lattice models and the data of the corresponding conformal field theories with high accuracy. However, a rigorous understanding of its success and precise relation to the continuum is still lacking. To address this challenge, we provide an explicit construction of entanglement-renormalization quantum circuits that rigorously approximate correlation functions of the massless Dirac conformal field theory. We directly target the continuum theory: discreteness is introduced by our choice of how to probe the system, not by any underlying short-distance lattice regulator. To achieve this, we use multiresolution analysis from wavelet theory to obtain an approximation scheme and to implement entanglement renormalization in a natural way. This could be a starting point for constructing quantum circuit approximations for more general conformal field theories. 

1 aWitteveen, Freek1 aScholz, Volkher1 aSwingle, Brian1 aWalter, Michael uhttps://arxiv.org/abs/1905.0882101947nas a2200397 4500008004100000245005400041210005400095260001500149520085000164100001801014700001601032700002301048700002301071700002201094700002401116700001901140700001801159700001801177700002001195700002501215700001801240700001801258700001901276700001901295700001601314700002301330700001901353700001701372700002401389700001901413700002201432700001901454700001901473700002001492856003701512 2019 eng d00aQuantum Computer Systems for Scientific Discovery0 aQuantum Computer Systems for Scientific Discovery c12/16/20193 a

The great promise of quantum computers comes with the dual challenges of building them and finding their useful applications. We argue that these two challenges should be considered together, by co-designing full stack quantum computer systems along with their applications in order to hasten their development and potential for scientific discovery. In this context, we identify scientific and community needs, opportunities, and significant challenges for the development of quantum computers for science over the next 2-10 years. This document is written by a community of university, national laboratory, and industrial researchers in the field of Quantum Information Science and Technology, and is based on a summary from a U.S. National Science Foundation workshop on Quantum Computing held on October 21-22, 2019 in Alexandria, VA.

1 aAlexeev, Yuri1 aBacon, Dave1 aBrown, Kenneth, R.1 aCalderbank, Robert1 aCarr, Lincoln, D.1 aChong, Frederic, T.1 aDeMarco, Brian1 aEnglund, Dirk1 aFarhi, Edward1 aFefferman, Bill1 aGorshkov, Alexey, V.1 aHouck, Andrew1 aKim, Jungsang1 aKimmel, Shelby1 aLange, Michael1 aLloyd, Seth1 aLukin, Mikhail, D.1 aMaslov, Dmitri1 aMaunz, Peter1 aMonroe, Christopher1 aPreskill, John1 aRoetteler, Martin1 aSavage, Martin1 aThompson, Jeff1 aVazirani, Umesh uhttps://arxiv.org/abs/1912.0757702574nas a2200313 4500008004100000245006200041210006200103260001500165520165200180100002401832700002201856700002001878700002201898700002001920700002701940700002201967700002401989700001802013700002102031700002102052700001702073700003102090700001902121700002002140700001902160700002302179700002102202856003702223 2019 eng d00aQuantum Computing at the Frontiers of Biological Sciences0 aQuantum Computing at the Frontiers of Biological Sciences c2019/11/163 a

The search for meaningful structure in biological data has relied on cutting-edge advances in computational technology and data science methods. However, challenges arise as we push the limits of scale and complexity in biological problems. Innovation in massively parallel, classical computing hardware and algorithms continues to address many of these challenges, but there is a need to simultaneously consider new paradigms to circumvent current barriers to processing speed. Accordingly, we articulate a view towards quantum computation and quantum information science, where algorithms have demonstrated potential polynomial and exponential computational speedups in certain applications, such as machine learning. The maturation of the field of quantum computing, in hardware and algorithm development, also coincides with the growth of several collaborative efforts to address questions across length and time scales, and scientific disciplines. We use this coincidence to explore the potential for quantum computing to aid in one such endeavor: the merging of insights from genetics, genomics, neuroimaging and behavioral phenotyping. By examining joint opportunities for computational innovation across fields, we highlight the need for a common language between biological data analysis and quantum computing. Ultimately, we consider current and future prospects for the employment of quantum computing algorithms in the biological sciences. 

1 aEmani, Prashant, S.1 aWarrell, Jonathan1 aAnticevic, Alan1 aBekiranov, Stefan1 aGandal, Michael1 aMcConnell, Michael, J.1 aSapiro, Guillermo1 aAspuru-Guzik, Alán1 aBaker, Justin1 aBastiani, Matteo1 aMcClure, Patrick1 aMurray, John1 aSotiropoulos, Stamatios, N1 aTaylor, J., M.1 aSenthil, Geetha1 aLehner, Thomas1 aGerstein, Mark, B.1 aHarrow, Aram, W. uhttps://arxiv.org/abs/1911.0712702203nas a2200205 4500008004100000245008000041210006900121260001500190520157300205100002001778700002101798700002401819700001901843700001901862700001801881700002201899700001901921700002001940856003701960 2019 eng d00aQuantum Gravity in the Lab: Teleportation by Size and Traversable Wormholes0 aQuantum Gravity in the Lab Teleportation by Size and Traversable c2019/11/143 a

With the long-term goal of studying quantum gravity in the lab, we propose holographic teleportation protocols that can be readily executed in table-top experiments. These protocols exhibit similar behavior to that seen in recent traversable wormhole constructions: information that is scrambled into one half of an entangled system will, following a weak coupling between the two halves, unscramble into the other half. We introduce the concept of "teleportation by size" to capture how the physics of operator-size growth naturally leads to information transmission. The transmission of a signal through a semi-classical holographic wormhole corresponds to a rather special property of the operator-size distribution we call "size winding". For more general setups (which may not have a clean emergent geometry), we argue that imperfect size winding is a generalization of the traversable wormhole phenomenon. For example, a form of signalling continues to function at high temperature and at large times for generic chaotic systems, even though it does not correspond to a signal going through a geometrical wormhole, but rather to an interference effect involving macroscopically different emergent geometries. Finally, we outline implementations feasible with current technology in two experimental platforms: Rydberg atom arrays and trapped ions. 

1 aBrown, Adam, R.1 aGharibyan, Hrant1 aLeichenauer, Stefan1 aLin, Henry, W.1 aNezami, Sepehr1 aSalton, Grant1 aSusskind, Leonard1 aSwingle, Brian1 aWalter, Michael uhttps://arxiv.org/abs/1911.0631402244nas a2200133 4500008004100000245006000041210006000101260001500161520182800176100002802004700002002032700002102052856003702073 2019 eng d00aQuantum hardness of learning shallow classical circuits0 aQuantum hardness of learning shallow classical circuits c03/07/20193 a

In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1) Hardness of learning AC0 and TC0 under the uniform distribution. Our first result concerns the concept class TC0 (resp. AC0), the class of constant-depth and polynomial-sized circuits with unbounded fan-in majority gates (resp. AND, OR, NOT gates). We show that if there exists no quantum polynomial-time (resp. sub-exponential time) algorithm to solve the Learning with Errors (LWE) problem, then there exists no polynomial-time quantum learning algorithm for TC0 (resp. AC0) under the uniform distribution (even with access to quantum membership queries). The main technique in this result uses explicit pseudo-random generators that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2) Hardness of learning TC02 in the PAC setting. Our second result shows that if there exists no quantum polynomial time algorithm for the LWE problem, then there exists no polynomial time quantum PAC learning algorithm for the class TC02, i.e., depth-2 TC0 circuits. The main technique in this result is to establish a connection between the quantum security of public-key cryptosystems and the learnability of a concept class that consists of decryption functions of the cryptosystem. This gives a strong conditional negative answer to one of the "Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson [Aar05], who asked if AC0 and TC0 can be PAC-learned in quantum polynomial time.

1 aArunachalam, Srinivasan1 aGrilo, Alex, B.1 aSundaram, Aarthi uhttps://arxiv.org/abs/1903.0284001364nas a2200157 4500008004100000245003000041210003000071260001500101490000800116520096500124100002101089700002101110700001901131700001901150856003701169 2019 eng d00aQuantum Lyapunov Spectrum0 aQuantum Lyapunov Spectrum c04/10/20190 v0823 a

We introduce a simple quantum generalization of the spectrum of classical Lyapunov exponents. We apply it to the SYK and XXZ models, and study the Lyapunov growth and entropy production. Our numerical results suggest that a black hole is not just the fastest scrambler, but also the fastest entropy generator. We also study the statistical features of the quantum Lyapunov spectrum and find universal random matrix behavior, which resembles the recently-found universality in classical chaos. The random matrix behavior is lost when the system is deformed away from chaos, towards integrability or a many-body localized phase. We propose that quantum systems holographically dual to gravity satisfy this universality in a strong form. We further argue that the quantum Lyapunov spectrum contains important additional information beyond the largest Lyapunov exponent and hence provides us with a better characterization of chaos in quantum systems. 

1 aGharibyan, Hrant1 aHanada, Masanori1 aSwingle, Brian1 aTezuka, Masaki uhttps://arxiv.org/abs/1809.0167101467nas a2200157 4500008004100000245012900041210006900170260001500239520088900254100003001143700002401173700002601197700002301223700002601246856003701272 2019 eng d00aQuantum Physics Meets Music: A "Real-Time" Guitar Recording Using Rydberg-Atoms and Electromagnetically Induced Transparency0 aQuantum Physics Meets Music A RealTime Guitar Recording Using Ry c04/01/20193 a

We demonstrate how Rydberg atoms and the phenomena of electromagnetically induced transparency can be used to aid in the recording of a musical instrument in real time as it is played. Also, by using two different atomic species (cesium and rubidium) in the same vapor cell, we demonstrate the ability to record two guitars simultaneously, where each atomic species detects and allows for the recording of each guitar separately. The approach shows how audio data (the musical composition) can be detected with a quantum system, illustrating how we can control ensembles of atoms to such an extent that we can use them in this "entertaining" example of recording a musical instrument.

1 aHolloway, Christopher, L.1 aSimons, Matthew, T.1 aHaddab, Abdulaziz, H.1 aWilliams, Carl, J.1 aHolloway, Maxwell, W. uhttps://arxiv.org/abs/1904.0195202812nas a2200145 4500008004100000245005100041210005100092260001500143300001400158490000700172520241800179100001702597700001502614856003702629 2019 eng d00aQuantum query complexity of entropy estimation0 aQuantum query complexity of entropy estimation c10/16/2017 a2899-29210 v653 a

Estimation of Shannon and R´enyi entropies of unknown discrete distributions is a fundamental problem in statistical property testing and an active research topic in both theoretical computer science and information theory. Tight bounds on the number of samples to estimate these entropies have been established in the classical setting, while little is known about their quantum counterparts. In this paper, we give the first quantum algorithms for estimating α- R´enyi entropies (Shannon entropy being 1-Renyi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for α-R´enyi entropy estimation for all α ≥ 0, including a tight bound for the collision-entropy (2-R´enyi entropy). We also provide quantum upper bounds for extreme cases such as the Hartley entropy (i.e., the logarithm of the support size of a distribution, corresponding to α = 0) and the min-entropy case (i.e., α = +∞), as well as the Kullback-Leibler divergence between two distributions. Moreover, we complement our results with quantum lower bounds on α-R´enyi entropy estimation for all α ≥ 0. Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH) [13] on quantum algorithms for distributional property testing, however, with many new technical ingredients. For Shannon entropy and 0-R´enyi entropy estimation, we improve the performance of the BHH framework, especially its error dependence, using Montanaro’s approach to estimating the expected output value of a quantum subroutine with bounded variance [41] and giving a fine-tuned error analysis. For general α-R´enyi entropy estimation, we further develop a procedure that recursively approximates α-R´enyi entropy for a sequence of αs, which is in spirit similar to a cooling schedule in simulated annealing. For special cases such as integer α ≥ 2 and α = +∞ (i.e., the min-entropy), we reduce the entropy estimation problem to the α-distinctness and the dlog ne-distinctness problems, respectively. We exploit various techniques to obtain our lower bounds for different ranges of α, including reductions to (variants of) existing lower bounds in quantum query complexity as well as the polynomial method inspired by the celebrated quantum lower bound for the collision problem.

1 aLi, Tongyang1 aWu, Xiaodi uhttps://arxiv.org/abs/1710.0602501711nas a2200181 4500008004100000245005600041210005600097260001500153490000700168520117600175100002301351700002701374700002101401700001701422700002401439700002901463856003701492 2019 eng d00aQuantum repeaters based on two species trapped ions0 aQuantum repeaters based on two species trapped ions c05/02/20190 v213 a

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

1 aSantra, Siddhartha1 aMuralidharan, Sreraman1 aLichtman, Martin1 aJiang, Liang1 aMonroe, Christopher1 aMalinovsky, Vladimir, S. uhttps://arxiv.org/abs/1811.1072302892nas a2200397 4500008004100000245005600041210005500097260001500152520177700167100001701944700002301961700002101984700002202005700001902027700001602046700001902062700002502081700002302106700002002129700002002149700002602169700002302195700002402218700002202242700002302264700001602287700001302303700002002316700002402336700001702360700001902377700001802396700002302414700002002437856003702457 2019 eng d00aQuantum Simulators: Architectures and Opportunities0 aQuantum Simulators Architectures and Opportunities c12/14/20193 a

Quantum simulators are a promising technology on the spectrum of quantum devices from specialized quantum experiments to universal quantum computers. These quantum devices utilize entanglement and many-particle behaviors to explore and solve hard scientific, engineering, and computational problems. Rapid development over the last two decades has produced more than 300 quantum simulators in operation worldwide using a wide variety of experimental platforms. Recent advances in several physical architectures promise a golden age of quantum simulators ranging from highly optimized special purpose simulators to flexible programmable devices. These developments have enabled a convergence of ideas drawn from fundamental physics, computer science, and device engineering. They have strong potential to address problems of societal importance, ranging from understanding vital chemical processes, to enabling the design of new materials with enhanced performance, to solving complex computational problems. It is the position of the community, as represented by participants of the NSF workshop on "Programmable Quantum Simulators," that investment in a national quantum simulator program is a high priority in order to accelerate the progress in this field and to result in the first practical applications of quantum machines. Such a program should address two areas of emphasis: (1) support for creating quantum simulator prototypes usable by the broader scientific community, complementary to the present universal quantum computer effort in industry; and (2) support for fundamental research carried out by a blend of multi-investigator, multi-disciplinary collaborations with resources for quantum simulator software, hardware, and education. 

1 aAltman, Ehud1 aBrown, Kenneth, R.1 aCarleo, Giuseppe1 aCarr, Lincoln, D.1 aDemler, Eugene1 aChin, Cheng1 aDeMarco, Brian1 aEconomou, Sophia, E.1 aEriksson, Mark, A.1 aFu, Kai-Mei, C.1 aGreiner, Markus1 aHazzard, Kaden, R. A.1 aHulet, Randall, G.1 aKollár, Alicia, J.1 aLev, Benjamin, L.1 aLukin, Mikhail, D.1 aMa, Ruichao1 aMi, Xiao1 aMisra, Shashank1 aMonroe, Christopher1 aMurch, Kater1 aNazario, Zaira1 aNi, Kang-Kuen1 aPotter, Andrew, C.1 aRoushan, Pedram uhttps://arxiv.org/abs/1912.0693801810nas a2200169 4500008004100000245005600041210005600097260001500153490000700168520133300175100002701508700001801535700001701553700001801570700001501588856003701603 2019 eng d00aQuantum Wasserstein Generative Adversarial Networks0 aQuantum Wasserstein Generative Adversarial Networks c2019/10/310 v323 a

The study of quantum generative models is well-motivated, not only because of its importance in quantum machine learning and quantum chemistry but also because of the perspective of its implementation on near-term quantum machines. Inspired by previous studies on the adversarial training of classical and quantum generative models, we propose the first design of quantum Wasserstein Generative Adversarial Networks (WGANs), which has been shown to improve the robustness and the scalability of the adversarial training of quantum generative models even on noisy quantum hardware. Specifically, we propose a definition of the Wasserstein semimetric between quantum data, which inherits a few key theoretical merits of its classical counterpart. We also demonstrate how to turn the quantum Wasserstein semimetric into a concrete design of quantum WGANs that can be efficiently implemented on quantum machines. Our numerical study, via classical simulation of quantum systems, shows the more robust and scalable numerical performance of our quantum WGANs over other quantum GAN proposals. As a surprising application, our quantum WGAN has been used to generate a 3-qubit quantum circuit of ~50 gates that well approximates a 3-qubit 1-d Hamiltonian simulation circuit that requires over 10k gates using standard techniques.

1 aChakrabarti, Shouvanik1 aHuang, Yiming1 aLi, Tongyang1 aFeizi, Soheil1 aWu, Xiaodi uhttps://arxiv.org/abs/1911.0011102281nas a2200133 4500008004100000245012600041210006900167520180200236100001802038700001702056700001902073700001802092856003702110 2019 eng d00aQuantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches0 aQuantuminspired classical sublineartime algorithm for solving lo3 a

Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. Recently, quantum algorithms with superpolynomial speedups for solving SDPs have been proposed assuming access to its constraint matrices in quantum superposition. Mutually inspired by both classical and quantum SDP solvers, in this paper we present a sublinear classical algorithm for solving low-rank SDPs which is asymptotically as good as existing quantum algorithms. Specifically, given an SDP with m constraint matrices, each of dimension n and rank poly(logn), our algorithm gives a succinct description and any entry of the solution matrix in time O(m⋅poly(logn,1/ε)) given access to a sample-based low-overhead data structure of the constraint matrices, where ε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with both the SDP solvers based on the matrix multiplicative weight (MMW) framework and the recent studies of quantum-inspired machine learning algorithms. The cost of solving SDPs by MMW mainly comes from the exponentiation of Hermitian matrices, and we propose two new technical ingredients (compared to previous sample-based algorithms) for this task that may be of independent interest: ∙ Weighted sampling: assuming sampling access to each individual constraint matrix A1,…,Aτ, we propose a procedure that gives a good approximation of A=A1+⋯+Aτ. ∙ Symmetric approximation: we propose a sampling procedure that gives low-rank spectral decomposition of a Hermitian matrix A. This improves upon previous sampling procedures that only give low-rank singular value decompositions, losing the signs of eigenvalues.

1 aChia, Nai-Hui1 aLi, Tongyang1 aLin, Han-Hsuan1 aWang, Chunhao uhttps://arxiv.org/abs/1901.0325401495nas a2200121 4500008004100000245005200041210005100093260001500144520112900159100002901288700001901317856003701336 2019 eng d00aQuenched vs Annealed: Glassiness from SK to SYK0 aQuenched vs Annealed Glassiness from SK to SYK c11/26/20193 a

We show that any SYK-like model with finite-body interactions among \textit{local} degrees of freedom, e.g., bosons or spins, has a fundamental difference from the standard fermionic model: the former fails to be described by an annealed free energy at low temperature. In this respect, such models more closely resemble spin glasses. We demonstrate this by two means: first, a general theorem proving that the annealed free energy is divergent at low temperature in any model with a tensor product Hilbert space; and second, a replica treatment of two prominent examples which exhibit phase transitions from an "annealed" phase to a "non-annealed" phase as a function of temperature. We further show that this effect appears only at O(N)'th order in a 1/N expansion, even though lower-order terms misleadingly seem to converge. Our results prove that the non-bosonic nature of the particles in SYK is an essential ingredient for its physics, highlight connections between local models and spin glasses, and raise important questions as to the role of fermions and/or glassiness in holography.

1 aBaldwin, Christopher, L.1 aSwingle, Brian uhttps://arxiv.org/abs/1911.1186502679nas a2200181 4500008004100000245010000041210006900141260000900210300001300219490000700232520211600239100002402355700002602379700001602405700002002421700001902441856003702460 2018 eng d00aQFlow lite dataset: A machine-learning approach to the charge states in quantum dot experiments0 aQFlow lite dataset A machinelearning approach to the charge stat c2018 ae02058440 v133 a

Over the past decade, machine learning techniques have revolutionized how research is done, from designing new materials and predicting their properties to assisting drug discovery to advancing cybersecurity. Recently, we added to this list by showing how a machine learning algorithm (a so-called learner) combined with an optimization routine can assist experimental efforts in the realm of tuning semiconductor quantum dot (QD) devices. Among other applications, semiconductor QDs are a candidate system for building quantum computers. The present-day tuning techniques for bringing the QD devices into a desirable configuration suitable for quantum computing that rely on heuristics do not scale with the increasing size of the quantum dot arrays required for even near-term quantum computing demonstrations. Establishing a reliable protocol for tuning that does not rely on the gross-scale heuristics developed by experimentalists is thus of great importance. To implement the machine learning-based approach, we constructed a dataset of simulated QD device characteristics, such as the conductance and the charge sensor response versus the applied electrostatic gate voltages. Here, we describe the methodology for generating the dataset, as well as its validation in training convolutional neural networks. We show that the learner's accuracy in recognizing the state of a device is ~96.5 % in both current- and charge-sensor-based training. We also introduce a tool that enables other researchers to use this approach for further research: QFlow lite - a Python-based mini-software suite that uses the dataset to train neural networks to recognize the state of a device and differentiate between states in experimental data. This work gives the definitive reference for the new dataset that will help enable researchers to use it in their experiments or to develop new machine learning approaches and concepts

1 aZwolak, Justyna, P.1 aKalantre, Sandesh, S.1 aWu, Xingyao1 aRagole, Stephen1 aTaylor, J., M. uhttps://arxiv.org/abs/1809.1001801816nas a2200193 4500008004100000245007600041210006900117260001400186300001500200490000600215520125400221100001901475700001901494700001801513700002001531700001901551700001501570856003701585 2018 eng d00aQuantitative Robustness Analysis of Quantum Programs (Extended Version)0 aQuantitative Robustness Analysis of Quantum Programs Extended Ve c2018/12/1 aArticle 310 v33 a

Quantum computation is a topic of significant recent interest, with practical advances coming from both research and industry. A major challenge in quantum programming is dealing with errors (quantum noise) during execution. Because quantum resources (e.g., qubits) are scarce, classical error correction techniques applied at the level of the architecture are currently cost-prohibitive. But while this reality means that quantum programs are almost certain to have errors, there as yet exists no principled means to reason about erroneous behavior. This paper attempts to fill this gap by developing a semantics for erroneous quantum while-programs, as well as a logic for reasoning about them. This logic permits proving a property we have identified, called ε-robustness, which characterizes possible "distance" between an ideal program and an erroneous one. We have proved the logic sound, and showed its utility on several case studies, notably: (1) analyzing the robustness of noisy versions of the quantum Bernoulli factory (QBF) and quantum walk (QW); (2) demonstrating the (in)effectiveness of different error correction schemes on single-qubit errors; and (3) analyzing the robustness of a fault-tolerant version of QBF.

1 aHung, Shih-Han1 aHietala, Kesha1 aZhu, Shaopeng1 aYing, Mingsheng1 aHicks, Michael1 aWu, Xiaodi uhttps://arxiv.org/abs/1811.0358502027nas a2200133 4500008004100000245005400041210005400095520164000149100002001789700001701809700001401826700001601840856003701856 2018 eng d00aQuantum adiabatic optimization without heuristics0 aQuantum adiabatic optimization without heuristics3 a

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

1 aJarret, Michael1 aLackey, Brad1 aLiu, Aike1 aWan, Kianna uhttps://arxiv.org/abs/1810.0468601497nas a2200145 4500008004100000245006400041210006400105260001500169490000800184520103000192100001801222700002301240700001901263856006901282 2018 eng d00aQuantum algorithm for multivariate polynomial interpolation0 aQuantum algorithm for multivariate polynomial interpolation c2018/01/170 v4743 a

How many quantum queries are required to determine the coefficients of a degree-d polynomial in n variables? We present and analyze quantum algorithms for this multivariate polynomial interpolation problem over the fields Fq, R, and C. We show that kC and 2kC queries suffice to achieve probability 1 for C and R, respectively, where kC = ⌈ 1 n+1 ( n+d d )⌉ except for d = 2 and four other special cases. For Fq, we show that ⌈ d n+d ( n+d d )⌉ queries suffice to achieve probability approaching 1 for large field order q. The classical query complexity of this problem is ( n+d d ), so our result provides a speedup by a factor of n + 1, n+1 2 , and n+d d for C, R, and Fq, respectively. Thus we find a much larger gap between classical and quantum algorithms than the univariate case, where the speedup is by a factor of 2. For the case of Fq, we conjecture that 2kC queries also suffice to achieve probability approaching 1 for large field order q, although we leave this as an open problem.

1 aChen, Jianxin1 aChilds, Andrew, M.1 aHung, Shih-Han uhttp://rspa.royalsocietypublishing.org/content/474/2209/2017048001663nas a2200133 4500008004100000245007200041210006900113520124300182100001401425700001401439700002201453700001701475856003701492 2018 eng d00aQuantum Channel Simulation and the Channel's Smooth Max-Information0 aQuantum Channel Simulation and the Channels Smooth MaxInformatio3 a

We study the general framework of quantum channel simulation, that is, the ability of a quantum channel to simulate another one using different classes of codes. First, we show that the minimum error of simulation and the one-shot quantum simulation cost under no-signalling assisted codes are given by semidefinite programs. Second, we introduce the channel's smooth max-information, which can be seen as a one-shot generalization of the mutual information of a quantum channel. We provide an exact operational interpretation of the channel's smooth max-information as the one-shot quantum simulation cost under no-signalling assisted codes. Third, we derive the asymptotic equipartition property of the channel's smooth max-information, i.e., it converges to the quantum mutual information of the channel in the independent and identically distributed asymptotic limit. This implies the quantum reverse Shannon theorem in the presence of no-signalling correlations. Finally, we explore the simulation cost of various quantum channels.

1 aFang, Kun1 aWang, Xin1 aTomamichel, Marco1 aBerta, Mario uhttps://arxiv.org/abs/1807.0535400433nas a2200133 4500008004100000245005200041210004900093260001200142300001000154490000700164100002400171700001600195856008800211 2018 eng d00aQuantum Cryptanalysis: Shor, Grover, and Beyond0 aQuantum Cryptanalysis Shor Grover and Beyond c2018/09 a14-210 v161 aJordan, Stephen, P.1 aLiu, Yi-Kai uhttps://www.quics.umd.edu/publications/quantum-cryptanalysis-shor-grover-and-beyond01937nas a2200157 4500008004100000245008200041210006900123260001500192300001200207490000700219520145800226100001901684700002001703700001901723856003701742 2018 eng d00aQuantum field theory for the chiral clock transition in one spatial dimension0 aQuantum field theory for the chiral clock transition in one spat c2018/11/09 a205118 0 vB 3 a

We describe the quantum phase transition in the N-state chiral clock model in spatial dimension d=1. With couplings chosen to preserve time-reversal and spatial inversion symmetries, such a model is in the universality class of recent experimental studies of the ordering of pumped Rydberg states in a one-dimensional chain of trapped ultracold alkali atoms. For such couplings and N=3, the clock model is expected to have a direct phase transition from a gapped phase with a broken global ZN symmetry, to a gapped phase with the ZN symmetry restored. The transition has dynamical critical exponent z≠1, and so cannot be described by a relativistic quantum field theory. We use a lattice duality transformation to map the transition onto that of a Bose gas in d=1, involving the onset of a single boson condensate in the background of a higher-dimensional N-boson condensate. We present a renormalization group analysis of the strongly coupled field theory for the Bose gas transition in an expansion in 2−d, with 4−N chosen to be of order 2−d. At two-loop order, we find a regime of parameters with a renormalization group fixed point which can describe a direct phase transition. We also present numerical density-matrix renormalization group studies of lattice chiral clock and Bose gas models for N=3, finding good evidence for a direct phase transition, and obtain estimates for z and the correlation length exponent ν.

1 aWhitsitt, Seth1 aSamajdar, Rhine1 aSachdev, Subir uhttps://arxiv.org/abs/1808.0705601662nas a2200145 4500008004100000245008400041210006900125520118800194100002101382700001901403700001801422700002101440700001801461856003701479 2018 eng d00aQuantum generalizations of the polynomial hierarchy with applications to QMA(2)0 aQuantum generalizations of the polynomial hierarchy with applica3 a

The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH does not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, QCPH, uses classical proofs, and the second, QPH, uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, QΣ3, into NEXP {using the Ellipsoid Method for efficiently solving semidefinite programs}. These results yield two implications for QMA(2), the variant of Quantum Merlin-Arthur (QMA) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if QCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs "equivalent"), then QMA(2) is in the Counting Hierarchy (specifically, in PPPPP). Second, unless QMA(2)=QΣ3 (i.e., alternating quantifiers do not help in the presence of "unentanglement"), QMA(2) is strictly contained in NEXP.

1 aGharibian, Sevag1 aSantha, Miklos1 aSikora, Jamie1 aSundaram, Aarthi1 aYirka, Justin uhttps://arxiv.org/abs/1805.1113902409nas a2200157 4500008004100000245009100041210006900132520188600201100003302087700001602120700001702136700002402153700002202177700001502199856003702214 2018 eng d00aQuantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning0 aQuantum SDP Solvers Large Speedups Optimality and Applications t3 a

We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank r, and sparsity s. The first algorithm assumes an input model where one is given access to entries of the matrices at unit cost. We show that it has run time O~(s2(m−−√ε−10+n−−√ε−12)), where ε is the error. This gives an optimal dependence in terms of m,n and quadratic improvement over previous quantum algorithms when m≈n. The second algorithm assumes a fully quantum input model in which the matrices are given as quantum states. We show that its run time is O~(m−−√+poly(r))⋅poly(logm,logn,B,ε−1), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only poly-logarithmically in n and polynomially in r. We apply the second 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 copies of an unknown state ρ, we show we can find in time m−−√⋅poly(logm,logn,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 from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight 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, which could be of independent interest.

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.0258102587nas a2200157 4500008004100000245011000041210006900151260001500220300001200235520207500247100001902322700001302341700002002354700001802374856003702392 2018 eng d00aQuantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics0 aQuantum singular value transformation and beyond exponential imp c2018/06/05 a193-2043 a

Quantum computing is powerful because unitary operators describing the time-evolution of a quantum system have exponential size in terms of the number of qubits present in the system. We develop a new "Singular value transformation" algorithm capable of harnessing this exponential advantage, that can apply polynomial transformations to the singular values of a block of a unitary, generalizing the optimal Hamiltonian simulation results of Low and Chuang. The proposed quantum circuits have a very simple structure, often give rise to optimal algorithms and have appealing constant factors, while usually only use a constant number of ancilla qubits. We show that singular value transformation leads to novel algorithms. We give an efficient solution to a certain "non-commutative" measurement problem and propose a new method for singular value estimation. We also show how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum. Finally, as a quantum machine learning application we show how to efficiently implement principal component regression. "Singular value transformation" is conceptually simple and efficient, and leads to a unified framework of quantum algorithms incorporating a variety of quantum speed-ups. We illustrate this by showing how it generalizes a number of prominent quantum algorithms, including: optimal Hamiltonian simulation, implementing the Moore-Penrose pseudoinverse with exponential precision, fixed-point amplitude amplification, robust oblivious amplitude amplification, fast QMA amplification, fast quantum OR lemma, certain quantum walk results and several quantum machine learning algorithms. In order to exploit the strengths of the presented method it is useful to know its limitations too, therefore we also prove a lower bound on the efficiency of singular value transformation, which often gives optimal bounds.

1 aGilyen, Andras1 aSu, Yuan1 aLow, Guang, Hao1 aWiebe, Nathan uhttps://arxiv.org/abs/1806.0183801599nas a2200133 4500008004100000245006800041210006800109520117300177100001801350700002001368700002001388700002001408856003701428 2018 eng d00aQuantum Supremacy and the Complexity of Random Circuit Sampling0 aQuantum Supremacy and the Complexity of Random Circuit Sampling3 a

A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration. 

1 aBouland, Adam1 aFefferman, Bill1 aNirkhe, Chinmay1 aVazirani, Umesh uhttps://arxiv.org/abs/1803.0440202448nas a2200133 4500008004100000245006700041210006500108520202500173100001902198700002202217700002302239700001502262856003702277 2018 eng d00aQuantum-secure message authentication via blind-unforgeability0 aQuantumsecure message authentication via blindunforgeability3 a

Formulating and designing unforgeable authentication of classical messages in the presence of quantum adversaries has been a challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of "predicting an unqueried value" when the adversary can query in quantum superposition. In this work, we uncover serious shortcomings in existing approaches, and propose a new definition. We then support its viability by a number of constructions and characterizations. Specifically, we demonstrate a function which is secure according to the existing definition by Boneh and Zhandry, but is clearly vulnerable to a quantum forgery attack, whereby a query supported only on inputs that start with 0 divulges the value of the function on an input that starts with 1. We then propose a new definition, which we call "blind-unforgeability" (or BU.) This notion matches "intuitive unpredictability" in all examples studied thus far. It defines a function to be predictable if there exists an adversary which can use "partially blinded" oracle access to predict values in the blinded region. Our definition (BU) coincides with standard unpredictability (EUF-CMA) in the classical-query setting. We show that quantum-secure pseudorandom functions are BU-secure MACs. In addition, we show that BU satisfies a composition property (Hash-and-MAC) using "Bernoulli-preserving" hash functions, a new notion which may be of independent interest. Finally, we show that BU is amenable to security reductions by giving a precise bound on the extent to which quantum algorithms can deviate from their usual behavior due to the blinding in the BU security experiment. 

1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander1 aSong, Fang uhttps://arxiv.org/abs/1803.0376102365nas a2200145 4500008004100000245006700041210006000108260001200168490000600180520192900186100002802115700001902143700002002162856003702182 2018 eng d00aThe quasiprobability behind the out-of-time-ordered correlator0 aquasiprobability behind the outoftimeordered correlator c04/20180 vA3 a

Two topics, evolving rapidly in separate fields, were combined recently: The out-of-time-ordered correlator (OTOC) signals quantum-information scrambling in many-body systems. The Kirkwood-Dirac (KD) quasiprobability represents operators in quantum optics. The OTOC has been shown to equal a moment of a summed quasiprobability. That quasiprobability, we argue, is an extension of the KD distribution. We explore the quasiprobability's structure from experimental, numerical, and theoretical perspectives. First, we simplify and analyze the weak-measurement and interference protocols for measuring the OTOC and its quasiprobability. We decrease, exponentially in system size, the number of trials required to infer the OTOC from weak measurements. We also construct a circuit for implementing the weak-measurement scheme. Next, we calculate the quasiprobability (after coarse-graining) numerically and analytically: We simulate a transverse-field Ising model first. Then, we calculate the quasiprobability averaged over random circuits, which model chaotic dynamics. The quasiprobability, we find, distinguishes chaotic from integrable regimes. We observe nonclassical behaviors: The quasiprobability typically has negative components. It becomes nonreal in some regimes. The onset of scrambling breaks a symmetry that bifurcates the quasiprobability, as in classical-chaos pitchforks. Finally, we present mathematical properties. The quasiprobability obeys a Bayes-type theorem, for example, that exponentially decreases the memory required to calculate weak values, in certain cases. A time-ordered correlator analogous to the OTOC, insensitive to quantum-information scrambling, depends on a quasiprobability closer to a classical probability. This work not only illuminates the OTOC's underpinnings, but also generalizes quasiprobability theory and motivates immediate-future weak-measurement challenges.

1 aHalpern, Nicole, Yunger1 aSwingle, Brian1 aDressel, Justin uhttps://arxiv.org/abs/1704.0197101429nas a2200169 4500008004100000245010800041210006900149260001500218300001400233490000800247520088200255100002301137700002301160700002101183700001801204856003701222 2017 eng d00aQuantum algorithm for linear differential equations with exponentially improved dependence on precision0 aQuantum algorithm for linear differential equations with exponen c2017/12/01 a1057-10810 v3563 a

We present a quantum algorithm for systems of (possibly inhomogeneous) linear ordinary differential equations with constant coefficients. The algorithm produces a quantum state that is proportional to the solution at a desired final time. The complexity of the algorithm is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. Our result builds upon recent advances in quantum linear systems algorithms by encoding the simulation into a sparse, well-conditioned linear system that approximates evolution according to the propagator using a Taylor series. Unlike with finite difference methods, our approach does not require additional hypotheses to ensure numerical stability.

1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aOstrander, Aaron1 aWang, Guoming uhttps://arxiv.org/abs/1701.0368401566nas a2200133 4500008004100000245004400041210004400085260001500129300001100144490000700155520121600162100001801378856003601396 2017 eng d00aQuantum Algorithm for Linear Regression0 aQuantum Algorithm for Linear Regression c2017/07/31 a0123350 v963 a

We present a quantum algorithm for fitting a linear regression model to a given data set using the least squares approach. Different from previous algorithms which only yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at negligible cost. Moreover, our algorithm does not require the design matrix to be sparse or need any help from additional state preparation procedures. It runs in time poly(log(N), d, κ, 1/), where N is the size of the data set, d is the number of adjustable parameters, κ is the condition number of the design matrix, and  is the desired precision in the output. We also show that the polynomial dependence on d and κ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit without computing its parameters explicitly. This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.

1 aWang, Guoming uhttps://arxiv.org/abs/1402.066001362nas a2200157 4500008004100000245010600041210006900147260001500216300001400231490000700245520083800252100002301090700001901113700002301132856004901155 2017 eng d00aQuantum algorithm for systems of linear equations with exponentially improved dependence on precision0 aQuantum algorithm for systems of linear equations with exponenti c2017/12/21 a1920-19500 v463 a

Harrow, Hassidim, and Lloyd showed that for a suitably specified N×N matrix A and N-dimensional vector b⃗ , there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations Ax⃗ =b⃗ . If A is sparse and well-conditioned, their algorithm runs in time poly(logN,1/ϵ), where ϵ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log(1/ϵ), exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on ϵ is prohibitive.

1 aChilds, Andrew, M.1 aKothari, Robin1 aSomma, Rolando, D. uhttp://epubs.siam.org/doi/10.1137/16M108707201240nas a2200121 4500008004100000245006900041210006900110260001500179520084800194100002001042700001901062856003701081 2017 eng d00aQuantum Algorithms for Graph Connectivity and Formula Evaluation0 aQuantum Algorithms for Graph Connectivity and Formula Evaluation c2017/04/033 a

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

1 aJeffery, Stacey1 aKimmel, Shelby uhttps://arxiv.org/abs/1704.0076501898nas a2200157 4500008004100000245005900041210005900100260001500159300001200174520143500186100001901621700001601640700002501656700002201681856003701703 2017 eng d00aQuantum Fully Homomorphic Encryption With Verification0 aQuantum Fully Homomorphic Encryption With Verification c2017/11/30 a438-4673 a

Fully-homomorphic encryption (FHE) enables computation on encrypted data while maintaining secrecy. Recent research has shown that such schemes exist even for quantum computation. Given the numerous applications of classical FHE (zero-knowledge proofs, secure two-party computation, obfuscation, etc.) it is reasonable to hope that quantum FHE (or QFHE) will lead to many new results in the quantum setting. However, a crucial ingredient in almost all applications of FHE is circuit verification. Classically, verification is performed by checking a transcript of the homomorphic computation. Quantumly, this strategy is impossible due to no-cloning. This leads to an important open question: can quantum computations be delegated and verified in a non-interactive manner? In this work, we answer this question in the affirmative, by constructing a scheme for QFHE with verification (vQFHE). Our scheme provides authenticated encryption, and enables arbitrary polynomial-time quantum computations without the need of interaction between client and server. Verification is almost entirely classical; for computations that start and end with classical states, it is completely classical. As a first application, we show how to construct quantum one-time programs from classical one-time programs and vQFHE.

1 aAlagic, Gorjan1 aDulek, Yfke1 aSchaffner, Christian1 aSpeelman, Florian uhttps://arxiv.org/abs/1708.0915601828nas a2200121 4500008004100000245004800041210004700089490001000136520143200146100001901578700002201597856008701619 2017 eng d00aQuantum Non-malleability and Authentication0 aQuantum Nonmalleability and Authentication0 v104023 a

In encryption, non-malleability is a highly desirable property: it ensures that adversaries cannot manipulate the plaintext by acting on the ciphertext. In [6], Ambainis et al. gave a definition of non-malleability for the encryption of quantum data. In this work, we show that this definition is too weak, as it allows adversaries to “inject” plaintexts of their choice into the ciphertext. We give a new definition of quantum non-malleability which resolves this problem. Our definition is expressed in terms of entropic quantities, considers stronger adversaries, and does not assume secrecy. Rather, we prove that quantum non-malleability implies secrecy; this is in stark contrast to the classical setting, where the two properties are completely independent. For unitary schemes, our notion of non-malleability is equivalent to encryption with a two-design (and hence also to the definition of [6]).

Our techniques also yield new results regarding the closely-related task of quantum authentication. We show that “total authentication” (a notion recently proposed by Garg et al. [18]) can be satisfied with two-designs, a significant improvement over the eight-design construction of [18]. We also show that, under a mild adaptation of the rejection procedure, both total authentication and our notion of non-malleability yield quantum authentication as defined by Dupuis et al. [16].

1 aAlagic, Gorjan1 aMajenz, Christian uhttps://www.quics.umd.edu/publications/quantum-non-malleability-and-authentication01311nas a2200133 4500008004100000245005700041210005700098260001500155520091500170100001701085700001901102700001901121856003701140 2017 eng d00aQuantum simulation of ferromagnetic Heisenberg model0 aQuantum simulation of ferromagnetic Heisenberg model c2017/12/143 a

Large quantum simulators, with sufficiently many qubits to be impossible to simulate classically, become hard to experimentally validate. We propose two tests of a quantum simulator with Heisenberg interaction in a linear chain of spins. In the first, we propagate half of a singlet state through a chain of spin with a ferromagnetic interaction and subsequently recover the state with an antiferromagnetic interaction. The antiferromagnetic interaction is intrinsic to the system while the ferromagnetic one can be simulated by a sequence of time-dependent controls of the antiferromagnetic interaction and Suzuki-Trotter approximations. In the second test, we use the same technique to transfer a spin singlet state from one end of a spin chain to the other. We show that the tests are robust against parametric errors in operation of the simulator and may be applicable even without error correction.

1 aWang, Yiping1 aTran, Minh, C.1 aTaylor, J., M. uhttps://arxiv.org/abs/1712.0528201598nas a2200241 4500008004100000245005800041210005800099260001500157300001100172490000800183520093100191100001301122700001401135700001801149700001601167700001801183700001801201700001301219700001601232700001401248700002201262856007201284 2017 eng d00aQuantum state tomography via reduced density matrices0 aQuantum state tomography via reduced density matrices c2017/01/09 a0204010 v1183 a

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

1 aXin, Tao1 aLu, Dawei1 aKlassen, Joel1 aYu, Nengkun1 aJi, Zhengfeng1 aChen, Jianxin1 aMa, Xian1 aLong, Guilu1 aZeng, Bei1 aLaflamme, Raymond uhttp://journals.aps.org/prl/abstract/10.1103/PhysRevLett.118.02040102297nas a2200121 4500008004100000245006900041210006700110490001000177520184100187100001902028700002302047856010502070 2017 eng d00aQuantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts0 aQuantumSecure SymmetricKey Cryptography Based on Hidden Shifts0 v102123 a

Recent results of Kaplan et al., building on work by Kuwakado and Morii, have shown that a wide variety of classically-secure symmetric-key cryptosystems can be completely broken by quantum chosen-plaintext attacks (qCPA). In such an attack, the quantum adversary has the ability to query the cryptographic functionality in superposition. The vulnerable cryptosystems include the Even-Mansour block cipher, the three-round Feistel network, the Encrypted-CBC-MAC, and many others.

In this article, we study simple algebraic adaptations of such schemes that replace   (Z/2)n  addition with operations over alternate finite groups—such as   Z/2n —and provide evidence that these adaptations are qCPA-secure. These adaptations furthermore retain the classical security properties and basic structural features enjoyed by the original schemes.

We establish security by treating the (quantum) hardness of the well-studied Hidden Shift problem as a cryptographic assumption. We observe that this problem has a number of attractive features in this cryptographic context, including random self-reducibility, hardness amplification, and—in many cases of interest—a reduction from the “search version” to the “decisional version.” We then establish, under this assumption, the qCPA-security of several such Hidden Shift adaptations of symmetric-key constructions. We show that a Hidden Shift version of the Even-Mansour block cipher yields a quantum-secure pseudorandom function, and that a Hidden Shift version of the Encrypted CBC-MAC yields a collision-resistant hash function. Finally, we observe that such adaptations frustrate the direct Simon’s algorithm-based attacks in more general circumstances, e.g., Feistel networks and slide attacks.

1 aAlagic, Gorjan1 aRussell, Alexander uhttps://www.quics.umd.edu/publications/quantum-secure-symmetric-key-cryptography-based-hidden-shifts01224nas a2200169 4500008004100000245005300041210005300094260001500147300001100162490000700173520074800180100001800928700002400946700001800970700001900988856004701007 2016 eng d00aQuantifying the coherence of pure quantum states0 aQuantifying the coherence of pure quantum states c2016/10/07 a0423130 v943 a

In recent years, several measures have been proposed for characterizing the coherence of a given quantum state. We derive several results that illuminate how these measures behave when restricted to pure states. Notably, we present an explicit characterization of the closest incoherent state to a given pure state under the trace distance measure of coherence, and we affirm a recent conjecture that the ℓ1 measure of coherence of a pure state is never smaller than its relative entropy of coherence. We then use our result to show that the states maximizing the trace distance of coherence are exactly the maximally coherent states, and we derive a new inequality relating the negativity and distillable entanglement of pure states.

1 aChen, Jianxin1 aJohnston, Nathaniel1 aLi, Chi-Kwong1 aPlosker, Sarah uhttps://doi.org/10.1103/PhysRevA.94.04231300861nas a2200121 4500008004100000245005500041210005500096260001500151520049300166100002000659700002400679856003600703 2016 eng d00aQuantum Merlin Arthur with Exponentially Small Gap0 aQuantum Merlin Arthur with Exponentially Small Gap c2016/01/083 aWe study the complexity of QMA proof systems with inverse exponentially small promise gap. We show that this class can be exactly characterized by PSPACE, the class of problems solvable with a polynomial amount of memory. As applications we show that a "precise" version of the Local Hamiltonian problem is PSPACE-complete, and give a provable setting in which the ability to prepare PEPS states is not as powerful as the ability to prepare the ground state of general Local Hamiltonians.1 aFefferman, Bill1 aLin, Cedric, Yen-Yu uhttp://arxiv.org/abs/1601.0197500982nas a2200145 4500008004100000245004300041210004100084260001500125300001100140490000700151520059900158100002200757700001900779856003800798 2016 eng d00aA Quantum Model for an Entropic Spring0 aQuantum Model for an Entropic Spring c2016/06/01 a2141020 v933 a

Motivated by understanding the emergence of thermodynamic restoring forces and oscillations, we develop a quantum-mechanical model of a bath of spins coupled to the elasticity of a material. We show our model reproduces the behavior of a variety of entropic springs while enabling investigation of non-equilibrium resonator states in the quantum domain. We find our model emerges naturally in disordered elastic media such as glasses, and is an additional, expected effect in systems with anomalous specific heat and 1/f noise at low temperatures due to two-level systems that fluctuate.

1 aWang, Chiao-Hsuan1 aTaylor, J., M. uhttp://arxiv.org/abs/1507.08658v102209nas a2200121 4500008004100000245002700041210002400068260001500092520190500107100001902012700002002031856003602051 2016 eng d00aOn Quantum Obfuscation0 aQuantum Obfuscation c2016/02/043 aEncryption of data is fundamental to secure communication in the modern world. Beyond encryption of data lies obfuscation, i.e., encryption of functionality. It is well-known that the most powerful means of obfuscating classical programs, so-called ``black-box obfuscation',' is provably impossible [Barak et al '12]. However, several recent results have yielded candidate schemes that satisfy a definition weaker than black-box, and yet still have numerous applications. In this work, we initialize the rigorous study of obfuscating programs via quantum-mechanical means. We define notions of quantum obfuscation which encompass several natural variants. The input to the obfuscator can describe classical or quantum functionality, and the output can be a circuit description or a quantum state. The obfuscator can also satisfy one of a number of obfuscation conditions: black-box, information-theoretic black-box, indistinguishability, and best possible; the last two conditions come in three variants: perfect, statistical, and computational. We discuss many applications, including CPA-secure quantum encryption, quantum fully-homomorphic encryption, and public-key quantum money. We then prove several impossibility results, extending a number of foundational papers on classical obfuscation to the quantum setting. We prove that quantum black-box obfuscation is impossible in a setting where adversaries can possess more than one output of the obfuscator. In particular, generic transformation of quantum circuits into black-box-obfuscated quantum circuits is impossible. We also show that statistical indistinguishability obfuscation is impossible, up to an unlikely complexity-theoretic collapse. Our proofs involve a new tool: chosen-ciphertext-secure encryption of quantum data, which was recently shown to be possible assuming quantum-secure one-way functions exist [Alagic et al '16].1 aAlagic, Gorjan1 aFefferman, Bill uhttp://arxiv.org/abs/1602.0177101010nas a2200145 4500008004100000245007200041210006800113260001500181490000700196520056900203100001800772700001900790700001900809856003600828 2016 eng d00aA Quantum Version of Schöning's Algorithm Applied to Quantum 2-SAT0 aQuantum Version of Schönings Algorithm Applied to Quantum 2SAT c2016/03/220 v163 a

We study a quantum algorithm that consists of a simple quantum Markov process, and we analyze its behavior on restricted versions of Quantum 2-SAT. We prove that the algorithm solves this decision problem with high probability for n qubits, L clauses, and promise gap c in time O(n^2 L^2 c^{-2}). If the Hamiltonian is additionally polynomially gapped, our algorithm efficiently produces a state that has high overlap with the satisfying subspace. The Markov process we study is a quantum analogue of Sch\"oning's probabilistic algorithm for k-SAT.

1 aFarhi, Edward1 aKimmel, Shelby1 aTemme, Kristan uhttp://arxiv.org/abs/1603.0698501578nas a2200157 4500008004100000245003800041210003700079260001500116300001100131490000800142520115100150100001901301700001901320700002201339856005901361 2016 eng d00aQuantum-Enhanced Machine Learning0 aQuantumEnhanced Machine Learning c2016/09/20 a1305010 v1173 a

The emerging field of quantum machine learning has the potential to substantially aid in the problems and scope of artificial intelligence. This is only enhanced by recent successes in the field of classical machine learning. In this work we propose an approach for the systematic treatment of machine learning, from the perspective of quantum information. Our approach is general and covers all three main branches of machine learning: supervised, unsupervised, and reinforcement learning. While quantum improvements in supervised and unsupervised learning have been reported, reinforcement learning has received much less attention. Within our approach, we tackle the problem of quantum enhancements in reinforcement learning as well, and propose a systematic scheme for providing improvements. As an example, we show that quadratic improvements in learning efficiency, and exponential improvements in performance over limited time periods, can be obtained for a broad class of learning problems.

1 aDunjko, Vedran1 aTaylor, J., M.1 aBriegel, Hans, J. uhttp://link.aps.org/doi/10.1103/PhysRevLett.117.13050101938nas a2200145 4500008004100000245004200041210003900083260001500122520154800137100001601685700001801701700001701719700001901736856003701755 2016 eng d00aA quasi-mode theory of chiral phonons0 aquasimode theory of chiral phonons c2016/12/293 a

The coherence properties of mechanical resonators are often limited by multiple unavoidable forms of loss -- including phonon-phonon and phonon-defect scattering -- which result in the scattering of sound into other resonant modes and into the phonon bath. Dynamic suppression of this scattering loss can lift constraints on device structure and can improve tolerance to defects in the material, even after fabrication. Inspired by recent experiments, here we introduce a model of phonon losses resulting from disorder in a whispering gallery mode resonator with acousto-optical coupling between optical and mechanical modes. We show that a typical elastic scattering mechanism of high quality factor (Q) mechanical modes flips the direction of phonon propagation via high-angle scattering, leading to damping into modes with the opposite parity. When the optical mode overlaps co-propagating high-Q and bulk mechanical modes, the addition of laser cooling via sideband-resolved damping of the mechanical mode of a chosen parity also damps and modifies the response of the bulk modes of the same parity. This, in turn, simultaneously improves the quality factor and reduces the thermal load of the counter-propagating high-Q modes, leading to the dynamical creation of a cold phononic shield. We compare our theoretical results to the recent experiments of Kim et al., and find quantitative agreement with our theory.

1 aXu, Xunnong1 aKim, Seunghwi1 aBahl, Gaurav1 aTaylor, J., M. uhttps://arxiv.org/abs/1612.0924001216nas a2200121 4500008004100000245004700041210004600088260001500134520087400149100001901023700001601042856003601058 2015 eng d00aQuantum Compressed Sensing Using 2-Designs0 aQuantum Compressed Sensing Using 2Designs c2015/10/293 aWe develop a method for quantum process tomography that combines the efficiency of compressed sensing with the robustness of randomized benchmarking. Our method is robust to state preparation and measurement errors, and it achieves a quadratic speedup over conventional tomography when the unknown process is a generic unitary evolution. Our method is based on PhaseLift, a convex programming technique for phase retrieval. We show that this method achieves approximate recovery of almost all signals, using measurements sampled from spherical or unitary 2-designs. This is the first positive result on PhaseLift using 2-designs. We also show that exact recovery of all signals is possible using unitary 4-designs. Previous positive results for PhaseLift required spherical 4-designs, while PhaseLift was known to fail in certain cases when using spherical 2-designs.1 aKimmel, Shelby1 aLiu, Yi-Kai uhttp://arxiv.org/abs/1510.0888700905nas a2200121 4500008004100000245004100041210004100082260001500123520053800138100001700676700002200693856006800715 2015 eng d00aQuantum Entanglement and Information0 aQuantum Entanglement and Information c02/07/20153 aQuantum entanglement is a physical resource, like energy, associated with the peculiar nonclassical correlations that are possible between separated quantum systems. Entanglement can be measured, transformed, and purified. A pair of quantum systems in an entangled state can be used as a quantum information channel to perform computational and cryptographic tasks that are impossible for classical systems. The general study of the information-processing capabilities of quantum systems is the subject of quantum information theory.1 aBub, Jeffrey1 aZalta, Edward, N. uhttp://plato.stanford.edu/archives/sum2015/entries/qt-entangle/00602nas a2200193 4500008004100000022001400041245007400055210006900129260001500198300001400213490000600227100002000233700001700253700001600270700002500286700001900311700001800330856006000348 2015 eng d a1749-488500aQuantum many-body models with cold atoms coupled to photonic crystals0 aQuantum manybody models with cold atoms coupled to photonic crys c2015/04/04 a326 - 3310 v91 aDouglas, J., S.1 aHabibian, H.1 aHung, C.-L.1 aGorshkov, Alexey, V.1 aKimble, H., J.1 aChang, D., E. uhttp://www.nature.com/doifinder/10.1038/nphoton.2015.5701482nas a2200157 4500008004100000245006300041210006300104260001500167300001100182490000700193520103100200100001601231700002101247700001901268856003701287 2015 eng d00aQuantum Nonlinear Optics Near Optomechanical Instabilities0 aQuantum Nonlinear Optics Near Optomechanical Instabilities c2015/01/09 a0138180 v913 a Optomechanical systems provide a unique platform for observing quantum behavior of macroscopic objects. However, efforts towards realizing nonlinear behavior at the single photon level have been inhibited by the small size of the radiation pressure interaction. Here we show that it is not necessary to reach the single-photon strong-coupling regime in order to realize significant optomechanical nonlinearities. Instead, nonlinearities at the few quanta level can be achieved, even with weak-coupling, in a two-mode optomechanical system driven near instability. In this limit, we establish a new figure of merit for realizing strong nonlinearity which scales with the single-photon optomechanical coupling and the sideband resolution of the mechanical mode with respect to the cavity linewidth. We find that current devices based on optomechanical crystals, thought to be in the weak-coupling regime, can still achieve strong quantum nonlinearity; enabling deterministic interactions between single photons. 1 aXu, Xunnong1 aGullans, Michael1 aTaylor, J., M. uhttp://arxiv.org/abs/1404.3726v201003nas a2200121 4500008004100000245005600041210005600097260001500153520063800168100002000806700001900826856003600845 2015 eng d00aQuantum vs Classical Proofs and Subset Verification0 aQuantum vs Classical Proofs and Subset Verification c2015/10/223 aWe study the ability of efficient quantum verifiers to decide properties of exponentially large subsets given either a classical or quantum witness. We develop a general framework that can be used to prove that QCMA machines, with only classical witnesses, cannot verify certain properties of subsets given implicitly via an oracle. We use this framework to prove an oracle separation between QCMA and QMA using an ``in-place'' permutation oracle, making the first progress on this question since Aaronson and Kuperberg in 2007. We also use the framework to prove a particularly simple standard oracle separation between QCMA and AM.1 aFefferman, Bill1 aKimmel, Shelby uhttp://arxiv.org/abs/1510.0675001107nas a2200109 4500008004100000245004100041210004100082260001500123520080600138100001800944856003500962 2014 eng d00aQuantum Algorithms for Curve Fitting0 aQuantum Algorithms for Curve Fitting c2014/04/023 aWe present quantum algorithms for estimating the best-fit parameters and the quality of least-square curve fitting. The running times of these algorithms are polynomial in logn, d, κ, ν, χ, 1/Φ and 1/ϵ, where n is the number of data points to be fitted, d is the dimension of feature vectors, κ is the condition number of the design matrix, ν and χ are some parameters reflecting the variances of the design matrix and response vector, Φ is the fit quality, and ϵ is the tolerable error. Different from previous quantum algorithms for these tasks, our algorithms do not require the design matrix to be sparse, and they do completely determine the fitted curve. They are developed by combining phase estimation and the density matrix exponentiation technique for dense Hamiltonian simulation.1 aWang, Guoming uhttp://arxiv.org/abs/1402.066001013nas a2200133 4500008004100000245006000041210006000101260001500161520060100176100002400777700002200801700001900823856003700842 2014 eng d00aQuantum Algorithms for Fermionic Quantum Field Theories0 aQuantum Algorithms for Fermionic Quantum Field Theories c2014/04/283 a Extending previous work on scalar field theories, we develop a quantum algorithm to compute relativistic scattering amplitudes in fermionic field theories, exemplified by the massive Gross-Neveu model, a theory in two spacetime dimensions with quartic interactions. The algorithm introduces new techniques to meet the additional challenges posed by the characteristics of fermionic fields, and its run time is polynomial in the desired precision and the energy. Thus, it constitutes further progress towards an efficient quantum algorithm for simulating the Standard Model of particle physics. 1 aJordan, Stephen, P.1 aLee, Keith, S. M.1 aPreskill, John uhttp://arxiv.org/abs/1404.7115v101152nas 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.6238v201375nas a2200157 4500008004100000245007100041210006900112260001500181300001400196490000700210520089800217100002401115700002201139700001901161856003701180 2014 eng d00aQuantum Computation of Scattering in Scalar Quantum Field Theories0 aQuantum Computation of Scattering in Scalar Quantum Field Theori c2014/09/01 a1014-10800 v143 a Quantum field theory provides the framework for the most fundamental physical theories to be confirmed experimentally, and has enabled predictions of unprecedented precision. However, calculations of physical observables often require great computational complexity and can generally be performed only when the interaction strength is weak. A full understanding of the foundations and rich consequences of quantum field theory remains an outstanding challenge. We develop a quantum algorithm to compute relativistic scattering amplitudes in massive phi-fourth theory in spacetime of four and fewer dimensions. The algorithm runs in a time that is polynomial in the number of particles, their energy, and the desired precision, and applies at both weak and strong coupling. Thus, it offers exponential speedup over existing classical methods at high precision or strong coupling. 1 aJordan, Stephen, P.1 aLee, Keith, S. M.1 aPreskill, John uhttp://arxiv.org/abs/1112.4833v101850nas a2200205 4500008004100000245008200041210006900123260001500192490000700207520120600214100002601420700002601446700002301472700002701495700002701522700001701549700002101566700002001587856003701607 2014 eng d00aQuantum correlations and entanglement in far-from-equilibrium spin systems 0 aQuantum correlations and entanglement in farfromequilibrium spin c2014/12/150 v903 a By applying complementary analytic and numerical methods, we investigate the dynamics of spin-$1/2$ XXZ models with variable-range interactions in arbitrary dimensions. The dynamics we consider is initiated from uncorrelated states that are easily prepared in experiments, and can be equivalently viewed as either Ramsey spectroscopy or a quantum quench. Our primary focus is the dynamical emergence of correlations and entanglement in these far-from-equilibrium interacting quantum systems: we characterize these correlations by the entanglement entropy, concurrence, and squeezing, which are inequivalent measures of entanglement corresponding to different quantum resources. In one spatial dimension, we show that the time evolution of correlation functions manifests a non-perturbative dynamic singularity. This singularity is characterized by a universal power-law exponent that is insensitive to small perturbations. Explicit realizations of these models in current experiments using polar molecules, trapped ions, Rydberg atoms, magnetic atoms, and alkaline-earth and alkali atoms in optical lattices, along with the relative merits and limitations of these different systems, are discussed. 1 aHazzard, Kaden, R. A.1 avan den Worm, Mauritz1 aFoss-Feig, Michael1 aManmana, Salvatore, R.1 aTorre, Emanuele, Dalla1 aPfau, Tilman1 aKastner, Michael1 aRey, Ana, Maria uhttp://arxiv.org/abs/1406.0937v102166nas a2200133 4500008004100000245005300041210005300094260001400147300001600161490000700177520179400184100001701978856003701995 2014 eng d00aQuantum Correlations and the Measurement Problem0 aQuantum Correlations and the Measurement Problem c2013/6/30 a3346 - 33690 v533 a The transition from classical to quantum mechanics rests on the recognition that the structure of information is not what we thought it was: there are operational, i.e., phenomenal, probabilistic correlations that lie outside the polytope of local correlations. Such correlations cannot be simulated with classical resources, which generate classical correlations represented by the points in a simplex, where the vertices of the simplex represent joint deterministic states that are the common causes of the correlations. The `no go' hidden variable theorems tell us that we can't shoe-horn correlations outside the local polytope into a classical simplex by supposing that something has been left out of the story. The replacement of the classical simplex by the quantum convex set as the structure representing probabilistic correlations is the analogue for quantum mechanics of the replacement of Newton's Euclidean space and time by Minkowski spacetime in special relativity. The nonclassical features of quantum mechanics, including the irreducible information loss on measurement, are generic features of correlations that lie outside the local correlation polytope. This paper is an elaboration of these ideas, and its consequences for the measurement problem of quantum mechanics. A large part of the difficulty is removed by seeing that the inconsistency in reconciling the entangled state at the end of a quantum measurement process with the definiteness of the macroscopic pointer reading and the definiteness of the correlated value of the measured micro-observable is only apparent and depends on a stipulation that is not required by the structure of the quantum possibility space. Replacing this stipulation by an alternative consistent stipulation resolves the problem. 1 aBub, Jeffrey uhttp://arxiv.org/abs/1210.6371v302190nas a2200133 4500008004100000245008300041210006900124260001400193490000700207520177000214100001701984700001802001856003702019 2014 eng d00aQuantum Interactions with Closed Timelike Curves and Superluminal Signaling 0 aQuantum Interactions with Closed Timelike Curves and Superlumina c2014/2/120 v893 a There is now a significant body of results on quantum interactions with closed timelike curves (CTCs) in the quantum information literature, for both the Deutsch model of CTC interactions (D-CTCs) and the projective model (P-CTCs). As a consequence, there is a prima facie argument exploiting entanglement that CTC interactions would enable superluminal and, indeed, effectively instantaneous signaling. In cases of spacelike separation between the sender of a signal and the receiver, whether a receiver measures the local part of an entangled state or a disentangled state to access the signal can depend on the reference frame. We propose a consistency condition that gives priority to either an entangled perspective or a disentangled perspective in spacelike separated scenarios. For D-CTC interactions, the consistency condition gives priority to frames of reference in which the state is disentangled, while for P-CTC interactions the condition selects the entangled state. Using the consistency condition, we show that there is a procedure that allows Alice to signal to Bob in the past via relayed superluminal communications between spacelike separated Alice and Clio, and spacelike separated Clio and Bob. This opens the door to time travel paradoxes in the classical domain. Ralph (arXiv:1107.4675) first pointed this out for P-CTCs, but we show that Ralph's procedure for a 'radio to the past' is flawed. Since both D-CTCs and P-CTCs allow classical information to be sent around a spacetime loop, it follows from a result by Aaronson and Watrous (Proc.Roy.Soc.A, 465:631-647 (2009)) for CTC-enhanced classical computation that a quantum computer with access to P-CTCs would have the power of PSPACE, equivalent to a D-CTC-enhanced quantum computer. 1 aBub, Jeffrey1 aStairs, Allen uhttp://arxiv.org/abs/1309.4751v401000nas a2200121 4500008004100000245007700041210006900118260001500187520059900202100002100801700001900822856003700841 2014 eng d00aA Quantum Network of Silicon Qubits using Mid-Infrared Graphene Plasmons0 aQuantum Network of Silicon Qubits using MidInfrared Graphene Pla c2014/07/253 a We consider a quantum network of mid-infrared, graphene plasmons coupled to the hydrogen-like excited states of group-V donors in silicon. First, we show how to use plasmon-enhanced light-matter interactions to achieve single-shot spin readout of the donor qubits via optical excitation and electrical detection of the emitted plasmons. We then show how plasmons in high mobility graphene nanoribbons can be used to achieve high-fidelity, two-qubit gates and entanglement of distant Si donor qubits. The proposed device is readily compatible with existing technology and fabrication methods. 1 aGullans, Michael1 aTaylor, J., M. uhttp://arxiv.org/abs/1407.7035v101088nas a2200145 4500008004100000245006400041210006300105260001500168520063800183100002400821700001900845700002000864700002100884856003700905 2014 eng d00aQuipper: Concrete Resource Estimation in Quantum Algorithms0 aQuipper Concrete Resource Estimation in Quantum Algorithms c2014/12/013 a

Despite the rich literature on quantum algorithms, there is a surprisingly small amount of coverage of their concrete logical design and implementation. Most resource estimation is done at the level of complexity analysis, but actual concrete numbers (of quantum gates, qubits, etc.) can differ by orders of magnitude. The line of work we present here is a formal framework to write, and reason about, quantum algorithms. Specifically, we designed a language, Quipper, with scalability in mind, and we are able to report actual resource counts for seven non-trivial algorithms found in the quantum computer science literature.

1 aSmith, Jonathan, M.1 aRoss, Neil, J.1 aSelinger, Peter1 aValiron, Benoît uhttp://arxiv.org/abs/1412.0625v102134nas a2200133 4500008004100000245008900041210006900130260001400199490000700213520170000220100001901920700002401939856003701963 2013 eng d00aQuadrature interferometry for nonequilibrium ultracold bosons in optical lattices 0 aQuadrature interferometry for nonequilibrium ultracold bosons in c2013/1/220 v873 a We develop an interferometric technique for making time-resolved measurements of field-quadrature operators for nonequilibrium ultracold bosons in optical lattices. The technique exploits the internal state structure of magnetic atoms to create two subsystems of atoms in different spin states and lattice sites. A Feshbach resonance turns off atom-atom interactions in one spin subsystem, making it a well-characterized reference state, while atoms in the other subsystem undergo nonequilibrium dynamics for a variable hold time. Interfering the subsystems via a second beam-splitting operation, time-resolved quadrature measurements on the interacting atoms are obtained by detecting relative spin populations. The technique can provide quadrature measurements for a variety of Hamiltonians and lattice geometries (e.g., cubic, honeycomb, superlattices), including systems with tunneling, spin-orbit couplings using artificial gauge fields, and higher-band effects. Analyzing the special case of a deep lattice with negligible tunneling, we obtain the time evolution of both quadrature observables and their fluctuations. As a second application, we show that the interferometer can be used to measure atom-atom interaction strengths with super-Heisenberg scaling n^(-3/2) in the mean number of atoms per lattice site n, and standard quantum limit scaling M^(-1/2) in the number of lattice sites M. In our analysis, we require M >> 1 and for realistic systems n is small, and therefore the scaling in total atom number N = nM is below the Heisenberg limit; nevertheless, measurements testing the scaling behaviors for interaction-based quantum metrologies should be possible in this system. 1 aTiesinga, Eite1 aJohnson, Philip, R. uhttp://arxiv.org/abs/1212.1193v200905nas a2200133 4500008004100000245003600041210003400077260001500111300001100126490000700137520057100144100001900715856003700734 2013 eng d00aQuantum Adversary (Upper) Bound0 aQuantum Adversary Upper Bound c2013/04/05 a1 - 140 v193 a We describe a method to upper bound the quantum query complexity of Boolean formula evaluation problems, using fundamental theorems about the general adversary bound. This nonconstructive method can give an upper bound on query complexity without producing an algorithm. For example, we describe an oracle problem which we prove (non-constructively) can be solved in $O(1)$ queries, where the previous best quantum algorithm uses a polylogarithmic number of queries. We then give an explicit $O(1)$-query algorithm for this problem based on span programs. 1 aKimmel, Shelby uhttp://arxiv.org/abs/1101.0797v501289nas 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.6983v201052nas a2200145 4500008004100000245005700041210005600098260001500154490000700169520062400176100002700800700002300827700001900850856003700869 2013 eng d00aQuantum Cherenkov Radiation and Non-contact Friction0 aQuantum Cherenkov Radiation and Noncontact Friction c2013/10/210 v883 a We present a number of arguments to demonstrate that a quantum analog of Cherenkov effect occurs when two dispersive objects are in relative motion. Specifically we show that two semi-infinite plates experience friction beyond a threshold velocity which, in their center-of-mass frame, is the phase speed of light within their medium. The loss in mechanical energy is radiated away through the plates before getting fully absorbed in the form of heat. By deriving various correlation functions inside and outside the two plates, we explicitly compute the radiation, and discuss its dependence on the reference frame. 1 aMaghrebi, Mohammad, F.1 aGolestanian, Ramin1 aKardar, Mehran uhttp://arxiv.org/abs/1304.4909v201995nas a2200205 4500008004100000245005100041210005100092260001300143490000700156520142000163100002001583700001901603700002301622700002401645700001801669700002301687700001701710700002501727856003701752 2013 eng d00aQuantum Logic between Remote Quantum Registers0 aQuantum Logic between Remote Quantum Registers c2013/2/60 v873 a We analyze two approaches to quantum state transfer in solid-state spin systems. First, we consider unpolarized spin-chains and extend previous analysis to various experimentally relevant imperfections, including quenched disorder, dynamical decoherence, and uncompensated long range coupling. In finite-length chains, the interplay between disorder-induced localization and decoherence yields a natural optimal channel fidelity, which we calculate. Long-range dipolar couplings induce a finite intrinsic lifetime for the mediating eigenmode; extensive numerical simulations of dipolar chains of lengths up to L=12 show remarkably high fidelity despite these decay processes. We further consider the extension of the protocol to bosonic systems of coupled oscillators. Second, we introduce a quantum mirror based architecture for universal quantum computing which exploits all of the spins in the system as potential qubits. While this dramatically increases the number of qubits available, the composite operations required to manipulate "dark" spin qubits significantly raise the error threshold for robust operation. Finally, as an example, we demonstrate that eigenmode-mediated state transfer can enable robust long-range logic between spatially separated Nitrogen-Vacancy registers in diamond; numerical simulations confirm that high fidelity gates are achievable even in the presence of moderate disorder. 1 aYao, Norman, Y.1 aGong, Zhe-Xuan1 aLaumann, Chris, R.1 aBennett, Steven, D.1 aDuan, L., -M.1 aLukin, Mikhail, D.1 aJiang, Liang1 aGorshkov, Alexey, V. uhttp://arxiv.org/abs/1206.0014v100594nas a2200205 4500008004100000245006400041210006100105300000800166490000800174100001700182700001400199700001900213700001300232700001300245700001900258700002500277700001400302700001200316856006000328 2013 eng d00aA quantum many-body spin system in an optical lattice clock0 aquantum manybody spin system in an optical lattice clock a6320 v3411 aMartin, M, J1 aBishof, M1 aSwallows, M, D1 aZhang, X1 aBenko, C1 avon-Stecher, J1 aGorshkov, Alexey, V.1 aRey, A, M1 aYe, Jun uhttp://www.sciencemag.org/content/341/6146/632.abstract00562nas a2200193 4500008004100000245005900041210005800100300000700158490000700165100001900172700001600191700001600207700001700223700001500240700002500255700001900280700001200299856005700311 2013 eng d00aQuantum Nonlinear Optics: Strongly Interacting Photons0 aQuantum Nonlinear Optics Strongly Interacting Photons a480 v241 aFirstenberg, O1 aLukin, M, D1 aPeyronel, T1 aLiang, Q, -Y1 aVuletic, V1 aGorshkov, Alexey, V.1 aHofferberth, S1 aPohl, T uhttp://www.osa-opn.org/abstract.cfm?URI=opn-24-12-4801302nas a2200181 4500008004100000245005300041210005200094260001500146300001200161490000700173520078900180100002500969700002900994700001901023700002001042700002101062856003701083 2013 eng d00aQuipper: A Scalable Quantum Programming Language0 aQuipper A Scalable Quantum Programming Language c2013/06/23 a333-3420 v483 a

The field of quantum algorithms is vibrant. Still, there is currently a lack of programming languages for describing quantum computation on a practical scale, i.e., not just at the level of toy problems. We address this issue by introducing Quipper, a scalable, expressive, functional, higher-order quantum programming language. Quipper has been used to program a diverse set of non-trivial quantum algorithms, and can generate quantum gate representations using trillions of gates. It is geared towards a model of computation that uses a classical computer to control a quantum device, but is not dependent on any particular model of quantum hardware. Quipper has proven effective and easy to use, and opens the door towards using formal methods to analyze quantum algorithms.

1 aGreen, Alexander, S.1 aLumsdaine, Peter, LeFanu1 aRoss, Neil, J.1 aSelinger, Peter1 aValiron, Benoît uhttp://arxiv.org/abs/1304.3390v101584nas a2200133 4500008004100000245006400041210006400105300001200169490000700181520117000188100001901358700001901377856005401396 2012 eng d00aQuantum Algorithms for Invariants of Triangulated Manifolds0 aQuantum Algorithms for Invariants of Triangulated Manifolds a843-8630 v123 a

One of the apparent advantages of quantum computers over their classical counterparts is their ability to efficiently contract tensor networks. In this article, we study some implications of this fact in the case of topological tensor networks. The graph underlying these networks is given by the triangulation of a manifold, and the structure of the tensors ensures that the overall tensor is independent of the choice of internal triangulation. This leads to quantum algorithms for additively approximating certain invariants of triangulated manifolds. We discuss the details of this construction in two specific cases. In the first case, we consider triangulated surfaces, where the triangle tensor is defined by the multiplication operator of a finite group; the resulting invariant has a simple closed-form expression involving the dimensions of the irreducible representations of the group and the Euler characteristic of the surface. In the second case, we consider triangulated 3-manifolds, where the tetrahedral tensor is defined by the so-called Fibonacci anyon model; the resulting invariant is the well-known Turaev-Viro invariant of 3-manifolds.

1 aAlagic, Gorjan1 aBering, E., A. uhttp://dl.acm.org/citation.cfm?id=2481580.248158801068nas a2200157 4500008004100000245005000041210005000091260001500141300001600156490000800172520062800180100002400808700002200832700001900854856003700873 2012 eng d00aQuantum Algorithms for Quantum Field Theories0 aQuantum Algorithms for Quantum Field Theories c2012/05/31 a1130 - 11330 v3363 a Quantum field theory reconciles quantum mechanics and special relativity, and plays a central role in many areas of physics. We develop a quantum algorithm to compute relativistic scattering probabilities in a massive quantum field theory with quartic self-interactions (phi-fourth theory) in spacetime of four and fewer dimensions. Its run time is polynomial in the number of particles, their energy, and the desired precision, and applies at both weak and strong coupling. In the strong-coupling and high-precision regimes, our quantum algorithm achieves exponential speedup over the fastest known classical algorithm. 1 aJordan, Stephen, P.1 aLee, Keith, S. M.1 aPreskill, John uhttp://arxiv.org/abs/1111.3633v201226nas a2200169 4500008004100000245007000041210006900111260001400180490000800194520072500202100001900927700001400946700002000960700002000980700001901000856003701019 2012 eng d00aQuantum interface between an electrical circuit and a single atom0 aQuantum interface between an electrical circuit and a single ato c2012/3/300 v1083 aWe show how to bridge the divide between atomic systems and electronic devices by engineering a coupling between the motion of a single ion and the quantized electric field of a resonant circuit. Our method can be used to couple the internal state of an ion to the quantized circuit with the same speed as the internal-state coupling between two ions. All the well-known quantum information protocols linking ion internal and motional states can be converted to protocols between circuit photons and ion internal states. Our results enable quantum interfaces between solid state qubits, atomic qubits, and light, and lay the groundwork for a direct quantum connection between electrical and atomic metrology standards. 1 aKielpinski, D.1 aKafri, D.1 aWoolley, M., J.1 aMilburn, G., J.1 aTaylor, J., M. uhttp://arxiv.org/abs/1111.5999v100654nas a2200193 4500008004100000245008700041210006900128300000700197490000800204100002300212700002200235700001700257700002700274700002500301700001700326700002300343700002000366856007400386 2012 eng d00aQuantum nonlinear optics with single photons enabled by strongly interacting atoms0 aQuantum nonlinear optics with single photons enabled by strongly a570 v4881 aPeyronel, Thibault1 aFirstenberg, Ofer1 aLiang, Qi-Yu1 aHofferberth, Sebastian1 aGorshkov, Alexey, V.1 aPohl, Thomas1 aLukin, Mikhail, D.1 aVuletic, Vladan uhttp://www.nature.com/nature/journal/v488/n7409/full/nature11361.html01823nas a2200157 4500008004100000245005500041210005000096260001500146300001200161490000900173520138500182100002301567700001901590700001901609856003701628 2012 eng d00aThe quantum query complexity of read-many formulas0 aquantum query complexity of readmany formulas c2012/09/10 a337-3480 v75013 a The quantum query complexity of evaluating any read-once formula with n black-box input bits is Theta(sqrt(n)). However, the corresponding problem for read-many formulas (i.e., formulas in which the inputs have fanout) is not well understood. Although the optimal read-once formula evaluation algorithm can be applied to any formula, it can be suboptimal if the inputs have large fanout. We give an algorithm for evaluating any formula with n inputs, size S, and G gates using O(min{n, sqrt{S}, n^{1/2} G^{1/4}}) quantum queries. Furthermore, we show that this algorithm is optimal, since for any n,S,G there exists a formula with n inputs, size at most S, and at most G gates that requires Omega(min{n, sqrt{S}, n^{1/2} G^{1/4}}) queries. We also show that the algorithm remains nearly optimal for circuits of any particular depth k >= 3, and we give a linear-size circuit of depth 2 that requires Omega (n^{5/9}) queries. Applications of these results include a Omega (n^{19/18}) lower bound for Boolean matrix product verification, a nearly tight characterization of the quantum query complexity of evaluating constant-depth circuits with bounded fanout, new formula gate count lower bounds for several functions including PARITY, and a construction of an AC^0 circuit of linear size that can only be evaluated by a formula with Omega(n^{2-epsilon}) gates. 1 aChilds, Andrew, M.1 aKimmel, Shelby1 aKothari, Robin uhttp://arxiv.org/abs/1112.0548v101417nas 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.0776v102431nas a2200169 4500008004100000245010800041210006900149260001500218300001100233490000700244520189900251100002402150700001702174700001602191700001702207856003702224 2012 eng d00aQuantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators 0 aQuantum Tomography via Compressed Sensing Error Bounds Sample Co c2012/09/27 a0950220 v143 a Intuitively, if a density operator has small rank, then it should be easier to estimate from experimental data, since in this case only a few eigenvectors need to be learned. We prove two complementary results that confirm this intuition. First, we show that a low-rank density matrix can be estimated using fewer copies of the state, i.e., the sample complexity of tomography decreases with the rank. Second, we show that unknown low-rank states can be reconstructed from an incomplete set of measurements, using techniques from compressed sensing and matrix completion. These techniques use simple Pauli measurements, and their output can be certified without making any assumptions about the unknown state. We give a new theoretical analysis of compressed tomography, based on the restricted isometry property (RIP) for low-rank matrices. Using these tools, we obtain near-optimal error bounds, for the realistic situation where the data contains noise due to finite statistics, and the density matrix is full-rank with decaying eigenvalues. We also obtain upper-bounds on the sample complexity of compressed tomography, and almost-matching lower bounds on the sample complexity of any procedure using adaptive sequences of Pauli measurements. Using numerical simulations, we compare the performance of two compressed sensing estimators with standard maximum-likelihood estimation (MLE). We find that, given comparable experimental resources, the compressed sensing estimators consistently produce higher-fidelity state reconstructions than MLE. In addition, the use of an incomplete set of measurements leads to faster classical processing with no loss of accuracy. Finally, we show how to certify the accuracy of a low rank estimate using direct fidelity estimation and we describe a method for compressed quantum process tomography that works for processes with small Kraus rank. 1 aFlammia, Steven, T.1 aGross, David1 aLiu, Yi-Kai1 aEisert, Jens uhttp://arxiv.org/abs/1205.2300v201573nas a2200181 4500008004100000245004700041210004700088260001400135490000700149520106900156100002501225700002701250700001501277700001901292700002301311700002001334856003701354 2011 eng d00aQuantum Magnetism with Polar Alkali Dimers0 aQuantum Magnetism with Polar Alkali Dimers c2011/9/150 v843 a We show that dipolar interactions between ultracold polar alkali dimers in optical lattices can be used to realize a highly tunable generalization of the t-J model, which we refer to as the t-J-V-W model. The model features long-range spin-spin interactions J_z and J_perp of XXZ type, long-range density-density interaction V, and long-range density-spin interaction W, all of which can be controlled in both magnitude and sign independently of each other and of the tunneling t. The "spin" is encoded in the rotational degree of freedom of the molecules, while the interactions are controlled by applied static electric and continuous-wave microwave fields. Furthermore, we show that nuclear spins of the molecules can be used to implement an additional (orbital) degree of freedom that is coupled to the original rotational degree of freedom in a tunable way. The presented system is expected to exhibit exotic physics and to provide insights into strongly correlated phenomena in condensed matter systems. Realistic experimental imperfections are discussed. 1 aGorshkov, Alexey, V.1 aManmana, Salvatore, R.1 aChen, Gang1 aDemler, Eugene1 aLukin, Mikhail, D.1 aRey, Ana, Maria uhttp://arxiv.org/abs/1106.1655v100483nas a2200169 4500008004100000245005300041210005200094300001100146490000700157100002500164700001800189700001200207700001400219700001600233700001400249856005000263 2011 eng d00aQuantum magnetism with polar alkali-metal dimers0 aQuantum magnetism with polar alkalimetal dimers a0336190 v841 aGorshkov, Alexey, V.1 aManmana, S, R1 aChen, G1 aDemler, E1 aLukin, M, D1 aRey, A, M uhttp://link.aps.org/abstract/PRA/v84/e033619/01380nas a2200145 4500008004100000245006200041210006100103260001500164300001200179490000600191520095800197100002301155700001901178856003701197 2011 eng d00aQuantum query complexity of minor-closed graph properties0 aQuantum query complexity of minorclosed graph properties c2011/01/01 a661-6720 v93 a We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether an $n$-vertex graph is planar, is a forest, or does not contain a path of a given length. We show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity \Theta(n^{3/2}). To establish this, we prove an adversary lower bound using a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. On the other hand, we show that minor-closed properties (and more generally, sparse graph properties) that can be characterized by finitely many forbidden subgraphs can be solved strictly faster, in o(n^{3/2}) queries. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems. 1 aChilds, Andrew, M.1 aKothari, Robin uhttp://arxiv.org/abs/1011.1443v201051nas a2200145 4500008004100000245007400041210006900115260001400184490000700198520060100205100002400806700001800830700002000848856003700868 2010 eng d00aQMA-complete problems for stoquastic Hamiltonians and Markov matrices0 aQMAcomplete problems for stoquastic Hamiltonians and Markov matr c2010/3/290 v813 a We show that finding the lowest eigenvalue of a 3-local symmetric stochastic matrix is QMA-complete. We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation using certain excited states of a stoquastic Hamiltonian is universal. We also show that adiabatic evolution in the ground state of a stochastic frustration free Hamiltonian is universal. Our results give a new QMA-complete problem arising in the classical setting of Markov chains, and new adiabatically universal Hamiltonians that arise in many physical systems. 1 aJordan, Stephen, P.1 aGosset, David1 aLove, Peter, J. uhttp://arxiv.org/abs/0905.4755v201122nas a2200145 4500008004100000245004600041210004600087260001400133300001100147490000700158520073400165100002300899700001700922856003700939 2010 eng d00aQuantum algorithms for algebraic problems0 aQuantum algorithms for algebraic problems c2010/1/15 a1 - 520 v823 a Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation, and in particular, on problems with an algebraic flavor. 1 aChilds, Andrew, M.1 avan Dam, Wim uhttp://arxiv.org/abs/0812.0380v102230nas a2200133 4500008004100000245006800041210006600109490000600175520174200181100001901923700002201942700002301964856010901987 2010 eng d00aQuantum Algorithms for Simon’s Problem over Nonabelian Groups0 aQuantum Algorithms for Simon s Problem over Nonabelian Groups0 v63 a

Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding “hidden shifts” of Z2n provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. In this article, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution m = (m1,…,mn) ∈ Gn from an oracle f with the property that f(x ⋅ y) = f(x) ⇔ y ∈ {1, m}. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form Gn, where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two.

Although groups of the form Gn have a simple product structure, they share important representation--theoretic properties with the symmetric groups Sn, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called “standard method” requires highly entangled measurements on the tensor product of many coset states.

In this article, we provide quantum algorithms with time complexity 2O(√n) that recover hidden involutions m = (m1,…mn) ∈ Gn where, as in Simon's problem, each mi is either the identity or the conjugate of a known element m which satisfies κ(m) = −κ(1) for some κ ∈ Ĝ. Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the “missing harmonic” approach of Moore and Russell. These are the first nontrivial HSP algorithms for group families that require highly entangled multiregister Fourier sampling.

1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://www.quics.umd.edu/publications/quantum-algorithms-simon%E2%80%99s-problem-over-nonabelian-groups01335nas a2200133 4500008004100000245005200041210005100093260001500144300001200159490000700171520096900178100001701147856003701164 2010 eng d00aQuantum computation and pseudo-telepathic games0 aQuantum computation and pseudotelepathic games c2010/05/14 a458-4720 v753 a A quantum algorithm succeeds not because the superposition principle allows 'the computation of all values of a function at once' via 'quantum parallelism,' but rather because the structure of a quantum state space allows new sorts of correlations associated with entanglement, with new possibilities for information-processing transformations between correlations, that are not possible in a classical state space. I illustrate this with an elementary example of a problem for which a quantum algorithm is more efficient than any classical algorithm. I also introduce the notion of 'pseudo-telepathic' games and show how the difference between classical and quantum correlations plays a similar role here for games that can be won by quantum players exploiting entanglement, but not by classical players whose only allowed common resource consists of shared strings of random numbers (common causes of the players' correlated responses in a game). 1 aBub, Jeffrey uhttp://arxiv.org/abs/1005.2449v102052nas a2200193 4500008004100000245002200041210002200063260001300085300001200098490000800110520156800118100002301686700001901709700002201728700002301750700002401773700002401797856003701821 2010 eng d00aQuantum Computing0 aQuantum Computing c2010/3/4 a45 - 530 v4643 a Quantum mechanics---the theory describing the fundamental workings of nature---is famously counterintuitive: it predicts that a particle can be in two places at the same time, and that two remote particles can be inextricably and instantaneously linked. These predictions have been the topic of intense metaphysical debate ever since the theory's inception early last century. However, supreme predictive power combined with direct experimental observation of some of these unusual phenomena leave little doubt as to its fundamental correctness. In fact, without quantum mechanics we could not explain the workings of a laser, nor indeed how a fridge magnet operates. Over the last several decades quantum information science has emerged to seek answers to the question: can we gain some advantage by storing, transmitting and processing information encoded in systems that exhibit these unique quantum properties? Today it is understood that the answer is yes. Many research groups around the world are working towards one of the most ambitious goals humankind has ever embarked upon: a quantum computer that promises to exponentially improve computational power for particular tasks. A number of physical systems, spanning much of modern physics, are being developed for this task---ranging from single particles of light to superconducting circuits---and it is not yet clear which, if any, will ultimately prove successful. Here we describe the latest developments for each of the leading approaches and explain what the major challenges are for the future. 1 aLadd, Thaddeus, D.1 aJelezko, Fedor1 aLaflamme, Raymond1 aNakamura, Yasunobu1 aMonroe, Christopher1 aO'Brien, Jeremy, L. uhttp://arxiv.org/abs/1009.2267v101818nas a2200109 4500008004100000245006700041210006500108260001500173520146600188100001701654856003701671 2010 eng d00aQuantum probabilities: an information-theoretic interpretation0 aQuantum probabilities an informationtheoretic interpretation c2010/05/143 a This Chapter develops a realist information-theoretic interpretation of the nonclassical features of quantum probabilities. On this view, what is fundamental in the transition from classical to quantum physics is the recognition that \emph{information in the physical sense has new structural features}, just as the transition from classical to relativistic physics rests on the recognition that space-time is structurally different than we thought. Hilbert space, the event space of quantum systems, is interpreted as a kinematic (i.e., pre-dynamic) framework for an indeterministic physics, in the sense that the geometric structure of Hilbert space imposes objective probabilistic or information-theoretic constraints on correlations between events, just as the geometric structure of Minkowski space in special relativity imposes spatio-temporal kinematic constraints on events. The interpretation of quantum probabilities is more subjectivist in spirit than other discussions in this book (e.g., the chapter by Timpson), insofar as the quantum state is interpreted as a credence function---a bookkeeping device for keeping track of probabilities---but it is also objective (or intersubjective), insofar as the credences specified by the quantum state are understood as uniquely determined, via Gleason's theorem, by objective correlational constraints on events in the nonclassical quantum event space defined by the subspace structure of Hilbert space. 1 aBub, Jeffrey uhttp://arxiv.org/abs/1005.2448v101146nas a2200145 4500008004100000245005500041210005400096260001500150300001200165520072600177100002100903700002300924700001600947856003700963 2010 eng d00aQuantum property testing for bounded-degree graphs0 aQuantum property testing for boundeddegree graphs c2010/12/14 a365-3763 a We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound. For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph structure. 1 aAmbainis, Andris1 aChilds, Andrew, M.1 aLiu, Yi-Kai uhttp://arxiv.org/abs/1012.3174v301338nas a2200169 4500008004100000245005200041210005200093260001400145490000800159520087000167100001701037700001601054700002401070700002001094700001701114856003701131 2010 eng d00aQuantum state tomography via compressed sensing0 aQuantum state tomography via compressed sensing c2010/10/40 v1053 a We establish methods for quantum state tomography based on compressed sensing. These methods are specialized for quantum states that are fairly pure, and they offer a significant performance improvement on large quantum systems. In particular, they are able to reconstruct an unknown density matrix of dimension d and rank r using O(rd log^2 d) measurement settings, compared to standard methods that require d^2 settings. Our methods have several features that make them amenable to experimental implementation: they require only simple Pauli measurements, use fast convex optimization, are stable against noise, and can be applied to states that are only approximately low-rank. The acquired data can be used to certify that the state is indeed close to pure, so no a priori assumptions are needed. We present both theoretical bounds and numerical simulations. 1 aGross, David1 aLiu, Yi-Kai1 aFlammia, Steven, T.1 aBecker, Stephen1 aEisert, Jens uhttp://arxiv.org/abs/0909.3304v401260nas a2200133 4500008004100000245010100041210006900142260001400211490000700225520080900232100002401041700002401065856003701089 2009 eng d00aQuadratic fermionic interactions yield effective Hamiltonians for adiabatic quantum computing 0 aQuadratic fermionic interactions yield effective Hamiltonians fo c2009/3/240 v793 a Polynomially-large ground-state energy gaps are rare in many-body quantum systems, but useful for adiabatic quantum computing. We show analytically that the gap is generically polynomially-large for quadratic fermionic Hamiltonians. We then prove that adiabatic quantum computing can realize the ground states of Hamiltonians with certain random interactions, as well as the ground states of one, two, and three-dimensional fermionic interaction lattices, in polynomial time. Finally, we use the Jordan-Wigner transformation and a related transformation for spin-3/2 particles to show that our results can be restated using spin operators in a surprisingly simple manner. A direct consequence is that the one-dimensional cluster state can be found in polynomial time using adiabatic quantum computing. 1 aO'Hara, Michael, J.1 aO'Leary, Dianne, P. uhttp://arxiv.org/abs/0808.1768v101371nas a2200121 4500008004100000245005200041210005200093260001500145300001200160520102400172100001601196856003701212 2009 eng d00aQuantum Algorithms Using the Curvelet Transform0 aQuantum Algorithms Using the Curvelet Transform c2009/10/28 a391-4003 a The curvelet transform is a directional wavelet transform over R^n, which is used to analyze functions that have singularities along smooth surfaces (Candes and Donoho, 2002). I demonstrate how this can lead to new quantum algorithms. I give an efficient implementation of a quantum curvelet transform, together with two applications: a single-shot measurement procedure for approximately finding the center of a ball in R^n, given a quantum-sample over the ball; and, a quantum algorithm for finding the center of a radial function over R^n, given oracle access to the function. I conjecture that these algorithms succeed with constant probability, using one quantum-sample and O(1) oracle queries, respectively, independent of the dimension n -- this can be interpreted as a quantum speed-up. To support this conjecture, I prove rigorous bounds on the distribution of probability mass for the continuous curvelet transform. This shows that the above algorithms work in an idealized "continuous" model. 1 aLiu, Yi-Kai uhttp://arxiv.org/abs/0810.4968v201274nas a2200181 4500008004100000245011400041210006900155260001400224490000800238520068400246100001700930700002000947700002500967700002400992700001901016700002001035856003701055 2009 eng d00aQuantum Phase Transitions and Continuous Observation of Spinor Dynamics in an Antiferromagnetic Condensate 0 aQuantum Phase Transitions and Continuous Observation of Spinor D c2009/3/230 v1023 a Condensates of spin-1 sodium display rich spin dynamics due to the antiferromagnetic nature of the interactions in this system. We use Faraday rotation spectroscopy to make a continuous and minimally destructive measurement of the dynamics over multiple spin oscillations on a single evolving condensate. This method provides a sharp signature to locate a magnetically tuned separatrix in phase space which depends on the net magnetization. We also observe a phase transition from a two- to a three-component condensate at a low but finite temperature using a Stern-Gerlach imaging technique. This transition should be preserved as a zero-temperature quantum phase transition. 1 aLiu, Yingmei1 aJung, Sebastian1 aMaxwell, Stephen, E.1 aTurner, Lincoln, D.1 aTiesinga, Eite1 aLett, Paul., D. uhttp://arxiv.org/abs/0902.3189v100937nas a2200145 4500008004100000245005000041210004600091260001500137520051500152100002100667700002300688700002300711700002000734856003700754 2009 eng d00aThe quantum query complexity of certification0 aquantum query complexity of certification c2009/03/063 a We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem. 1 aAmbainis, Andris1 aChilds, Andrew, M.1 aLe Gall, François1 aTani, Seiichiro uhttp://arxiv.org/abs/0903.1291v201333nas a2200181 4500008004100000245004900041210004900090260001400139490000700153520083600160100001900996700002001015700001701035700002101052700002201073700001901095856003701114 2008 eng d00aQuantum behavior of the dc SQUID phase qubit0 aQuantum behavior of the dc SQUID phase qubit c2008/6/130 v773 a We analyze the behavior of a dc Superconducting Quantum Interference Device (SQUID) phase qubit in which one junction acts as a phase qubit and the rest of the device provides isolation from dissipation and noise in the bias leads. Ignoring dissipation, we find the two-dimensional Hamiltonian of the system and use numerical methods and a cubic approximation to solve Schrodinger's equation for the eigenstates, energy levels, tunneling rates, and expectation value of the currents in the junctions. Using these results, we investigate how well this design provides isolation while preserving the characteristics of a phase qubit. In addition, we show that the expectation value of current flowing through the isolation junction depends on the state of the qubit and can be used for non-destructive read out of the qubit state. 1 aMitra, Kaushik1 aStrauch, F., W.1 aLobb, C., J.1 aAnderson, J., R.1 aWellstood, F., C.1 aTiesinga, Eite uhttp://arxiv.org/abs/0805.3680v101534nas a2200109 4500008004100000245004900041210004900090260001500139520120900154100002401363856003701387 2008 eng d00aQuantum Computation Beyond the Circuit Model0 aQuantum Computation Beyond the Circuit Model c2008/09/133 a The quantum circuit model is the most widely used model of quantum computation. It provides both a framework for formulating quantum algorithms and an architecture for the physical construction of quantum computers. However, several other models of quantum computation exist which provide useful alternative frameworks for both discovering new quantum algorithms and devising new physical implementations of quantum computers. In this thesis, I first present necessary background material for a general physics audience and discuss existing models of quantum computation. Then, I present three results relating to various models of quantum computation: a scheme for improving the intrinsic fault tolerance of adiabatic quantum computers using quantum error detecting codes, a proof that a certain problem of estimating Jones polynomials is complete for the one clean qubit complexity class, and a generalization of perturbative gadgets which allows k-body interactions to be directly simulated using 2-body interactions. Lastly, I discuss general principles regarding quantum computation that I learned in the course of my research, and using these principles I propose directions for future research. 1 aJordan, Stephen, P. uhttp://arxiv.org/abs/0809.2307v100989nas a2200133 4500008004100000245005500041210005500096260001500151520057900166100002300745700002600768700002400794856003700818 2007 eng d00aQuantum algorithms for hidden nonlinear structures0 aQuantum algorithms for hidden nonlinear structures c2007/05/213 a Attempts to find new quantum algorithms that outperform classical computation have focused primarily on the nonabelian hidden subgroup problem, which generalizes the central problem solved by Shor's factoring algorithm. We suggest an alternative generalization, namely to problems of finding hidden nonlinear structures over finite fields. We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures. 1 aChilds, Andrew, M.1 aSchulman, Leonard, J.1 aVazirani, Umesh, V. uhttp://arxiv.org/abs/0705.2784v102185nas a2200145 4500008004100000245006500041210006300106260001400169300001600183520173300199100001901932700002201951700002301973856004301996 2007 eng d00aQuantum Algorithms for Simon’s Problem over General Groups0 aQuantum Algorithms for Simon s Problem over General Groups c1/25/2007 a1217–12243 a

Daniel Simon's 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (HSP) over Zn2 provided one of the first algebraic problems for which quantum computers are exponentially faster than their classical counterparts. In this paper, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution m = (m1,...,mn) ε Gn from an oracle f with the property that f(x) = f(x · y) ⇔ y ε {1, m}. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form Gn, where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two.

Although groups of the form Gn have a simple product structure, they share important representation-theoretic properties with the symmetric groups Sn, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called "standard method" requires highly entangled measurements on the tensor product of many coset states.

Here we give quantum algorithms with time complexity 2O(√n log n) that recover hidden involutions m = (m1,..., mn) ε Gn where, as in Simon's problem, each mi is either the identity or the conjugate of a known element m and there is a character X of G for which X(m) = - X(1). Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the "missing harmonic" approach of Moore and Russell. These are the first nontrivial hidden subgroup algorithms for group families that require highly entangled multiregister Fourier sampling.

1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://arxiv.org/abs/quant-ph/060325102060nas a2200133 4500008004100000245005500041210005500096300001000151490000700161520157400168100001901742700002301761856014201784 2007 eng d00aQuantum Computing and the Hunt for Hidden Symmetry0 aQuantum Computing and the Hunt for Hidden Symmetry a53-750 v933 a

In 1994, Peter Shor gave e cient quantum algorithms for factoring integers and extracting discrete logarithms [20]. If we believe that nature will permit us to faithfully implement our current model of quantum computation, then these algorithms dramatically contradict the Strong Church-Turing thesis. The e ect is heightened by the fact that these algorithms solve computational problems with long histories of attention by the computational and mathematical communities alike. In this article we discuss the branch of quantum algorithms research arising from attempts to generalize the core quantum algorithmic aspects of Shor's algorithms. Roughly, this can be viewed as the problem of generalizing algorithms of Simon [21] and Shor [20], which work over abelian groups, to general nonabelian groups. The article is meant to be self-contained, assuming no knowledge of quantum computing or the representation theory of nite groups. We begin in earnest in Section 2, describing the problem of symmetry nding : given a function f : G → S on a group G, this is the problem of determining {g ∈ G | ∀x, f(x) = f(gx)}, the set of symmetries of f . We switch gears in Section 3, giving a short introduction to the circuit model of quantum computation. The connection between these two sections is eventually established in Section 4, where we discuss the representation theory of nite groups and the quantum Fourier transform a unitary transformation speci cally tuned to the symmetries of the underlying group. Section 4.2 is devoted to Fourier

1 aAlagic, Gorjan1 aRussell, Alexander uhttps://pdfs.semanticscholar.org/08f7/abc04ca0bd38c1351ee1179139d8b0fc172b.pdf?_ga=2.210619804.800377824.1595266095-1152452310.159526609500956nas a2200109 4500008004100000245006300041210006100104260001500165520061000180100001900790856003700809 2007 eng d00aA quantum dot implementation of the quantum NAND algorithm0 aquantum dot implementation of the quantum NAND algorithm c2007/08/103 aWe propose a physical implementation of the quantum NAND tree evaluation algorithm. Our approach, based on continuous time quantum walks, uses the wave interference of a single electron in a heirarchical set of tunnel coupled quantum dots. We find that the query complexity of the NAND tree evaluation does not suffer strongly from disorder and dephasing, nor is it directly limited by temperature or restricted dimensionality for 2-d structures. Finally, we suggest a potential application of this algorithm to the efficient determination of high-order correlation functions of complex quantum systems. 1 aTaylor, J., M. uhttp://arxiv.org/abs/0708.1484v101544nas a2200109 4500008004100000245005900041210005900100260001500159520119900174100001701373856004401390 2006 eng d00aQuantum computation from a quantum logical perspective0 aQuantum computation from a quantum logical perspective c2006/05/293 a It is well-known that Shor's factorization algorithm, Simon's period-finding algorithm, and Deutsch's original XOR algorithm can all be formulated as solutions to a hidden subgroup problem. Here the salient features of the information-processing in the three algorithms are presented from a different perspective, in terms of the way in which the algorithms exploit the non-Boolean quantum logic represented by the projective geometry of Hilbert space. From this quantum logical perspective, the XOR algorithm appears directly as a special case of Simon's algorithm, and all three algorithms can be seen as exploiting the non-Boolean logic represented by the subspace structure of Hilbert space in a similar way. Essentially, a global property of a function (such as a period, or a disjunctive property) is encoded as a subspace in Hilbert space representing a quantum proposition, which can then be efficiently distinguished from alternative propositions, corresponding to alternative global properties, by a measurement (or sequence of measurements) that identifies the target proposition as the proposition represented by the subspace containing the final state produced by the algorithm. 1 aBub, Jeffrey uhttp://arxiv.org/abs/quant-ph/0605243v201321nas a2200157 4500008004100000022001400041245005800055210005800113260001500171300001000186490000700196520083300203100002401036700002501060856007801085 2005 eng d a1068-961300aQR Factorizations Using a Restricted Set of Rotations0 aQR Factorizations Using a Restricted Set of Rotations c2005/07/11 a20-270 v213 aAny matrix A of dimension m × n (m ≥ n) can be reduced to upper triangular form by multiplying by a sequence of mn − n(n + 1)/2 appropriately chosen rotation matrices. In this work, we address the question of whether such a factorization exists when the set of allowed rotation planes is restricted. We introduce the rotation graph as a tool to devise elimination orderings in QR factorizations. Properties of this graph characterize sets of rotation planes that are sufficient (or sufficient under permutation) and identify rotation planes to add to complete a deficient set. We also devise a constructive way to determine all feasible rotation sequences for performing the QR factorization using a restricted set of rotation planes. We present applications to quantum circuit design and parallel QR factorization.1 aO'Leary, Dianne, P.1 aBullock, Stephen, S. uhttp://www.emis.ams.org/journals/ETNA/vol.21.2005/pp20-27.dir/pp20-27.pdf01092nas a2200121 4500008004100000245006100041210006100102260001500163520070800178100002300886700001700909856004400926 2005 eng d00aQuantum algorithm for a generalized hidden shift problem0 aQuantum algorithm for a generalized hidden shift problem c2005/07/193 a Consider the following generalized hidden shift problem: given a function f on {0,...,M-1} x Z_N satisfying f(b,x)=f(b+1,x+s) for b=0,1,...,M-2, find the unknown shift s in Z_N. For M=N, this problem is an instance of the abelian hidden subgroup problem, which can be solved efficiently on a quantum computer, whereas for M=2, it is equivalent to the dihedral hidden subgroup problem, for which no efficient algorithm is known. For any fixed positive epsilon, we give an efficient (i.e., poly(log N)) quantum algorithm for this problem provided M > N^epsilon. The algorithm is based on the "pretty good measurement" and uses H. Lenstra's (classical) algorithm for integer programming as a subroutine. 1 aChilds, Andrew, M.1 avan Dam, Wim uhttp://arxiv.org/abs/quant-ph/0507190v101105nas a2200121 4500008004100000245009900041210006900140260001500209520067400224100002300898700001800921856004400939 2005 eng d00aOn the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems 0 aquantum hardness of solving isomorphism problems as nonabelian h c2005/10/253 a We consider an approach to deciding isomorphism of rigid n-vertex graphs (and related isomorphism problems) by solving a nonabelian hidden shift problem on a quantum computer using the standard method. Such an approach is arguably more natural than viewing the problem as a hidden subgroup problem. We prove that the hidden shift approach to rigid graph isomorphism is hard in two senses. First, we prove that Omega(n) copies of the hidden shift states are necessary to solve the problem (whereas O(n log n) copies are sufficient). Second, we prove that if one is restricted to single-register measurements, an exponential number of hidden shift states are required. 1 aChilds, Andrew, M.1 aWocjan, Pawel uhttp://arxiv.org/abs/quant-ph/0510185v100763nas a2200109 4500008004100000245004000041210004000081260001500121520045600136100001700592856004400609 2005 eng d00aQuantum information and computation0 aQuantum information and computation c2005/12/153 a This article deals with theoretical developments in the subject of quantum information and quantum computation, and includes an overview of classical information and some relevant quantum mechanics. The discussion covers topics in quantum communication, quantum cryptography, and quantum computation, and concludes by considering whether a perspective in terms of quantum information sheds new light on the conceptual problems of quantum mechanics. 1 aBub, Jeffrey uhttp://arxiv.org/abs/quant-ph/0512125v200876nas a2200133 4500008004100000245005100041210005100092260001500143300001400158490000700172520050200179100001700681856004400698 2005 eng d00aQuantum mechanics is about quantum information0 aQuantum mechanics is about quantum information c2005/04/01 a541 - 5600 v353 a I argue that quantum mechanics is fundamentally a theory about the representation and manipulation of information, not a theory about the mechanics of nonclassical waves or particles. The notion of quantum information is to be understood as a new physical primitive -- just as, following Einstein's special theory of relativity, a field is no longer regarded as the physical manifestation of vibrations in a mechanical medium, but recognized as a new physical primitive in its own right. 1 aBub, Jeffrey uhttp://arxiv.org/abs/quant-ph/0408020v201230nas 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/0407640v201386nas a2200265 4500008004100000245006600041210006500107260001500172300000900187490000700196520066500203100002100868700001800889700001300907700002100920700001700941700001300958700001100971700001500982700002200997700002301019700001901042700001501061856004401076 2004 eng d00aQuantum key distribution with 1.25 Gbps clock synchronization0 aQuantum key distribution with 125 Gbps clock synchronization c2004/05/17 a20110 v123 a We have demonstrated the exchange of sifted quantum cryptographic key over a 730 meter free-space link at rates of up to 1.0 Mbps, two orders of magnitude faster than previously reported results. A classical channel at 1550 nm operates in parallel with a quantum channel at 845 nm. Clock recovery techniques on the classical channel at 1.25 Gbps enable quantum transmission at up to the clock rate. System performance is currently limited by the timing resolution of our silicon avalanche photodiode detectors. With improved detector resolution, our technique will yield another order of magnitude increase in performance, with existing technology. 1 aBienfang, J., C.1 aGross, A., J.1 aMink, A.1 aHershman, B., J.1 aNakassis, A.1 aTang, X.1 aLu, R.1 aSu, D., H.1 aClark, Charles, W1 aWilliams, Carl, J.1 aHagley, E., W.1 aWen, Jesse uhttp://arxiv.org/abs/quant-ph/0405097v101268nas a2200121 4500008004100000245004200041210004200083260001500125520091400140100002301054700002501077856004401102 2003 eng d00aQuantum algorithms for subset finding0 aQuantum algorithms for subset finding c2003/11/063 a Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds. 1 aChilds, Andrew, M.1 aEisenberg, Jason, M. uhttp://arxiv.org/abs/quant-ph/0311038v201194nas a2200145 4500008004100000245006400041210006200105260001400167490000700181520075200188100002300940700001800963700002300981856004401004 2003 eng d00aA Quantum Computer Architecture using Nonlocal Interactions0 aQuantum Computer Architecture using Nonlocal Interactions c2003/5/270 v673 a Several authors have described the basic requirements essential to build a scalable quantum computer. Because many physical implementation schemes for quantum computing rely on nearest neighbor interactions, there is a hidden quantum communication overhead to connect distant nodes of the computer. In this paper we propose a physical solution to this problem which, together with the key building blocks, provides a pathway to a scalable quantum architecture using nonlocal interactions. Our solution involves the concept of a quantum bus that acts as a refreshable entanglement resource to connect distant memory nodes providing an architectural concept for quantum computers analogous to the von Neumann architecture for classical computers. 1 aBrennen, Gavin, K.1 aSong, Daegene1 aWilliams, Carl, J. uhttp://arxiv.org/abs/quant-ph/0301012v201071nas a2200181 4500008004100000245003400041210003400075260001400109490000700123520059100130100002300721700001900744700001800763700002300781700001700804700002400821856004400845 2002 eng d00aQuantum search by measurement0 aQuantum search by measurement c2002/9/230 v663 a We propose a quantum algorithm for solving combinatorial search problems that uses only a sequence of measurements. The algorithm is similar in spirit to quantum computation by adiabatic evolution, in that the goal is to remain in the ground state of a time-varying Hamiltonian. Indeed, we show that the running times of the two algorithms are closely related. We also show how to achieve the quadratic speedup for Grover's unstructured search problem with only two measurements. Finally, we discuss some similarities and differences between the adiabatic and measurement algorithms. 1 aChilds, Andrew, M.1 aDeotto, Enrico1 aFarhi, Edward1 aGoldstone, Jeffrey1 aGutmann, Sam1 aLandahl, Andrew, J. uhttp://arxiv.org/abs/quant-ph/0204013v100978nas a2200109 4500008004100000245003900041210003500080260001500115520067700130100001700807856004400824 2000 eng d00aThe quantum bit commitment theorem0 aquantum bit commitment theorem c2000/07/253 a Unconditionally secure two-party bit commitment based solely on the principles of quantum mechanics (without exploiting special relativistic signalling constraints, or principles of general relativity or thermodynamics) has been shown to be impossible, but the claim is repeatedly challenged. The quantum bit commitment theorem is reviewed here and the central conceptual point, that an `Einstein-Podolsky-Rosen' attack or cheating strategy can always be applied, is clarified. The question of whether following such a cheating strategy can ever be disadvantageous to the cheater is considered and answered in the negative. There is, indeed, no loophole in the theorem. 1 aBub, Jeffrey uhttp://arxiv.org/abs/quant-ph/0007090v401129nas a2200157 4500008004100000245005000041210005000091260001500141300001400156490000700170520069000177100002300867700001900890700001800909856004400927 2000 eng d00aQuantum information and precision measurement0 aQuantum information and precision measurement c1999/04/07 a155 - 1760 v473 a We describe some applications of quantum information theory to the analysis of quantum limits on measurement sensitivity. A measurement of a weak force acting on a quantum system is a determination of a classical parameter appearing in the master equation that governs the evolution of the system; limitations on measurement accuracy arise because it is not possible to distinguish perfectly among the different possible values of this parameter. Tools developed in the study of quantum information and computation can be exploited to improve the precision of physics experiments; examples include superdense coding, fast database search, and the quantum Fourier transform. 1 aChilds, Andrew, M.1 aPreskill, John1 aRenes, Joseph uhttp://arxiv.org/abs/quant-ph/9904021v200624nas a2200109 4500008004100000245004400041210004400085260001500129520030900144100001700453856004400470 1999 eng d00aQuantum Mechanics as a Principle Theory0 aQuantum Mechanics as a Principle Theory c1999/10/223 a I show how quantum mechanics, like the theory of relativity, can be understood as a 'principle theory' in Einstein's sense, and I use this notion to explore the approach to the problem of interpretation developed in my book Interpreting the Quantum World (Cambridge: Cambridge University Press, 1999). 1 aBub, Jeffrey uhttp://arxiv.org/abs/quant-ph/9910096v1