TY - JOUR T1 - A Case for Synthesis of Recursive Quantum Unitary Programs JF - Proceedings of the ACM on Programming Languages Y1 - 2024 A1 - Deng, Haowei A1 - Tao, Runzhou A1 - Peng, Yuxiang A1 - Wu, Xiaodi AB -

Quantum programs are notoriously difficult to code and verify due to unintuitive quantum knowledge associated with quantum programming. Automated tools relieving the tedium and errors associated with low-level quantum details would hence be highly desirable. In this paper, we initiate the study of program synthesis for quantum unitary programs that recursively define a family of unitary circuits for different input sizes, which are widely used in existing quantum programming languages. Specifically, we present QSynth, the first quantum program synthesis framework, including a new inductive quantum programming language, its specification, a sound logic for reasoning, and an encoding of the reasoning procedure into SMT instances. By leveraging existing SMT solvers, QSynth successfully synthesizes ten quantum unitary programs including quantum adder circuits, quantum eigenvalue inversion circuits and Quantum Fourier Transformation, which can be readily transpiled to executable programs on major quantum platforms, e.g., Q#, IBM Qiskit, and AWS Braket.

VL - 8 U4 - 1759–1788 UR - https://arxiv.org/abs/2311.11503 U5 - 10.1145/3632901 ER - TY - JOUR T1 - SimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog Compilation JF - Proceedings of the ACM on Programming Languages Y1 - 2024 A1 - Peng, Yuxiang A1 - Young, Jacob A1 - Liu, Pengyu A1 - Wu, Xiaodi AB -

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

VL - 8 U4 - 2425–2455 UR - https://arxiv.org/abs/2303.02775 U5 - 10.1145/3632923 ER - TY - JOUR T1 - Analyzing Convergence in Quantum Neural Networks: Deviations from Neural Tangent Kernels Y1 - 2023 A1 - Xuchen You A1 - Shouvanik Chakrabarti A1 - Boyang Chen A1 - Xiaodi Wu AB -

A quantum neural network (QNN) is a parameterized mapping efficiently implementable on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. It can be used for supervised learning when combined with classical gradient-based optimizers. Despite the existing empirical and theoretical investigations, the convergence of QNN training is not fully understood. Inspired by the success of the neural tangent kernels (NTKs) in probing into the dynamics of classical neural networks, a recent line of works proposes to study over-parameterized QNNs by examining a quantum version of tangent kernels. In this work, we study the dynamics of QNNs and show that contrary to popular belief it is qualitatively different from that of any kernel regression: due to the unitarity of quantum operations, there is a non-negligible deviation from the tangent kernel regression derived at the random initialization. As a result of the deviation, we prove the at-most sublinear convergence for QNNs with Pauli measurements, which is beyond the explanatory power of any kernel regression dynamics. We then present the actual dynamics of QNNs in the limit of over-parameterization. The new dynamics capture the change of convergence rate during training and implies that the range of measurements is crucial to the fast QNN convergence.

UR - https://arxiv.org/abs/2303.14844 ER - TY - JOUR T1 - Clifford operations and homological codes for rotors and oscillators Y1 - 2023 A1 - Yijia Xu A1 - Yixu Wang A1 - Victor V. Albert AB -

We develop quantum information processing primitives for the planar rotor, the state space of a particle on a circle. By interpreting rotor wavefunctions as periodically identified wavefunctions of a harmonic oscillator, we determine the group of bosonic Gaussian operations inherited by the rotor. This n-rotor Clifford group, U(1)n(n+1)/2⋊GLn(Z), is represented by continuous U(1) gates generated by polynomials quadratic in angular momenta, as well as discrete GLn(Z) momentum sign-flip and sum gates. We classify homological rotor error-correcting codes [arXiv:2303.13723] and various rotor states based on equivalence under Clifford operations.
Reversing direction, we map homological rotor codes and rotor Clifford operations back into oscillators by interpreting occupation-number states as rotor states of non-negative angular momentum. This yields new multimode homological bosonic codes protecting against dephasing and changes in occupation number, along with their corresponding encoding and decoding circuits. In particular, we show how to non-destructively measure the oscillator phase using conditional occupation-number addition and post selection. We also outline several rotor and oscillator varieties of the GKP-stabilizer codes [arXiv:1903.12615].

UR - https://arxiv.org/abs/2311.07679 ER - TY - JOUR T1 - Colloquium: Quantum and Classical Discrete Time Crystals Y1 - 2023 A1 - Michael P. Zaletel A1 - Mikhail Lukin A1 - Christopher Monroe A1 - Chetan Nayak A1 - Frank Wilczek A1 - Norman Y. Yao AB -

The spontaneous breaking of time translation symmetry has led to the discovery of a new phase of matter - the discrete time crystal. Discrete time crystals exhibit rigid subharmonic oscillations, which result from a combination of many-body interactions, collective synchronization, and ergodicity breaking. This Colloquium reviews recent theoretical and experimental advances in the study of quantum and classical discrete time crystals. We focus on the breaking of ergodicity as the key to discrete time crystals and the delaying of ergodicity as the source of numerous phenomena that share many of the properties of discrete time crystals, including the AC Josephson effect, coupled map lattices, and Faraday waves. Theoretically, there exists a diverse array of strategies to stabilize time crystalline order in both closed and open systems, ranging from localization and prethermalization to dissipation and error correction. Experimentally, many-body quantum simulators provide a natural platform for investigating signatures of time crystalline order; recent work utilizing trapped ions, solid-state spin systems, and superconducting qubits will be reviewed. Finally, this Colloquium concludes by describing outstanding challenges in the field and a vision for new directions on both the experimental and theoretical fronts.

UR - https://arxiv.org/abs/2305.08904 ER - TY - RPRT T1 - Data Needs and Challenges of Quantum Dot Devices Automation: Workshop Report Y1 - 2023 A1 - Justyna P. Zwolak A1 - Jacob M. Taylor A1 - Reed Andrews A1 - Jared Benson A1 - Garnett Bryant A1 - Donovan Buterakos A1 - Anasua Chatterjee A1 - Sankar Das Sarma A1 - Mark A. Eriksson A1 - Eliška Greplová A1 - Michael J. Gullans A1 - Fabian Hader A1 - Tyler J. Kovach A1 - Pranav S. Mundada A1 - Mick Ramsey A1 - Torbjoern Rasmussen A1 - Brandon Severin A1 - Anthony Sigillito A1 - Brennan Undseth A1 - Brian Weber AB -

Gate-defined quantum dots are a promising candidate system to realize scalable, coupled qubit systems and serve as a fundamental building block for quantum computers. However, present-day quantum dot devices suffer from imperfections that must be accounted for, which hinders the characterization, tuning, and operation process. Moreover, with an increasing number of quantum dot qubits, the relevant parameter space grows sufficiently to make heuristic control infeasible. Thus, it is imperative that reliable and scalable autonomous tuning approaches are developed. In this report, we outline current challenges in automating quantum dot device tuning and operation with a particular focus on datasets, benchmarking, and standardization. We also present ideas put forward by the quantum dot community on how to overcome them.

UR - https://arxiv.org/abs/2312.14322 U5 - https://doi.org/10.48550/arXiv.2312.14322 ER - TY - JOUR T1 - Efficient learning of ground & thermal states within phases of matter Y1 - 2023 A1 - Emilio Onorati A1 - Cambyse Rouzé A1 - Daniel Stilck França A1 - James D. Watson AB -

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

UR - https://arxiv.org/abs/2301.12946 ER - TY - JOUR T1 - Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model Y1 - 2023 A1 - Kelsey A. Jackson A1 - Carl Miller A1 - Daochen Wang AB -

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

UR - https://arxiv.org/abs/2312.16619 ER - TY - JOUR T1 - Ever more optimized simulations of fermionic systems on a quantum computer Y1 - 2023 A1 - Qingfeng Wang A1 - Ze-Pei Cian A1 - Ming Li A1 - Igor L. Markov A1 - Yunseong Nam AB -

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

UR - https://arxiv.org/abs/2303.03460 ER - TY - CONF T1 - Fixing and Mechanizing the Security Proof of Fiat-Shamir with Aborts and Dilithium T2 - Advances in Cryptology – CRYPTO 2023 Y1 - 2023 A1 - Barbosa, Manuel A1 - Barthe, Gilles A1 - Doczkal, Christian A1 - Don, Jelle A1 - Fehr, Serge A1 - Grégoire, Benjamin A1 - Huang, Yu-Hsuan A1 - Hülsing, Andreas A1 - Lee, Yi A1 - Wu, Xiaodi ED - Handschuh, Helena ED - Lysyanskaya, Anna AB -

We extend and consolidate the security justification for the Dilithium signature scheme. In particular, we identify a subtle but crucial gap that appears in several ROM and QROM security proofs for signature schemes that are based on the Fiat-Shamir with aborts paradigm, including Dilithium. The gap lies in the CMA-to-NMA reduction and was uncovered when trying to formalize a variant of the QROM security proof by Kiltz, Lyubashevsky, and Schaffner (Eurocrypt 2018). The gap was confirmed by the authors, and there seems to be no simple patch for it. We provide new, fixed proofs for the affected CMA-to-NMA reduction, both for the ROM and the QROM, and we perform a concrete security analysis for the case of Dilithium to show that the claimed security level is still valid after addressing the gap. Furthermore, we offer a fully mechanized ROM proof for the CMA-security of Dilithium in the EasyCrypt proof assistant. Our formalization includes several new tools and techniques of independent interest for future formal verification results.

JA - Advances in Cryptology – CRYPTO 2023 PB - Springer Nature Switzerland CY - Cham SN - 978-3-031-38554-4 ER - TY - JOUR T1 - High-Energy Collision of Quarks and Hadrons in the Schwinger Model: From Tensor Networks to Circuit QED Y1 - 2023 A1 - Ron Belyansky A1 - Seth Whitsitt A1 - Niklas Mueller A1 - Ali Fahimniya A1 - Elizabeth R. Bennewitz A1 - Zohreh Davoudi A1 - Alexey V. Gorshkov AB -

With the aim of studying nonperturbative out-of-equilibrium dynamics of high-energy particle collisions on quantum simulators, we investigate the scattering dynamics of lattice quantum electrodynamics in 1+1 dimensions. Working in the bosonized formulation of the model, we propose an analog circuit-QED implementation that is native to the platform, requires minimal ingredients and approximations, and enables practical schemes for particle wave-packet preparation and evolution. Furthermore, working in the thermodynamic limit, we use uniform-matrix-product-state tensor networks to construct multi-particle wave-packet states, evolve them in time, and detect outgoing particles post collision. This facilitates the numerical simulation of scattering experiments in both confined and deconfined regimes of the model at different energies, giving rise to rich phenomenology, including inelastic production of quark and meson states, meson disintegration, and dynamical string formation and breaking. We obtain elastic and inelastic scattering cross sections, together with time-resolved momentum and position distributions of the outgoing particles. This study highlights the role of classical and quantum simulation in enhancing our understanding of scattering processes in quantum field theories in real time.

UR - https://arxiv.org/abs/2307.02522 ER - TY - JOUR T1 - Lattice quantum chromodynamics at large isospin density: 6144 pions in a box Y1 - 2023 A1 - Ryan Abbott A1 - William Detmold A1 - Fernando Romero-López A1 - Zohreh Davoudi A1 - Marc Illa A1 - Assumpta Parreño A1 - Robert J. Perry A1 - Phiala E. Shanahan A1 - Michael L. Wagman AB -

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

UR - https://arxiv.org/abs/2307.15014 ER - TY - JOUR T1 - The maximum refractive index of an atomic crystal - from quantum optics to quantum chemistry Y1 - 2023 A1 - Francesco Andreoli A1 - Bennet Windt A1 - Stefano Grava A1 - Gian Marcello Andolina A1 - Michael J. Gullans A1 - Alexander A. High A1 - Darrick E. Chang AB -

All known optical materials have an index of refraction of order unity. Despite the tremendous implications that an ultrahigh index could have for optical technologies, little research has been done on why the refractive index of materials is universally small, and whether this observation is fundamental. Here, we investigate the index of an ordered arrangement of atoms, as a function of atomic density. At dilute densities, this problem falls into the realm of quantum optics, where atoms do not interact with one another except via the scattering of light. On the other hand, when the lattice constant becomes comparable to the Bohr radius, the electronic orbitals begin to overlap, giving rise to quantum chemistry. We present a minimal model that allows for a unifying theory of index spanning these two regimes. A key aspect is the treatment of multiple light scattering, which can be highly non-perturbative over a large density range, and which is the reason that conventional theories of the index break down. In the quantum optics regime, we show that ideal light-matter interactions can have a single-mode nature, allowing for a purely real refractive index that grows with density as (N/V)1/3. At the onset of quantum chemistry, we show how two physical mechanisms (excited electron tunneling dynamics and the buildup of electronic density-density correlations) can open up inelastic or spatial multi-mode light scattering processes, which ultimately reduce the index back to order unity while introducing absorption. Around the onset of chemistry, our theory predicts that ultrahigh index (n∼30), low-loss materials could in principle be allowed by the laws of nature. 

UR - https://arxiv.org/abs/2303.10998 ER - TY - JOUR T1 - Microwave signal processing using an analog quantum reservoir computer Y1 - 2023 A1 - Alen Senanian A1 - Sridhar Prabhu A1 - Vladimir Kremenetski A1 - Saswata Roy A1 - Yingkang Cao A1 - Jeremy Kline A1 - Tatsuhiro Onodera A1 - Logan G. Wright A1 - Xiaodi Wu A1 - Valla Fatemi A1 - Peter L. McMahon AB -

Quantum reservoir computing (QRC) has been proposed as a paradigm for performing machine learning with quantum processors where the training is efficient in the number of required runs of the quantum processor and takes place in the classical domain, avoiding the issue of barren plateaus in parameterized-circuit quantum neural networks. It is natural to consider using a quantum processor based on superconducting circuits to classify microwave signals that are analog -- continuous in time. However, while theoretical proposals of analog QRC exist, to date QRC has been implemented using circuit-model quantum systems -- imposing a discretization of the incoming signal in time, with each time point input by executing a gate operation. In this paper we show how a quantum superconducting circuit comprising an oscillator coupled to a qubit can be used as an analog quantum reservoir for a variety of classification tasks, achieving high accuracy on all of them. Our quantum system was operated without artificially discretizing the input data, directly taking in microwave signals. Our work does not attempt to address the question of whether QRCs could provide a quantum computational advantage in classifying pre-recorded classical signals. However, beyond illustrating that sophisticated tasks can be performed with a modest-size quantum system and inexpensive training, our work opens up the possibility of achieving a different kind of advantage than a purely computational advantage: superconducting circuits can act as extremely sensitive detectors of microwave photons; our work demonstrates processing of ultra-low-power microwave signals in our superconducting circuit, and by combining sensitive detection with QRC processing within the same system, one could achieve a quantum sensing-computational advantage, i.e., an advantage in the overall analysis of microwave signals comprising just a few photons.

UR - https://arxiv.org/abs/2312.16166 ER - TY - JOUR T1 - Parallel self-testing of EPR pairs under computational assumptions Y1 - 2023 A1 - Honghao Fu A1 - Daochen Wang A1 - Qi Zhao AB -

Self-testing is a fundamental feature of quantum mechanics that allows a classical verifier to force untrusted quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Quantum, 2021] showed that a single EPR pair of a single quantum device can be self-tested under computational assumptions. In this work, we generalize their results to give the first parallel self-test of N EPR pairs and measurements on them in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ϵ must be poly(N,ϵ)-close to being honest in the appropriate sense. In particular, our protocol can test any distribution over tensor products of computational or Hadamard basis measurements, making it suitable for applications such as device-independent quantum key distribution under computational assumptions. Moreover, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a single cloud quantum computer using only classical communication.

UR - https://arxiv.org/abs/2201.13430 ER - TY - JOUR T1 - Parallel self-testing of EPR pairs under computational assumptions Y1 - 2023 A1 - Honghao Fu A1 - Daochen Wang A1 - Qi Zhao AB -

Self-testing is a fundamental feature of quantum mechanics that allows a classical verifier to force untrusted quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Quantum, 2021] showed that a single EPR pair of a single quantum device can be self-tested under computational assumptions. In this work, we generalize their results to give the first parallel self-test of N EPR pairs and measurements on them in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ϵ must be poly(N,ϵ)-close to being honest in the appropriate sense. In particular, our protocol can test any distribution over tensor products of computational or Hadamard basis measurements, making it suitable for applications such as device-independent quantum key distribution under computational assumptions. Moreover, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a single cloud quantum computer using only classical communication.

UR - https://arxiv.org/abs/2201.13430 ER - TY - JOUR T1 - Provably Efficient Learning of Phases of Matter via Dissipative Evolutions Y1 - 2023 A1 - Emilio Onorati A1 - Cambyse Rouzé A1 - Daniel Stilck França A1 - James D. Watson AB -

The combination of quantum many-body and machine learning techniques has recently proved to be a fertile ground for new developments in quantum computing. Several works have shown that it is possible to classically efficiently predict the expectation values of local observables on all states within a phase of matter using a machine learning algorithm after learning from data obtained from other states in the same phase. However, existing results are restricted to phases of matter such as ground states of gapped Hamiltonians and Gibbs states that exhibit exponential decay of correlations. In this work, we drop this requirement and show how it is possible to learn local expectation values for all states in a phase, where we adopt the Lindbladian phase definition by Coser \& Pérez-García [Coser \& Pérez-García, Quantum 3, 174 (2019)], which defines states to be in the same phase if we can drive one to other rapidly with a local Lindbladian. This definition encompasses the better-known Hamiltonian definition of phase of matter for gapped ground state phases, and further applies to any family of states connected by short unitary circuits, as well as non-equilibrium phases of matter, and those stable under external dissipative interactions. Under this definition, we show that N=O(log(n/δ)2polylog(1/ϵ)) samples suffice to learn local expectation values within a phase for a system with n qubits, to error ϵ with failure probability δ. This sample complexity is comparable to previous results on learning gapped and thermal phases, and it encompasses previous results of this nature in a unified way. Furthermore, we also show that we can learn families of states which go beyond the Lindbladian definition of phase, and we derive bounds on the sample complexity which are dependent on the mixing time between states under a Lindbladian evolution.

UR - arXiv:2311.07506 Search... ER - TY - JOUR T1 - Qafny: Quantum Program Verification Through Type-guided Classical Separation Logic Y1 - 2023 A1 - Liyi Li A1 - Mingwei Zhu A1 - Rance Cleaveland A1 - Yi Lee A1 - Le Chang A1 - Xiaodi Wu AB -

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.

UR - https://arxiv.org/abs/2211.06411 ER - TY - JOUR T1 - Quantum algorithm for estimating volumes of convex bodies JF - ACM Transactions on Quantum Computing Y1 - 2023 A1 - Shouvanik Chakrabarti A1 - Andrew M. Childs A1 - Shih-Han Hung A1 - Tongyang Li A1 - Chunhao Wang A1 - Xiaodi Wu AB -

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.

VL - 4 UR - https://arxiv.org/abs/1908.03903 ER - TY - JOUR T1 - Quantum Algorithms for Simulating Nuclear Effective Field Theories Y1 - 2023 A1 - James D. Watson A1 - Jacob Bringewatt A1 - Alexander F. Shaw A1 - Andrew M. Childs A1 - Alexey V. Gorshkov A1 - Zohreh Davoudi AB -

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.

UR - https://arxiv.org/abs/2312.05344 ER - TY - JOUR T1 - A quantum central path algorithm for linear optimization Y1 - 2023 A1 - Brandon Augustino A1 - Jiaqi Leng A1 - Giacomo Nannicini A1 - Tamás Terlaky A1 - Xiaodi Wu AB -

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.

UR - https://arxiv.org/abs/2311.03977 ER - TY - JOUR T1 - Quantum Hamiltonian Descent Y1 - 2023 A1 - Jiaqi Leng A1 - Ethan Hickman A1 - Joseph Li A1 - Xiaodi Wu AB -

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.

UR - https://arxiv.org/abs/2303.01471 ER - TY - JOUR T1 - Quantum Lego Expansion Pack: Enumerators from Tensor Networks Y1 - 2023 A1 - ChunJun Cao A1 - Michael J. Gullans A1 - Brad Lackey A1 - Zitao Wang AB -

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.

UR - https://arxiv.org/abs/2308.05152 ER - TY - JOUR T1 - Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions Y1 - 2023 A1 - Yuri Alexeev A1 - Maximilian Amsler A1 - Paul Baity A1 - Marco Antonio Barroca A1 - Sanzio Bassini A1 - Torey Battelle A1 - Daan Camps A1 - David Casanova A1 - Young jai Choi A1 - Frederic T. Chong A1 - Charles Chung A1 - Chris Codella A1 - Antonio D. Corcoles A1 - James Cruise A1 - Alberto Di Meglio A1 - Jonathan Dubois A1 - Ivan Duran A1 - Thomas Eckl A1 - Sophia Economou A1 - Stephan Eidenbenz A1 - Bruce Elmegreen A1 - Clyde Fare A1 - Ismael Faro A1 - Cristina Sanz Fernández A1 - Rodrigo Neumann Barros Ferreira A1 - Keisuke Fuji A1 - Bryce Fuller A1 - Laura Gagliardi A1 - Giulia Galli A1 - Jennifer R. Glick A1 - Isacco Gobbi A1 - Pranav Gokhale A1 - Salvador de la Puente Gonzalez A1 - Johannes Greiner A1 - Bill Gropp A1 - Michele Grossi A1 - Emmanuel Gull A1 - Burns Healy A1 - Benchen Huang A1 - Travis S. Humble A1 - Nobuyasu Ito A1 - Artur F. Izmaylov A1 - Ali Javadi-Abhari A1 - Douglas Jennewein A1 - Shantenu Jha A1 - Liang Jiang A1 - Barbara Jones A1 - Wibe Albert de Jong A1 - Petar Jurcevic A1 - William Kirby A1 - Stefan Kister A1 - Masahiro Kitagawa A1 - Joel Klassen A1 - Katherine Klymko A1 - Kwangwon Koh A1 - Masaaki Kondo A1 - Doga Murat Kurkcuoglu A1 - Krzysztof Kurowski A1 - Teodoro Laino A1 - Ryan Landfield A1 - Matt Leininger A1 - Vicente Leyton-Ortega A1 - Ang Li A1 - Meifeng Lin A1 - Junyu Liu A1 - Nicolas Lorente A1 - Andre Luckow A1 - Simon Martiel A1 - Francisco Martin-Fernandez A1 - Margaret Martonosi A1 - Claire Marvinney A1 - Arcesio Castaneda Medina A1 - Dirk Merten A1 - Antonio Mezzacapo A1 - Kristel Michielsen A1 - Abhishek Mitra A1 - Tushar Mittal A1 - Kyungsun Moon A1 - Joel Moore A1 - Mario Motta A1 - Young-Hye Na A1 - Yunseong Nam A1 - Prineha Narang A1 - Yu-ya Ohnishi A1 - Daniele Ottaviani A1 - Matthew Otten A1 - Scott Pakin A1 - Vincent R. Pascuzzi A1 - Ed Penault A1 - Tomasz Piontek A1 - Jed Pitera A1 - Patrick Rall A1 - Gokul Subramanian Ravi A1 - Niall Robertson A1 - Matteo Rossi A1 - Piotr Rydlichowski A1 - Hoon Ryu A1 - Georgy Samsonidze A1 - Mitsuhisa Sato A1 - Nishant Saurabh A1 - Vidushi Sharma A1 - Kunal Sharma A1 - Soyoung Shin A1 - George Slessman A1 - Mathias Steiner A1 - Iskandar Sitdikov A1 - In-Saeng Suh A1 - Eric Switzer A1 - Wei Tang A1 - Joel Thompson A1 - Synge Todo A1 - Minh Tran A1 - Dimitar Trenev A1 - Christian Trott A1 - Huan-Hsin Tseng A1 - Esin Tureci A1 - David García Valinas A1 - Sofia Vallecorsa A1 - Christopher Wever A1 - Konrad Wojciechowski A1 - Xiaodi Wu A1 - Shinjae Yoo A1 - Nobuyuki Yoshioka A1 - Victor Wen-zhe Yu A1 - Seiji Yunoki A1 - Sergiy Zhuk A1 - Dmitry Zubarev AB -

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.

UR - https://arxiv.org/abs/2312.09733 ER - TY - JOUR T1 - A quantum-classical performance separation in nonconvex optimization Y1 - 2023 A1 - Jiaqi Leng A1 - Yufan Zheng A1 - Xiaodi Wu AB -

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.

UR - https://arxiv.org/abs/2311.00811 ER - TY - JOUR T1 - Qubit-Oscillator Concatenated Codes: Decoding Formalism and Code Comparison JF - PRX Quantum Y1 - 2023 A1 - Xu, Yijia A1 - Wang, Yixu A1 - Kuo, En-Jui A1 - Victor V. Albert AB -

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.

VL - 4 U4 - 020342 UR - https://arxiv.org/abs/2209.04573 U5 - 10.1103/PRXQuantum.4.020342 ER - TY - JOUR T1 - On the Rational Degree of Boolean Functions and Applications Y1 - 2023 A1 - Vishnu Iyer A1 - Siddhartha Jain A1 - Matt Kovacs-Deak A1 - Vinayak M. Kumar A1 - Luke Schaeffer A1 - Daochen Wang A1 - Michael Whitmeyer AB -

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

UR - arXiv:2310.08004 ER - TY - JOUR T1 - A sharp phase transition in linear cross-entropy benchmarking Y1 - 2023 A1 - Brayden Ware A1 - Abhinav Deshpande A1 - Dominik Hangleiter A1 - Pradeep Niroula A1 - Bill Fefferman A1 - Alexey V. Gorshkov A1 - Michael J. Gullans AB -

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

UR - https://arxiv.org/abs/2305.04954 ER - TY - JOUR T1 - SimuQ: A Domain-Specific Language For Quantum Simulation With Analog Compilation Y1 - 2023 A1 - Yuxiang Peng A1 - Jacob Young A1 - Pengyu Liu A1 - Xiaodi Wu AB -

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

UR - https://arxiv.org/abs/2303.02775 ER - TY - JOUR T1 - Spin-selective strong light-matter coupling in a 2D hole gas-microcavity system Y1 - 2023 A1 - Daniel G. Suarez-Forero A1 - Deric Weston Session A1 - Mahmoud Jalali Mehrabad A1 - Patrick Knuppel A1 - Stefan Faelt A1 - Werner Wegscheider A1 - Mohammad Hafezi AB -

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

UR - https://arxiv.org/abs/2302.06023 ER - TY - JOUR T1 - A theory of quantum differential equation solvers: limitations and fast-forwarding Y1 - 2023 A1 - Dong An A1 - Jin-Peng Liu A1 - Daochen Wang A1 - Qi Zhao AB -

We study the limitations and fast-forwarding of quantum algorithms for linear ordinary differential equation (ODE) systems with a particular focus on non-quantum dynamics, where the coefficient matrix in the ODE is not anti-Hermitian or the ODE is inhomogeneous. On the one hand, for generic homogeneous linear ODEs, by proving worst-case lower bounds, we show that quantum algorithms suffer from computational overheads due to two types of ``non-quantumness'': real part gap and non-normality of the coefficient matrix. We then show that homogeneous ODEs in the absence of both types of ``non-quantumness'' are equivalent to quantum dynamics, and reach the conclusion that quantum algorithms for quantum dynamics work best. We generalize our results to the inhomogeneous case and find that existing generic quantum ODE solvers cannot be substantially improved. To obtain these lower bounds, we propose a general framework for proving lower bounds on quantum algorithms that are amplifiers, meaning that they amplify the difference between a pair of input quantum states. On the other hand, we show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved efficiency. More specifically, we obtain quadratic improvements in the evolution time T for inhomogeneous ODEs with a negative semi-definite coefficient matrix, and exponential improvements in both T and the spectral norm of the coefficient matrix for inhomogeneous ODEs with efficiently implementable eigensystems, including various spatially discretized linear evolutionary partial differential equations. We give fast-forwarding algorithms that are conceptually different from existing ones in the sense that they neither require time discretization nor solving high-dimensional linear systems.

UR - https://arxiv.org/abs/2211.05246 ER - TY - JOUR T1 - Time-energy uncertainty relation for noisy quantum metrology JF - PRX Quantum Y1 - 2023 A1 - Faist, Philippe A1 - Woods, Mischa P. A1 - Victor V. Albert A1 - Renes, Joseph M. A1 - Eisert, Jens A1 - Preskill, John KW - FOS: Physical sciences KW - Quantum Physics (quant-ph) AB -

Detection of weak forces and precise measurement of time are two of the many applications of quantum metrology to science and technology. We consider a quantum system initialized in a pure state and whose evolution is goverened by a Hamiltonian H; a measurement can later estimate the time t for which the system has evolved. In this work, we introduce and study a fundamental trade-off which relates the amount by which noise reduces the accuracy of a quantum clock to the amount of information about the energy of the clock that leaks to the environment. Specifically, we consider an idealized scenario in which Alice prepares an initial pure state of the clock, allows the clock to evolve for a time t that is not precisely known, and then transmits the clock through a noisy channel to Bob. The environment (Eve) receives any information that is lost. We prove that Bob's loss of quantum Fisher information (QFI) about t is equal to Eve's gain of QFI about a complementary energy parameter. We also prove a more general trade-off that applies when Bob and Eve wish to estimate the values of parameters associated with two non-commuting observables. We derive the necessary and sufficient conditions for the accuracy of the clock to be unaffected by the noise. These are a subset of the Knill-Laflamme error-correction conditions; states satisfying these conditions are said to form a metrological code. We provide a scheme to construct metrological codes in the stabilizer formalism. We show that there are metrological codes that cannot be written as a quantum error-correcting code with similar distance in which the Hamiltonian acts as a logical operator, potentially offering new schemes for constructing states that do not lose any sensitivity upon application of a noisy channel. We discuss applications of our results to sensing using a many-body state subject to erasure or amplitude-damping noise.

VL - 4(4) UR - https://arxiv.org/abs/2207.13707 CP - 040336 U5 - https://journals.aps.org/prxquantum/pdf/10.1103/PRXQuantum.4.040336 ER - TY - JOUR T1 - A Watermark for Large Language Models Y1 - 2023 A1 - John Kirchenbauer A1 - Jonas Geiping A1 - Yuxin Wen A1 - Jonathan Katz A1 - Ian Miers A1 - Tom Goldstein AB -

Potential harms of large language models can be mitigated by watermarking model output, i.e., embedding signals into generated text that are invisible to humans but algorithmically detectable from a short span of tokens. We propose a watermarking framework for proprietary language models. The watermark can be embedded with negligible impact on text quality, and can be detected using an efficient open-source algorithm without access to the language model API or parameters. The watermark works by selecting a randomized set of "green" tokens before a word is generated, and then softly promoting use of green tokens during sampling. We propose a statistical test for detecting the watermark with interpretable p-values, and derive an information-theoretic framework for analyzing the sensitivity of the watermark. We test the watermark using a multi-billion parameter model from the Open Pretrained Transformer (OPT) family, and discuss robustness and security.

UR - https://arxiv.org/abs/2301.10226 ER - TY - JOUR T1 - Approximating the two-mode two-photon Rabi model JF - Physics Letters A Y1 - 2022 A1 - David H. Wu A1 - Victor V. Albert AB -

The Rabi model describes the simplest nontrivial interaction between a few-level system and a bosonic mode, featuring in multiple seemingly unrelated systems of importance to quantum science and technology. While exact expressions for the energies of this model and its few-mode extensions have been obtained, they involve roots of transcendental functions and are thus cumbersome and unintuitive. Utilizing the symmetric generalized rotating wave approximation (S-GRWA), we develop a family of approximations to the energies of the two-mode two-photon Rabi model. The simplest elements of the family are analytically tractable, providing good approximations in regimes of interest such as ultra- and deep-strong coupling. Higher-order approximate energies can be used if more accuracy is required. 

VL - 422 UR - https://arxiv.org/abs/2012.06994 U5 - https://doi.org/10.1016/j.physleta.2021.127779 ER - TY - JOUR T1 - Bosonic Qiskit Y1 - 2022 A1 - Stavenger, Timothy J A1 - Crane, Eleanor A1 - Smith, Kevin A1 - Kang, Christopher T A1 - Girvin, Steven M A1 - Wiebe, Nathan KW - Emerging Technologies (cs.ET) KW - FOS: Computer and information sciences KW - FOS: Physical sciences KW - Quantum Physics (quant-ph) AB -

The practical benefits of hybrid quantum information processing hardware that contains continuous-variable objects (bosonic modes such as mechanical or electromagnetic oscillators) in addition to traditional (discrete-variable) qubits have recently been demonstrated by experiments with bosonic codes that reach the break-even point for quantum error correction and by efficient Gaussian boson sampling simulation of the Franck-Condon spectra of triatomic molecules that is well beyond the capabilities of current qubit-only hardware. The goal of this Co-design Center for Quantum Advantage (C2QA) project is to develop an instruction set architecture (ISA) for hybrid qubit/bosonic mode systems that contains an inventory of the fundamental operations and measurements that are possible in such hardware. The corresponding abstract machine model (AMM) would also contain a description of the appropriate error models associated with the gates, measurements and time evolution of the hardware. This information has been implemented as an extension of Qiskit. Qiskit is an opensource software development toolkit (SDK) for simulating the quantum state of a quantum circuit on a system with Python 3.7+ and for running the same circuits on prototype hardware within the IBM Quantum Lab. We introduce the Bosonic Qiskit software to enable the simulation of hybrid qubit/bosonic systems using the existing Qiskit software development kit. This implementation can be used for simulating new hybrid systems, verifying proposed physical systems, and modeling systems larger than can currently be constructed. We also cover tutorials and example use cases included within the software to study Jaynes- Cummings models, bosonic Hubbard models, plotting Wigner functions and animations, and calculating maximum likelihood estimations using Wigner functions.

UR - https://arxiv.org/abs/2209.11153 U5 - 10.48550/ARXIV.2209.11153 ER - TY - JOUR T1 - Closing the Locality and Detection Loopholes in Multiparticle Entanglement Self-Testing JF - Physical Review Letters Y1 - 2022 A1 - Dian Wu A1 - Qi Zhao A1 - Can Wang A1 - Liang Huang A1 - Yang-Fan Jiang A1 - Bing Bai A1 - You Zhou A1 - Xue-Mei Gu A1 - Feng-Ming Liu A1 - Ying-Qiu Mao A1 - Qi-Chao Sun A1 - Ming-Cheng Chen A1 - Jun Zhang A1 - Cheng-Zhi Peng A1 - Xiao-Bo Zhu A1 - Qiang Zhang A1 - Chao-Yang Lu A1 - Jian-Wei Pan AB -

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

VL - 128 U4 - 250401 UR - https://www.researchgate.net/profile/Dian-Wu/publication/361497881_Closing_the_Locality_and_Detection_Loopholes_in_Multiparticle_Entanglement_Self-Testing/links/62b55a8c1010dc02cc57530c/Closing-the-Locality-and-Detection-Loopholes-in-Multiparticle-Entangl CP - 25 U5 - https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.128.250401 ER - TY - JOUR T1 - Computational self-testing of multi-qubit states and measurements Y1 - 2022 A1 - Fu, Honghao A1 - Daochen Wang A1 - Zhao, Qi KW - FOS: Physical sciences KW - Quantum Physics (quant-ph) AB -

Self-testing is a fundamental technique within quantum information theory that allows a classical verifier to force (untrusted) quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Quantum, 2021] showed that a single EPR pair of a single quantum device can be self-tested under standard computational assumptions. In this work, we generalize their techniques to give the first protocol that self-tests N EPR pairs and measurements in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ϵ must be poly(N,ϵ)-close to being honest in the appropriate sense. In particular, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a cloud quantum computer, on which we cannot enforce spatial separation, using only classical communication.

UR - https://arxiv.org/abs/2201.13430 U5 - 10.48550/ARXIV.2201.13430 ER - TY - JOUR T1 - A Convergence Theory for Over-parameterized Variational Quantum Eigensolvers Y1 - 2022 A1 - Xuchen You A1 - Shouvanik Chakrabarti A1 - Xiaodi Wu AB -

The Variational Quantum Eigensolver (VQE) is a promising candidate for quantum applications on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. Despite a lot of empirical studies and recent progress in theoretical understanding of VQE's optimization landscape, the convergence for optimizing VQE is far less understood. We provide the first rigorous analysis of the convergence of VQEs in the over-parameterization regime. By connecting the training dynamics with the Riemannian Gradient Flow on the unit-sphere, we establish a threshold on the sufficient number of parameters for efficient convergence, which depends polynomially on the system dimension and the spectral ratio, a property of the problem Hamiltonian, and could be resilient to gradient noise to some extent. We further illustrate that this overparameterization threshold could be vastly reduced for specific VQE instances by establishing an ansatz-dependent threshold paralleling our main result. We showcase that our ansatz-dependent threshold could serve as a proxy of the trainability of different VQE ansatzes without performing empirical experiments, which hence leads to a principled way of evaluating ansatz design. Finally, we conclude with a comprehensive empirical study that supports our theoretical findings

UR - https://arxiv.org/abs/2205.12481 ER - TY - JOUR T1 - Differentiable Quantum Programming with Unbounded Loops Y1 - 2022 A1 - Fang, Wang A1 - Ying, Mingsheng A1 - Wu, Xiaodi KW - FOS: Computer and information sciences KW - FOS: Physical sciences KW - Machine Learning (cs.LG) KW - Programming Languages (cs.PL) KW - Quantum Physics (quant-ph) AB -

The emergence of variational quantum applications has led to the development of automatic differentiation techniques in quantum computing. Recently, Zhu et al. (PLDI 2020) have formulated differentiable quantum programming with bounded loops, providing a framework for scalable gradient calculation by quantum means for training quantum variational applications. However, promising parameterized quantum applications, e.g., quantum walk and unitary implementation, cannot be trained in the existing framework due to the natural involvement of unbounded loops. To fill in the gap, we provide the first differentiable quantum programming framework with unbounded loops, including a newly designed differentiation rule, code transformation, and their correctness proof. Technically, we introduce a randomized estimator for derivatives to deal with the infinite sum in the differentiation of unbounded loops, whose applicability in classical and probabilistic programming is also discussed. We implement our framework with Python and Q#, and demonstrate a reasonable sample efficiency. Through extensive case studies, we showcase an exciting application of our framework in automatically identifying close-to-optimal parameters for several parameterized quantum applications.

UR - https://arxiv.org/abs/2211.04507 U5 - 10.48550/ARXIV.2211.04507 ER - TY - JOUR T1 - Efficient and practical quantum compiler towards multi-qubit systems with deep reinforcement learning Y1 - 2022 A1 - Chen, Qiuhao A1 - Du, Yuxuan A1 - Zhao, Qi A1 - Jiao, Yuling A1 - Lu, Xiliang A1 - Wu, Xingyao KW - FOS: Computer and information sciences KW - FOS: Physical sciences KW - Machine Learning (cs.LG) KW - Quantum Physics (quant-ph) AB -

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

UR - https://arxiv.org/abs/2204.06904 U5 - 10.48550/ARXIV.2204.06904 ER - TY - JOUR T1 - Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation Y1 - 2022 A1 - Dong An A1 - Di Fang A1 - Stephen Jordan A1 - Jin-Peng Liu A1 - Guang Hao Low A1 - Jiasu Wang AB -

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

UR - https://arxiv.org/abs/2205.01141 ER - TY - JOUR T1 - Experimental Implementation of an Efficient Test of Quantumness Y1 - 2022 A1 - Lewis, Laura A1 - Zhu, Daiwei A1 - Gheorghiu, Alexandru A1 - Noel, Crystal A1 - Katz, Or A1 - Harraz, Bahaa A1 - Wang, Qingfeng A1 - Risinger, Andrew A1 - Feng, Lei A1 - Biswas, Debopriyo A1 - Egan, Laird A1 - Vidick, Thomas A1 - Cetina, Marko A1 - Monroe, Christopher KW - FOS: Physical sciences KW - Other Condensed Matter (cond-mat.other) KW - Quantum Physics (quant-ph) AB -

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

UR - https://arxiv.org/abs/2209.14316 U5 - 10.48550/ARXIV.2209.14316 ER - TY - JOUR T1 - FIPS Compliant Quantum Secure Communication using Quantum Permutation Pad Y1 - 2022 A1 - He, Alex A1 - Lou, Dafu A1 - She, Eric A1 - Guo, Shangjie A1 - Watson, Hareesh A1 - Weng, Sibyl A1 - Perepechaenko, Maria A1 - Kuang, Rand KW - Cryptography and Security (cs.CR) KW - FOS: Computer and information sciences KW - FOS: Physical sciences KW - Quantum Physics (quant-ph) AB -

Quantum computing has entered fast development track since Shor's algorithm was proposed in 1994. Multi-cloud services of quantum computing farms are currently available. One of which, IBM quantum computing, presented a road map showing their Kookaburra system with over 4158 qubits will be available in 2025. For the standardization of Post-Quantum Cryptography or PQC, the National Institute of Standards and Technology or NIST recently announced the first candidates for standardization with one algorithm for key encapsulation mechanism (KEM), Kyber, and three algorithms for digital signatures. NIST has also issued a new call for quantum-safe digital signature algorithms due June 1, 2023. This timeline shows that FIPS-certified quantum-safe TLS protocol would take a predictably long time. However, "steal now, crack later" tactic requires protecting data against future quantum threat actors today. NIST recommended the use of a hybrid mode of TLS 1.3 with its extensions to support PQC. The hybrid mode works for certain cases but FIPS certification for the hybridized cryptomodule might still be required. This paper proposes to take a nested mode to enable TLS 1.3 protocol with quantum-safe data, which can be made available today and is FIPS compliant. We discussed the performance impacts of the handshaking phase of the nested TLS 1.3 with PQC and the symmetric encryption phase. The major impact on performance using the nested mode is in the data symmetric encryption with AES. To overcome this performance reduction, we suggest using quantum encryption with a quantum permutation pad for the data encryption with a minor performance reduction of less than 10 percent.

UR - https://arxiv.org/abs/2301.00062 U5 - 10.48550/ARXIV.2301.00062 ER - TY - JOUR T1 - Infinite-randomness criticality in monitored quantum dynamics with static disorder Y1 - 2022 A1 - Aidan Zabalo A1 - Justin H. Wilson A1 - Michael J. Gullans A1 - Romain Vasseur A1 - Sarang Gopalakrishnan A1 - David A. Huse A1 - J. H. Pixley AB -

We consider a model of monitored quantum dynamics with quenched spatial randomness: specifically, random quantum circuits with spatially varying measurement rates. These circuits undergo a measurement-induced phase transition (MIPT) in their entanglement structure, but the nature of the critical point differs drastically from the case with constant measurement rate. In particular, at the critical measurement rate, we find that the entanglement of a subsystem of size ℓ scales as S∼ℓ√; moreover, the dynamical critical exponent z=∞. The MIPT is flanked by Griffiths phases with continuously varying dynamical exponents. We argue for this infinite-randomness scenario on general grounds and present numerical evidence that it captures some features of the universal critical properties of MIPT using large-scale simulations of Clifford circuits. These findings demonstrate that the relevance and irrelevance of perturbations to the MIPT can naturally be interpreted using a powerful heuristic known as the Harris criterion. 

UR - https://arxiv.org/abs/2205.14002 ER - TY - JOUR T1 - Lattice-Based Quantum Advantage from Rotated Measurements Y1 - 2022 A1 - Yusuf Alnawakhtha A1 - Mantri, Atul A1 - Carl Miller A1 - Wang, Daochen KW - Cryptography and Security (cs.CR) KW - Emerging Technologies (cs.ET) KW - FOS: Computer and information sciences KW - FOS: Physical sciences KW - Quantum Physics (quant-ph) AB -

Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic interactions between a classical client and a quantum server. Typically, a protocol has the quantum server prepare a superposition of two-bit strings of a claw and then measure it using Pauli-X or Z measurements. In this paper, we demonstrate a new technique that uses the entire range of qubit measurements from the XY-plane. We show the advantage of this approach in two applications. First, building on (Brakerski et al. 2018, Kalai et al. 2022), we show an optimized two-round proof of quantumness whose security can be expressed directly in terms of the hardness of the LWE (learning with errors) problem. Second, we construct a one-round protocol for blind remote preparation of an arbitrary state on the XY-plane up to a Pauli-Z correction.

UR - https://arxiv.org/abs/2210.10143 U5 - 10.48550/ARXIV.2210.10143 ER - TY - JOUR T1 - Mana and thermalization: Probing the feasibility of near-Clifford Hamiltonian simulation JF - Physical Review B Y1 - 2022 A1 - Troy J. Sewell A1 - Christopher David White AB -

Quantum hydrodynamics is the emergent classical dynamics governing transport of conserved quantities in generic strongly-interacting quantum systems. Recent matrix product operator methods have made simulations of quantum hydrodynamics in 1+1d tractable, but they do not naturally generalize to 2+1d or higher, and they offer limited guidance as to the difficulty of simulations on quantum computers. Near-Clifford simulation algorithms are not limited to one dimension, and future error-corrected quantum computers will likely be bottlenecked by non-Clifford operations. We therefore investigate the non-Clifford resource requirements for simulation of quantum hydrodynamics using ``mana'', a resource theory of non-Clifford operations. For infinite-temperature starting states we find that the mana of subsystems quickly approaches zero, while for starting states with energy above some threshold the mana approaches a nonzero value. Surprisingly, in each case the finite-time mana is governed by the subsystem entropy, not the thermal state mana; we argue that this is because mana is a sensitive diagnostic of finite-time deviations from canonical typicality.

VL - 106 UR - https://arxiv.org/abs/2201.12367 U5 - 10.1103/physrevb.106.125130 ER - TY - JOUR T1 - Operator Scaling Dimensions and Multifractality at Measurement-Induced Transitions JF - Physical Review Letters Y1 - 2022 A1 - Aidan Zabalo A1 - Michael Gullans A1 - Justin H. Wilson A1 - Romain Vasseur A1 - Andreas W. W. Ludwig A1 - Sarang Gopalakrishnan A1 - David A. Huse A1 - J. H. Pixley AB -

Repeated local measurements of quantum many body systems can induce a phase transition in their entanglement structure. These measurement-induced phase transitions (MIPTs) have been studied for various types of dynamics, yet most cases yield quantitatively similar values of the critical exponents, making it unclear if there is only one underlying universality class. Here, we directly probe the properties of the conformal field theories governing these MIPTs using a numerical transfer-matrix method, which allows us to extract the effective central charge, as well as the first few low-lying scaling dimensions of operators at these critical points. Our results provide convincing evidence that the generic and Clifford MIPTs for qubits lie in different universality classes and that both are distinct from the percolation transition for qudits in the limit of large onsite Hilbert space dimension. For the generic case, we find strong evidence of multifractal scaling of correlation functions at the critical point, reflected in a continuous spectrum of scaling dimensions.

VL - 128 UR - https://arxiv.org/abs/2107.03393 U5 - 10.1103/physrevlett.128.050602 ER - TY - JOUR T1 - Pauli Stabilizer Models of Twisted Quantum Doubles JF - PRX Quantum Y1 - 2022 A1 - Tyler D. Ellison A1 - Yu-An Chen A1 - Arpit Dua A1 - Wilbur Shirley A1 - Nathanan Tantivasadakarn A1 - Dominic J. Williamson AB -

We construct a Pauli stabilizer model for every two-dimensional Abelian topological order that admits a gapped boundary. Our primary example is a Pauli stabilizer model on four-dimensional qudits that belongs to the double semion (DS) phase of matter. The DS stabilizer Hamiltonian is constructed by condensing an emergent boson in a Z4 toric code, where the condensation is implemented by making certain two-body measurements. We rigorously verify the topological order of the DS stabilizer model by identifying an explicit finite-depth quantum circuit (with ancillary qubits) that maps its ground state subspace to that of a DS string-net model. We show that the construction of the DS stabilizer Hamiltonian generalizes to all twisted quantum doubles (TQDs) with Abelian anyons. This yields a Pauli stabilizer code on composite-dimensional qudits for each such TQD, implying that the classification of topological Pauli stabilizer codes extends well beyond stacks of toric codes - in fact, exhausting all Abelian anyon theories that admit a gapped boundary. We also demonstrate that symmetry-protected topological phases of matter characterized by type I and type II cocycles can be modeled by Pauli stabilizer Hamiltonians by gauging certain 1-form symmetries of the TQD stabilizer models.

VL - 3 UR - https://arxiv.org/abs/2112.11394 U5 - https://doi.org/10.1103%2Fprxquantum.3.010353 ER - TY - JOUR T1 - Pauli topological subsystem codes from Abelian anyon theories Y1 - 2022 A1 - Ellison, Tyler D. A1 - Chen, Yu-An A1 - Dua, Arpit A1 - Shirley, Wilbur A1 - Tantivasadakarn, Nathanan A1 - Williamson, Dominic J. KW - FOS: Physical sciences KW - Quantum Physics (quant-ph) KW - Strongly Correlated Electrons (cond-mat.str-el) AB -

We construct Pauli topological subsystem codes characterized by arbitrary two-dimensional Abelian anyon theories--this includes anyon theories with degenerate braiding relations and those without a gapped boundary to the vacuum. Our work both extends the classification of two-dimensional Pauli topological subsystem codes to systems of composite-dimensional qudits and establishes that the classification is at least as rich as that of Abelian anyon theories. We exemplify the construction with topological subsystem codes defined on four-dimensional qudits based on the Z(1)4 anyon theory with degenerate braiding relations and the chiral semion theory--both of which cannot be captured by topological stabilizer codes. The construction proceeds by "gauging out" certain anyon types of a topological stabilizer code. This amounts to defining a gauge group generated by the stabilizer group of the topological stabilizer code and a set of anyonic string operators for the anyon types that are gauged out. The resulting topological subsystem code is characterized by an anyon theory containing a proper subset of the anyons of the topological stabilizer code. We thereby show that every Abelian anyon theory is a subtheory of a stack of toric codes and a certain family of twisted quantum doubles that generalize the double semion anyon theory. We further prove a number of general statements about the logical operators of translation invariant topological subsystem codes and define their associated anyon theories in terms of higher-form symmetries.

UR - https://arxiv.org/abs/2211.03798 U5 - 10.48550/ARXIV.2211.03798 ER - TY - JOUR T1 - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants JF - Advances in Neural Information Processing Systems (NeurIPS 2022) Y1 - 2022 A1 - Andrew M. Childs A1 - Li, Tongyang A1 - Liu, Jin-Peng A1 - Wang, Chunhao A1 - Zhang, Ruizhe KW - FOS: Computer and information sciences KW - FOS: Mathematics KW - FOS: Physical sciences KW - Machine Learning (cs.LG) KW - Optimization and Control (math.OC) KW - Quantum Physics (quant-ph) VL - 35 UR - https://arxiv.org/abs/2210.06539 CP - 23205 U5 - 10.48550/ARXIV.2210.06539 ER - TY - JOUR T1 - Quantum Depth in the Random Oracle Model Y1 - 2022 A1 - Arora, Atul Singh A1 - Coladangelo, Andrea A1 - Coudron, Matthew A1 - Gheorghiu, Alexandru A1 - Singh, Uttam A1 - Waldner, Hendrik KW - Computational Complexity (cs.CC) KW - Cryptography and Security (cs.CR) KW - FOS: Computer and information sciences KW - FOS: Physical sciences KW - Quantum Physics (quant-ph) AB -

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].

UR - https://arxiv.org/abs/2210.06454 U5 - 10.48550/ARXIV.2210.06454 ER - TY - JOUR T1 - Quantum divide and conquer Y1 - 2022 A1 - Andrew M. Childs A1 - Kothari, Robin A1 - Kovacs-Deak, Matt A1 - Sundaram, Aarthi A1 - Wang, Daochen KW - Data Structures and Algorithms (cs.DS) KW - FOS: Computer and information sciences KW - FOS: Physical sciences KW - Quantum Physics (quant-ph) AB -

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.

UR - https://arxiv.org/abs/2210.06419 U5 - 10.48550/ARXIV.2210.06419 ER - TY - JOUR T1 - Quantum Many-Body Scars from Einstein-Podolsky-Rosen States in Bilayer Systems Y1 - 2022 A1 - Wildeboer, Julia A1 - Langlett, Christopher M. A1 - Yang, Zhi-Cheng A1 - Alexey V. Gorshkov A1 - Iadecola, Thomas A1 - Xu, Shenglong KW - FOS: Physical sciences KW - Strongly Correlated Electrons (cond-mat.str-el) AB -

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.

UR - https://arxiv.org/abs/2209.05527 U5 - 10.48550/ARXIV.2209.05527 ER - TY - JOUR T1 - Quantum Natural Proof: A New Perspective of Hybrid Quantum-Classical Program Verification Y1 - 2022 A1 - Li, Liyi A1 - Zhu, Mingwei A1 - Lee, Yi A1 - Chang, Le A1 - Wu, Xiaodi KW - FOS: Computer and information sciences KW - FOS: Physical sciences KW - Programming Languages (cs.PL) KW - Quantum Physics (quant-ph) AB -

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.

UR - https://arxiv.org/abs/2211.06411 U5 - 10.48550/ARXIV.2211.06411 ER - TY - JOUR T1 - Quantum Simulation for High Energy Physics Y1 - 2022 A1 - Bauer, Christian W. A1 - Davoudi, Zohreh A1 - Balantekin, A. Baha A1 - Bhattacharya, Tanmoy A1 - Carena, Marcela A1 - de Jong, Wibe A. A1 - Draper, Patrick A1 - El-Khadra, Aida A1 - Gemelke, Nate A1 - Hanada, Masanori A1 - Kharzeev, Dmitri A1 - Lamm, Henry A1 - Li, Ying-Ying A1 - Liu, Junyu A1 - Lukin, Mikhail A1 - Meurice, Yannick A1 - Monroe, Christopher A1 - Nachman, Benjamin A1 - Pagano, Guido A1 - Preskill, John A1 - Rinaldi, Enrico A1 - Roggero, Alessandro A1 - Santiago, David I. A1 - Savage, Martin J. A1 - Siddiqi, Irfan A1 - Siopsis, George A1 - Van Zanten, David A1 - Wiebe, Nathan A1 - Yamauchi, Yukari A1 - Yeter-Aydeniz, Kübra A1 - Zorzetti, Silvia KW - FOS: Physical sciences KW - High Energy Physics - Lattice (hep-lat) KW - High Energy Physics - Phenomenology (hep-ph) KW - High Energy Physics - Theory (hep-th) KW - Nuclear Theory (nucl-th) KW - Quantum Physics (quant-ph) AB -

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.

UR - https://arxiv.org/abs/2204.03381 U5 - 10.48550/ARXIV.2204.03381 ER - TY - JOUR T1 - Scalably learning quantum many-body Hamiltonians from dynamical data Y1 - 2022 A1 - Wilde, Frederik A1 - Kshetrimayum, Augustine A1 - Roth, Ingo A1 - Hangleiter, Dominik A1 - Sweke, Ryan A1 - Eisert, Jens KW - FOS: Computer and information sciences KW - FOS: Physical sciences KW - Machine Learning (cs.LG) KW - Quantum Gases (cond-mat.quant-gas) KW - Quantum Physics (quant-ph) KW - Strongly Correlated Electrons (cond-mat.str-el) AB -

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

UR - https://arxiv.org/abs/2209.14328 U5 - 10.48550/ARXIV.2209.14328 ER - TY - JOUR T1 - Self-Testing of a Single Quantum System: Theory and Experiment Y1 - 2022 A1 - Hu, Xiao-Min A1 - Xie, Yi A1 - Arora, Atul Singh A1 - Ai, Ming-Zhong A1 - Bharti, Kishor A1 - Zhang, Jie A1 - Wu, Wei A1 - Chen, Ping-Xing A1 - Cui, Jin-Ming A1 - Liu, Bi-Heng A1 - Huang, Yun-Feng A1 - Li, Chuan-Feng A1 - Guo, Guang-Can A1 - Roland, Jérémie A1 - Cabello, Adán A1 - Kwek, Leong-Chuan KW - Atomic Physics (physics.atom-ph) KW - FOS: Physical sciences KW - Quantum Physics (quant-ph) AB -

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

UR - https://arxiv.org/abs/2203.09003 U5 - https://doi.org/10.48550/arXiv.2203.09003 ER - TY - JOUR T1 - Spectral Form Factor of a Quantum Spin Glass Y1 - 2022 A1 - Winer, Michael A1 - Barney, Richard A1 - Christopher L. Baldwin A1 - Galitski, Victor A1 - Swingle, Brian KW - Disordered Systems and Neural Networks (cond-mat.dis-nn) KW - FOS: Physical sciences KW - High Energy Physics - Theory (hep-th) KW - Statistical Mechanics (cond-mat.stat-mech) KW - Strongly Correlated Electrons (cond-mat.str-el) AB -

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

UR - https://arxiv.org/abs/2203.12753 U5 - https://doi.org/10.48550/arXiv.2203.12753 ER - TY - JOUR T1 - Theoretical bounds on data requirements for the ray-based classification JF - SN Comput. Sci. Y1 - 2022 A1 - Brian J. Weber A1 - Sandesh S. Kalantre A1 - Thomas McJunkin A1 - J. M. Taylor A1 - Justyna P. Zwolak AB -

The problem of classifying high-dimensional shapes in real-world data grows in complexity as the dimension of the space increases. For the case of identifying convex shapes of different geometries, a new classification framework has recently been proposed in which the intersections of a set of one-dimensional representations, called rays, with the boundaries of the shape are used to identify the specific geometry. This ray-based classification (RBC) has been empirically verified using a synthetic dataset of two- and three-dimensional shapes [1] and, more recently, has also been validated experimentally [2]. Here, we establish a bound on the number of rays necessary for shape classification, defined by key angular metrics, for arbitrary convex shapes. For two dimensions, we derive a lower bound on the number of rays in terms of the shape's length, diameter, and exterior angles. For convex polytopes in R^N, we generalize this result to a similar bound given as a function of the dihedral angle and the geometrical parameters of polygonal faces. This result enables a different approach for estimating high-dimensional shapes using substantially fewer data elements than volumetric or surface-based approaches.

VL - 3 UR - https://arxiv.org/abs/2103.09577 CP - 57 U5 - https://doi.org/10.1007/s42979-021-00921-0 ER - TY - JOUR T1 - A theory of quantum differential equation solvers: limitations and fast-forwarding Y1 - 2022 A1 - An, Dong A1 - Liu, Jin-Peng A1 - Wang, Daochen A1 - Zhao, Qi KW - FOS: Mathematics KW - FOS: Physical sciences KW - Numerical Analysis (math.NA) KW - Quantum Physics (quant-ph) AB -

We study the limitations and fast-forwarding of quantum algorithms for solving linear ordinary differential equation (ODE) systems with particular focus on non-quantum dynamics, where the coefficient matrix in the ODE is not anti-Hermitian or the ODE is inhomogeneous. On the one hand, for generic homogeneous linear ODEs, by proving worst-case lower bounds, we show that quantum algorithms suffer from computational overheads due to two types of ``non-quantumness'': real part gap and non-normality of the coefficient matrix. We then show that ODEs in the absence of both types of ``non-quantumness'' are equivalent to quantum dynamics, and reach the conclusion that quantum algorithms for quantum dynamics work best. We generalize our results to the inhomogeneous case and find that existing generic quantum ODE solvers cannot be substantially improved. To obtain these lower bounds, we propose a general framework for proving lower bounds on quantum algorithms that are amplifiers, meaning that they amplify the difference between a pair of input quantum states. On the other hand, we show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved efficiency. More specifically, we obtain quadratic to exponential improvements in terms of the evolution time T and the spectral norm of the coefficient matrix for the following classes of ODEs: inhomogeneous ODEs with a negative definite coefficient matrix, inhomogeneous ODEs with a coefficient matrix having an eigenbasis that can be efficiently prepared on a quantum computer and eigenvalues that can be efficiently computed classically, and the spatially discretized inhomogeneous heat equation and advection-diffusion equation. We give fast-forwarding algorithms that are conceptually different from existing ones in the sense that they neither require time discretization nor solving high-dimensional linear systems.

UR - https://arxiv.org/abs/2211.05246 U5 - 10.48550/ARXIV.2211.05246 ER - TY - JOUR T1 - Three-dimensional quantum cellular automata from chiral semion surface topological order and beyond Y1 - 2022 A1 - Shirley, Wilbur A1 - Chen, Yu-An A1 - Dua, Arpit A1 - Ellison, Tyler D. A1 - Tantivasadakarn, Nathanan A1 - Williamson, Dominic J. KW - FOS: Physical sciences KW - Mathematical Physics (math-ph) KW - Quantum Physics (quant-ph) KW - Strongly Correlated Electrons (cond-mat.str-el) AB -

We construct a novel three-dimensional quantum cellular automaton (QCA) based on a system with short-range entangled bulk and chiral semion boundary topological order. We argue that either the QCA is nontrivial, i.e. not a finite-depth circuit of local quantum gates, or there exists a two-dimensional commuting projector Hamiltonian realizing the chiral semion topological order (characterized by U(1)2 Chern-Simons theory). Our QCA is obtained by first constructing the Walker-Wang Hamiltonian of a certain premodular tensor category of order four, then condensing the deconfined bulk boson at the level of lattice operators. We show that the resulting Hamiltonian hosts chiral semion surface topological order in the presence of a boundary and can be realized as a non-Pauli stabilizer code on qubits, from which the QCA is defined. The construction is then generalized to a class of QCAs defined by non-Pauli stabilizer codes on 2n-dimensional qudits that feature surface anyons described by U(1)2n Chern-Simons theory. Our results support the conjecture that the group of nontrivial three-dimensional QCAs is isomorphic to the Witt group of non-degenerate braided fusion categories.

UR - https://arxiv.org/abs/2202.05442 U5 - 10.48550/ARXIV.2202.05442 ER - TY - JOUR T1 - Ultrastrong light-matter interaction in a photonic crystal Y1 - 2022 A1 - Vrajitoarea, Andrei A1 - Belyansky, Ron A1 - Lundgren, Rex A1 - Whitsitt, Seth A1 - Alexey V. Gorshkov A1 - Houck, Andrew A. KW - FOS: Physical sciences KW - Quantum Gases (cond-mat.quant-gas) KW - Quantum Physics (quant-ph) AB -

Harnessing the interaction between light and matter at the quantum level has been a central theme in the fields of atomic physics and quantum optics, with applications from quantum computation to quantum metrology. Combining complex interactions with photonic synthetic materials provides an opportunity to investigate novel quantum phases and phenomena, establishing interesting connections to condensed matter physics. Here we explore many-body phenomena with a single artificial atom coupled to the many discrete modes of a photonic crystal. This experiment reaches the ultrastrong light-matter coupling regime using the circuit QED paradigm, by galvanically coupling a highly nonlinear fluxonium qubit to a tight-binding lattice of microwave resonators. In this regime, the transport of a single photon is strongly modified by the presence of multi-photon bound states, owing to interactions that break particle number conservation. Exploiting the effective photon-photon interactions mediated by the qubit, the driven system can be configured as a continuous reservoir of strongly-correlated photons, a resource of interest for quantum networks. This work opens exciting prospects for exploring nonlinear quantum optics at the single-photon level and stabilizing entangled many-body phases of light.

UR - https://arxiv.org/abs/2209.14972 U5 - 10.48550/ARXIV.2209.14972 ER - TY - JOUR T1 - Universal scattering with general dispersion relations JF - Phys. Rev. Research Y1 - 2022 A1 - Wang, Yidan A1 - Michael Gullans A1 - Na, Xuesen A1 - Whitsitt, Seth A1 - Alexey V. Gorshkov KW - FOS: Physical sciences KW - Mathematical Physics (math-ph) KW - Quantum Physics (quant-ph) AB -

Many synthetic quantum systems allow particles to have dispersion relations that are neither linear nor quadratic functions. Here, we explore single-particle scattering in general spatial dimension D≥1 when the density of states diverges at a specific energy. To illustrate the underlying principles in an experimentally relevant setting, we focus on waveguide quantum electrodynamics (QED) problems (i.e. D=1) with dispersion relation ϵ(k)=±|d|km, where m≥2 is an integer. For a large class of these problems for any positive integer m, we rigorously prove that when there are no bright zero-energy eigenstates, the S-matrix evaluated at an energy E→0 converges to a universal limit that is only dependent on m. We also give a generalization of a key index theorem in quantum scattering theory known as Levinson's theorem -- which relates the scattering phases to the number of bound states -- to waveguide QED scattering for these more general dispersion relations. We then extend these results to general integer dimensions D≥1, dispersion relations ϵ(k)=|k|a for a D-dimensional momentum vector k with any real positive a, and separable potential scattering.

VL - 4 UR - https://arxiv.org/abs/2103.09830 U5 - https://doi.org/10.1103/PhysRevResearch.4.023014 ER - TY - JOUR T1 - Universality in one-dimensional scattering with general dispersion relations JF - Phys. Rev. Res. Y1 - 2022 A1 - Yidan Wang A1 - Michael Gullans A1 - Xuesen Na A1 - Alexey V. Gorshkov AB -

Many synthetic quantum systems allow particles to have dispersion relations that are neither linear nor quadratic functions. Here, we explore single-particle scattering in one dimension when the dispersion relation is ϵ(k)=±|d|km, where m≥2 is an integer. We study impurity scattering problems in which a single-particle in a one-dimensional waveguide scatters off of an inhomogeneous, discrete set of sites locally coupled to the waveguide. For a large class of these problems, we rigorously prove that when there are no bright zero-energy eigenstates, the S-matrix evaluated at an energy E→0 converges to a universal limit that is only dependent on m. We also give a generalization of a key index theorem in quantum scattering theory known as Levinson's theorem -- which relates the scattering phases to the number of bound states -- to impurity scattering for these more general dispersion relations.

VL - 4 UR - https://arxiv.org/abs/2103.09830 U5 - https://doi.org/10.48550/arXiv.2103.09830 ER - TY - JOUR T1 - Algebraic Reasoning of Quantum Programs via Non-Idempotent Kleene Algebra Y1 - 2021 A1 - Yuxiang Peng A1 - Mingsheng Ying A1 - Xiaodi Wu AB -

We investigate the algebraic reasoning of quantum programs inspired by the success of classical program analysis based on Kleene algebra. One prominent example of such is the famous Kleene Algebra with Tests (KAT), which has furnished both theoretical insights and practical tools. The succinctness of algebraic reasoning would be especially desirable for scalable analysis of quantum programs, given the involvement of exponential-size matrices in most of the existing methods. A few key features of KAT including the idempotent law and the nice properties of classical tests, however, fail to hold in the context of quantum programs due to their unique quantum features, especially in branching. We propose the Non-idempotent Kleena Algebra (NKA) as a natural alternative and identify complete and sound semantic models for NKA as well as their appropriate quantum interpretations. In light of applications of KAT, we are able to demonstrate algebraic proofs in NKA of quantum compiler optimization and the normal form of quantum while-programs. Moreover, we extend NKA with Tests (i.e., NKAT), where tests model quantum predicates following the rules of effect algebra, and illustrate how to encode propositional quantum Hoare logic as NKAT theorems.

UR - https://arxiv.org/abs/2110.07018 U5 - https://doi.org/10.1145/3519939.3523713 ER - TY - JOUR T1 - Chiral transport of hot carriers in graphene in the quantum Hall regime Y1 - 2021 A1 - Bin Cao A1 - Tobias Grass A1 - Olivier Gazzano A1 - Kishan Ashokbhai Patel A1 - Jiuning Hu A1 - Markus Müller A1 - Tobias Huber A1 - Luca Anzi A1 - Kenji Watanabe A1 - Takashi Taniguchi A1 - David Newell A1 - Michael Gullans A1 - Roman Sordan A1 - Mohammad Hafezi A1 - Glenn Solomon AB -

Photocurrent (PC) measurements can reveal the relaxation dynamics of photo-excited hot carriers beyond the linear response of conventional transport experiments, a regime important for carrier multiplication. In graphene subject to a magnetic field, PC measurements are able to probe the existence of Landau levels with different edge chiralities which is exclusive to relativistic electron systems. Here, we report the accurate measurement of PC in graphene in the quantum Hall regime. Prominent PC oscillations as a function of gate voltage on samples' edges are observed. These oscillation amplitudes form an envelope which depends on the strength of the magnetic field, as does the PCs' power dependence and their saturation behavior. We explain these experimental observations through a model using optical Bloch equations, incorporating relaxations through acoustic-, optical- phonons and Coulomb interactions. The simulated PC agrees with our experimental results, leading to a unified understanding of the chiral PC in graphene at various magnetic field strengths, and providing hints for the occurrence of a sizable carrier multiplication. 

UR - https://arxiv.org/abs/2110.01079 ER - TY - JOUR T1 - Conformal field theories are magical JF - Physical Review B Y1 - 2021 A1 - Christopher David White A1 - ChunJun Cao A1 - Brian Swingle AB -

"Magic" is the degree to which a state cannot be approximated by Clifford gates. We study mana, a measure of magic, in the ground state of the Z3 Potts model, and argue that it is a broadly useful diagnostic for many-body physics. In particular we find that the q=3 ground state has large mana at the model's critical point, and that this mana resides in the system's correlations. We explain the form of the mana by a simple tensor-counting calculation based on a MERA representation of the state. Because mana is present at all length scales, we conclude that the conformal field theory describing the 3-state Potts model critical point is magical. These results control the difficulty of preparing the Potts ground state on an error-corrected quantum computer, and constrain tensor network models of AdS-CFT.

VL - 103 U4 - 075145 UR - https://arxiv.org/abs/2007.01303 CP - 7 U5 - https://journals.aps.org/prb/pdf/10.1103/PhysRevB.103.075145 ER - TY - JOUR T1 - Cross-Platform Comparison of Arbitrary Quantum Computations Y1 - 2021 A1 - Daiwei Zhu A1 - Ze-Pei Cian A1 - Crystal Noel A1 - Andrew Risinger A1 - Debopriyo Biswas A1 - Laird Egan A1 - Yingyue Zhu A1 - Alaina M. Green A1 - Cinthia Huerta Alderete A1 - Nhung H. Nguyen A1 - Qingfeng Wang A1 - Andrii Maksymov A1 - Yunseong Nam A1 - Marko Cetina A1 - Norbert M. Linke A1 - Mohammad Hafezi A1 - Christopher Monroe AB -

As we approach the era of quantum advantage, when quantum computers (QCs) can outperform any classical computer on particular tasks, there remains the difficult challenge of how to validate their performance. While algorithmic success can be easily verified in some instances such as number factoring or oracular algorithms, these approaches only provide pass/fail information for a single QC. On the other hand, a comparison between different QCs on the same arbitrary circuit provides a lower-bound for generic validation: a quantum computation is only as valid as the agreement between the results produced on different QCs. Such an approach is also at the heart of evaluating metrological standards such as disparate atomic clocks. In this paper, we report a cross-platform QC comparison using randomized and correlated measurements that results in a wealth of information on the QC systems. We execute several quantum circuits on widely different physical QC platforms and analyze the cross-platform fidelities.

UR - https://arxiv.org/abs/2107.11387 ER - TY - JOUR T1 - Decoding conformal field theories: from supervised to unsupervised learning Y1 - 2021 A1 - En-Jui Kuo A1 - Alireza Seif A1 - Rex Lundgren A1 - Seth Whitsitt A1 - Mohammad Hafezi AB -

We use machine learning to classify rational two-dimensional conformal field theories. We first use the energy spectra of these minimal models to train a supervised learning algorithm. We find that the machine is able to correctly predict the nature and the value of critical points of several strongly correlated spin models using only their energy spectra. This is in contrast to previous works that use machine learning to classify different phases of matter, but do not reveal the nature of the critical point between phases. Given that the ground-state entanglement Hamiltonian of certain topological phases of matter is also described by conformal field theories, we use supervised learning on Réyni entropies and find that the machine is able to identify which conformal field theory describes the entanglement Hamiltonian with only the lowest few Réyni entropies to a high degree of accuracy. Finally, using autoencoders, an unsupervised learning algorithm, we find a hidden variable that has a direct correlation with the central charge and discuss prospects for using machine learning to investigate other conformal field theories, including higher-dimensional ones. Our results highlight that machine learning can be used to find and characterize critical points and also hint at the intriguing possibility to use machine learning to learn about more complex conformal field theories.

UR - https://arxiv.org/abs/2106.13485 ER - TY - JOUR T1 - EasyPQC: Verifying Post-Quantum Cryptography JF - ACM CCS 2021 Y1 - 2021 A1 - Manuel Barbosa A1 - Gilles Barthe A1 - Xiong Fan A1 - Benjamin Grégoire A1 - Shih-Han Hung A1 - Jonathan Katz A1 - Pierre-Yves Strub A1 - Xiaodi Wu A1 - Li Zhou AB -

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

U5 - https://dx.doi.org/10.1145/3460120.3484567 ER - TY - JOUR T1 - Efficient quantum measurement of Pauli operators JF - Quantum Y1 - 2021 A1 - Ophelia Crawford A1 - Barnaby van Straaten A1 - Daochen Wang A1 - Thomas Parks A1 - Earl Campbell A1 - Stephen Brierley AB -

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

VL - 5 UR - https://arxiv.org/abs/1908.06942 U5 - https://doi.org/10.22331/q-2021-01-20-385 ER - TY - JOUR T1 - Estimating distinguishability measures on quantum computers Y1 - 2021 A1 - Rochisha Agarwal A1 - Soorya Rethinasamy A1 - Kunal Sharma A1 - Mark M. Wilde AB -

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

UR - https://arxiv.org/abs/2108.08406 ER - TY - CONF T1 - Expanding the VOQC Toolkit T2 - The Second International Workshop on Programming Languages for Quantum Computing (PLanQC 2021) Y1 - 2021 A1 - Kesha Hietala A1 - Liyi Li A1 - Akshaj Gaur A1 - Aaron Green A1 - Robert Rand A1 - Xiaodi Wu A1 - Michael Hicks AB -

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

JA - The Second International Workshop on Programming Languages for Quantum Computing (PLanQC 2021) UR - http://rand.cs.uchicago.edu/files/planqc_2021c.pdf ER - TY - JOUR T1 - Exponentially Many Local Minima in Quantum Neural Networks JF - Proceedings of the 38th International Conference on Machine Learning, PMLR Y1 - 2021 A1 - Xuchen You A1 - Xiaodi Wu AB -

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

VL - 139 U4 - 12144-12155 UR - https://arxiv.org/pdf/2110.02479.pdf ER - TY - JOUR T1 - Frustration-induced anomalous transport and strong photon decay in waveguide QED JF - Phys. Rev. Research Y1 - 2021 A1 - Ron Belyansky A1 - Seth Whitsitt A1 - Rex Lundgren A1 - Yidan Wang A1 - Andrei Vrajitoarea A1 - Andrew A. Houck A1 - Alexey V. Gorshkov AB -

We study the propagation of photons in a one-dimensional environment consisting of two non-interacting species of photons frustratingly coupled to a single spin-1/2. The ultrastrong frustrated coupling leads to an extreme mixing of the light and matter degrees of freedom, resulting in the disintegration of the spin and a breakdown of the "dressed-spin", or polaron, description. Using a combination of numerical and analytical methods, we show that the elastic response becomes increasingly weak at the effective spin frequency, showing instead an increasingly strong and broadband response at higher energies. We also show that the photons can decay into multiple photons of smaller energies. The total probability of these inelastic processes can be as large as the total elastic scattering rate, or half of the total scattering rate, which is as large as it can be. The frustrated spin induces strong anisotropic photon-photon interactions that are dominated by inter-species interactions. Our results are relevant to state-of-the-art circuit and cavity quantum electrodynamics experiments.

VL - 3 UR - https://arxiv.org/abs/2007.03690 CP - 032058 U5 - https://doi.org/10.1103/PhysRevResearch.3.L032058 ER - TY - JOUR T1 - Hyper-Invariant MERA: Approximate Holographic Error Correction Codes with Power-Law Correlations Y1 - 2021 A1 - ChunJun Cao A1 - Jason Pollack A1 - Yixu Wang AB -

We consider a class of holographic tensor networks that are efficiently contractible variational ansatze, manifestly (approximate) quantum error correction codes, and can support power-law correlation functions. In the case when the network consists of a single type of tensor that also acts as an erasure correction code, we show that it cannot be both locally contractible and sustain power-law correlation functions. Motivated by this no-go theorem, and the desirability of local contractibility for an efficient variational ansatz, we provide guidelines for constructing networks consisting of multiple types of tensors that can support power-law correlation. We also provide an explicit construction of one such network, which approximates the holographic HaPPY pentagon code in the limit where variational parameters are taken to be small.

UR - https://arxiv.org/abs/2103.08631 ER - TY - JOUR T1 - Interactive Protocols for Classically-Verifiable Quantum Advantage Y1 - 2021 A1 - Daiwei Zhu A1 - Gregory D. Kahanamoku-Meyer A1 - Laura Lewis A1 - Crystal Noel A1 - Or Katz A1 - Bahaa Harraz A1 - Qingfeng Wang A1 - Andrew Risinger A1 - Lei Feng A1 - Debopriyo Biswas A1 - Laird Egan A1 - Alexandru Gheorghiu A1 - Yunseong Nam A1 - Thomas Vidick A1 - Umesh Vazirani A1 - Norman Y. Yao A1 - Marko Cetina A1 - Christopher Monroe AB -

Achieving quantum computational advantage requires solving a classically intractable problem on a quantum device. Natural proposals rely upon the intrinsic hardness of classically simulating quantum mechanics; however, verifying the output is itself classically intractable. On the other hand, certain quantum algorithms (e.g. prime factorization via Shor's algorithm) are efficiently verifiable, but require more resources than what is available on near-term devices. One way to bridge the gap between verifiability and implementation is to use "interactions" between a prover and a verifier. By leveraging cryptographic functions, such protocols enable the classical verifier to enforce consistency in a quantum prover's responses across multiple rounds of interaction. In this work, we demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer. We execute two complementary protocols -- one based upon the learning with errors problem and another where the cryptographic construction implements a computational Bell test. To perform multiple rounds of interaction, we implement mid-circuit measurements on a subset of trapped ion qubits, with subsequent coherent evolution. For both protocols, the performance exceeds the asymptotic bound for classical behavior; maintaining this fidelity at scale would conclusively demonstrate verifiable quantum advantage.

UR - https://arxiv.org/abs/2112.05156 ER - TY - JOUR T1 - Localization crossover and subdiffusive transport in a classical facilitated network model of a disordered, interacting quantum spin chain Y1 - 2021 A1 - Kai Klocke A1 - Christopher David White A1 - Michael Buchhold AB -

We consider the random-field Heisenberg model, a paradigmatic model for many-body localization (MBL), and add a Markovian dephasing bath coupled to the Anderson orbitals of the model's non-interacting limit. We map this system to a classical facilitated hopping model that is computationally tractable for large system sizes, and investigate its dynamics. The classical model exhibits a robust crossover between an ergodic (thermal) phase and a frozen (localized) phase. The frozen phase is destabilized by thermal subregions (bubbles), which thermalize surrounding sites by providing a fluctuating interaction energy and so enable off-resonance particle transport. Investigating steady state transport, we observe that the interplay between thermal and frozen bubbles leads to a clear transition between diffusive and subdiffusive regimes. This phenomenology both describes the MBL system coupled to a bath, and provides a classical analogue for the many-body localization transition in the corresponding quantum model, in that the classical model displays long local memory times. It also highlights the importance of the details of the bath coupling in studies of MBL systems coupled to thermal environments.

UR - https://arxiv.org/abs/2109.10926 ER - TY - JOUR T1 - Noise-induced barren plateaus in variational quantum algorithms JF - Nature Communications Y1 - 2021 A1 - Samson Wang A1 - Enrico Fontana A1 - M. Cerezo A1 - Kunal Sharma A1 - Akira Sone A1 - Lukasz Cincio A1 - Patrick J. Coles AB -

Variational Quantum Algorithms (VQAs) may be a path to quantum advantage on Noisy Intermediate-Scale Quantum (NISQ) computers. A natural question is whether noise on NISQ devices places fundamental limitations on VQA performance. We rigorously prove a serious limitation for noisy VQAs, in that the noise causes the training landscape to have a barren plateau (i.e., vanishing gradient). Specifically, for the local Pauli noise considered, we prove that the gradient vanishes exponentially in the number of qubits n if the depth of the ansatz grows linearly with n. These noise-induced barren plateaus (NIBPs) are conceptually different from noise-free barren plateaus, which are linked to random parameter initialization. Our result is formulated for a generic ansatz that includes as special cases the Quantum Alternating Operator Ansatz and the Unitary Coupled Cluster Ansatz, among others. For the former, our numerical heuristics demonstrate the NIBP phenomenon for a realistic hardware noise model.

VL - 12 U4 - 6961 U5 - https://doi.org/10.1038/s41467-021-27045-6 ER - TY - JOUR T1 - Quantum Algorithms for Reinforcement Learning with a Generative Model JF - Proceedings of the 38th International Conference on Machine Learning, PMLR Y1 - 2021 A1 - Daochen Wang A1 - Sundaram, Aarthi A1 - Kothari, Robin A1 - Kapoor, Ashish A1 - Roetteler, Martin KW - FOS: Computer and information sciences KW - FOS: Physical sciences KW - Machine Learning (cs.LG) KW - Quantum Physics (quant-ph) AB -

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.

VL - 139 UR - https://arxiv.org/abs/2112.08451 U5 - 10.48550/ARXIV.2112.08451 ER - TY - JOUR T1 - Quantum exploration algorithms for multi-armed bandits JF - Proceedings of the 35th Conference on Artificial Intelligence (AAAI 2021) Y1 - 2021 A1 - Daochen Wang A1 - Xuchen You A1 - Tongyang Li A1 - Andrew M. Childs AB -

 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).

VL - 35 U4 - 10102-10110 UR - https://ojs.aaai.org/index.php/AAAI/article/view/17212 CP - 11 ER - TY - JOUR T1 - Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance JF - Quantum 5, 481 (2021) Y1 - 2021 A1 - Dong An A1 - Noah Linden A1 - Jin-Peng Liu A1 - Ashley Montanaro A1 - Changpeng Shao A1 - Jiasu Wang AB -

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.

VL - 5 U4 - 481 UR - https://arxiv.org/abs/2012.06283 U5 - https://doi.org/10.22331/q-2021-06-24-481 ER - TY - JOUR T1 - Rainbow Scars: From Area to Volume Law Y1 - 2021 A1 - Christopher M. Langlett A1 - Zhi-Cheng Yang A1 - Julia Wildeboer A1 - Alexey V. Gorshkov A1 - Thomas Iadecola A1 - Shenglong Xu AB -

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

UR - https://arxiv.org/abs/2107.03416 ER - TY - JOUR T1 - Resource-Optimized Fermionic Local-Hamiltonian Simulation on Quantum Computer for Quantum Chemistry JF - Quantum Y1 - 2021 A1 - Qingfeng Wang A1 - Ming Li A1 - Christopher Monroe A1 - Yunseong Nam AB -

The ability to simulate a fermionic system on a quantum computer is expected to revolutionize chemical engineering, materials design, nuclear physics, to name a few. Thus, optimizing the simulation circuits is of significance in harnessing the power of quantum computers. Here, we address this problem in two aspects. In the fault-tolerant regime, we optimize the $\rzgate$ and $\tgate$ gate counts along with the ancilla qubit counts required, assuming the use of a product-formula algorithm for implementation. We obtain a savings ratio of two in the gate counts and a savings ratio of eleven in the number of ancilla qubits required over the state of the art. In the pre-fault tolerant regime, we optimize the two-qubit gate counts, assuming the use of the variational quantum eigensolver (VQE) approach. Specific to the latter, we present a framework that enables bootstrapping the VQE progression towards the convergence of the ground-state energy of the fermionic system. This framework, based on perturbation theory, is capable of improving the energy estimate at each cycle of the VQE progression, by about a factor of three closer to the known ground-state energy compared to the standard VQE approach in the test-bed, classically-accessible system of the water molecule. The improved energy estimate in turn results in a commensurate level of savings of quantum resources, such as the number of qubits and quantum gates, required to be within a pre-specified tolerance from the known ground-state energy. We also explore a suite of generalized transformations of fermion to qubit operators and show that resource-requirement savings of up to more than 20% is possible.

VL - 5 UR - https://arxiv.org/abs/2004.04151 CP - 509 U5 - https://doi.org/10.22331/q-2021-07-26-509 ER - TY - JOUR T1 - Robust Self-Testing of Multiparticle Entanglement JF - Phys. Rev. Lett. Y1 - 2021 A1 - Dian Wu A1 - Qi Zhao A1 - Xue-Mei Gu A1 - Han-Sen Zhong A1 - You Zhou A1 - Li-Chao Peng A1 - Jian Qin A1 - Yi-Han Luo A1 - Kai Chen A1 - Li Li A1 - Nai-Le Liu A1 - Chao-Yang Lu A1 - Jian-Wei Pan AB -

Quantum self-testing is a device-independent way to certify quantum states and measurements using only the input-output statistics, with minimal assumptions about the quantum devices. Due to the high demand on tolerable noise, however, experimental self-testing was limited to two-photon systems. Here, we demonstrate the first robust self-testing for multi-particle quantum entanglement. We prepare two examples of four-photon graph states, the Greenberger-Horne-Zeilinger (GHZ) states with a fidelity of 0.957(2) and the linear cluster states with a fidelity of 0.945(2). Based on the observed input-output statistics, we certify the genuine four-photon entanglement and further estimate their qualities with respect to realistic noise in a device-independent manner.

VL - 127 U4 - 230503 UR - https://arxiv.org/abs/2105.10298 U5 - https://doi.org/10.1103/PhysRevLett.127.230503 ER - TY - JOUR T1 - Subdiffusive hydrodynamics of nearly-integrable anisotropic spin chains Y1 - 2021 A1 - Jacopo De Nardis A1 - Sarang Gopalakrishnan A1 - Romain Vasseur A1 - Brayden Ware AB -

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

UR - https://arxiv.org/abs/2109.13251 ER - TY - JOUR T1 - Theory of Trotter Error with Commutator Scaling JF - Phys. Rev. X Y1 - 2021 A1 - Andrew M. Childs A1 - Yuan Su A1 - Minh C. Tran A1 - Nathan Wiebe A1 - Shuchen Zhu AB -

The Lie-Trotter formula, together with its higher-order generalizations, provides a direct approach to decomposing the exponential of a sum of operators. Despite significant effort, the error scaling of such product formulas remains poorly understood. We develop a theory of Trotter error that overcomes the limitations of prior approaches based on truncating the Baker-Campbell-Hausdorff expansion. Our analysis directly exploits the commutativity of operator summands, producing tighter error bounds for both real- and imaginary-time evolutions. Whereas previous work achieves similar goals for systems with geometric locality or Lie-algebraic structure, our approach holds in general. We give a host of improved algorithms for digital quantum simulation and quantum Monte Carlo methods, including simulations of second-quantized plane-wave electronic structure, k-local Hamiltonians, rapidly decaying power-law interactions, clustered Hamiltonians, the transverse field Ising model, and quantum ferromagnets, nearly matching or even outperforming the best previous results. We obtain further speedups using the fact that product formulas can preserve the locality of the simulated system. Specifically, we show that local observables can be simulated with complexity independent of the system size for power-law interacting systems, which implies a Lieb-Robinson bound as a byproduct. Our analysis reproduces known tight bounds for first- and second-order formulas. Our higher-order bound overestimates the complexity of simulating a one-dimensional Heisenberg model with an even-odd ordering of terms by only a factor of 5, and is close to tight for power-law interactions and other orderings of terms. This suggests that our theory can accurately characterize Trotter error in terms of both asymptotic scaling and constant prefactor.

VL - 11 U4 - 49 UR - https://arxiv.org/abs/1912.08854 CP - 1 U5 - https://journals.aps.org/prx/abstract/10.1103/PhysRevX.11.011020 ER - TY - JOUR T1 - A Threshold for Quantum Advantage in Derivative Pricing JF - Quantum Y1 - 2021 A1 - Shouvanik Chakrabarti A1 - Rajiv Krishnakumar A1 - Guglielmo Mazzola A1 - Nikitas Stamatopoulos A1 - Stefan Woerner A1 - William J. Zeng AB -

We give an upper bound on the resources required for valuable quantum advantage in pricing derivatives. To do so, we give the first complete resource estimates for useful quantum derivative pricing, using autocallable and Target Accrual Redemption Forward (TARF) derivatives as benchmark use cases. We uncover blocking challenges in known approaches and introduce a new method for quantum derivative pricing - the re-parameterization method - that avoids them. This method combines pre-trained variational circuits with fault-tolerant quantum computing to dramatically reduce resource requirements. We find that the benchmark use cases we examine require 7.5k logical qubits and a T-depth of 46 million and thus estimate that quantum advantage would require a logical clock speed of 10Mhz. While the resource requirements given here are out of reach of current systems, we hope they will provide a roadmap for further improvements in algorithms, implementations, and planned hardware architectures. 

VL - 5 U4 - 463 UR - https://arxiv.org/abs/2012.03819 U5 - https://doi.org/10.22331/q-2021-06-01-463 ER - TY - JOUR T1 - Torus Spectroscopy of the Gross-Neveu-Yukawa Quantum Field Theory: Free Dirac versus Chiral Ising Fixed Point JF - Phys. Rev. B Y1 - 2021 A1 - Michael Schuler A1 - Stephan Hesselmann A1 - Seth Whitsitt A1 - Thomas C. Lang A1 - Stefan Wessel A1 - Andreas M. Läuchli AB -

We establish the universal torus low-energy spectra at the free Dirac fixed point and at the strongly coupled chiral Ising fixed point and their subtle crossover behaviour in the Gross-Neuveu-Yukawa field theory with nD=4 component Dirac spinors in D=(2+1) dimensions. These fixed points and the field theories are directly relevant for the long-wavelength physics of certain interacting Dirac systems, such as repulsive spinless fermions on the honeycomb lattice or π-flux square lattice. The torus energy spectrum has been shown previously to serve as a characteristic fingerprint of relativistic fixed points and is a powerful tool to discriminate quantum critical behaviour in numerical simulations. Here, we use a combination of exact diagonalization and quantum Monte Carlo simulations of strongly interacting fermionic lattice models, to compute the critical torus energy spectrum on finite-size clusters with periodic boundaries and extrapolate them to the thermodynamic limit. Additionally, we compute the torus energy spectrum analytically using the perturbative expansion in ε=4−D, which is in good agreement with the numerical results, thereby validating the presence of the chiral Ising fixed point in the lattice models at hand. We show that the strong interaction between the spinor field and the scalar order-parameter field strongly influences the critical torus energy spectrum and we observe prominent multiplicity features related to an emergent symmetry predicted from the quantum field theory. Building on these results we are able to address the subtle crossover physics of the low-energy spectrum flowing from the chiral Ising fixed point to the Dirac fixed point, and analyze earlier flawed attempts to extract Fermi velocity renormalizations from the low-energy spectrum.

VL - 103 U4 - 125128 UR - https://arxiv.org/abs/1907.05373 U5 - https://doi.org/10.1103/PhysRevB.103.125128 ER - TY - JOUR T1 - Verified Compilation of Quantum Oracles Y1 - 2021 A1 - Liyi Li A1 - Finnegan Voichick A1 - Kesha Hietala A1 - Yuxiang Peng A1 - Xiaodi Wu A1 - Michael Hicks AB -

Quantum algorithms often apply classical operations, such as arithmetic or predicate checks, over a quantum superposition of classical data; these so-called oracles are often the largest components of a quantum algorithm. To ease the construction of efficient, correct oracle functions, this paper presents VQO, a high-assurance framework implemented with the Coq proof assistant. The core of VQO is OQASM, the oracle quantum assembly language. OQASM operations move qubits among three different bases via the Quantum Fourier Transform and Hadamard operations, thus admitting important optimizations, but without inducing entanglement and the exponential blowup that comes with it. OQASM's design enabled us to prove correct VQO's compilers -- from a simple imperative language called OQIMP to OQASM, and from OQASM to SQIR, a general-purpose quantum assembly language -- and allowed us to efficiently test properties of OQASM programs using the QuickChick property-based testing framework. We have used VQO to implement oracles used in Shor's and Grover's algorithms, as well as several common arithmetic operators. VQO's oracles have performance comparable to those produced by Quipper, a state-of-the-art but unverified quantum programming platform.

UR - https://arxiv.org/abs/2112.06700 ER - TY - JOUR T1 - A Verified Optimizer for Quantum Circuits JF - Proceedings of the ACM on Programming Languages Y1 - 2021 A1 - Kesha Hietala A1 - Robert Rand A1 - Shih-Han Hung A1 - Xiaodi Wu A1 - Michael Hicks AB -

We present VOQC, the first fully verified compiler for quantum circuits, written using the Coq proof assistant. Quantum circuits are expressed as programs in a simple, low-level language called SQIR, which is deeply embedded in Coq. Optimizations and other transformations are expressed as Coq functions, which are proved correct with respect to a semantics of SQIR programs. We evaluate VOQC's verified optimizations on a series of benchmarks, and it performs comparably to industrial-strength compilers. VOQC's optimizations reduce total gate counts on average by 17.7% on a benchmark of 29 circuit programs compared to a 10.7% reduction when using IBM's Qiskit compiler.

VL - 5 UR - https://arxiv.org/abs/1912.02250 CP - POPL U5 - https://doi.org/10.1145/3434318 ER - TY - JOUR T1 - Approximate recovery and relative entropy I. general von Neumann subalgebras Y1 - 2020 A1 - Thomas Faulkner A1 - Stefan Hollands A1 - Brian Swingle A1 - Yixu Wang AB -

We prove the existence of a universal recovery channel that approximately recovers states on a v. Neumann subalgebra when the change in relative entropy, with respect to a fixed reference state, is small. Our result is a generalization of previous results that applied to type-I v. Neumann algebras by Junge at al. [arXiv:1509.07127]. We broadly follow their proof strategy but consider here arbitrary v. Neumann algebras, where qualitatively new issues arise. Our results hinge on the construction of certain analytic vectors and computations/estimations of their Araki-Masuda Lp norms. We comment on applications to the quantum null energy condition.

UR - https://arxiv.org/abs/2006.08002 ER - TY - JOUR T1 - Approximate recovery and relative entropy I. general von Neumann subalgebras Y1 - 2020 A1 - Thomas Faulkner A1 - Stefan Hollands A1 - Brian Swingle A1 - Yixu Wang AB -

We prove the existence of a universal recovery channel that approximately recovers states on a v. Neumann subalgebra when the change in relative entropy, with respect to a fixed reference state, is small. Our result is a generalization of previous results that applied to type-I v. Neumann algebras by Junge at al. [arXiv:1509.07127]. We broadly follow their proof strategy but consider here arbitrary v. Neumann algebras, where qualitatively new issues arise. Our results hinge on the construction of certain analytic vectors and computations/estimations of their Araki-Masuda Lp norms. We comment on applications to the quantum null energy condition.

UR - https://arxiv.org/abs/2006.08002 ER - TY - JOUR T1 - Can graph properties have exponential quantum speedup? Y1 - 2020 A1 - Andrew M. Childs A1 - Daochen Wang AB -

Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity R of any graph property P has R(P)=O(Q(P)6), where Q is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove R(P)=O(Q(P)3l) for any l-uniform hypergraph property P in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.

UR - https://arxiv.org/abs/2001.10520 ER - TY - JOUR T1 - Constant-round Blind Classical Verification of Quantum Sampling Y1 - 2020 A1 - Kai-Min Chung A1 - Yi Lee A1 - Han-Hsuan Lin A1 - Xiaodi Wu AB -

In a recent breakthrough, Mahadev constructed a classical verification of quantum computation (CVQC) protocol for a classical client to delegate decision problems in BQP to an untrusted quantum prover under computational assumptions. In this work, we explore further the feasibility of CVQC with the more general sampling problems in BQP and with the desirable blindness property. We contribute affirmative solutions to both as follows. (1) Motivated by the sampling nature of many quantum applications (e.g., quantum algorithms for machine learning and quantum supremacy tasks), we initiate the study of CVQC for quantum sampling problems (denoted by SampBQP). More precisely, in a CVQC protocol for a SampBQP problem, the prover and the verifier are given an input x∈{0,1}n and a quantum circuit C, and the goal of the classical client is to learn a sample from the output z←C(x) up to a small error, from its interaction with an untrusted prover. We demonstrate its feasibility by constructing a four-message CVQC protocol for SampBQP based on the quantum Learning With Error assumption. (2) The blindness of CVQC protocols refers to a property of the protocol where the prover learns nothing, and hence is blind, about the client's input. It is a highly desirable property that has been intensively studied for the delegation of quantum computation. We provide a simple yet powerful generic compiler that transforms any CVQC protocol to a blind one while preserving its completeness and soundness errors as well as the number of rounds. Applying our compiler to (a parallel repetition of) Mahadev's CVQC protocol for BQP and our CVQC protocol for SampBQP yields the first constant-round blind CVQC protocol for BQP and SampBQP respectively, with negligible completeness and soundness errors.

UR - https://arxiv.org/abs/2012.04848 ER - TY - JOUR T1 - Efficiently computable bounds for magic state distillation JF - Phys. Rev. Lett. Y1 - 2020 A1 - Xin Wang A1 - Mark M. Wilde A1 - Yuan Su AB -

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

VL - 124 UR - https://arxiv.org/abs/1812.10145 CP - 090505 U5 - https://doi.org/10.1103/PhysRevLett.124.090505 ER - TY - JOUR T1 - An exponential ramp in the quadratic Sachdev-Ye-Kitaev model Y1 - 2020 A1 - Michael Winer A1 - Shao-Kai Jian A1 - Brian Swingle AB -

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

UR - https://arxiv.org/abs/2006.15152 ER - TY - JOUR T1 - Mechanical Quantum Sensing in the Search for Dark Matter Y1 - 2020 A1 - D. Carney A1 - G. Krnjaic A1 - D. C. Moore A1 - C. A. Regal A1 - G. Afek A1 - S. Bhave A1 - B. Brubaker A1 - T. Corbitt A1 - J. Cripe A1 - N. Crisosto A1 - A.Geraci A1 - S. Ghosh A1 - J. G. E. Harris A1 - A. Hook A1 - E. W. Kolb A1 - J. Kunjummen A1 - R. F. Lang A1 - T. Li A1 - T. Lin A1 - Z. Liu A1 - J. Lykken A1 - L. Magrini A1 - J. Manley A1 - N. Matsumoto A1 - A. Monte A1 - F. Monteiro A1 - T. Purdy A1 - C. J. Riedel A1 - R. Singh A1 - S. Singh A1 - K. Sinha A1 - J. M. Taylor A1 - J. Qin A1 - D. J. Wilson A1 - Y. Zhao AB -

Numerous astrophysical and cosmological observations are best explained by the existence of dark matter, a mass density which interacts only very weakly with visible, baryonic matter. Searching for the extremely weak signals produced by this dark matter strongly motivate the development of new, ultra-sensitive detector technologies. Paradigmatic advances in the control and readout of massive mechanical systems, in both the classical and quantum regimes, have enabled unprecedented levels of sensitivity. In this white paper, we outline recent ideas in the potential use of a range of solid-state mechanical sensing technologies to aid in the search for dark matter in a number of energy scales and with a variety of coupling mechanisms.

UR - https://arxiv.org/abs/2008.06074 ER - TY - JOUR T1 - On-demand indistinguishable single photons from an efficient and pure source based on a Rydberg ensemble Y1 - 2020 A1 - Dalia P. Ornelas-Huerta A1 - Alexander N. Craddock A1 - Elizabeth A. Goldschmidt A1 - Andrew J. Hachtel A1 - Yidan Wang A1 - P. Bienias A1 - Alexey V. Gorshkov A1 - Steve L. Rolston A1 - James V. Porto AB -

Single photons coupled to atomic systems have shown to be a promising platform for developing quantum technologies. Yet a bright on-demand, highly pure and highly indistinguishable single-photon source compatible with atomic platforms is lacking. In this work, we demonstrate such a source based on a strongly interacting Rydberg system. The large optical nonlinearities in a blockaded Rydberg ensemble convert coherent light into a single-collective excitation that can be coherently retrieved as a quantum field. We observe a single-transverse-mode efficiency up to 0.18(2), g(2)=2.0(1.5)×10−4, and indistinguishability of 0.982(7), making this system promising for scalable quantum information applications. Accounting for losses, we infer a generation probability up to 0.40(4). Furthermore, we investigate the effects of contaminant Rydberg excitations on the source efficiency. Finally, we introduce metrics to benchmark the performance of on-demand single-photon sources. 

UR - https://arxiv.org/abs/2003.02202 ER - TY - JOUR T1 - On the Principles of Differentiable Quantum Programming Languages Y1 - 2020 A1 - Shaopeng Zhu A1 - Shih-Han Hung A1 - Shouvanik Chakrabarti A1 - Xiaodi Wu AB -

Variational Quantum Circuits (VQCs), or the so-called quantum neural-networks, are predicted to be one of the most important near-term quantum applications, not only because of their similar promises as classical neural-networks, but also because of their feasibility on near-term noisy intermediate-size quantum (NISQ) machines. The need for gradient information in the training procedure of VQC applications has stimulated the development of auto-differentiation techniques for quantum circuits. We propose the first formalization of this technique, not only in the context of quantum circuits but also for imperative quantum programs (e.g., with controls), inspired by the success of differentiable programming languages in classical machine learning. In particular, we overcome a few unique difficulties caused by exotic quantum features (such as quantum no-cloning) and provide a rigorous formulation of differentiation applied to bounded-loop imperative quantum programs, its code-transformation rules, as well as a sound logic to reason about their correctness. Moreover, we have implemented our code transformation in OCaml and demonstrated the resource-efficiency of our scheme both analytically and empirically. We also conduct a case study of training a VQC instance with controls, which shows the advantage of our scheme over existing auto-differentiation for quantum circuits without controls.

UR - https://arxiv.org/abs/2004.01122 U5 - https://doi.org/10.1145/3385412.3386011 ER - TY - JOUR T1 - Quantum algorithms and lower bounds for convex optimization JF - Quantum Y1 - 2020 A1 - Shouvanik Chakrabarti A1 - Andrew M. Childs A1 - Tongyang Li A1 - Xiaodi Wu AB -

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.

VL - 4 UR - https://arxiv.org/abs/1809.01731 CP - 221 U5 - https://doi.org/10.22331/q-2020-01-13-221 ER - TY - JOUR T1 - Quantum Algorithms for Simulating the Lattice Schwinger Model JF - Quantum Y1 - 2020 A1 - Alexander F. Shaw A1 - Pavel Lougovski A1 - Jesse R. Stryker A1 - Nathan Wiebe AB -

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. 

VL - 4 UR - https://arxiv.org/abs/2002.11146 CP - 306 U5 - https://doi.org/10.22331/q-2020-08-10-306 ER - TY - JOUR T1 - Ray-based classification framework for high-dimensional data JF - Proceedings of the Machine Learning and the Physical Sciences Workshop at NeurIPS 2020, Vancouver, Canada Y1 - 2020 A1 - Justyna P. Zwolak A1 - Sandesh S. Kalantre A1 - Thomas McJunkin A1 - Brian J. Weber A1 - J. M. Taylor AB -

While classification of arbitrary structures in high dimensions may require complete quantitative information, for simple geometrical structures, low-dimensional qualitative information about the boundaries defining the structures can suffice. Rather than using dense, multi-dimensional data, we propose a deep neural network (DNN) classification framework that utilizes a minimal collection of one-dimensional representations, called \emph{rays}, to construct the "fingerprint" of the structure(s) based on substantially reduced information. We empirically study this framework using a synthetic dataset of double and triple quantum dot devices and apply it to the classification problem of identifying the device state. We show that the performance of the ray-based classifier is already on par with traditional 2D images for low dimensional systems, while significantly cutting down the data acquisition cost.

UR - https://arxiv.org/abs/2010.00500 ER - TY - JOUR T1 - Realizing and Probing Baryonic Excitations in Rydberg Atom Arrays Y1 - 2020 A1 - Fangli Liu A1 - Seth Whitsitt A1 - Przemyslaw Bienias A1 - Rex Lundgren A1 - Alexey V. Gorshkov AB -

We propose a realization of mesonic and baryonic quasiparticle excitations in Rydberg atom arrays with programmable interactions. Recent experiments have shown that such systems possess a Z3-ordered crystalline phase whose low-energy quasiparticles are defects in the crystalline order. By engineering a Z3-translational-symmetry breaking field on top of the Rydberg-blockaded Hamiltonian, we show that different types of defects experience confinement, and as a consequence form mesonic or baryonic quasiparticle excitations. We illustrate the formation of these quasiparticles by studying a quantum chiral clock model related to the Rydberg Hamiltonian. We then propose an experimental protocol involving out-of-equilibrium dynamics to directly probe the spectrum of the confined excitations. We show that the confined quasiparticle spectrum can limit quantum information spreading in this system. This proposal is readily applicable to current Rydberg experiments, and the method can be easily generalized to more complex confined excitations (e.g. `tetraquarks', `pentaquarks') in phases with Zq order for q>3. 

UR - https://arxiv.org/abs/2007.07258 ER - TY - JOUR T1 - Resonant enhancement of three-body loss between strongly interacting photons Y1 - 2020 A1 - Marcin Kalinowski A1 - Yidan Wang A1 - Przemyslaw Bienias A1 - Michael Gullans A1 - Dalia P. Ornelas-Huerta A1 - Alexander N. Craddock A1 - Steven L. Rolston A1 - J. V. Porto A1 - Hans Peter Büchler A1 - Alexey V. Gorshkov AB -

Rydberg polaritons provide an example of a rare type of system where three-body interactions can be as strong or even stronger than two-body interactions. The three-body interactions can be either dispersive or dissipative, with both types possibly giving rise to exotic, strongly-interacting, and topological phases of matter. Despite past theoretical and experimental studies of the regime with dispersive interaction, the dissipative regime is still mostly unexplored. Using a renormalization group technique to solve the three-body Schrödinger equation, we show how the shape and strength of dissipative three-body forces can be universally enhanced for Rydberg polaritons. We demonstrate how these interactions relate to the transmission through a single-mode cavity, which can be used as a probe of the three-body physics in current experiment

UR - https://arxiv.org/abs/2010.09772 ER - TY - JOUR T1 - Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning JF - to appear in Proceedings of STOC 2020 Y1 - 2020 A1 - Nai-Hui Chia A1 - Andras Gilyen A1 - Tongyang Li A1 - Han-Hsuan Lin A1 - Ewin Tang A1 - Chunhao Wang AB -

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

UR - https://arxiv.org/abs/1910.06151 U5 - https://doi.org/10.1145/3357713.3384314 ER - TY - JOUR T1 - Search for composite dark matter with optically levitated sensors JF - Phys. Rev. Lett. Y1 - 2020 A1 - Fernando Monteiro A1 - Gadi Afek A1 - Daniel Carney A1 - Gordan Krnjaic A1 - Jiaxiang Wang A1 - David C. Moore AB -

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

VL - 125 UR - https://arxiv.org/abs/2007.12067 CP - 181102 U5 - https://doi.org/10.1103/PhysRevLett.125.181102 ER - TY - JOUR T1 - Security Limitations of Classical-Client Delegated Quantum Computing Y1 - 2020 A1 - Christian Badertscher A1 - Alexandru Cojocaru A1 - Léo Colisson A1 - Elham Kashefi A1 - Dominik Leichtle A1 - Atul Mantri A1 - Petros Wallden AB -

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

UR - https://arxiv.org/abs/2007.01668 ER - TY - JOUR T1 - Simulating large quantum circuits on a small quantum computer JF - Phys. Rev. Lett. Y1 - 2020 A1 - Tianyi Peng A1 - Aram Harrow A1 - Maris Ozols A1 - Xiaodi Wu AB -

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

VL - 125 UR - https://arxiv.org/abs/1904.00102 CP - 150504 U5 - https://doi.org/10.1103/PhysRevLett.125.150504 ER - TY - JOUR T1 - Sublinear classical and quantum algorithms for general matrix games JF - To appear in the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021) Y1 - 2020 A1 - Tongyang Li A1 - Chunhao Wang A1 - Shouvanik Chakrabarti A1 - Xiaodi Wu AB -

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

UR - https://arxiv.org/abs/2012.06519 ER - TY - CONF T1 - Symmetries, graph properties, and quantum speedups T2 - Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pp. 649–660 (2020) Y1 - 2020 A1 - Shalev Ben-David A1 - Andrew M. Childs A1 - Andras Gilyen A1 - William Kretschmer A1 - Supartha Podder A1 - Daochen Wang AB -

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

JA - Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pp. 649–660 (2020) UR - https://arxiv.org/abs/2006.12760 U5 - https://doi.org/10.1109/FOCS46700.2020.00066 ER - TY - JOUR T1 - Time-dependent Hamiltonian simulation with L1-norm scaling JF - Quantum Y1 - 2020 A1 - Dominic W. Berry A1 - Andrew M. Childs A1 - Yuan Su A1 - Xin Wang A1 - Nathan Wiebe AB -

The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that exploit this intuition. For the case of sparse Hamiltonian simulation, the gate complexity scales with the L1 norm ∫t0dτ∥H(τ)∥max, whereas the best previous results scale with tmaxτ∈[0,t]∥H(τ)∥max. We also show analogous results for Hamiltonians that are linear combinations of unitaries. Our approaches thus provide an improvement over previous simulation algorithms that can be substantial when the Hamiltonian varies significantly. We introduce two new techniques: a classical sampler of time-dependent Hamiltonians and a rescaling principle for the Schrödinger equation. The rescaled Dyson-series algorithm is nearly optimal with respect to all parameters of interest, whereas the sampling-based approach is easier to realize for near-term simulation. By leveraging the L1-norm information, we obtain polynomial speedups for semi-classical simulations of scattering processes in quantum chemistry.

VL - 4 UR - https://arxiv.org/abs/1906.07115 CP - 254 U5 - https://doi.org/10.22331/q-2020-04-20-254 ER - TY - JOUR T1 - Transport and dynamics in the frustrated two-bath spin-boson model Y1 - 2020 A1 - Ron Belyansky A1 - Seth Whitsitt A1 - Rex Lundgren A1 - Yidan Wang A1 - Andrei Vrajitoarea A1 - Andrew A. Houck A1 - Alexey V. Gorshkov AB -

We study the strong coupling dynamics as well as transport properties of photons in the two-bath spin-boson model, in which a spin-1/2 particle is frustratingly coupled to two independent Ohmic bosonic baths. Using a combination of numerical and analytical methods, we show that the frustration in this model gives rise to rich physics in a very wide range of energies. This is in contrast to the one-bath spin-boson model, where the non-trivial physics occurs at an energy scale close to the renormalized spin frequency. The renormalized spin frequency in the two-bath spin-boson model is still important, featuring in different observables, including the non-equiblirum dynamics of both the spin and the baths along with the elastic transport properties of a photon. The latter however reveals a much more complex structure. The elastic scattering displays non-monotonic behavior at high frequencies, and is very different in the two channels: intra- and inter-bath scattering. The photon can also be inelastically scattered, a process in which it is split into several photons of smaller energies. We show that such inelastic processes are highly anisotropic, with the outgoing particles being preferentially emitted into only one of the baths. Moreover, the inelastic scattering rate is parameterically larger than in the one-bath case, and can even exceed the total elastic rate. Our results can be verified with state-of-the-art circuit and cavity quantum electrodynamics experiments. 

UR - https://arxiv.org/abs/2007.03690 ER - TY - JOUR T1 - Accelerated Variational Quantum Eigensolver JF - Phys. Rev. Lett. Y1 - 2019 A1 - Daochen Wang A1 - Oscar Higgott A1 - Stephen Brierley AB -

The problem of finding the ground state energy of a Hamiltonian using a quantum computer is currently solved using either the quantum phase estimation (QPE) or variational quantum eigensolver (VQE) algorithms. For precision ε, QPE requires O(1) repetitions of circuits with depth O(1/ε), whereas each expectation estimation subroutine within VQE requires O(1/ε2) samples from circuits with depth O(1). We propose a generalised VQE algorithm that interpolates between these two regimes via a free parameter α∈[0,1] which can exploit quantum coherence over a circuit depth of O(1/εα) to reduce the number of samples to O(1/ε2(1−α)). Along the way, we give a new routine for expectation estimation under limited quantum resources that is of independent interest.

VL - 122 UR - https://arxiv.org/abs/1802.00171 CP - 140504 U5 - https://doi.org/10.1103/PhysRevLett.122.140504 ER - TY - JOUR T1 - Beyond Spontaneous Emission: Giant Atom Bounded in Continuum Y1 - 2019 A1 - Shangjie Guo A1 - Yidan Wang A1 - Thomas Purdy A1 - J. M. Taylor AB -

The quantum coupling of individual superconducting qubits to microwave photons leads to remarkable experimental opportunities. Here we consider the phononic case where the qubit is coupled to an electromagnetic surface acoustic wave antenna that enables supersonic propagation of the qubit oscillations. This can be considered as a giant atom that is many phonon wavelengths long. We study an exactly solvable toy model that captures these effects, and find that this non-Markovian giant atom has a suppressed relaxation, as well as an effective vacuum coupling between a qubit excitation and a localized wave packet of sound, even in the absence of a cavity for the sound waves. Finally, we consider practical implementations of these ideas in current surface acoustic wave devices. 

UR - https://arxiv.org/abs/1912.09980 ER - TY - JOUR T1 - Floquet engineering of optical lattices with spatial features and periodicity below the diffraction limit Y1 - 2019 A1 - S. Subhankar A1 - P. Bienias A1 - P. Titum A1 - T-C. Tsui A1 - Y. Wang A1 - Alexey V. Gorshkov A1 - S. L. Rolston A1 - J. V. Porto AB -

Floquet engineering or coherent time periodic driving of quantum systems has been successfully used to synthesize Hamiltonians with novel properties. In ultracold atomic systems, this has led to experimental realizations of artificial gauge fields, topological band structures, and observation of dynamical localization, to name just a few. Here we present a Floquet-based framework to stroboscopically engineer Hamiltonians with spatial features and periodicity below the diffraction limit of light used to create them by time-averaging over various configurations of a 1D optical Kronig-Penney (KP) lattice. The KP potential is a lattice of narrow subwavelength barriers spaced by half the optical wavelength (λ/2) and arises from the non-linear optical response of the atomic dark state. Stroboscopic control over the strength and position of this lattice requires time-dependent adiabatic manipulation of the dark state spin composition. We investigate adiabaticity requirements and shape our time-dependent light fields to respect the requirements. We apply this framework to show that a λ/4-spaced lattice can be synthesized using realistic experimental parameters as an example, discuss mechanisms that limit lifetimes in these lattices, explore candidate systems and their limitations, and treat adiabatic loading into the ground band of these lattices.

UR - https://arxiv.org/abs/1906.07646 ER - TY - JOUR T1 - Ground-state energy estimation of the water molecule on a trapped ion quantum computer Y1 - 2019 A1 - Yunseong Nam A1 - Jwo-Sy Chen A1 - Neal C. Pisenti A1 - Kenneth Wright A1 - Conor Delaney A1 - Dmitri Maslov A1 - Kenneth R. Brown A1 - Stewart Allen A1 - Jason M. Amini A1 - Joel Apisdorf A1 - Kristin M. Beck A1 - Aleksey Blinov A1 - Vandiver Chaplin A1 - Mika Chmielewski A1 - Coleman Collins A1 - Shantanu Debnath A1 - Andrew M. Ducore A1 - Kai M. Hudek A1 - Matthew Keesan A1 - Sarah M. Kreikemeier A1 - Jonathan Mizrahi A1 - Phil Solomon A1 - Mike Williams A1 - Jaime David Wong-Campos A1 - Christopher Monroe A1 - Jungsang Kim AB -

Quantum computing leverages the quantum resources of superposition and entanglement to efficiently solve computational problems considered intractable for classical computers. Examples include calculating molecular and nuclear structure, simulating strongly-interacting electron systems, and modeling aspects of material function. While substantial theoretical advances have been made in mapping these problems to quantum algorithms, there remains a large gap between the resource requirements for solving such problems and the capabilities of currently available quantum hardware. Bridging this gap will require a co-design approach, where the expression of algorithms is developed in conjunction with the hardware itself to optimize execution. Here, we describe a scalable co-design framework for solving chemistry problems on a trapped ion quantum computer, and apply it to compute the ground-state energy of the water molecule. The robust operation of the trapped ion quantum computer yields energy estimates with errors approaching the chemical accuracy, which is the target threshold necessary for predicting the rates of chemical reaction dynamics.

UR - https://arxiv.org/abs/1902.10171 ER - TY - JOUR T1 - Limitations of semidefinite programs for separable states and entangled games JF - Commun. Math. Phys. Y1 - 2019 A1 - Aram W. Harrow A1 - Anand Natarajan A1 - Xiaodi Wu AB -

Semidefinite programs (SDPs) are a framework for exact or approximate optimization that have widespread application in quantum information theory. We introduce a new method for using reductions to construct integrality gaps for SDPs. These are based on new limitations on the sum-of-squares (SoS) hierarchy in approximating two particularly important sets in quantum information theory, where previously no ω(1)-round integrality gaps were known: the set of separable (i.e. unentangled) states, or equivalently, the 2→4 norm of a matrix, and the set of quantum correlations; i.e. conditional probability distributions achievable with local measurements on a shared entangled state. In both cases no-go theorems were previously known based on computational assumptions such as the Exponential Time Hypothesis (ETH) which asserts that 3-SAT requires exponential time to solve. Our unconditional results achieve the same parameters as all of these previous results (for separable states) or as some of the previous results (for quantum correlations). In some cases we can make use of the framework of Lee-Raghavendra-Steurer (LRS) to establish integrality gaps for any SDP, not only the SoS hierarchy. Our hardness result on separable states also yields a dimension lower bound of approximate disentanglers, answering a question of Watrous and Aaronson et al. These results can be viewed as limitations on the monogamy principle, the PPT test, the ability of Tsirelson-type bounds to restrict quantum correlations, as well as the SDP hierarchies of Doherty-Parrilo-Spedalieri, Navascues-Pironio-Acin and Berta-Fawzi-Scholz.

VL - 366 UR - https://arxiv.org/abs/1612.09306 CP - 2 U5 - https://doi.org/10.1007/s00220-019-03382-y ER - TY - JOUR T1 - Observation of Domain Wall Confinement and Dynamics in a Quantum Simulator Y1 - 2019 A1 - W. L. Tan A1 - P. Becker A1 - F. Liu A1 - G. Pagano A1 - K. S. Collins A1 - A. De A1 - L. Feng A1 - H. B. Kaplan A1 - A. Kyprianidis A1 - R. Lundgren A1 - W. Morong A1 - S. Whitsitt A1 - Alexey V. Gorshkov A1 - C. Monroe AB -

Confinement is a ubiquitous mechanism in nature, whereby particles feel an attractive force that increases without bound as they separate. A prominent example is color confinement in particle physics, in which baryons and mesons are produced by quark confinement. Analogously, confinement can also occur in low-energy quantum many-body systems when elementary excitations are confined into bound quasiparticles. Here, we report the first observation of magnetic domain wall confinement in interacting spin chains with a trapped-ion quantum simulator. By measuring how correlations spread, we show that confinement can dramatically suppress information propagation and thermalization in such many-body systems. We are able to quantitatively determine the excitation energy of domain wall bound states from non-equilibrium quench dynamics. Furthermore, we study the number of domain wall excitations created for different quench parameters, in a regime that is difficult to model with classical computers. This work demonstrates the capability of quantum simulators for investigating exotic high-energy physics phenomena, such as quark collision and string breaking

UR - https://arxiv.org/abs/1912.11117 ER - TY - JOUR T1 - Quantifying the magic of quantum channels JF - New Journal of Physics Y1 - 2019 A1 - Xin Wang A1 - Mark M. Wilde A1 - Yuan Su AB -

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.

VL - 21 UR - https://arxiv.org/abs/1903.04483 CP - 103002 U5 - https://doi.org/10.1088/1367-2630/ab451d ER - TY - JOUR T1 - Quantum circuit approximations and entanglement renormalization for the Dirac field in 1+1 dimensions Y1 - 2019 A1 - Freek Witteveen A1 - Volkher Scholz A1 - Brian Swingle A1 - Michael Walter AB -

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. 

UR - https://arxiv.org/abs/1905.08821 ER - TY - JOUR T1 - Quantum Computing at the Frontiers of Biological Sciences Y1 - 2019 A1 - Prashant S. Emani A1 - Jonathan Warrell A1 - Alan Anticevic A1 - Stefan Bekiranov A1 - Michael Gandal A1 - Michael J. McConnell A1 - Guillermo Sapiro A1 - Alán Aspuru-Guzik A1 - Justin Baker A1 - Matteo Bastiani A1 - Patrick McClure A1 - John Murray A1 - Stamatios N Sotiropoulos A1 - J. M. Taylor A1 - Geetha Senthil A1 - Thomas Lehner A1 - Mark B. Gerstein A1 - Aram W. Harrow AB -

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. 

UR - https://arxiv.org/abs/1911.07127 ER - TY - JOUR T1 - Quantum Gravity in the Lab: Teleportation by Size and Traversable Wormholes Y1 - 2019 A1 - Adam R. Brown A1 - Hrant Gharibyan A1 - Stefan Leichenauer A1 - Henry W. Lin A1 - Sepehr Nezami A1 - Grant Salton A1 - Leonard Susskind A1 - Brian Swingle A1 - Michael Walter AB -

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. 

UR - https://arxiv.org/abs/1911.06314 ER - TY - JOUR T1 - Quantum Physics Meets Music: A "Real-Time" Guitar Recording Using Rydberg-Atoms and Electromagnetically Induced Transparency Y1 - 2019 A1 - Christopher L. Holloway A1 - Matthew T. Simons A1 - Abdulaziz H. Haddab A1 - Carl J. Williams A1 - Maxwell W. Holloway AB -

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.

UR - https://arxiv.org/abs/1904.01952 ER - TY - JOUR T1 - Quantum query complexity of entropy estimation JF - IEEE Transactions on Information Theory Y1 - 2019 A1 - Tongyang Li A1 - Xiaodi Wu AB -

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.

VL - 65 U4 - 2899-2921 UR - https://arxiv.org/abs/1710.06025 CP - 5 U5 - https://doi.org/10.1109/TIT.2018.2883306 ER - TY - JOUR T1 - Quantum Wasserstein Generative Adversarial Networks JF - Advances in Neural Information Processing Systems (NIPS) Y1 - 2019 A1 - Shouvanik Chakrabarti A1 - Yiming Huang A1 - Tongyang Li A1 - Soheil Feizi A1 - Xiaodi Wu AB -

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.

VL - 32 UR - https://arxiv.org/abs/1911.00111 U5 - https://papers.nips.cc/paper/8903-quantum-wasserstein-generative-adversarial-networks.pdf ER - TY - JOUR T1 - Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches Y1 - 2019 A1 - Nai-Hui Chia A1 - Tongyang Li A1 - Han-Hsuan Lin A1 - Chunhao Wang AB -

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.

UR - https://arxiv.org/abs/1901.03254 ER - TY - JOUR T1 - Real-time dynamics of string breaking in quantum spin chains Y1 - 2019 A1 - Roberto Verdel A1 - Fangli Liu A1 - Seth Whitsitt A1 - Alexey V. Gorshkov A1 - Markus Heyl AB -

String breaking is a central dynamical process in theories featuring confinement, where a string connecting two charges decays at the expense of the creation of new particle-antiparticle pairs. Here, we show that this process can also be observed in quantum Ising chains where domain walls get confined either by a symmetry-breaking field or by long-range interactions. We find that string breaking occurs, in general, as a two-stage process: First, the initial charges remain essentially static and stable. The connecting string, however, can become a dynamical object. We develop an effective description of this motion, which we find is strongly constrained. In the second stage, which can be severely delayed due to these dynamical constraints, the string finally breaks. We observe that the associated time scale can depend crucially on the initial separation between domain walls and can grow by orders of magnitude by changing the distance by just a few lattice sites. We discuss how our results generalize to one-dimensional confining gauge theories and how they can be made accessible in quantum simulator experiments such as Rydberg atoms or trapped ions.

UR - https://arxiv.org/abs/1911.11382 ER - TY - JOUR T1 - Resource theory of asymmetric distinguishability for quantum channels Y1 - 2019 A1 - Xin Wang A1 - Mark M. Wilde AB -

This paper develops the resource theory of asymmetric distinguishability for quantum channels, generalizing the related resource theory for states [arXiv:1006.0302, arXiv:1905.11629]. The key constituents of the channel resource theory are quantum channel boxes, consisting of a pair of quantum channels, which can be manipulated for free by means of an arbitrary quantum superchannel (the most general physical transformation of a quantum channel). One main question of the resource theory is the approximate channel box transformation problem, in which the goal is to transform an initial channel box (or boxes) to a final channel box (or boxes), while allowing for an asymmetric error in the transformation. The channel resource theory is richer than its counterpart for states because there is a wider variety of ways in which this question can be framed, either in the one-shot or n-shot regimes, with the latter having parallel and sequential variants. As in [arXiv:1905.11629], we consider two special cases of the general channel box transformation problem, known as distinguishability distillation and dilution. For the one-shot case, we find that the optimal values of the various tasks are equal to the non-smooth or smooth channel min- or max-relative entropies, thus endowing all of these quantities with operational interpretations. In the asymptotic sequential setting, we prove that the exact distinguishability cost is equal to channel max-relative entropy and the distillable distinguishability is equal to the amortized channel relative entropy of [arXiv:1808.01498]. This latter result can also be understood as a solution to Stein's lemma for quantum channels in the sequential setting. Finally, the theory simplifies significantly for environment-seizable and classical--quantum channel boxes.

UR - https://arxiv.org/abs/1907.06306 ER - TY - JOUR T1 - Resource theory of entanglement for bipartite quantum channels Y1 - 2019 A1 - Stefan Bäuml A1 - Siddhartha Das A1 - Xin Wang A1 - Mark M. Wilde AB -

The traditional perspective in quantum resource theories concerns how to use free operations to convert one resourceful quantum state to another one. For example, a fundamental and well known question in entanglement theory is to determine the distillable entanglement of a bipartite state, which is equal to the maximum rate at which fresh Bell states can be distilled from many copies of a given bipartite state by employing local operations and classical communication for free. It is the aim of this paper to take this kind of question to the next level, with the main question being: What is the best way of using free channels to convert one resourceful quantum channel to another? Here we focus on the the resource theory of entanglement for bipartite channels and establish several fundamental tasks and results regarding it. In particular, we establish bounds on several pertinent information processing tasks in channel entanglement theory, and we define several entanglement measures for bipartite channels, including the logarithmic negativity and the κ-entanglement. We also show that the max-Rains information of [Bäuml et al., Physical Review Letters, 121, 250504 (2018)] has a divergence interpretation, which is helpful for simplifying the results of this earlier work. 

UR - https://arxiv.org/abs/1907.04181 ER - TY - JOUR T1 - Simulating quantum circuits by classical circuits Y1 - 2019 A1 - Daochen Wang AB -

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

UR - https://arxiv.org/abs/1904.05282 ER - TY - JOUR T1 - Sublinear quantum algorithms for training linear and kernel-based classifiers JF - Proceedings of the 36th International Conference on Machine Learning (ICML 2019) PMLR Y1 - 2019 A1 - Tongyang Li A1 - Shouvanik Chakrabarti A1 - Xiaodi Wu AB -

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

VL - 97 U4 - 3815-3824 UR - https://arxiv.org/abs/1904.02276 ER - TY - JOUR T1 - Two-qubit entangling gates within arbitrarily long chains of trapped ions Y1 - 2019 A1 - Kevin A. Landsman A1 - Yukai Wu A1 - Pak Hong Leung A1 - Daiwei Zhu A1 - Norbert M. Linke A1 - Kenneth R. Brown A1 - Luming Duan A1 - Christopher R. Monroe AB -

Ion trap systems are a leading platform for large scale quantum computers. Trapped ion qubit crystals are fully-connected and reconfigurable, owing to their long range Coulomb interaction that can be modulated with external optical forces. However, the spectral crowding of collective motional modes could pose a challenge to the control of such interactions for large numbers of qubits. Here, we show that high-fidelity quantum gate operations are still possible with very large trapped ion crystals, simplifying the scaling of ion trap quantum computers. To this end, we present analytical work that determines how parallel entangling gates produce a crosstalk error that falls off as the inverse cube of the distance between the pairs. We also show experimental work demonstrating entangling gates on a fully-connected chain of seventeen 171Yb+ ions with fidelities as high as 97(1)%.

UR - https://arxiv.org/abs/1905.10421 ER - TY - JOUR T1 - Variational Quantum Computation of Excited States JF - Quantum Y1 - 2019 A1 - Oscar Higgott A1 - Daochen Wang A1 - Stephen Brierley AB -

The calculation of excited state energies of electronic structure Hamiltonians has many important applications, such as the calculation of optical spectra and reaction rates. While low-depth quantum algorithms, such as the variational quantum eigenvalue solver (VQE), have been used to determine ground state energies, methods for calculating excited states currently involve the implementation of high-depth controlled-unitaries or a large number of additional samples. Here we show how overlap estimation can be used to deflate eigenstates once they are found, enabling the calculation of excited state energies and their degeneracies. We propose an implementation that requires the same number of qubits as VQE and at most twice the circuit depth. Our method is robust to control errors, is compatible with error-mitigation strategies and can be implemented on near-term quantum compute

VL - 3 UR - https://arxiv.org/abs/1805.08138 CP - 156 U5 - https://doi.org/10.22331/q-2019-07-01-156 ER - TY - JOUR T1 - Verified Optimization in a Quantum Intermediate Representation Y1 - 2019 A1 - Kesha Hietala A1 - Robert Rand A1 - Shih-Han Hung A1 - Xiaodi Wu A1 - Michael Hicks AB -

We present sqire, a low-level language for quantum computing and verification. sqire uses a global register of quantum bits, allowing easy compilation to and from existing `quantum assembly' languages and simplifying the verification process. We demonstrate the power of sqire as an intermediate representation of quantum programs by verifying a number of useful optimizations, and we demonstrate sqire's use as a tool for general verification by proving several quantum programs correct.

UR - https://arxiv.org/abs/1904.06319 ER - TY - JOUR T1 - α-Logarithmic negativity Y1 - 2019 A1 - Xin Wang A1 - Mark M. Wilde AB -

The logarithmic negativity of a bipartite quantum state is a widely employed entanglement measure in quantum information theory, due to the fact that it is easy to compute and serves as an upper bound on distillable entanglement. More recently, the κ-entanglement of a bipartite state was shown to be the first entanglement measure that is both easily computable and operationally meaningful, being equal to the exact entanglement cost of a bipartite quantum state when the free operations are those that completely preserve the positivity of the partial transpose. In this paper, we provide a non-trivial link between these two entanglement measures, by showing that they are the extremes of an ordered family of α-logarithmic negativity entanglement measures, each of which is identified by a parameter α∈[1,∞]. In this family, the original logarithmic negativity is recovered as the smallest with α=1, and the κ-entanglement is recovered as the largest with α=∞. We prove that the α-logarithmic negativity satisfies the following properties: entanglement monotone, normalization, faithfulness, and subadditivity. We also prove that it is neither convex nor monogamous. Finally, we define the α-logarithmic negativity of a quantum channel as a generalization of the notion for quantum states, and we show how to generalize many of the concepts to arbitrary resource theories. 

UR - https://arxiv.org/abs/1904.10437 ER - TY - JOUR T1 - Black Hole Microstate Cosmology Y1 - 2018 A1 - Sean Cooper A1 - Moshe Rozali A1 - Brian Swingle A1 - Mark Van Raamsdonk A1 - Christopher Waddell A1 - David Wakeham AB -

In this note, we explore the possibility that certain high-energy holographic CFT states correspond to black hole microstates with a geometrical behind-the-horizon region, modelled by a portion of a second asymptotic region terminating at an end-of-the-world (ETW) brane. We study the time-dependent physics of this behind-the-horizon region, whose ETW boundary geometry takes the form of a closed FRW spacetime. We show that in many cases, this behind-the-horizon physics can be probed directly by looking at the time dependence of entanglement entropy for sufficiently large spatial CFT subsystems. We study in particular states defined via Euclidean evolution from conformal boundary states and give specific predictions for the behavior of the entanglement entropy in this case. We perform analogous calculations for the SYK model and find qualitative agreement with our expectations. A fascinating possibility is that for certain states, we might have gravity localized to the ETW brane as in the Randall-Sundrum II scenario for cosmology. In this case, the effective description of physics beyond the horizon could be a big bang/big crunch cosmology of the same dimensionality as the CFT. In this case, the d-dimensional CFT describing the black hole microstate would give a precise, microscopic description of the d-dimensional cosmological physics. 

UR - https://arxiv.org/abs/1810.10601 ER - TY - JOUR T1 - Bose Condensation of Photons Thermalized via Laser Cooling of Atoms Y1 - 2018 A1 - Chiao-Hsuan Wang A1 - Michael Gullans A1 - J. V. Porto A1 - William D. Phillips A1 - J. M. Taylor AB -

A Bose-Einstein condensate (BEC) is a quantum phase of matter achieved at low temperatures. Photons, one of the most prominent species of bosons, do not typically condense due to the lack of a particle number-conservation. We recently described a photon thermalization mechanism which gives rise to a grand canonical ensemble of light with effective photon number conservation between a subsystem and a particle reservoir. This mechanism occurs during Doppler laser cooling of atoms where the atoms serve as a temperature reservoir while the cooling laser photons serve as a particle reservoir. Here we address the question of the possibility of a BEC of photons in this laser cooling photon thermalization scenario and theoretically demonstrate that a Bose condensation of photons can be realized by cooling an ensemble of two-level atoms (realizable with alkaline earth atoms) inside a Fabry-Perot cavity.

UR - https://arxiv.org/abs/1809.07777 ER - TY - JOUR T1 - Coherent optical nano-tweezers for ultra-cold atoms Y1 - 2018 A1 - P. Bienias A1 - S. Subhankar A1 - Y. Wang A1 - T-C Tsui A1 - F. Jendrzejewski A1 - T. Tiecke A1 - G. Juzeliūnas A1 - L. Jiang A1 - S. L. Rolston A1 - J. V. Porto A1 - Alexey V. Gorshkov AB -

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

UR - https://arxiv.org/abs/1808.02487 ER - TY - JOUR T1 - Cryogenic Trapped-Ion System for Large Scale Quantum Simulation Y1 - 2018 A1 - G. Pagano A1 - P. W. Hess A1 - H. B. Kaplan A1 - W. L. Tan A1 - P. Richerme A1 - P. Becker A1 - A. Kyprianidis A1 - J. Zhang A1 - E. Birckelbaw A1 - M. R. Hernandez A1 - Y. Wu A1 - C. Monroe AB -

We present a cryogenic ion trapping system designed for large scale quantum simulation of spin models. Our apparatus is based on a segmented-blade ion trap enclosed in a 4 K cryostat, which enables us to routinely trap over 100 171Yb+ ions in a linear configuration for hours due to a low background gas pressure from differential cryo-pumping. We characterize the cryogenic vacuum by using trapped ion crystals as a pressure gauge, measuring both inelastic and elastic collision rates with the molecular background gas. We demonstrate nearly equidistant ion spacing for chains of up to 44 ions using anharmonic axial potentials. This reliable production and lifetime enhancement of large linear ion chains will enable quantum simulation of spin models that are intractable with classical computer modelling.

UR - https://arxiv.org/abs/1802.03118 ER - TY - JOUR T1 - Dark state optical lattice with sub-wavelength spatial structure JF - Phys. Rev. Lett. Y1 - 2018 A1 - Yang Wang A1 - Sarthak Subhankar A1 - Przemyslaw Bienias A1 - Mateusz Lacki A1 - Tsz-Chun Tsui A1 - Mikhail A. Baranov A1 - Alexey V. Gorshkov A1 - Peter Zoller A1 - James V. Porto A1 - Steven L. Rolston AB -

We report on the experimental realization of a conservative optical lattice for cold atoms with a subwavelength spatial structure. The potential is based on the nonlinear optical response of three-level atoms in laser-dressed dark states, which is not constrained by the diffraction limit of the light generating the potential. The lattice consists of a one-dimensional array of ultranarrow barriers with widths less than 10 nm, well below the wavelength of the lattice light, physically realizing a Kronig-Penney potential. We study the band structure and dissipation of this lattice and find good agreement with theoretical predictions. Even on resonance, the observed lifetimes of atoms trapped in the lattice are as long as 44 ms, nearly 105times the excited state lifetime, and could be further improved with more laser intensity. The potential is readily generalizable to higher dimensions and different geometries, allowing, for example, nearly perfect box traps, narrow tunnel junctions for atomtronics applications, and dynamically generated lattices with subwavelength spacings.

VL - 120 U4 - 083601 UR - https://link.aps.org/doi/10.1103/PhysRevLett.120.083601 U5 - 10.1103/PhysRevLett.120.083601 ER - TY - JOUR T1 - Dissipation induced dipole blockade and anti-blockade in driven Rydberg systems JF - Phys. Rev. A Y1 - 2018 A1 - Jeremy T. Young A1 - Thomas Boulier A1 - Eric Magnan A1 - Elizabeth A. Goldschmidt A1 - Ryan M. Wilson A1 - Steven L. Rolston A1 - James V. Porto A1 - Alexey V. Gorshkov AB -

We study theoretically and experimentally the competing blockade and antiblockade effects induced by spontaneously generated contaminant Rydberg atoms in driven Rydberg systems. These contaminant atoms provide a source of strong dipole-dipole interactions and play a crucial role in the system's behavior. We study this problem theoretically using two different approaches. The first is a cumulant expansion approximation, in which we ignore third-order and higher connected correlations. Using this approach for the case of resonant drive, a many-body blockade radius picture arises, and we find qualitative agreement with previous experimental results. We further predict that as the atomic density is increased, the Rydberg population's dependence on Rabi frequency will transition from quadratic to linear dependence at lower Rabi frequencies. We study this behavior experimentally by observing this crossover at two different atomic densities. We confirm that the larger density system has a smaller crossover Rabi frequency than the smaller density system. The second theoretical approach is a set of phenomenological inhomogeneous rate equations. We compare the results of our rate-equation model to the experimental observations [E. A. Goldschmidt et al.Phys. Rev. Lett. 116, 113001 (2016)] and find that these rate equations provide quantitatively good scaling behavior of the steady-state Rydberg population for both resonant and off-resonant drives.

VL - 97 U4 - 023424 UR - https://link.aps.org/doi/10.1103/PhysRevA.97.023424 U5 - 10.1103/PhysRevA.97.023424 ER - TY - JOUR T1 - Exact entanglement cost of quantum states and channels under PPT-preserving operations Y1 - 2018 A1 - Xin Wang A1 - Mark M. Wilde AB -

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

UR - https://arxiv.org/abs/1809.09592 ER - TY - JOUR T1 - Geometry of the quantum set of correlations JF - Physical Review A Y1 - 2018 A1 - Koon Tong Goh A1 - Jedrzej Kaniewski A1 - Elie Wolfe A1 - Tamás Vértesi A1 - Xingyao Wu A1 - Yu Cai A1 - Yeong-Cherng Liang A1 - Valerio Scarani AB -

It is well known that correlations predicted by quantum mechanics cannot be explained by any classical (local-realistic) theory. The relative strength of quantum and classical correlations is usually studied in the context of Bell inequalities, but this tells us little about the geometry of the quantum set of correlations. In other words, we do not have good intuition about what the quantum set actually looks like. In this paper we study the geometry of the quantum set using standard tools from convex geometry. We find explicit examples of rather counter-intuitive features in the simplest non-trivial Bell scenario (two parties, two inputs and two outputs) and illustrate them using 2-dimensional slice plots. We also show that even more complex features appear in Bell scenarios with more inputs or more parties. Finally, we discuss the limitations that the geometry of the quantum set imposes on the task of self-testing.

VL - 97 U4 - 022104 UR - https://journals.aps.org/pra/abstract/10.1103/PhysRevA.97.022104 CP - 2 U5 - 10.1103/PhysRevA.97.022104 ER - TY - JOUR T1 - Holographic Complexity of Einstein-Maxwell-Dilaton Gravity JF - J. High Energ. Phys. Y1 - 2018 A1 - Brian Swingle A1 - Yixu Wang AB -

We study the holographic complexity of Einstein-Maxwell-Dilaton gravity using the recently proposed "complexity = volume" and "complexity = action" dualities. The model we consider has a ground state that is represented in the bulk via a so-called hyperscaling violating geometry. We calculate the action growth of the Wheeler-DeWitt patch of the corresponding black hole solution at non-zero temperature and find that, in the presence of violations of hyperscaling, there is a parametric enhancement of the action growth rate. We partially match this behavior to simple tensor network models which can capture aspects of hyperscaling violation. We also exhibit the switchback effect in complexity growth using shockwave geometries and comment on a subtlety of our action calculations when the metric is discontinuous at a null surface.

VL - 106 UR - https://arxiv.org/abs/1712.09826 U5 - https://doi.org/10.1007/JHEP09(2018)106 ER - TY - JOUR T1 - Multiparty quantum data hiding with enhanced security and remote deletion Y1 - 2018 A1 - Xingyao Wu A1 - Jianxin Chen AB -

One of the applications of quantum technology is to use quantum states and measurements to communicate which offers more reliable security promises. Quantum data hiding, which gives the source party the ability of sharing data among multiple receivers and revealing it at a later time depending on his/her will, is one of the promising information sharing schemes which may address practical security issues. In this work, we propose a novel quantum data hiding protocol. By concatenating different subprotocols which apply to rather symmetric hiding scenarios, we cover a variety of more general hiding scenarios. We provide the general requirements for constructing such protocols and give explicit examples of encoding states for five parties. We also proved the security of the protocol in sense that the achievable information by unauthorized operations asymptotically goes to zero. In addition, due to the capability of the sender to manipulate his/her subsystem, the sender is able to abort the protocol remotely at any time before he/she reveals the information.

U4 - 5 UR - https://arxiv.org/abs/1804.01982 ER - TY - JOUR T1 - Optomechanical approach to controlling the temperature and chemical potential of light JF - Phys. Rev. A 97, 033850 Y1 - 2018 A1 - Chiao-Hsuan Wang A1 - J. M. Taylor AB -

Massless particles, including photons, are not conserved even at low energies and thus have no chemical potential. However, in driven systems, near equilibrium dynamics can lead to equilibration of photons with a finite number, describable using an effective chemical potential. Here we build upon this general concept with an implementation appropriate for a nonlinear photon-based quantum simulator. We consider how laser cooling of a well-isolated mechanical mode can provide an effective low-frequency bath for the quantum simulator system. We show that the use of auxiliary photon modes, coupled by the mechanical system, enables control of both the chemical potential, by drive frequency, and temperature, by drive amplitude, of the resulting photonic quantum simulator's grand canonical ensemble.

UR - https://arxiv.org/abs/1706.00789 U5 - https://doi.org/10.1103/PhysRevA.97.033850 ER - TY - JOUR T1 - Photon thermalization via laser cooling of atoms JF - Phys. Rev. A 98, 013834 Y1 - 2018 A1 - Chiao-Hsuan Wang A1 - Michael Gullans A1 - J. V. Porto A1 - William D. Phillips A1 - J. M. Taylor AB -

Laser cooling of atomic motion enables a wide variety of technological and scientific explorations using cold atoms. Here we focus on the effect of laser cooling on the photons instead of on the atoms. Specifically, we show that non-interacting photons can thermalize with the atoms to a grand canonical ensemble with a non-zero chemical potential. This thermalization is accomplished via scattering of light between different optical modes, mediated by the laser cooling process. While optically thin modes lead to traditional laser cooling of the atoms, the dynamics of multiple scattering in optically thick modes has been more challenging to describe. We find that in an appropriate set of limits, multiple scattering leads to thermalization of the light with the atomic motion in a manner that approximately conserves total photon number between the laser beams and optically thick modes. In this regime, the subsystem corresponding to the thermalized modes is describable by a grand canonical ensemble with a chemical potential set by the energy of a single laser photon. We consider realization of this regime using two-level atoms in Doppler cooling, and find physically realistic conditions for rare earth atoms. With the addition of photon-photon interactions, this system could provide a new platform for exploring many-body physics.

UR - https://arxiv.org/abs/1712.08643 U5 - https://doi.org/10.1103/PhysRevA.98.013834 ER - TY - JOUR T1 - QFlow lite dataset: A machine-learning approach to the charge states in quantum dot experiments JF - PLOS ONE Y1 - 2018 A1 - Justyna P. Zwolak A1 - Sandesh S. Kalantre A1 - Xingyao Wu A1 - Stephen Ragole A1 - J. M. Taylor AB -

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

VL - 13 U4 - e0205844 UR - https://arxiv.org/abs/1809.10018 CP - 10 U5 - https://doi.org/10.1371/journal.pone.0205844 ER - TY - JOUR T1 - Quantitative Robustness Analysis of Quantum Programs (Extended Version) JF - Proc. ACM Program. Lang. Y1 - 2018 A1 - Shih-Han Hung A1 - Kesha Hietala A1 - Shaopeng Zhu A1 - Mingsheng Ying A1 - Michael Hicks A1 - Xiaodi Wu AB -

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.

VL - 3 U4 - Article 31 UR - https://arxiv.org/abs/1811.03585 CP - POPL U5 - https://doi.org/10.1145/3290344 ER - TY - JOUR T1 - Quantum adiabatic optimization without heuristics Y1 - 2018 A1 - Michael Jarret A1 - Brad Lackey A1 - Aike Liu A1 - Kianna Wan AB -

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.

UR - https://arxiv.org/abs/1810.04686 ER - TY - JOUR T1 - Quantum Channel Simulation and the Channel's Smooth Max-Information Y1 - 2018 A1 - Kun Fang A1 - Xin Wang A1 - Marco Tomamichel A1 - Mario Berta AB -

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.

UR - https://arxiv.org/abs/1807.05354 ER - TY - JOUR T1 - Quantum field theory for the chiral clock transition in one spatial dimension JF - Phys. Rev. Y1 - 2018 A1 - Seth Whitsitt A1 - Rhine Samajdar A1 - Subir Sachdev AB -

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 ν.

VL - B U4 - 205118 UR - https://arxiv.org/abs/1808.07056 CP - 98 U5 - https://doi.org/10.1103/PhysRevB.98.205118 ER - TY - JOUR T1 - Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning JF - To appear at the 46th International Colloquium on Automata, Languages and Programming (ICALP 2019) Y1 - 2018 A1 - Fernando G. S. L. Brandão A1 - Amir Kalev A1 - Tongyang Li A1 - Cedric Yen-Yu Lin A1 - Krysta M. Svore A1 - Xiaodi Wu AB -

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.

UR - https://arxiv.org/abs/1710.02581 ER - TY - JOUR T1 - Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics JF - Proceedings of the 51st ACM Symposium on Theory of Computing Y1 - 2018 A1 - Andras Gilyen A1 - Yuan Su A1 - Guang Hao Low A1 - Nathan Wiebe AB -

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.

U4 - 193-204 UR - https://arxiv.org/abs/1806.01838 U5 - https://doi.org/10.1145/3313276.3316366 ER - TY - JOUR T1 - Recovery Map for Fermionic Gaussian Channels Y1 - 2018 A1 - Brian Swingle A1 - Yixu Wang AB -

A recovery map effectively cancels the action of a quantum operation to a partial or full extent. We study the Petz recovery map in the case where the quantum channel and input states are fermionic and Gaussian. Gaussian states are convenient because they are totally determined by their covariance matrix and because they form a closed set under so-called Gaussian channels. Using a Grassmann representation of fermionic Gaussian maps, we show that the Petz recovery map is also Gaussian and determine it explicitly in terms of the covariance matrix of the reference state and the data of the channel. As a by-product, we obtain a formula for the fidelity between two fermionic Gaussian states. We also discuss subtleties arising from the singularities of the involved matrices.

UR - https://arxiv.org/abs/1811.04956 ER - TY - JOUR T1 - Single-photon bound states in atomic ensembles Y1 - 2018 A1 - Yidan Wang A1 - Michael Gullans A1 - Antoine Browaeys A1 - J. V. Porto A1 - Darrick E. Chang A1 - Alexey V. Gorshkov AB -

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

UR - https://arxiv.org/abs/1809.01147 ER - TY - JOUR T1 - A spinor Bose-Einstein condensate phase-sensitive amplifier for SU(1,1) interferometry JF - Phys. Rev Y1 - 2018 A1 - J. P. Wrubel A1 - A. Schwettmann A1 - D. P. Fahey A1 - Z. Glassman A1 - H. K. Pechkis A1 - P. F. Griffin A1 - R. Barnett A1 - E. Tiesinga A1 - P. D. Lett AB -

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

VL - A 98 UR - https://arxiv.org/abs/1807.06676 CP - 023620 ER - TY - JOUR T1 - Study of radon reduction in gases for rare event search experiments Y1 - 2018 A1 - K. Pushkin A1 - C. Akerlof A1 - D. Anbajagane A1 - J. Armstrong A1 - M. Arthurs A1 - Jacob Bringewatt A1 - T. Edberg A1 - C. Hall A1 - M. Lei A1 - R. Raymond A1 - M. Reh A1 - D. Saini A1 - A. Sander A1 - J. Schaefer A1 - D. Seymour A1 - N. Swanson A1 - Y. Wang A1 - W. Lorenzon AB -

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

UR - https://arxiv.org/abs/1805.11306 U5 - https://doi.org/10.1016/j.nima.2018.06.076 ER - TY - JOUR T1 - Time-reversal of rank-one quantum strategy functions JF - Quantum Y1 - 2018 A1 - Yuan Su A1 - John Watrous AB -

The quantum strategy (or quantum combs) framework is a useful tool for reasoning about interactions among entities that process and exchange quantum information over the course of multiple turns. We prove a time-reversal property for a class of linear functions, defined on quantum strategy representations within this framework, that corresponds to the set of rank-one positive semidefinite operators on a certain space. This time-reversal property states that the maximum value obtained by such a function over all valid quantum strategies is also obtained when the direction of time for the function is reversed, despite the fact that the strategies themselves are generally not time reversible. An application of this fact is an alternative proof of a known relationship between the conditional min- and max-entropy of bipartite quantum states, along with generalizations of this relationship.

VL - 2 UR - https://arxiv.org/abs/1801.08491 CP - 98 U5 - https://doi.org/10.22331/q-2018-10-04-98 ER - TY - JOUR T1 - Two-Dimensional Dilaton Gravity Theory and Lattice Schwarzian Theory Y1 - 2018 A1 - Su-Kuan Chu A1 - Chen-Te Ma A1 - Chih-Hung Wu AB -
We report a holographic study of a two-dimensional dilaton gravity theory with the Dirichlet boundary condition for the cases of non-vanishing and vanishing cosmological constants. Our result shows that the boundary theory of the two-dimensional dilaton gravity theory with the Dirichlet boundary condition for the case of non-vanishing cosmological constants is the Schwarzian term coupled to a dilaton field, while for the case of vanishing cosmological constant, a theory does not have a kinetic term. We also include the higher derivative term R2, where R is the scalar curvature that is coupled to a dilaton field. We find that the form of the boundary theory is not modified perturbatively. Finally, we show that a lattice holographic picture is realized up to the second-order perturbation of boundary cut-off ε2 under a constant boundary dilaton field and the non-vanishing cosmological constant by identifying the lattice spacing a of a lattice Schwarzian theory with the boundary cut-off ε of the two-dimensional dilaton gravity theory. 
UR - https://arxiv.org/abs/1802.04599 ER - TY - JOUR T1 - Computational Notions of Quantum Min-Entropy Y1 - 2017 A1 - Yi-Hsiu Chen A1 - Kai-Min Chung A1 - Ching-Yi Lai A1 - Salil P. Vadhan A1 - Xiaodi Wu AB -

We initiate the study of computational entropy in the quantum setting. We investigate to what extent the classical notions of computational entropy generalize to the quantum setting, and whether quantum analogues of classical theorems hold. Our main results are as follows. (1) The classical Leakage Chain Rule for pseudoentropy can be extended to the case that the leakage information is quantum (while the source remains classical). Specifically, if the source has pseudoentropy at least k, then it has pseudoentropy at least k − ℓ conditioned on an ℓ- qubit leakage. (2) As an application of the Leakage Chain Rule, we construct the first quantum leakage-resilient stream-cipher in the bounded-quantum-storage model, assuming the existence of a quantum-secure pseudorandom generator. (3) We show that the general form of the classical Dense Model Theorem (interpreted as the equivalence between two definitions of pseudo-relativemin-entropy) does not extend to quantum states. Along the way, we develop quantum analogues of some classical techniques (e.g., the Leakage Simulation Lemma, which is proven by a Nonuniform Min-Max Theorem or Boosting). On the other hand, we also identify some classical techniques (e.g., Gap Amplification) that do not work in the quantum setting. Moreover, we introduce a variety of notions that combine quantum information and quantum complexity, and this raises several directions for future work.

UR - https://arxiv.org/abs/1704.07309 ER - TY - JOUR T1 - Efficient quantum algorithms for analyzing large sparse electrical networks JF - Quantum Information & Computation Y1 - 2017 A1 - Guoming Wang AB -

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

VL - 17 U4 - 987-1026 UR - https://arxiv.org/abs/1311.1851 CP - 11&12 ER - TY - JOUR T1 - Emergent equilibrium in many-body optical bistability JF - Physical Review A Y1 - 2017 A1 - Michael Foss-Feig A1 - Pradeep Niroula A1 - Jeremy T. Young A1 - Mohammad Hafezi A1 - Alexey V. Gorshkov A1 - Ryan M. Wilson A1 - Mohammad F. Maghrebi AB -

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

VL - 95 U4 - 043826 UR - https://journals.aps.org/pra/abstract/10.1103/PhysRevA.95.043826 U5 - doi.org/10.1103/PhysRevA.95.043826 ER - TY - JOUR T1 - Entanglement Wedge Reconstruction via Universal Recovery Channels Y1 - 2017 A1 - Jordan Cotler A1 - Patrick Hayden A1 - Geoffrey Penington A1 - Grant Salton A1 - Brian Swingle A1 - Michael Walter AB -

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

UR - https://arxiv.org/abs/1704.05839 ER - TY - Generic T1 - Experimental Comparison of Two Quantum Computing Architectures T2 - Proceedings of the National Academy of Sciences Y1 - 2017 A1 - N.M. Linke A1 - Dmitri Maslov A1 - Martin Roetteler A1 - S. Debnath A1 - C. Figgatt A1 - K. A. Landsman A1 - K. Wright A1 - Christopher Monroe AB -

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

JA - Proceedings of the National Academy of Sciences VL - 114 U4 - 3305-3310 UR - http://www.pnas.org/content/114/13/3305 U5 - 10.1073/pnas.1618020114 ER - TY - JOUR T1 - Exponential improvements for quantum-accessible reinforcement learning Y1 - 2017 A1 - Vedran Dunjko A1 - Yi-Kai Liu A1 - Xingyao Wu A1 - J. M. Taylor AB -

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

UR - https://arxiv.org/abs/1710.11160 ER - TY - JOUR T1 - Exponential Quantum Speed-ups for Semidefinite Programming with Applications to Quantum Learning Y1 - 2017 A1 - Fernando G. S. L. Brandão A1 - Amir Kalev A1 - Tongyang Li A1 - Cedric Yen-Yu Lin A1 - Krysta M. Svore A1 - Xiaodi Wu AB -

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

UR - https://arxiv.org/abs/1710.02581 ER - TY - JOUR T1 - Genuine N -partite entanglement without N -partite correlation functions JF - Physical Review A Y1 - 2017 A1 - Minh C. Tran A1 - Margherita Zuppardo A1 - Anna de Rosier A1 - Lukas Knips A1 - Wieslaw Laskowski A1 - Tomasz Paterek A1 - Harald Weinfurter AB -

A genuinely N-partite entangled state may display vanishing N-partite correlations measured for arbitrary local observables. In such states the genuine entanglement is noticeable solely in correlations between subsets of particles. A straightforward way to obtain such states for odd N is to design an “antistate” in which all correlations between an odd number of observers are exactly opposite. Evenly mixing a state with its antistate then produces a mixed state with no N-partite correlations, with many of them genuinely multiparty entangled. Intriguingly, all known examples of “entanglement without correlations” involve an odd number of particles. Here we further develop the idea of antistates, thereby shedding light on the different properties of even and odd particle systems. We conjecture that there is no antistate to any pure even-N-party entangled state making the simple construction scheme unfeasible. However, as we prove by construction, higher-rank examples of entanglement without correlations for arbitrary even N indeed exist. These classes of states exhibit genuine entanglement and even violate an N-partite Bell inequality, clearly demonstrating the nonclassical features of these states as well as showing their applicability for quantum information processing.

VL - 95 U4 - 062331 UR - https://journals.aps.org/pra/abstract/10.1103/PhysRevA.95.062331 CP - 6 U5 - doi.org/10.1103/PhysRevA.95.062331 ER - TY - JOUR T1 - Machine Learning techniques for state recognition and auto-tuning in quantum dots Y1 - 2017 A1 - Sandesh S. Kalantre A1 - Justyna P. Zwolak A1 - Stephen Ragole A1 - Xingyao Wu A1 - Neil M. Zimmerman A1 - M. D. Stewart A1 - J. M. Taylor AB -

Recent progress in building large-scale quantum devices for exploring quantum computing and simulation paradigms has relied upon effective tools for achieving and maintaining good experimental parameters, i.e. tuning up devices. In many cases, including in quantum-dot based architectures, the parameter space grows substantially with the number of qubits, and may become a limit to scalability. Fortunately, machine learning techniques for pattern recognition and image classification using so-called deep neural networks have shown surprising successes for computer-aided understanding of complex systems. In this work, we use deep and convolutional neural networks to characterize states and charge configurations of semiconductor quantum dot arrays when one can only measure a current-voltage characteristic of transport (here conductance) through such a device. For simplicity, we model a semiconductor nanowire connected to leads and capacitively coupled to depletion gates using the Thomas-Fermi approximation and Coulomb blockade physics. We then generate labeled training data for the neural networks, and find at least 90 % accuracy for charge and state identification for single and double dots purely from the dependence of the nanowire’s conductance upon gate voltages. Using these characterization networks, we can then optimize the parameter space to achieve a desired configuration of the array, a technique we call ‘auto-tuning’. Finally, we show how such techniques can be implemented in an experimental setting by applying our approach to an experimental data set, and outline further problems in this domain, from using charge sensing data to extensions to full one and two-dimensional arrays, that can be tackled with machine learning.

UR - https://arxiv.org/abs/1712.04914 ER - TY - JOUR T1 - Multicritical behavior in dissipative Ising models JF - Physical Review A Y1 - 2017 A1 - Vincent R. Overbeck A1 - Mohammad F. Maghrebi A1 - Alexey V. Gorshkov A1 - Hendrik Weimer AB -

We analyze theoretically the many-body dynamics of a dissipative Ising model in a transverse field using a variational approach. We find that the steady state phase diagram is substantially modified compared to its equilibrium counterpart, including the appearance of a multicritical point belonging to a different universality class. Building on our variational analysis, we establish a field-theoretical treatment corresponding to a dissipative variant of a Ginzburg-Landau theory, which allows us to compute the upper critical dimension of the system. Finally, we present a possible experimental realization of the dissipative Ising model using ultracold Rydberg gases.

VL - 95 U4 - 042133 UR - https://journals.aps.org/pra/abstract/10.1103/PhysRevA.95.042133 U5 - doi.org/10.1103/PhysRevA.95.042133 ER - TY - JOUR T1 - Quantum algorithm for linear differential equations with exponentially improved dependence on precision JF - Communications in Mathematical Physics Y1 - 2017 A1 - Dominic W. Berry A1 - Andrew M. Childs A1 - Aaron Ostrander A1 - Guoming Wang AB -

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.

VL - 356 U4 - 1057-1081 UR - https://arxiv.org/abs/1701.03684 CP - 3 ER - TY - JOUR T1 - Quantum Algorithm for Linear Regression JF - Physical Review A Y1 - 2017 A1 - Guoming Wang AB -

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.

VL - 96 U4 - 012335 UR - https://arxiv.org/abs/1402.0660 ER - TY - JOUR T1 - Quantum simulation of ferromagnetic Heisenberg model Y1 - 2017 A1 - Yiping Wang A1 - Minh C. Tran A1 - J. M. Taylor AB -

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.

UR - https://arxiv.org/abs/1712.05282 ER - TY - JOUR T1 - Raz-McKenzie simulation with the inner product gadget JF - Electronic Colloquium on Computational Complexity (ECCC) Y1 - 2017 A1 - Xiaodi Wu A1 - Penghui Yao A1 - Henry Yuen AB -

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions f composed with the Inner Product gadget 1ip(x, y) = P i xiyi mod 2 of logarithmic size. In other words, given a function f : {0, 1} n → {0, 1} with deterministic query complexity D(f), we show that the deterministic communication complexity of the composed function f ◦ 1 n ip is Θ(D(f) log n), where f ◦ 1 n ip(x, y) = f(1ip(x 1 , y 1 ), . . . , 1ip(x n , y n )) where x = (x 1 , . . . , x n ), y = (y 1 , . . . , y n ) and each x i and y i are O(log n) bit strings. In [RM97] and [GPW15], the simulation algorithm is implemented for functions composed with the Indexing gadget, where the size of the gadget is polynomial in the input length of the outer function f.

UR - https://eccc.weizmann.ac.il/report/2017/010/ ER - TY - JOUR T1 - Super-polynomial and exponential improvements for quantum-enhanced reinforcement learning Y1 - 2017 A1 - Vedran Dunjko A1 - Yi-Kai Liu A1 - Xingyao Wu A1 - J. M. Taylor AB -

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

UR - https://arxiv.org/abs/1710.11160 ER - TY - JOUR T1 - Collective phases of strongly interacting cavity photons JF - Physical Review A Y1 - 2016 A1 - Ryan M. Wilson A1 - Khan W. Mahmud A1 - Anzi Hu A1 - Alexey V. Gorshkov A1 - Mohammad Hafezi A1 - Michael Foss-Feig AB -

We study a coupled array of coherently driven photonic cavities, which maps onto a driven-dissipative XY spin-12 model with ferromagnetic couplings in the limit of strong optical nonlinearities. Using a site-decoupled mean-field approximation, we identify steady state phases with canted antiferromagnetic order, in addition to limit cycle phases, where oscillatory dynamics persist indefinitely. We also identify collective bistable phases, where the system supports two steady states among spatially uniform, antiferromagnetic, and limit cycle phases. We compare these mean-field results to exact quantum trajectories simulations for finite one-dimensional arrays. The exact results exhibit short-range antiferromagnetic order for parameters that have significant overlap with the mean-field phase diagram. In the mean-field bistable regime, the exact quantum dynamics exhibits real-time collective switching between macroscopically distinguishable states. We present a clear physical picture for this dynamics, and establish a simple relationship between the switching times and properties of the quantum Liouvillian.

VL - 94 U4 - 033801 UR - http://arxiv.org/abs/1601.06857 CP - 3 U5 - http://dx.doi.org/10.1103/PhysRevA.94.033801 ER - TY - JOUR T1 - Complexity of the XY antiferromagnet at fixed magnetization JF - Quantum Information and Computation Y1 - 2016 A1 - Andrew M. Childs A1 - David Gosset A1 - Zak Webb AB - We prove that approximating the ground energy of the antiferromagnetic XY model on a simple graph at fixed magnetization (given as part of the instance specification) is QMA-complete. To show this, we strengthen a previous result by establishing QMA-completeness for approximating the ground energy of the Bose-Hubbard model on simple graphs. Using a connection between the XY and Bose-Hubbard models that we exploited in previous work, this establishes QMA-completeness of the XY model. VL - 16 U4 - 1-18 UR - http://arxiv.org/abs/1503.07083v1 CP - 1-2 ER - TY - JOUR T1 - Demonstration of a small programmable quantum computer with atomic qubits JF - Nature Y1 - 2016 A1 - S. Debnath A1 - N. M. Linke A1 - C. Figgatt A1 - K. A. Landsman A1 - K. Wright A1 - C. Monroe AB -

Quantum computers can solve certain problems more efficiently than any possible conventional computer. Small quantum algorithms have been demonstrated on multiple quantum computing platforms, many specifically tailored in hardware to implement a particular algorithm or execute a limited number of computational paths. Here, we demonstrate a five-qubit trapped-ion quantum computer that can be programmed in software to implement arbitrary quantum algorithms by executing any sequence of universal quantum logic gates. We compile algorithms into a fully-connected set of gate operations that are native to the hardware and have a mean fidelity of 98 %. Reconfiguring these gate sequences provides the flexibility to implement a variety of algorithms without altering the hardware. As examples, we implement the Deutsch-Jozsa (DJ) and Bernstein-Vazirani (BV) algorithms with average success rates of 95 % and 90 %, respectively. We also perform a coherent quantum Fourier transform (QFT) on five trappedion qubits for phase estimation and period finding with average fidelities of 62 % and 84 %, respectively. This small quantum computer can be scaled to larger numbers of qubits within a single register, and can be further expanded by connecting several such modules through ion shuttling or photonic quantum channels.

VL - 536 U4 - 63-66 UR - http://www.nature.com/nature/journal/v536/n7614/full/nature18648.html CP - 7614 U5 - 10.1038/nature18648 ER - TY - JOUR T1 - Effective Field Theory for Rydberg Polaritons JF - Physical Review Letters Y1 - 2016 A1 - Michael Gullans A1 - J. D. Thompson A1 - Y. Wang A1 - Q. -Y. Liang A1 - V. Vuletic A1 - M. D. Lukin A1 - Alexey V. Gorshkov AB -

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

VL - 117 U4 - 113601 UR - http://arxiv.org/abs/1605.05651 CP - 11 U5 - http://dx.doi.org/10.1103/PhysRevLett.117.113601 ER - TY - JOUR T1 - High resolution adaptive imaging of a single atom JF - Nature Photonics Y1 - 2016 A1 - J. D. Wong-Campos A1 - K. G. Johnson A1 - Brian Neyenhuis A1 - J. Mizrahi A1 - Chris Monroe AB -

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

U4 - 606-610 UR - https://www.nature.com/nphoton/journal/v10/n9/full/nphoton.2016.136.html CP - 10 U5 - 10.1038/nphoton.2016.136 ER - TY - JOUR T1 - Landauer formulation of photon transport in driven systems JF - Physical Review B Y1 - 2016 A1 - Chiao-Hsuan Wang A1 - J. M. Taylor AB -

Understanding the behavior of light in non-equilibrium scenarios underpins much of quantum optics and optical physics. While lasers provide a severe example of a non-equilibrium problem, recent interests in the near-equilibrium physics of photon `gases', such as in Bose condensation of light or in attempts to make photonic quantum simulators, suggest one reexamine some near-equilibrium cases. Here we consider how a sinusoidal parametric coupling between two semi-infinite photonic transmission lines leads to the creation and flow of photons between the two lines. Our approach provides a photonic analogue to the Landauer transport formula, and using non-equilbrium Green's functions, we can extend it to the case of an interacting region between two photonic `leads' where the sinusoid frequency plays the role of a voltage bias. Crucially, we identify both the mathematical framework and the physical regime in which photonic transport is directly analogous to electronic transport, and regimes in which other new behavior such as two-mode squeezing can emerge.

VL - 94 U4 - 155437 UR - https://doi.org/10.1103/PhysRevB.94.155437 CP - 15 U5 - 10.1103/PhysRevB.94.155437 ER - TY - JOUR T1 - Multiple scattering dynamics of fermions at an isolated p-wave resonance JF - Nature Communications Y1 - 2016 A1 - Ryan Thomas A1 - Kris O. Roberts A1 - Eite Tiesinga A1 - Andrew C.J. Wade A1 - P. Blair Blakie A1 - Amita B. Deb A1 - Niels Kjærgaard AB -

The wavefunction for indistinguishable fermions is anti-symmetric under particle exchange, which directly leads to the Pauli exclusion principle, and hence underlies the structure of atoms and the properties of almost all materials. In the dynamics of collisions between two indistinguishable fermions this requirement strictly prohibits scattering into 90 degree angles. Here we experimentally investigate the collisions of ultracold clouds fermionic 40K atoms by directly measuring scattering distributions. With increasing collision energy we identify the Wigner threshold for p-wave scattering with its tell-tale dumb-bell shape and no 90 yield. Above this threshold effects of multiple scattering become manifest as deviations from the underlying binary p-wave shape, adding particles either isotropically or axially. A shape resonance for 40K facilitates the separate observation of these two processes. The isotropically enhanced multiple scattering mode is a generic p-wave threshold phenomenon, while the axially enhanced mode should occur in any colliding particle system with an elastic scattering resonance.

VL - 7 U4 - 12069 UR - http://www.nature.com/articles/ncomms12069 U5 - 10.1038/ncomms12069 ER - TY - JOUR T1 - A Quantum Model for an Entropic Spring JF - Physical Review B Y1 - 2016 A1 - Chiao-Hsuan Wang A1 - J. M. Taylor AB -

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.

VL - 93 U4 - 214102 UR - http://arxiv.org/abs/1507.08658v1 CP - 21 U5 - http://dx.doi.org/10.1103/PhysRevB.93.214102 ER - TY - JOUR T1 - Serialized Quantum Error Correction Protocol for High-Bandwidth Quantum Repeaters JF - New Journal of Physics Y1 - 2016 A1 - Andrew N. Glaudell A1 - Edo Waks A1 - J. M. Taylor AB -

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

VL - 18 U4 - 093008 UR - http://iopscience.iop.org/article/10.1088/1367-2630/18/9/093008/meta CP - 9 U5 - 10.1088/1367-2630/18/9/093008 ER - TY - JOUR T1 - Topological phases with long-range interactions JF - Physical Review B Y1 - 2016 A1 - Zhe-Xuan Gong A1 - Mohammad F. Maghrebi A1 - Anzi Hu A1 - Michael L. Wall A1 - Michael Foss-Feig A1 - Alexey V. Gorshkov AB - Topological phases of matter are primarily studied in quantum many-body systems with short-range interactions. Whether various topological phases can survive in the presence of long-range interactions, however, is largely unknown. Here we show that a paradigmatic example of a symmetry-protected topological phase, the Haldane phase of an antiferromagnetic spin-1 chain, surprisingly remains intact in the presence of arbitrarily slowly decaying power-law interactions. The influence of long-range interactions on the topological order is largely quantitative, and we expect similar results for more general systems. Our conclusions are based on large-scale matrix-product-state simulations and two complementary effective-field-theory calculations. The striking agreement between the numerical and analytical results rules out finite-size effects. The topological phase considered here should be experimentally observable in a recently developed trapped-ion quantum simulator. VL - 93 U4 - 041102 UR - http://arxiv.org/abs/1505.03146 CP - 4 U5 - 10.1103/PhysRevB.93.041102 ER - TY - JOUR T1 - 2D Superexchange mediated magnetization dynamics in an optical lattice JF - Science Y1 - 2015 A1 - R. C. Brown A1 - R. Wyllie A1 - S. B. Koller A1 - E. A. Goldschmidt A1 - Michael Foss-Feig A1 - J. V. Porto AB - The competition of magnetic exchange interactions and tunneling underlies many complex quantum phenomena observed in real materials. We study non-equilibrium magnetization dynamics in an extended 2D system by loading effective spin-1/2 bosons into a spin-dependent optical lattice, and we use the lattice to separately control the resonance conditions for tunneling and superexchange. After preparing a non-equilibrium anti-ferromagnetically ordered state, we observe relaxation dynamics governed by two well-separated rates, which scale with the underlying Hamiltonian parameters associated with superexchange and tunneling. Remarkably, with tunneling off-resonantly suppressed, we are able to observe superexchange dominated dynamics over two orders of magnitude in magnetic coupling strength, despite the presence of vacancies. In this regime, the measured timescales are in agreement with simple theoretical estimates, but the detailed dynamics of this 2D, strongly correlated, and far-from-equilibrium quantum system remain out of reach of current computational techniques. VL - 348 U4 - 540 - 544 UR - http://arxiv.org/abs/1411.7036v1 CP - 6234 J1 - Science U5 - 10.1126/science.aaa1385 ER - TY - JOUR T1 - Driving Rabi oscillations at the giant dipole resonance in xenon JF - Phys. Rev. A Y1 - 2015 A1 - Stefan Pabst A1 - Daochen Wang A1 - Robin Santra AB -

Free-electron lasers (FELs) produce short and very intense light pulses in the XUV and x-ray regimes. We investigate the possibility to drive Rabi oscillations in xenon with an intense FEL pulse by using the unusually large dipole strength of the giant-dipole resonance (GDR). The GDR decays within less than 30 as due to its position, which is above the 4d ionization threshold. We find that intensities around 1018 W/cm2 are required to induce Rabi oscillations with a period comparable to the lifetime. The pulse duration should not exceed 100 as because xenon will be fully ionized within a few lifetimes. Rabi oscillations reveal themselves also in the photoelectron spectrum in form of Autler-Townes splittings extending over several tens of electronvolt.

VL - 92 UR - https://arxiv.org/abs/1511.00058 CP - 053424 U5 - https://doi.org/10.1103/PhysRevA.92.053424 ER - TY - JOUR T1 - Entangling two transportable neutral atoms via local spin exchange JF - Nature Y1 - 2015 A1 - A. M. Kaufman A1 - B. J. Lester A1 - Michael Foss-Feig A1 - M. L. Wall A1 - A. M. Rey A1 - C. A. Regal AB - To advance quantum information science a constant pursuit is the search for physical systems that meet the stringent requirements for creating and preserving quantum entanglement. In atomic physics, robust two-qubit entanglement is typically achieved by strong, long-range interactions in the form of Coulomb interactions between ions or dipolar interactions between Rydberg atoms. While these interactions allow fast gates, atoms subject to these interactions must overcome the associated coupling to the environment and cross-talk among qubits. Local interactions, such as those requiring significant wavefunction overlap, can alleviate these detrimental effects yet present a new challenge: To distribute entanglement, qubits must be transported, merged for interaction, and then isolated for storage and subsequent operations. Here we show how, via a mobile optical tweezer, it is possible to prepare and locally entangle two ultracold neutral atoms, and then separate them while preserving their entanglement. While ultracold neutral atom experiments have measured dynamics consistent with spin entanglement, we are now able to demonstrate two-particle coherence via application of a local gradient and parity measurements; this new entanglement-verification protocol could be applied to arbitrary spin-entangled states of spatially-separated atoms. The local entangling operation is achieved via ultracold spin-exchange interactions, and quantum tunneling is used to combine and separate atoms. Our toolset provides a framework for dynamically entangling remote qubits via local operations within a large-scale quantum register. VL - 527 U4 - 208-211 UR - http://arxiv.org/abs/1507.05586 U5 - 10.1038/nature16073 ER - TY - JOUR T1 - Momentum switches JF - Quantum Information and Computation Y1 - 2015 A1 - Andrew M. Childs A1 - David Gosset A1 - Daniel Nagaj A1 - Mouktik Raha A1 - Zak Webb AB - Certain continuous-time quantum walks can be viewed as scattering processes. These processes can perform quantum computations, but it is challenging to design graphs with desired scattering behavior. In this paper, we study and construct momentum switches, graphs that route particles depending on their momenta. We also give an example where there is no exact momentum switch, although we construct an arbitrarily good approximation. VL - 15 U4 - 601-621 UR - http://arxiv.org/abs/1406.4510v1 CP - 7-8 J1 - Quantum Information and Computation 15 ER - TY - JOUR T1 - Tensor network non-zero testing JF - Quantum Information & Computation Y1 - 2015 A1 - Sevag Gharibian A1 - Zeph Landau A1 - Seung Woo Shin A1 - Guoming Wang AB - Tensor networks are a central tool in condensed matter physics. In this paper, we initiate the study of tensor network non-zero testing (TNZ): Given a tensor network T, does T represent a non-zero vector? We show that TNZ is not in the Polynomial-Time Hierarchy unless the hierarchy collapses. We next show (among other results) that the special cases of TNZ on non-negative and injective tensor networks are in NP. Using this, we make a simple observation: The commuting variant of the MA-complete stoquastic k-SAT problem on D-dimensional qudits is in NP for logarithmic k and constant D. This reveals the first class of quantum Hamiltonians whose commuting variant is known to be in NP for all (1) logarithmic k, (2) constant D, and (3) for arbitrary interaction graphs. VL - 15 U4 - 885-899 UR - http://arxiv.org/abs/1406.5279 CP - 9-10 ER - TY - JOUR T1 - The Bose-Hubbard model is QMA-complete JF - Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014) Y1 - 2014 A1 - Andrew M. Childs A1 - David Gosset A1 - Zak Webb AB - The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMA-complete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i.e., hard-core bosons). This feature, along with the well-known mapping between hard-core bosons and spin systems, lets us prove a related result for a class of 2-local Hamiltonians defined by graphs that generalizes the XY model. By avoiding the use of perturbation theory in our analysis, we circumvent the need to multiply terms in the Hamiltonian by large coefficients. VL - 8572 U4 - 308-319 UR - http://arxiv.org/abs/1311.3297v1 J1 - Proceedings of the 41st International Colloquium on Automata U5 - 10.1007/978-3-662-43948-7_26 ER - TY - JOUR T1 - Hong-Ou-Mandel atom interferometry in tunnel-coupled optical tweezers JF - Science Y1 - 2014 A1 - A. M. Kaufman A1 - B. J. Lester A1 - C. M. Reynolds A1 - M. L. Wall A1 - Michael Foss-Feig A1 - K. R. A. Hazzard A1 - A. M. Rey A1 - C. A. Regal AB - The quantum statistics of atoms is typically observed in the behavior of an ensemble via macroscopic observables. However, quantum statistics modifies the behavior of even two particles, inducing remarkable consequences that are at the heart of quantum science. Here we demonstrate near-complete control over all the internal and external degrees of freedom of two laser-cooled 87Rb atoms trapped in two optical tweezers. This full controllability allows us to implement a massive-particle analog of a Hong-Ou-Mandel interferometer where atom tunneling plays the role of a photon beamsplitter. We use the interferometer to probe the effect of quantum statistics on the two-atom dynamics under tunable initial conditions, chosen to adjust the degree of atomic indistinguishability. Our work thereby establishes laser-cooled atoms in optical tweezers as a new route to bottom-up engineering of scalable, low-entropy quantum systems. VL - 345 U4 - 306 - 309 UR - http://arxiv.org/abs/1312.7182v2 CP - 6194 J1 - Science U5 - 10.1126/science.1250057 ER - TY - JOUR T1 - Quantum Algorithms for Curve Fitting Y1 - 2014 A1 - Guoming Wang AB - We 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. UR - http://arxiv.org/abs/1402.0660 ER - TY - JOUR T1 - Suppressing the loss of ultracold molecules via the continuous quantum Zeno effect JF - Physical Review Letters Y1 - 2014 A1 - Bihui Zhu A1 - Bryce Gadway A1 - Michael Foss-Feig A1 - Johannes Schachenmayer A1 - Michael Wall A1 - Kaden R. A. Hazzard A1 - Bo Yan A1 - Steven A. Moses A1 - Jacob P. Covey A1 - Deborah S. Jin A1 - Jun Ye A1 - Murray Holland A1 - Ana Maria Rey AB - We investigate theoretically the suppression of two-body losses when the on-site loss rate is larger than all other energy scales in a lattice. This work quantitatively explains the recently observed suppression of chemical reactions between two rotational states of fermionic KRb molecules confined in one-dimensional tubes with a weak lattice along the tubes [Yan et al., Nature 501, 521-525 (2013)]. New loss rate measurements performed for different lattice parameters but under controlled initial conditions allow us to show that the loss suppression is a consequence of the combined effects of lattice confinement and the continuous quantum Zeno effect. A key finding, relevant for generic strongly reactive systems, is that while a single-band theory can qualitatively describe the data, a quantitative analysis must include multiband effects. Accounting for these effects reduces the inferred molecule filling fraction by a factor of five. A rate equation can describe much of the data, but to properly reproduce the loss dynamics with a fixed filling fraction for all lattice parameters we develop a mean-field model and benchmark it with numerically exact time-dependent density matrix renormalization group calculations. VL - 112 UR - http://arxiv.org/abs/1310.2221v2 CP - 7 J1 - Phys. Rev. Lett. U5 - 10.1103/PhysRevLett.112.070404 ER - TY - JOUR T1 - Controllable quantum spin glasses with magnetic impurities embedded in quantum solids JF - Physical Review B Y1 - 2013 A1 - Mikhail Lemeshko A1 - Norman Y. Yao A1 - Alexey V. Gorshkov A1 - Hendrik Weimer A1 - Steven D. Bennett A1 - Takamasa Momose A1 - Sarang Gopalakrishnan AB - Magnetic impurities embedded in inert solids can exhibit long coherence times and interact with one another via their intrinsic anisotropic dipolar interaction. We argue that, as a consequence of these properties, disordered ensembles of magnetic impurities provide an effective platform for realizing a controllable, tunable version of the dipolar quantum spin glass seen in LiHo$_x$Y$_{1-x}$F$_4$. Specifically, we propose and analyze a system composed of dysprosium atoms embedded in solid helium. We describe the phase diagram of the system and discuss the realizability and detectability of the quantum spin glass and antiglass phases. VL - 88 UR - http://arxiv.org/abs/1307.1130v1 CP - 1 J1 - Phys. Rev. B U5 - 10.1103/PhysRevB.88.014426 ER - TY - JOUR T1 - Optimal entanglement-assisted one-shot classical communication JF - Physical Review A Y1 - 2013 A1 - Hemenway, Brett A1 - Carl Miller A1 - Shi, Yaoyun A1 - Wootters, Mary AB -

The one-shot success probability of a noisy classical channel for transmitting one classical bit is the optimal probability with which the bit can be successfully sent via a single use of the channel. Prevedel et al. [Phys. Rev. Lett. 106, 110505 (2011)] recently showed that for a specific channel, this quantity can be increased if the parties using the channel share an entangled quantum state. In this paper, we characterize the optimal entanglement-assisted protocols in terms of the radius of a set of operators associated with the channel. This characterization can be used to construct optimal entanglement-assisted protocols for a given classical channel and to prove the limits of such protocols. As an example, we show that the Prevedel et al. protocol is optimal for two-qubit entanglement. We also prove some tight upper bounds on the improvement that can be obtained from quantum and nonsignaling correlations.

VL - 87 U4 - 062301 UR - http://link.aps.org/doi/10.1103/PhysRevA.87.062301 U5 - 10.1103/PhysRevA.87.062301 ER - TY - JOUR T1 - Product Formulas for Exponentials of Commutators JF - Journal of Mathematical Physics Y1 - 2013 A1 - Andrew M. Childs A1 - Nathan Wiebe AB - We provide a recursive method for constructing product formula approximations to exponentials of commutators, giving the first approximations that are accurate to arbitrarily high order. Using these formulas, we show how to approximate unitary exponentials of (possibly nested) commutators using exponentials of the elementary operators, and we upper bound the number of elementary exponentials needed to implement the desired operation within a given error tolerance. By presenting an algorithm for quantum search using evolution according to a commutator, we show that the scaling of the number of exponentials in our product formulas with the evolution time is nearly optimal. Finally, we discuss applications of our product formulas to quantum control and to implementing anticommutators, providing new methods for simulating many-body interaction Hamiltonians. VL - 54 U4 - 062202 UR - http://arxiv.org/abs/1211.4945v2 CP - 6 J1 - J. Math. Phys. U5 - 10.1063/1.4811386 ER - TY - JOUR T1 - Spinor dynamics in an antiferromagnetic spin-1 thermal Bose gas JF - Physical Review Letters Y1 - 2013 A1 - Hyewon K. Pechkis A1 - Jonathan P. Wrubel A1 - Arne Schwettmann A1 - Paul F. Griffin A1 - Ryan Barnett A1 - Eite Tiesinga A1 - Paul D. Lett AB - We present experimental observations of coherent spin-population oscillations in a cold thermal, Bose gas of spin-1 sodium-23 atoms. The population oscillations in a multi-spatial-mode thermal gas have the same behavior as those observed in a single-spatial-mode antiferromagnetic spinor Bose Einstein condensate. We demonstrate this by showing that the two situations are described by the same dynamical equations, with a factor of two change in the spin-dependent interaction coefficient, which results from the change to particles with distinguishable momentum states in the thermal gas. We compare this theory to the measured spin population evolution after times up to a few hundreds of ms, finding quantitative agreement with the amplitude and period. We also measure the damping time of the oscillations as a function of magnetic field. VL - 111 UR - http://arxiv.org/abs/1306.4255v1 CP - 2 J1 - Phys. Rev. Lett. U5 - 10.1103/PhysRevLett.111.025301 ER - TY - JOUR T1 - Symmetries of Codeword Stabilized Quantum Codes JF - 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013) Y1 - 2013 A1 - Salman Beigi A1 - Jianxin Chen A1 - Markus Grassl A1 - Zhengfeng Ji A1 - Qiang Wang A1 - Bei Zeng AB - Symmetry is at the heart of coding theory. Codes with symmetry, especially cyclic codes, play an essential role in both theory and practical applications of classical error-correcting codes. Here we examine symmetry properties for codeword stabilized (CWS) quantum codes, which is the most general framework for constructing quantum error-correcting codes known to date. A CWS code Q can be represented by a self-dual additive code S and a classical code C, i.,e., Q=(S,C), however this representation is in general not unique. We show that for any CWS code Q with certain permutation symmetry, one can always find a self-dual additive code S with the same permutation symmetry as Q such that Q=(S,C). As many good CWS codes have been found by starting from a chosen S, this ensures that when trying to find CWS codes with certain permutation symmetry, the choice of S with the same symmetry will suffice. A key step for this result is a new canonical representation for CWS codes, which is given in terms of a unique decomposition as union stabilizer codes. For CWS codes, so far mainly the standard form (G,C) has been considered, where G is a graph state. We analyze the symmetry of the corresponding graph of G, which in general cannot possess the same permutation symmetry as Q. We show that it is indeed the case for the toric code on a square lattice with translational symmetry, even if its encoding graph can be chosen to be translational invariant. VL - 22 U4 - 192-206 UR - http://arxiv.org/abs/1303.7020v2 U5 - 10.4230/LIPIcs.TQC.2013.192 ER - TY - JOUR T1 - Testing quantum expanders is co-QMA-complete JF - Physical Review A Y1 - 2013 A1 - Adam D. Bookatz A1 - Stephen P. Jordan A1 - Yi-Kai Liu A1 - Pawel Wocjan AB - A quantum expander is a unital quantum channel that is rapidly mixing, has only a few Kraus operators, and can be implemented efficiently on a quantum computer. We consider the problem of estimating the mixing time (i.e., the spectral gap) of a quantum expander. We show that this problem is co-QMA-complete. This has applications to testing randomized constructions of quantum expanders, and studying thermalization of open quantum systems. VL - 87 UR - http://arxiv.org/abs/1210.0787v2 CP - 4 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.87.042317 ER - TY - JOUR T1 - Topologically Protected Quantum State Transfer in a Chiral Spin Liquid JF - Nature Communications Y1 - 2013 A1 - Norman Y. Yao A1 - Chris R. Laumann A1 - Alexey V. Gorshkov A1 - Hendrik Weimer A1 - Liang Jiang A1 - J. Ignacio Cirac A1 - Peter Zoller A1 - Mikhail D. Lukin AB - Topology plays a central role in ensuring the robustness of a wide variety of physical phenomena. Notable examples range from the robust current carrying edge states associated with the quantum Hall and the quantum spin Hall effects to proposals involving topologically protected quantum memory and quantum logic operations. Here, we propose and analyze a topologically protected channel for the transfer of quantum states between remote quantum nodes. In our approach, state transfer is mediated by the edge mode of a chiral spin liquid. We demonstrate that the proposed method is intrinsically robust to realistic imperfections associated with disorder and decoherence. Possible experimental implementations and applications to the detection and characterization of spin liquid phases are discussed. VL - 4 U4 - 1585 UR - http://arxiv.org/abs/1110.3788v1 J1 - Nat Comms U5 - 10.1038/ncomms2531 ER - TY - JOUR T1 - Universal computation by multi-particle quantum walk JF - Science Y1 - 2013 A1 - Andrew M. Childs A1 - David Gosset A1 - Zak Webb AB - A quantum walk is a time-homogeneous quantum-mechanical process on a graph defined by analogy to classical random walk. The quantum walker is a particle that moves from a given vertex to adjacent vertices in quantum superposition. Here we consider a generalization of quantum walk to systems with more than one walker. A continuous-time multi-particle quantum walk is generated by a time-independent Hamiltonian with a term corresponding to a single-particle quantum walk for each particle, along with an interaction term. Multi-particle quantum walk includes a broad class of interacting many-body systems such as the Bose-Hubbard model and systems of fermions or distinguishable particles with nearest-neighbor interactions. We show that multi-particle quantum walk is capable of universal quantum computation. Since it is also possible to efficiently simulate a multi-particle quantum walk of the type we consider using a universal quantum computer, this model exactly captures the power of quantum computation. In principle our construction could be used as an architecture for building a scalable quantum computer with no need for time-dependent control. VL - 339 U4 - 791 - 794 UR - http://arxiv.org/abs/1205.3782v2 CP - 6121 J1 - Science U5 - 10.1126/science.1229957 ER - TY - JOUR T1 - Correlations in excited states of local Hamiltonians JF - Physical Review A Y1 - 2012 A1 - Jianxin Chen A1 - Zhengfeng Ji A1 - Zhaohui Wei A1 - Bei Zeng AB - Physical properties of the ground and excited states of a $k$-local Hamiltonian are largely determined by the $k$-particle reduced density matrices ($k$-RDMs), or simply the $k$-matrix for fermionic systems---they are at least enough for the calculation of the ground state and excited state energies. Moreover, for a non-degenerate ground state of a $k$-local Hamiltonian, even the state itself is completely determined by its $k$-RDMs, and therefore contains no genuine ${>}k$-particle correlations, as they can be inferred from $k$-particle correlation functions. It is natural to ask whether a similar result holds for non-degenerate excited states. In fact, for fermionic systems, it has been conjectured that any non-degenerate excited state of a 2-local Hamiltonian is simultaneously a unique ground state of another 2-local Hamiltonian, hence is uniquely determined by its 2-matrix. And a weaker version of this conjecture states that any non-degenerate excited state of a 2-local Hamiltonian is uniquely determined by its 2-matrix among all the pure $n$-particle states. We construct explicit counterexamples to show that both conjectures are false. It means that correlations in excited states of local Hamiltonians could be dramatically different from those in ground states. We further show that any non-degenerate excited state of a $k$-local Hamiltonian is a unique ground state of another $2k$-local Hamiltonian, hence is uniquely determined by its $2k$-RDMs (or $2k$-matrix). VL - 85 UR - http://arxiv.org/abs/1106.1373v2 CP - 4 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.85.040303 ER - TY - JOUR T1 - Ground-State Spaces of Frustration-Free Hamiltonians JF - Journal of Mathematical Physics Y1 - 2012 A1 - Jianxin Chen A1 - Zhengfeng Ji A1 - David Kribs A1 - Zhaohui Wei A1 - Bei Zeng AB - We study the ground-state space properties for frustration-free Hamiltonians. We introduce a concept of `reduced spaces' to characterize local structures of ground-state spaces. For a many-body system, we characterize mathematical structures for the set $\Theta_k$ of all the $k$-particle reduced spaces, which with a binary operation called join forms a semilattice that can be interpreted as an abstract convex structure. The smallest nonzero elements in $\Theta_k$, called atoms, are analogs of extreme points. We study the properties of atoms in $\Theta_k$ and discuss its relationship with ground states of $k$-local frustration-free Hamiltonians. For spin-1/2 systems, we show that all the atoms in $\Theta_2$ are unique ground states of some 2-local frustration-free Hamiltonians. Moreover, we show that the elements in $\Theta_k$ may not be the join of atoms, indicating a richer structure for $\Theta_k$ beyond the convex structure. Our study of $\Theta_k$ deepens the understanding of ground-state space properties for frustration-free Hamiltonians, from a new angle of reduced spaces. VL - 53 U4 - 102201 UR - http://arxiv.org/abs/1112.0762v1 CP - 10 J1 - J. Math. Phys. U5 - 10.1063/1.4748527 ER - TY - JOUR T1 - Hamiltonian Simulation Using Linear Combinations of Unitary Operations JF - Quantum Information and Computation Y1 - 2012 A1 - Andrew M. Childs A1 - Nathan Wiebe AB - We present a new approach to simulating Hamiltonian dynamics based on implementing linear combinations of unitary operations rather than products of unitary operations. The resulting algorithm has superior performance to existing simulation algorithms based on product formulas and, most notably, scales better with the simulation error than any known Hamiltonian simulation technique. Our main tool is a general method to nearly deterministically implement linear combinations of nearby unitary operations, which we show is optimal among a large class of methods. VL - 12 U4 - 901-924 UR - http://arxiv.org/abs/1202.5822v1 CP - 11-12 J1 - Quantum Information and Computation 12 ER - TY - JOUR T1 - Non-Additivity of the Entanglement of Purification (Beyond Reasonable Doubt) Y1 - 2012 A1 - Jianxin Chen A1 - Andreas Winter AB - We demonstrate the convexity of the difference between the regularized entanglement of purification and the entropy, as a function of the state. This is proved by means of a new asymptotic protocol to prepare a state from pre-shared entanglement and by local operations only. We go on to employ this convexity property in an investigation of the additivity of the (single-copy) entanglement of purification: using numerical results for two-qubit Werner states we find strong evidence that the entanglement of purification is different from its regularization, hence that entanglement of purification is not additive. UR - http://arxiv.org/abs/1206.1307v1 ER - TY - JOUR T1 - Photonic quantum simulation of ground state configurations of Heisenberg square and checkerboard lattice spin systems Y1 - 2012 A1 - Xiao-song Ma A1 - Borivoje Dakic A1 - Sebastian Kropatsche A1 - William Naylor A1 - Yang-hao Chan A1 - Zhe-Xuan Gong A1 - Lu-ming Duan A1 - Anton Zeilinger A1 - Philip Walther AB - Photonic quantum simulators are promising candidates for providing insight into other small- to medium-sized quantum systems. The available photonic quantum technology is reaching the state where significant advantages arise for the quantum simulation of interesting questions in Heisenberg spin systems. Here we experimentally simulate such spin systems with single photons and linear optics. The effective Heisenberg-type interactions among individual single photons are realized by quantum interference at the tunable direction coupler followed by the measurement process. The effective interactions are characterized by comparing the entanglement dynamics using pairwise concurrence of a four-photon quantum system. We further show that photonic quantum simulations of generalized Heisenberg interactions on a four-site square lattice and a six-site checkerboard lattice are in reach of current technology. UR - http://arxiv.org/abs/1205.2801v1 ER - TY - JOUR T1 - Quantum interface between an electrical circuit and a single atom JF - Physical Review Letters Y1 - 2012 A1 - D. Kielpinski A1 - D. Kafri A1 - M. J. Woolley A1 - G. J. Milburn A1 - J. M. Taylor AB - We 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. VL - 108 UR - http://arxiv.org/abs/1111.5999v1 CP - 13 J1 - Phys. Rev. Lett. U5 - 10.1103/PhysRevLett.108.130504 ER - TY - JOUR T1 - Chern numbers hiding in time-of-flight images JF - Physical Review A Y1 - 2011 A1 - Erhai Zhao A1 - Noah Bray-Ali A1 - Carl J. Williams A1 - I. B. Spielman A1 - Indubala I. Satija AB - We present a technique for detecting topological invariants -- Chern numbers -- from time-of-flight images of ultra-cold atoms. We show that the Chern numbers of integer quantum Hall states of lattice fermions leave their fingerprints in the atoms' momentum distribution. We analytically demonstrate that the number of local maxima in the momentum distribution is equal to the Chern number in two limiting cases, for large hopping anisotropy and in the continuum limit. In addition, our numerical simulations beyond these two limits show that these local maxima persist for a range of parameters. Thus, an everyday observable in cold atom experiments can serve as a useful tool to characterize and visualize quantum states with non-trivial topology. VL - 84 UR - http://arxiv.org/abs/1105.3100v3 CP - 6 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.84.063629 ER - TY - JOUR T1 - Detecting paired and counterflow superfluidity via dipole oscillations JF - Physical Review A Y1 - 2011 A1 - Anzi Hu A1 - L. Mathey A1 - Eite Tiesinga A1 - Ippei Danshita A1 - Carl J. Williams A1 - Charles W. Clark AB - We suggest an experimentally feasible procedure to observe paired and counterflow superfluidity in ultra-cold atom systems. We study the time evolution of one-dimensional mixtures of bosonic atoms in an optical lattice following an abrupt displacement of an additional weak confining potential. We find that the dynamic responses of the paired superfluid phase for attractive inter-species interactions and the counterflow superfluid phase for repulsive interactions are qualitatively distinct and reflect the quasi long-range order that characterizes these states. These findings suggest a clear experimental procedure to detect these phases, and give an intuitive insight into their dynamics. VL - 84 UR - http://arxiv.org/abs/1103.3513v3 CP - 4 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.84.041609 ER - TY - JOUR T1 - Far-field optical imaging and manipulation of individual spins with nanoscale resolution JF - Nature Phys. Y1 - 2010 A1 - Maurer, P C A1 - Maze, J R A1 - Stanwix, P L A1 - Jiang, L A1 - Alexey V. Gorshkov A1 - Zibrov, A A A1 - Harke, B A1 - Hodges, J S A1 - Zibrov, A S A1 - Yacoby, A A1 - Twitchen, D A1 - Hell, S W A1 - Walsworth, R L A1 - Lukin, M D VL - 6 U4 - 912 UR - http://www.nature.com/nphys/journal/v6/n11/abs/nphys1774.html ER - TY - JOUR T1 - Noise correlations of one-dimensional Bose mixtures in optical lattices JF - Physical Review A Y1 - 2010 A1 - Anzi Hu A1 - L. Mathey A1 - Carl J. Williams A1 - Charles W. Clark AB - We study the noise correlations of one-dimensional binary Bose mixtures, as a probe of their quantum phases. In previous work, we found a rich structure of many-body phases in such mixtures, such as paired and counterflow superfluidity. Here we investigate the signature of these phases in the noise correlations of the atomic cloud after time-of-flight expansion, using both Luttinger liquid theory and the time-evolving block decimation (TEBD) method. We find that paired and counterflow superfluidity exhibit distinctive features in the noise spectra. We treat both extended and inhomogeneous systems, and our numerical work shows that the essential physics of the extended systems is present in the trapped-atom systems of current experimental interest. For paired and counterflow superfluid phases, we suggest methods for extracting Luttinger parameters from noise correlation spectroscopy. VL - 81 UR - http://arxiv.org/abs/1002.4918v2 CP - 6 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.81.063602 ER - TY - JOUR T1 - Counterflow and paired superfluidity in one-dimensional Bose mixtures in optical lattices JF - Physical Review A Y1 - 2009 A1 - Anzi Hu A1 - L. Mathey A1 - Ippei Danshita A1 - Eite Tiesinga A1 - Carl J. Williams A1 - Charles W. Clark AB - We study the quantum phases of mixtures of ultra-cold bosonic atoms held in an optical lattice that confines motion or hopping to one spatial dimension. The phases are found by using Tomonaga-Luttinger liquid theory as well as the numerical method of time evolving block decimation (TEBD). We consider a binary mixture with repulsive intra-species interactions, and either repulsive or attractive inter-species interaction. For a homogeneous system, we find paired- and counterflow-superfluid phases at different filling and hopping energies. We also predict parameter regions in which these types of superfluid order coexist with charge density wave order. We show that the Tomonaga-Luttinger liquid theory and TEBD qualitatively agree on the location of the phase boundary to superfluidity. We then describe how these phases are modified and can be detected when an additional harmonic trap is present. In particular, we show how experimentally measurable quantities, such as time-of-flight images and the structure factor, can be used to distinguish the quantum phases. Finally, we suggest applying a Feshbach ramp to detect the paired superfluid state, and a $\pi/2$ pulse followed by Bragg spectroscopy to detect the counterflow superfluid phase. VL - 80 UR - http://arxiv.org/abs/0906.2150v1 CP - 2 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.80.023619 ER - TY - JOUR T1 - Efficient quantum circuits for arbitrary sparse unitaries JF - Physical Review A Y1 - 2009 A1 - Stephen P. Jordan A1 - Pawel Wocjan AB - Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided it has at most polynomially many nonzero entries in any row or column, and these entries are efficiently computable. One can formulate a model of computation based on the composition of sparse unitaries which includes the quantum Turing machine model, the quantum circuit model, anyonic models, permutational quantum computation, and discrete time quantum walks as special cases. Thus we obtain a simple unified proof that these models are all contained in BQP. Furthermore our general method for implementing sparse unitaries simplifies several existing quantum algorithms. VL - 80 UR - http://arxiv.org/abs/0904.2211v2 CP - 6 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.80.062301 ER - TY - JOUR T1 - Efficient quantum processing of ideals in finite rings Y1 - 2009 A1 - Pawel M. Wocjan A1 - Stephen P. Jordan A1 - Hamed Ahmadi A1 - Joseph P. Brennan AB - Suppose we are given black-box access to a finite ring R, and a list of generators for an ideal I in R. We show how to find an additive basis representation for I in poly(log |R|) time. This generalizes a recent quantum algorithm of Arvind et al. which finds a basis representation for R itself. We then show that our algorithm is a useful primitive allowing quantum computers to rapidly solve a wide variety of problems regarding finite rings. In particular we show how to test whether two ideals are identical, find their intersection, find their quotient, prove whether a given ring element belongs to a given ideal, prove whether a given element is a unit, and if so find its inverse, find the additive and multiplicative identities, compute the order of an ideal, solve linear equations over rings, decide whether an ideal is maximal, find annihilators, and test the injectivity and surjectivity of ring homomorphisms. These problems appear to be hard classically. UR - http://arxiv.org/abs/0908.0022v1 ER - TY - JOUR T1 - Entanglement Cost of Nonlocal Measurements JF - Physical Review A Y1 - 2009 A1 - Somshubhro Bandyopadhyay A1 - Gilles Brassard A1 - Shelby Kimmel A1 - William K. Wootters AB - For certain joint measurements on a pair of spatially separated particles, we ask how much entanglement is needed to carry out the measurement exactly. For a class of orthogonal measurements on two qubits with partially entangled eigenstates, we present upper and lower bounds on the entanglement cost. The upper bound is based on a recent result by D. Berry [Phys. Rev. A 75, 032349 (2007)]. The lower bound, based on the entanglement production capacity of the measurement, implies that for almost all measurements in the class we consider, the entanglement required to perform the measurement is strictly greater than the average entanglement of its eigenstates. On the other hand, we show that for any complete measurement in d x d dimensions that is invariant under all local Pauli operations, the cost of the measurement is exactly equal to the average entanglement of the states associated with the outcomes. VL - 80 UR - http://arxiv.org/abs/0809.2264v4 CP - 1 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.80.012313 ER - TY - JOUR T1 - Estimating Jones and HOMFLY polynomials with One Clean Qubit JF - Quantum Information and Computation Y1 - 2009 A1 - Stephen P. Jordan A1 - Pawel Wocjan AB -

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

VL - 9 U4 - 264-289 UR - http://dl.acm.org/citation.cfm?id=2011787 CP - 3 ER - TY - JOUR T1 - Protocol for Hybrid Entanglement Between a Trapped Atom and a Semiconductor Quantum Dot JF - Physical Review A Y1 - 2009 A1 - Edo Waks A1 - Christopher Monroe AB - We propose a quantum optical interface between an atomic and solid state system. We show that quantum states in a single trapped atom can be entangled with the states of a semiconductor quantum dot through their common interaction with a classical laser field. The interference and detection of the resulting scattered photons can then herald the entanglement of the disparate atomic and solid-state quantum bits. We develop a protocol that can succeed despite a significant mismatch in the radiative characteristics of the two matter-based qubits. We study in detail a particular case of this interface applied to a single trapped \Yb ion and a cavity-coupled InGaAs semiconductor quantum dot. Entanglement fidelity and success rates are found to be robust to a broad range of experimental nonideal effects such as dispersion mismatch, atom recoil, and multi-photon scattering. We conclude that it should be possible to produce highly entangled states of these complementary qubit systems under realistic experimental conditions. VL - 80 UR - http://arxiv.org/abs/0907.0444v1 CP - 6 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.80.062330 ER - TY - JOUR T1 - High-sensitivity diamond magnetometer with nanoscale resolution JF - Nature Physics Y1 - 2008 A1 - J. M. Taylor A1 - P. Cappellaro A1 - L. Childress A1 - L. Jiang A1 - D. Budker A1 - P. R. Hemmer A1 - A. Yacoby A1 - R. Walsworth A1 - M. D. Lukin AB - We present a novel approach to the detection of weak magnetic fields that takes advantage of recently developed techniques for the coherent control of solid-state electron spin quantum bits. Specifically, we investigate a magnetic sensor based on Nitrogen-Vacancy centers in room-temperature diamond. We discuss two important applications of this technique: a nanoscale magnetometer that could potentially detect precession of single nuclear spins and an optical magnetic field imager combining spatial resolution ranging from micrometers to millimeters with a sensitivity approaching few femtotesla/Hz$^{1/2}$. VL - 4 U4 - 810 - 816 UR - http://arxiv.org/abs/0805.1367v1 CP - 10 J1 - Nat Phys U5 - 10.1038/nphys1075 ER - TY - JOUR T1 - Multilevel effects in the Rabi oscillations of a Josephson phase qubit JF - Physical Review B Y1 - 2008 A1 - S. K. Dutta A1 - Frederick W. Strauch A1 - R. M. Lewis A1 - Kaushik Mitra A1 - Hanhee Paik A1 - T. A. Palomaki A1 - Eite Tiesinga A1 - J. R. Anderson A1 - Alex J. Dragt A1 - C. J. Lobb A1 - F. C. Wellstood AB - We present Rabi oscillation measurements of a Nb/AlOx/Nb dc superconducting quantum interference device (SQUID) phase qubit with a 100 um^2 area junction acquired over a range of microwave drive power and frequency detuning. Given the slightly anharmonic level structure of the device, several excited states play an important role in the qubit dynamics, particularly at high power. To investigate the effects of these levels, multiphoton Rabi oscillations were monitored by measuring the tunneling escape rate of the device to the voltage state, which is particularly sensitive to excited state population. We compare the observed oscillation frequencies with a simplified model constructed from the full phase qubit Hamiltonian and also compare time-dependent escape rate measurements with a more complete density-matrix simulation. Good quantitative agreement is found between the data and simulations, allowing us to identify a shift in resonance (analogous to the ac Stark effect), a suppression of the Rabi frequency, and leakage to the higher excited states. VL - 78 UR - http://arxiv.org/abs/0806.4711v2 CP - 10 J1 - Phys. Rev. B U5 - 10.1103/PhysRevB.78.104510 ER - TY - JOUR T1 - Optimizing Slow and Stored Light for Multidisciplinary Applications JF - Proc. SPIE Y1 - 2008 A1 - Klein, M A1 - Xiao, Y A1 - Alexey V. Gorshkov A1 - M Hohensee A1 - C D Leung A1 - M R Browning A1 - Phillips, D F A1 - Novikova, I A1 - Walsworth, R L VL - 6904 U4 - 69040C UR - http://spie.org/x648.xml?product_id=772216&Search_Origin=QuickSearch&Search_Results_URL=http://spie.org/x1636.xml&Alternate_URL=http://spie.org/x18509.xml&Alternate_URL_Name=timeframe&Alternate_URL_Value=Exhibitors&UseJavascript=1&Please_Wait_URL=http://s ER - TY - JOUR T1 - Quantum behavior of the dc SQUID phase qubit JF - Physical Review B Y1 - 2008 A1 - Kaushik Mitra A1 - F. W. Strauch A1 - C. J. Lobb A1 - J. R. Anderson A1 - F. C. Wellstood A1 - Eite Tiesinga AB - 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. VL - 77 UR - http://arxiv.org/abs/0805.3680v1 CP - 21 J1 - Phys. Rev. B U5 - 10.1103/PhysRevB.77.214512 ER - TY - JOUR T1 - Theoretical analysis of perfect quantum state transfer with superconducting qubits JF - Physical Review B Y1 - 2008 A1 - Frederick W. Strauch A1 - Carl J. Williams AB - Superconducting quantum circuits, fabricated with multiple layers, are proposed to implement perfect quantum state transfer between nodes of a hypercube network. For tunable devices such as the phase qubit, each node can transmit quantum information to any other node at a constant rate independent of the distance between qubits. The physical limits of quantum state transfer in this network are theoretically analyzed, including the effects of disorder, decoherence, and higher-order couplings. VL - 78 UR - http://arxiv.org/abs/0708.0577v3 CP - 9 J1 - Phys. Rev. B U5 - 10.1103/PhysRevB.78.094516 ER - TY - JOUR T1 - Tunneling phase gate for neutral atoms in a double-well lattice JF - Physical Review A Y1 - 2008 A1 - Frederick W. Strauch A1 - Mark Edwards A1 - Eite Tiesinga A1 - Carl J. Williams A1 - Charles W. Clark AB - We propose a new two--qubit phase gate for ultra--cold atoms confined in an experimentally realized tilted double--well optical lattice [Sebby--Strabley et al., Phys. Rev. A {\bf 73} 033605 (2006)]. Such a lattice is capable of confining pairs of atoms in a two--dimensional array of double--well potentials where control can be exercised over the barrier height and the energy difference of the minima of the two wells (known as the ``tilt''). The four lowest single--particle motional states consist of two pairs of motional states in which each pair is localized on one side of the central barrier, allowing for two atoms confined in such a lattice to be spatially separated qubits. We present a time--dependent scheme to manipulate the tilt to induce tunneling oscillations which produce a collisional phase gate. Numerical simulations demonstrate that this gate can be performed with high fidelity. VL - 77 UR - http://arxiv.org/abs/0712.1856v1 CP - 5 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.77.050304 ER - TY - JOUR T1 - The limitations of nice mutually unbiased bases JF - Journal of Algebraic Combinatorics Y1 - 2007 A1 - Michael Aschbacher A1 - Andrew M. Childs A1 - Pawel Wocjan AB - Mutually unbiased bases of a Hilbert space can be constructed by partitioning a unitary error basis. We consider this construction when the unitary error basis is a nice error basis. We show that the number of resulting mutually unbiased bases can be at most one plus the smallest prime power contained in the dimension, and therefore that this construction cannot improve upon previous approaches. We prove this by establishing a correspondence between nice mutually unbiased bases and abelian subgroups of the index group of a nice error basis and then bounding the number of such subgroups. This bound also has implications for the construction of certain combinatorial objects called nets. VL - 25 U4 - 111 - 123 UR - http://arxiv.org/abs/quant-ph/0412066v1 CP - 2 J1 - J Algebr Comb U5 - 10.1007/s10801-006-0002-y ER - TY - JOUR T1 - The LU-LC conjecture is false Y1 - 2007 A1 - Zhengfeng Ji A1 - Jianxin Chen A1 - Zhaohui Wei A1 - Mingsheng Ying AB - The LU-LC conjecture is an important open problem concerning the structure of entanglement of states described in the stabilizer formalism. It states that two local unitary equivalent stabilizer states are also local Clifford equivalent. If this conjecture were true, the local equivalence of stabilizer states would be extremely easy to characterize. Unfortunately, however, based on the recent progress made by Gross and Van den Nest, we find that the conjecture is false. UR - http://arxiv.org/abs/0709.1266v2 J1 - Quantum Inf. Comput. ER - TY - JOUR T1 - Multi-photon Entanglement: From Quantum Curiosity to Quantum Computing and Quantum Repeaters JF - Proc. SPIE Y1 - 2007 A1 - Walther, P A1 - Eisaman, M D A1 - Nemiroski, A A1 - Alexey V. Gorshkov A1 - Zibrov, A S A1 - Zeilinger, A A1 - Lukin, M D VL - 6664 U4 - 66640G UR - http://spiedigitallibrary.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=PSISDG00666400000166640G000001&idtype=cvips&gifs=Yes&bproc=volrange&scode=6600%20-%206699 ER - TY - JOUR T1 - Optimal control of light pulse storage and retrieval JF - Physical Review Letters Y1 - 2007 A1 - Irina Novikova A1 - Alexey V. Gorshkov A1 - David F. Phillips A1 - Anders S. Sorensen A1 - Mikhail D. Lukin A1 - Ronald L. Walsworth AB - We demonstrate experimentally a procedure to obtain the maximum efficiency for the storage and retrieval of light pulses in atomic media. The procedure uses time reversal to obtain optimal input signal pulse-shapes. Experimental results in warm Rb vapor are in good agreement with theoretical predictions and demonstrate a substantial improvement of efficiency. This optimization procedure is applicable to a wide range of systems. VL - 98 UR - http://arxiv.org/abs/quant-ph/0702266v1 CP - 24 J1 - Phys. Rev. Lett. U5 - 10.1103/PhysRevLett.98.243602 ER - TY - JOUR T1 - Optimization of slow and stored light in atomic vapor JF - Proc. SPIE Y1 - 2007 A1 - Novikova, I A1 - Alexey V. Gorshkov A1 - Phillips, D F A1 - Xiao, Y A1 - Klein, M A1 - Walsworth, R L VL - 6482 U4 - 64820M UR - http://spiedigitallibrary.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=PSISDG00648200000164820M000001&idtype=cvips&gifs=Yes&bproc=volrange&scode=6400%20-%206499 ER - TY - JOUR T1 - Signatures of incoherence in a quantum information processor Y1 - 2007 A1 - Michael K. Henry A1 - Alexey V. Gorshkov A1 - Yaakov S. Weinstein A1 - Paola Cappellaro A1 - Joseph Emerson A1 - Nicolas Boulant A1 - Jonathan S. Hodges A1 - Chandrasekhar Ramanathan A1 - Timothy F. Havel A1 - Rudy Martinez A1 - David G. Cory AB - Incoherent noise is manifest in measurements of expectation values when the underlying ensemble evolves under a classical distribution of unitary processes. While many incoherent processes appear decoherent, there are important differences. The distribution functions underlying incoherent processes are either static or slowly varying with respect to control operations and so the errors introduced by these distributions are refocusable. The observation and control of incoherence in small Hilbert spaces is well known. Here we explore incoherence during an entangling operation, such as is relevant in quantum information processing. As expected, it is more difficult to separate incoherence and decoherence over such processes. However, by studying the fidelity decay under a cyclic entangling map we are able to identify distinctive experimental signatures of incoherence. This result is demonstrated both through numerical simulations and experimentally in a three qubit nuclear magnetic resonance implementation. UR - http://arxiv.org/abs/0705.3666v2 ER - TY - JOUR T1 - Effects of finite temperature on the Mott insulator state JF - Physical Review A Y1 - 2006 A1 - Guido Pupillo A1 - Carl J. Williams A1 - Nikolay V. Prokof'ev AB - We investigate the effects of finite temperature on ultracold Bose atoms confined in an optical lattice plus a parabolic potential in the Mott insulator state. In particular, we analyze the temperature dependence of the density distribution of atomic pairs in the lattice, by means of exact Monte-Carlo simulations. We introduce a simple model that quantitatively accounts for the computed pair density distributions at low enough temperatures. We suggest that the temperature dependence of the atomic pair statistics may be used to estimate the system's temperature at energies of the order of the atoms' interaction energy. VL - 73 UR - http://arxiv.org/abs/cond-mat/0407075v3 CP - 1 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.73.013408 ER - TY - JOUR T1 - Mean-field treatment of the damping of the oscillations of a 1D Bose gas in an optical lattice JF - Physical Review A Y1 - 2006 A1 - Julio Gea-Banacloche A1 - Ana Maria Rey A1 - Guido Pupillo A1 - Carl J. Williams A1 - Charles W. Clark AB - We present a theoretical treatment of the surprisingly large damping observed recently in one-dimensional Bose-Einstein atomic condensates in optical lattices. We show that time-dependent Hartree-Fock-Bogoliubov (HFB) calculations can describe qualitatively the main features of the damping observed over a range of lattice depths. We also derive a formula of the fluctuation-dissipation type for the damping, based on a picture in which the coherent motion of the condensate atoms is disrupted as they try to flow through the random local potential created by the irregular motion of noncondensate atoms. We expect this irregular motion to result from the well-known dynamical instability exhibited by the mean-field theory for these systems. When parameters for the characteristic strength and correlation times of the fluctuations, obtained from the HFB calculations, are substituted in the damping formula, we find very good agreement with the experimentally-observed damping, as long as the lattice is shallow enough for the fraction of atoms in the Mott insulator phase to be negligible. We also include, for completeness, the results of other calculations based on the Gutzwiller ansatz, which appear to work better for the deeper lattices. VL - 73 UR - http://arxiv.org/abs/cond-mat/0410677v4 CP - 1 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.73.013605 ER - TY - JOUR T1 - Pseudo-fermionization of 1-D bosons in optical lattices JF - New Journal of Physics Y1 - 2006 A1 - Guido Pupillo A1 - Ana Maria Rey A1 - Carl J. Williams A1 - Charles W. Clark AB - We present a model that generalizes the Bose-Fermi mapping for strongly correlated 1D bosons in an optical lattice, to cases in which the average number of atoms per site is larger than one. This model gives an accurate account of equilibrium properties of such systems, in parameter regimes relevant to current experiments. The application of this model to non-equilibrium phenomena is explored by a study of the dynamics of an atom cloud subject to a sudden displacement of the confining potential. Good agreement is found with results of recent experiments. The simplicity and intuitive appeal of this model make it attractive as a general tool for understanding bosonic systems in the strongly correlated regime. VL - 8 U4 - 161 - 161 UR - http://arxiv.org/abs/cond-mat/0505325v2 CP - 8 J1 - New J. Phys. U5 - 10.1088/1367-2630/8/8/161 ER - TY - JOUR T1 - Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem Y1 - 2006 A1 - Andrew M. Childs A1 - Aram W. Harrow A1 - Pawel Wocjan AB - Schur duality decomposes many copies of a quantum state into subspaces labeled by partitions, a decomposition with applications throughout quantum information theory. Here we consider applying Schur duality to the problem of distinguishing coset states in the standard approach to the hidden subgroup problem. We observe that simply measuring the partition (a procedure we call weak Schur sampling) provides very little information about the hidden subgroup. Furthermore, we show that under quite general assumptions, even a combination of weak Fourier sampling and weak Schur sampling fails to identify the hidden subgroup. We also prove tight bounds on how many coset states are required to solve the hidden subgroup problem by weak Schur sampling, and we relate this question to a quantum version of the collision problem. UR - http://arxiv.org/abs/quant-ph/0609110v1 J1 - Proc. 24th Symposium on Theoretical Aspects of Computer Science (STACS 2007) U5 - 10.1007/978-3-540-70918-3_51 ER - TY - JOUR T1 - Bragg Spectroscopy of ultracold atoms loaded in an optical lattice JF - Physical Review A Y1 - 2005 A1 - Ana Maria Rey A1 - P. Blair Blakie A1 - Guido Pupillo A1 - Carl J. Williams A1 - Charles W. Clark AB - We study Bragg spectroscopy of ultra-cold atoms in one-dimensional optical lattices as a method for probing the excitation spectrum in the Mott insulator phase, in particular the one particle-hole excitation band. Within the framework of perturbation theory we obtain an analytical expression for the dynamic structure factor $S(q,\omega)$ and use it to calculate the imparted energy which has shown to be a relevant observable in recent experiments. We test the accuracy of our approximations by comparing them with numerically exact solutions of the Bose-Hubbard model in restricted cases and establish the limits of validity of our linear response analysis. Finally we show that when the system is deep in the Mott insulator regime, its response to the Bragg perturbation is temperature dependent. We suggest that this dependence might be used as a tool to probe temperatures of order of the Mott gap. VL - 72 UR - http://arxiv.org/abs/cond-mat/0406552v2 CP - 2 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.72.023407 ER - TY - JOUR T1 - Multichannel quantum-defect theory for slow atomic collisions JF - Physical Review A Y1 - 2005 A1 - Bo Gao A1 - Eite Tiesinga A1 - Carl J. Williams A1 - Paul S. Julienne AB - We present a multichannel quantum-defect theory for slow atomic collisions that takes advantages of the analytic solutions for the long-range potential, and both the energy and the angular-momentum insensitivities of the short-range parameters. The theory provides an accurate and complete account of scattering processes, including shape and Feshbach resonances, in terms of a few parameters such as the singlet and the triplet scattering lengths. As an example, results for $^{23}$Na-$^{23}$Na scattering are presented and compared close-coupling calculations. VL - 72 UR - http://arxiv.org/abs/physics/0508060v1 CP - 4 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.72.042719 ER - TY - JOUR T1 - On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems Y1 - 2005 A1 - Andrew M. Childs A1 - Pawel Wocjan AB - 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. UR - http://arxiv.org/abs/quant-ph/0510185v1 J1 - Quantum Information and Computation ER - TY - JOUR T1 - Scalable register initialization for quantum computing in an optical lattice JF - Journal of Physics B: Atomic, Molecular and Optical Physics Y1 - 2005 A1 - Gavin K. Brennen A1 - Guido Pupillo A1 - Ana Maria Rey A1 - Charles W. Clark A1 - Carl J. Williams AB - The Mott insulator state created by loading an atomic Bose-Einstein condensate (BEC) into an optical lattice may be used as a means to prepare a register of atomic qubits in a quantum computer. Such architecture requires a lattice commensurately filled with atoms, which corresponds to the insulator state only in the limit of zero inter-well tunneling. We show that a lattice with spatial inhomogeneity created by a quadratic magnetic trapping potential can be used to isolate a subspace in the center which is impervious to hole-hoping. Components of the wavefunction with more than one atom in any well can be projected out by selective measurement on a molecular photo-associative transition. Maintaining the molecular coupling induces a quantum Zeno effect that can sustain a commensurately filled register for the duration of a quantum computation. VL - 38 U4 - 1687 - 1694 UR - http://arxiv.org/abs/quant-ph/0312069v1 CP - 11 J1 - J. Phys. B: At. Mol. Opt. Phys. U5 - 10.1088/0953-4075/38/11/010 ER - TY - JOUR T1 - Ultracold atoms confined in an optical lattice plus parabolic potential: a closed-form approach JF - Physical Review A Y1 - 2005 A1 - Ana Maria Rey A1 - Guido Pupillo A1 - Charles W. Clark A1 - Carl J. Williams AB - We discuss interacting and non-interacting one dimensional atomic systems trapped in an optical lattice plus a parabolic potential. We show that, in the tight-binding approximation, the non-interacting problem is exactly solvable in terms of Mathieu functions. We use the analytic solutions to study the collective oscillations of ideal bosonic and fermionic ensembles induced by small displacements of the parabolic potential. We treat the interacting boson problem by numerical diagonalization of the Bose-Hubbard Hamiltonian. From analysis of the dependence upon lattice depth of the low-energy excitation spectrum of the interacting system, we consider the problems of "fermionization" of a Bose gas, and the superfluid-Mott insulator transition. The spectrum of the noninteracting system turns out to provide a useful guide to understanding the collective oscillations of the interacting system, throughout a large and experimentally relevant parameter regime. VL - 72 UR - http://arxiv.org/abs/cond-mat/0503477v2 CP - 3 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.72.033616 ER - TY - JOUR T1 - Advantages of high-speed technique for quantum key distribution; reply to quant-ph/0407050 Y1 - 2004 A1 - J. C. Bienfang A1 - Charles W. Clark A1 - Carl J. Williams A1 - E. W. Hagley A1 - Jesse Wen AB - We respond to a comment on our high-speed technique for the implementation of free-space quantum key distribution (QKD). The model used in the comment assigns inappropriately high link losses to the technique in question. We show that the use of reasonable loss parameters in the model invalidates the comment's main conclusion and highlights the benefits of increased transmission rates. UR - http://arxiv.org/abs/quant-ph/0407139v1 ER - TY - JOUR T1 - Quantum key distribution with 1.25 Gbps clock synchronization JF - Optics Express Y1 - 2004 A1 - J. C. Bienfang A1 - A. J. Gross A1 - A. Mink A1 - B. J. Hershman A1 - A. Nakassis A1 - X. Tang A1 - R. Lu A1 - D. H. Su A1 - Charles W Clark A1 - Carl J. Williams A1 - E. W. Hagley A1 - Jesse Wen AB - 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. VL - 12 U4 - 2011 UR - http://arxiv.org/abs/quant-ph/0405097v1 CP - 9 J1 - Opt. Express U5 - 10.1364/OPEX.12.002011 ER - TY - JOUR T1 - Relativistic many-body calculations of electric-dipole matrix elements, lifetimes and polarizabilities in rubidium JF - Physical Review A Y1 - 2004 A1 - M. S. Safronova A1 - Carl J. Williams A1 - Charles W. Clark AB - Electric-dipole matrix elements for ns-n'p, nd-n'p, and 6d-4f transitions in Rb are calculated using a relativistic all-order method. A third-order calculation is also carried out for these matrix elements to evaluate the importance of the high-order many-body perturbation theory contributions. The all-order matrix elements are used to evaluate lifetimes of ns and np levels with n=6, 7, 8 and nd levels with n=4, 5, 6 for comparison with experiment and to provide benchmark values for these lifetimes. The dynamic polarizabilities are calculated for ns states of rubidium. The resulting lifetime and polarizability values are compared with available theory and experiment. VL - 69 UR - http://arxiv.org/abs/physics/0307057v1 CP - 2 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.69.022509 ER - TY - JOUR T1 - Scalable quantum computation in systems with Bose-Hubbard dynamics JF - Journal of Modern Optics Y1 - 2004 A1 - Guido Pupillo A1 - Ana Maria Rey A1 - Gavin Brennen A1 - Carl J. Williams A1 - Charles W. Clark AB - Several proposals for quantum computation utilize a lattice type architecture with qubits trapped by a periodic potential. For systems undergoing many body interactions described by the Bose-Hubbard Hamiltonian, the ground state of the system carries number fluctuations that scale with the number of qubits. This process degrades the initialization of the quantum computer register and can introduce errors during error correction. In an earlier manuscript we proposed a solution to this problem tailored to the loading of cold atoms into an optical lattice via the Mott Insulator phase transition. It was shown that by adding an inhomogeneity to the lattice and performing a continuous measurement, the unit filled state suitable for a quantum computer register can be maintained. Here, we give a more rigorous derivation of the register fidelity in homogeneous and inhomogeneous lattices and provide evidence that the protocol is effective in the finite temperature regime. VL - 51 U4 - 2395 - 2404 UR - http://arxiv.org/abs/quant-ph/0403052v2 CP - 16-18 J1 - Journal of Modern Optics U5 - 10.1080/09500340408231798 ER - TY - JOUR T1 - Bogoliubov approach to superfluidity of atoms in an optical lattice JF - Journal of Physics B: Atomic, Molecular and Optical Physics Y1 - 2003 A1 - Ana Maria Rey A1 - Keith Burnett A1 - Robert Roth A1 - Mark Edwards A1 - Carl J. Williams A1 - Charles W. Clark AB - We use the Bogoliubov theory of atoms in an optical lattice to study the approach to the Mott-insulator transition. We derive an explicit expression for the superfluid density based on the rigidity of the system under phase variations. This enables us to explore the connection between the quantum depletion of the condensate and the quasi-momentum distribution on the one hand and the superfluid fraction on the other. The approach to the insulator phase may be characterized through the filling of the band by quantum depletion, which should be directly observable via the matter wave interference patterns. We complement these findings by self-consistent Hartree-Fock-Bogoliubov-Popov calculations for one-dimensional lattices including the effects of a parabolic trapping potential. VL - 36 U4 - 825 - 841 UR - http://arxiv.org/abs/cond-mat/0210550v2 CP - 5 J1 - J. Phys. B: At. Mol. Opt. Phys. U5 - 10.1088/0953-4075/36/5/304 ER - TY - CONF T1 - Language-reconfigurable universal phone recognition T2 - Eighth European Conference on Speech Communication and Technology Y1 - 2003 A1 - Walker, Brenton D A1 - Lackey, Bradley C A1 - Muller, JS A1 - Schone, Patrick John JA - Eighth European Conference on Speech Communication and Technology ER - TY - JOUR T1 - Optimizing the fast Rydberg quantum gate JF - Physical Review A Y1 - 2003 A1 - M. S. Safronova A1 - Carl J. Williams A1 - Charles W. Clark AB - The fast phase gate scheme, in which the qubits are atoms confined in sites of an optical lattice, and gate operations are mediated by excitation of Rydberg states, was proposed by Jaksch et al. Phys. Rev. Lett. 85, 2208 (2000). A potential source of decoherence in this system derives from motional heating, which occurs if the ground and Rydberg states of the atom move in different optical lattice potentials. We propose to minimize this effect by choosing the lattice photon frequency \omega so that the ground and Rydberg states have the same frequency-dependent polarizability \alpha(omega). The results are presented for the case of Rb. VL - 67 UR - http://arxiv.org/abs/quant-ph/0212081v1 CP - 4 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.67.040303 ER - TY - JOUR T1 - A Quantum Computer Architecture using Nonlocal Interactions JF - Physical Review A Y1 - 2003 A1 - Gavin K. Brennen A1 - Daegene Song A1 - Carl J. Williams AB - 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. VL - 67 UR - http://arxiv.org/abs/quant-ph/0301012v2 CP - 5 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.67.050302 ER - TY - JOUR T1 - Ultracold Cs$_2$ Feshbach Spectroscopy Y1 - 2003 A1 - Cheng Chin A1 - Vladan Vuletic A1 - Andrew J. Kerman A1 - Steven Chu A1 - Eite Tiesinga A1 - Paul J. Leo A1 - Carl J. Williams AB - We have observed and located more than 60 magnetic field-induced Feshbach resonances in ultracold collisions of ground-state $^{133}$Cs atoms. These resonances are associated with molecular states with up to four units of rotational angular momentum, and are detected through variations in the elastic, inelastic, and radiative collision cross sections. These observations allow us to greatly improve upon the interaction potentials between two cesium atoms and to reproduce the positions of most resonances to accuracies better than 0.5%. Based on the relevant coupling scheme between the electron spin, nuclear spin, and orbital angular momenta of the nuclei, quantum numbers and energy structure of the molecular states beneath the dissociation continuum are revealed. Finally, we predict the relevant collision properties for cesium Bose-Einstein condensation experiments. UR - http://arxiv.org/abs/cond-mat/0312613v2 ER - TY - JOUR T1 - `Flat Phase' Loading of a Bose-Einstein Condensate into an Optical Lattice JF - Physical Review A Y1 - 2002 A1 - Shlomo E. Sklarz A1 - Inbal Friedler A1 - David J. Tannor A1 - Yehuda B. Band A1 - Carl J. Williams AB - It has been proposed that the adiabatic loading of a Bose-Einstein Condensate (BEC) into an optical lattice via the Mott-insulator transition can be used to initialize a quantum computer [D. Jaksch, {\it et al.}, Phys. Rev. Lett. {\bf 81}, 3108 (1998)]. The loading of a BEC into the lattice without causing band excitation is readily achievable; however, unless one switches on an optical lattice very slowly, the optical lattice causes a phase to accumulate across the condensate. We show analytically and numerically that a cancellation of this effect is possible by adjusting the harmonic trap force-constant of the magnetic trap appropriately, thereby facilitating quick loading of an optical lattice for quantum computing purposes. A simple analytical theory is developed for a non-stationary BEC in a harmonic trap. VL - 66 UR - http://arxiv.org/abs/physics/0209071v1 CP - 5 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.66.053620 ER -