%0 Journal Article %D 2023 %T Accelerating Progress Towards Practical Quantum Advantage: The Quantum Technology Demonstration Project Roadmap %A Paul Alsing %A Phil Battle %A Joshua C. Bienfang %A Tammie Borders %A Tina Brower-Thomas %A Lincoln D. Carr %A Fred Chong %A Siamak Dadras %A Brian DeMarco %A Ivan Deutsch %A Eden Figueroa %A Danna Freedman %A Henry Everitt %A Daniel Gauthier %A Ezekiel Johnston-Halperin %A Jungsang Kim %A Mackillo Kira %A Prem Kumar %A Paul Kwiat %A John Lekki %A Anjul Loiacono %A Marko Lončar %A John R. Lowell %A Mikhail Lukin %A Celia Merzbacher %A Aaron Miller %A Christopher Monroe %A Johannes Pollanen %A David Pappas %A Michael Raymer %A Ronald Reano %A Brandon Rodenburg %A Martin Savage %A Thomas Searles %A Jun Ye %X

Quantum information science and technology (QIST) is a critical and emerging technology with the potential for enormous world impact and is currently invested in by over 40 nations. To bring these large-scale investments to fruition and bridge the lower technology readiness levels (TRLs) of fundamental research at universities to the high TRLs necessary to realize the promise of practical quantum advantage accessible to industry and the public, we present a roadmap for Quantum Technology Demonstration Projects (QTDPs). Such QTDPs, focused on intermediate TRLs, are large-scale public-private partnerships with a high probability of translation from laboratory to practice. They create technology demonstrating a clear 'quantum advantage' for science breakthroughs that are user-motivated and will provide access to a broad and diverse community of scientific users. Successful implementation of a program of QTDPs will have large positive economic impacts.

%8 3/20/2023 %G eng %U https://arxiv.org/abs/2210.14757 %0 Journal Article %D 2023 %T Bounds on Autonomous Quantum Error Correction %A Oles Shtanko %A Yu-Jie Liu %A Simon Lieu %A Alexey V. Gorshkov %A Victor V. Albert %X

Autonomous quantum memories are a way to passively protect quantum information using engineered dissipation that creates an "always-on'' decoder. We analyze Markovian autonomous decoders that can be implemented with a wide range of qubit and bosonic error-correcting codes, and derive several upper bounds and a lower bound on the logical error rate in terms of correction and noise rates. For many-body quantum codes, we show that, to achieve error suppression comparable to active error correction, autonomous decoders generally require correction rates that grow with code size. For codes with a threshold, we show that it is possible to achieve faster-than-polynomial decay of the logical error rate with code size by using superlogarithmic scaling of the correction rate. We illustrate our results with several examples. One example is an exactly solvable global dissipative toric code model that can achieve an effective logical error rate that decreases exponentially with the linear lattice size, provided that the recovery rate grows proportionally with the linear lattice size.

%8 8/30/2023 %G eng %U https://arxiv.org/abs/2308.16233 %0 Journal Article %D 2023 %T Clifford operations and homological codes for rotors and oscillators %A Yijia Xu %A Yixu Wang %A Victor V. Albert %X

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

%8 11/13/2023 %G eng %U https://arxiv.org/abs/2311.07679 %0 Journal Article %J Physical Review B %D 2023 %T Critical phase and spin sharpening in SU(2)-symmetric monitored quantum circuits %A Shayan Majidy %A Utkarsh Agrawal %A Sarang Gopalakrishnan %A Andrew C. Potter %A Romain Vasseur %A Nicole Yunger Halpern %X

Monitored quantum circuits exhibit entanglement transitions at certain measurement rates. Such a transition separates phases characterized by how much information an observer can learn from the measurement outcomes. We study SU(2)-symmetric monitored quantum circuits, using exact numerics and a mapping onto an effective statistical-mechanics model. Due to the symmetry's non-Abelian nature, measuring qubit pairs allows for nontrivial entanglement scaling even in the measurement-only limit. We find a transition between a volume-law entangled phase and a critical phase whose diffusive purification dynamics emerge from the non-Abelian symmetry. Additionally, we numerically identify a "spin-sharpening transition." On one side is a phase in which the measurements can efficiently identify the system's total spin quantum number; on the other side is a phase in which measurements cannot.

%B Physical Review B %V 108 %8 8/17/2023 %G eng %U https://arxiv.org/abs/2305.13356 %R 10.1103/physrevb.108.054307 %0 Report %D 2023 %T Data Needs and Challenges of Quantum Dot Devices Automation: Workshop Report %A Justyna P. Zwolak %A Jacob M. Taylor %A Reed Andrews %A Jared Benson %A Garnett Bryant %A Donovan Buterakos %A Anasua Chatterjee %A Sankar Das Sarma %A Mark A. Eriksson %A Eliška Greplová %A Michael J. Gullans %A Fabian Hader %A Tyler J. Kovach %A Pranav S. Mundada %A Mick Ramsey %A Torbjoern Rasmussen %A Brandon Severin %A Anthony Sigillito %A Brennan Undseth %A Brian Weber %X

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.

%8 12/21/2023 %G eng %U https://arxiv.org/abs/2312.14322 %R https://doi.org/10.48550/arXiv.2312.14322 %0 Journal Article %D 2023 %T The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver %A Pedro C. S. Costa %A Dong An %A Ryan Babbush %A Dominic Berry %X

The solution of linear systems of equations is the basis of many other quantum algorithms, and recent results provided an algorithm with optimal scaling in both the condition number κ and the allowable error ϵ [PRX Quantum \textbf{3}, 0403003 (2022)]. That work was based on the discrete adiabatic theorem, and worked out an explicit constant factor for an upper bound on the complexity. Here we show via numerical testing on random matrices that the constant factor is in practice about 1,500 times smaller than the upper bound found numerically in the previous results. That means that this approach is far more efficient than might naively be expected from the upper bound. In particular, it is over an order of magnitude more efficient than using a randomised approach from [arXiv:2305.11352] that claimed to be more efficient.

%8 12/12/2023 %G eng %U https://arxiv.org/abs/2312.07690 %0 Journal Article %D 2023 %T A family of permutationally invariant quantum codes %A Arda Aydin %A Max A. Alekseyev %A Alexander Barg %X

We construct a new family of permutationally invariant codes that correct t Pauli errors for any t≥1. We also show that codes in the new family correct spontaneous decay errors as well as deletion errors. In many cases the codes in this family are shorter than the best previously known explicit families of permutationally invariant codes both for Pauli errors, deletions, and for the amplitude damping channel. As a separate result, we generalize the conditions for permutationally invariant codes to correct t Pauli errors from the previously known results for t=1 to any number of errors. For small t, these conditions can be used to construct new examples of codes by computer.

%8 10/9/2023 %G eng %U https://arxiv.org/abs/2310.05358 %0 Journal Article %D 2023 %T Lattice quantum chromodynamics at large isospin density: 6144 pions in a box %A Ryan Abbott %A William Detmold %A Fernando Romero-López %A Zohreh Davoudi %A Marc Illa %A Assumpta Parreño %A Robert J. Perry %A Phiala E. Shanahan %A Michael L. Wagman %X

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.

%8 7/27/2023 %G eng %U https://arxiv.org/abs/2307.15014 %0 Journal Article %J Phys. Rev. Lett. %D 2023 %T Linear combination of Hamiltonian simulation for non-unitary dynamics with optimal state preparation cost %A Dong An %A Jin-Peng Liu %A Lin Lin %X

We propose a simple method for simulating a general class of non-unitary dynamics as a linear combination of Hamiltonian simulation (LCHS) problems. LCHS does not rely on converting the problem into a dilated linear system problem, or on the spectral mapping theorem. The latter is the mathematical foundation of many quantum algorithms for solving a wide variety of tasks involving non-unitary processes, such as the quantum singular value transformation (QSVT). The LCHS method can achieve optimal cost in terms of state preparation. We also demonstrate an application for open quantum dynamics simulation using the complex absorbing potential method with near-optimal dependence on all parameters.

%B Phys. Rev. Lett. %V 131 %8 10/13/2023 %G eng %U https://arxiv.org/abs/2303.01029 %N 150603 %R https://journals.aps.org/prl/pdf/10.1103/PhysRevLett.131.150603 %0 Journal Article %J Nature %D 2023 %T Logical quantum processor based on reconfigurable atom arrays %A Bluvstein, Dolev %A Evered, Simon J. %A Geim, Alexandra A. %A Li, Sophie H. %A Zhou, Hengyun %A Manovitz, Tom %A Ebadi, Sepehr %A Cain, Madelyn %A Kalinowski, Marcin %A Hangleiter, Dominik %A Ataides, J. Pablo Bonilla %A Maskara, Nishad %A Cong, Iris %A Gao, Xun %A Rodriguez, Pedro Sales %A Karolyshyn, Thomas %A Semeghini, Giulia %A Gullans, Michael J. %A Greiner, Markus %A Vuletic, Vladan %A Lukin, Mikhail D. %B Nature %8 12/7/2023 %G eng %U https://arxiv.org/abs/2312.03982 %R 10.1038/s41586-023-06927-3 %0 Journal Article %D 2023 %T The maximum refractive index of an atomic crystal - from quantum optics to quantum chemistry %A Francesco Andreoli %A Bennet Windt %A Stefano Grava %A Gian Marcello Andolina %A Michael J. Gullans %A Alexander A. High %A Darrick E. Chang %X

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. 

%8 3/20/2023 %G eng %U https://arxiv.org/abs/2303.10998 %0 Journal Article %J Phys. Rev. Lett. %D 2023 %T Nonclassical Advantage in Metrology Established via Quantum Simulations of Hypothetical Closed Timelike Curves %A Arvidsson-Shukur, David R. M. %A McConnell, Aidan G. %A Yunger Halpern, Nicole %X

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

%B Phys. Rev. Lett. %V 131 %P 150202 %8 10/12/2023 %G eng %U https://link.aps.org/doi/10.1103/PhysRevLett.131.150202 %R 10.1103/PhysRevLett.131.150202 %0 Journal Article %D 2023 %T Non-invertible symmetry-protected topological order in a group-based cluster state %A Christopher Fechisin %A Nathanan Tantivasadakarn %A Victor V. Albert %X

Despite growing interest in beyond-group symmetries in quantum condensed matter systems, there are relatively few microscopic lattice models explicitly realizing these symmetries, and many phenomena have yet to be studied at the microscopic level. We introduce a one-dimensional stabilizer Hamiltonian composed of group-based Pauli operators whose ground state is a G×Rep(G)-symmetric state: the G cluster state introduced in Brell, New Journal of Physics 17, 023029 (2015) [at this http URL]. We show that this state lies in a symmetry-protected topological (SPT) phase protected by G×Rep(G) symmetry, distinct from the symmetric product state by a duality argument. We identify several signatures of SPT order, namely protected edge modes, string order parameters, and topological response. We discuss how G cluster states may be used as a universal resource for measurement-based quantum computation, explicitly working out the case where G is a semidirect product of abelian groups.

%8 12/14/2023 %G eng %U https://arxiv.org/abs/2312.09272 %0 Journal Article %D 2023 %T Precision Bounds on Continuous-Variable State Tomography using Classical Shadows %A Srilekha Gandhari %A Victor V. Albert %A Thomas Gerrits %A Jacob M. Taylor %A Michael J. Gullans %X

Shadow tomography is a framework for constructing succinct descriptions of quantum states using randomized measurement bases, called classical shadows, with powerful methods to bound the estimators used. We recast existing experimental protocols for continuous-variable quantum state tomography in the classical-shadow framework, obtaining rigorous bounds on the number of independent measurements needed for estimating density matrices from these protocols. We analyze the efficiency of homodyne, heterodyne, photon number resolving (PNR), and photon-parity protocols. To reach a desired precision on the classical shadow of an N-photon density matrix with a high probability, we show that homodyne detection requires an order O(N4+1/3) measurements in the worst case, whereas PNR and photon-parity detection require O(N4) measurements in the worst case (both up to logarithmic corrections). We benchmark these results against numerical simulation as well as experimental data from optical homodyne experiments. We find that numerical and experimental homodyne tomography significantly outperforms our bounds, exhibiting a more typical scaling of the number of measurements that is close to linear in N. We extend our single-mode results to an efficient construction of multimode shadows based on local measurements.

%8 12/15/2023 %G eng %U https://arxiv.org/abs/2211.05149 %0 Journal Article %D 2023 %T Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters %A Dong An %A Andrew M. Childs %A Lin Lin %X

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

%8 12/6/2023 %G eng %U https://arxiv.org/abs/2312.03916 %0 Journal Article %D 2023 %T A quantum central path algorithm for linear optimization %A Brandon Augustino %A Jiaqi Leng %A Giacomo Nannicini %A Tamás Terlaky %A Xiaodi Wu %X

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.

%8 11/7/2023 %G eng %U https://arxiv.org/abs/2311.03977 %0 Journal Article %J Phys. Rev. Lett. %D 2023 %T Quantum simulations of time travel can power nonclassical metrology %A David R. M. Arvidsson-Shukur %A Aidan G. McConnell %A Nicole Yunger Halpern %X

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

%B Phys. Rev. Lett. %V 131 %8 11/3/2023 %G eng %U arXiv:2207.07666 %N 150202 %R https://doi.org/10.48550/arXiv.2207.07666 %0 Journal Article %D 2023 %T Quantum spherical codes %A Shubham P. Jain %A Joseph T. Iosue %A Alexander Barg %A Victor V. Albert %X

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

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

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.

%8 12/14/2023 %G eng %U https://arxiv.org/abs/2312.09733 %0 Journal Article %J PRX Quantum %D 2023 %T Qubit-Oscillator Concatenated Codes: Decoding Formalism and Code Comparison %A Xu, Yijia %A Wang, Yixu %A Kuo, En-Jui %A Victor V. Albert %X

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.

%B PRX Quantum %V 4 %P 020342 %8 6/14/2023 %G eng %U https://arxiv.org/abs/2209.04573 %R 10.1103/PRXQuantum.4.020342 %0 Journal Article %D 2023 %T Subsystem CSS codes, a tighter stabilizer-to-CSS mapping, and Goursat's Lemma %A Michael Liaofan Liu %A Nathanan Tantivasadakarn %A Victor V. Albert %X

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

%8 11/29/2023 %G eng %U https://arxiv.org/abs/2311.18003 %0 Journal Article %D 2023 %T A theory of quantum differential equation solvers: limitations and fast-forwarding %A Dong An %A Jin-Peng Liu %A Daochen Wang %A Qi Zhao %X

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.

%8 3/2/2023 %G eng %U https://arxiv.org/abs/2211.05246 %0 Journal Article %D 2023 %T Thermally driven quantum refrigerator autonomously resets superconducting qubit %A Mohammed Ali Aamir %A Paul Jamet Suria %A José Antonio Marín Guzmán %A Claudia Castillo-Moreno %A Jeffrey M. Epstein %A Nicole Yunger Halpern %A Simone Gasparinetti %X

The first thermal machines steered the industrial revolution, but their quantum analogs have yet to prove useful. Here, we demonstrate a useful quantum absorption refrigerator formed from superconducting circuits. We use it to reset a transmon qubit to a temperature lower than that achievable with any one available bath. The process is driven by a thermal gradient and is autonomous -- requires no external control. The refrigerator exploits an engineered three-body interaction between the target qubit and two auxiliary qudits coupled to thermal environments. The environments consist of microwave waveguides populated with synthesized thermal photons. The target qubit, if initially fully excited, reaches a steady-state excited-level population of 5×10−4±5×10−4 (an effective temperature of 23.5~mK) in about 1.6~μs. Our results epitomize how quantum thermal machines can be leveraged for quantum information-processing tasks. They also initiate a path toward experimental studies of quantum thermodynamics with superconducting circuits coupled to propagating thermal microwave fields.

%8 5/26/2023 %G eng %U https://arxiv.org/abs/2305.16710 %0 Journal Article %J PRX Quantum %D 2023 %T Time-energy uncertainty relation for noisy quantum metrology %A Faist, Philippe %A Woods, Mischa P. %A Victor V. Albert %A Renes, Joseph M. %A Eisert, Jens %A Preskill, John %K FOS: Physical sciences %K Quantum Physics (quant-ph) %X

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.

%B PRX Quantum %V 4(4) %8 12/5/2023 %G eng %U https://arxiv.org/abs/2207.13707 %N 040336 %R https://journals.aps.org/prxquantum/pdf/10.1103/PRXQuantum.4.040336 %0 Journal Article %D 2023 %T On the Two-sided Permutation Inversion Problem %A Gorjan Alagic %A Chen Bai %A Alexander Poremba %A Kaiyan Shi %X

In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This is a fundamental problem in query complexity, and appears in many contexts, particularly cryptography. In this work, we examine the setting in which the oracle allows for quantum queries to both the forward and the inverse direction of the permutation -- except that the challenge value cannot be submitted to the latter. Within that setting, we consider two options for the inversion algorithm: whether it can get quantum advice about the permutation, and whether it must produce the entire preimage (search) or only the first bit (decision). We prove several theorems connecting the hardness of the resulting variations of the inversion problem, and establish a number of lower bounds. Our results indicate that, perhaps surprisingly, the inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse, provided it cannot query the challenge itself.

%8 6/23/2023 %G eng %U https://arxiv.org/abs/2306.13729 %0 Journal Article %D 2023 %T Æ codes %A Shubham P. Jain %A Eric R. Hudson %A Wesley C. Campbell %A Victor V. Albert %X

Diatomic molecular codes [{arXiv:1911.00099}] are designed to encode quantum information in the orientation of a diatomic molecule, allowing error correction from small torques and changes in angular momentum. Here, we directly study noise native to atomic and molecular platforms -- spontaneous emission, stray electromagnetic fields, and Raman scattering -- and derive simple necessary and sufficient conditions for codes to protect against such noise. We identify existing and develop new absorption-emission (Æ) codes that are more practical than molecular codes, require lower average momentum, can directly protect against photonic processes up to arbitrary order, and are applicable to a broader set of atomic and molecular systems.

%8 11/21/2023 %G eng %U https://arxiv.org/abs/2311.12324 %0 Journal Article %J Physics Letters A %D 2022 %T Approximating the two-mode two-photon Rabi model %A David H. Wu %A Victor V. Albert %X

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. 

%B Physics Letters A %V 422 %8 01/17/2022 %G eng %U https://arxiv.org/abs/2012.06994 %& 127779 %R https://doi.org/10.1016/j.physleta.2021.127779 %0 Journal Article %D 2022 %T Bosonic coding: introduction and use cases %A Victor V. Albert %K FOS: Computer and information sciences %K FOS: Physical sciences %K Information Theory (cs.IT) %K Quantum Physics (quant-ph) %X

Bosonic or continuous-variable coding is a field concerned with robust quantum information processing and communication with electromagnetic signals or mechanical modes. I review bosonic quantum memories, characterizing them as either bosonic stabilizer or bosonic Fock-state codes. I then enumerate various applications of bosonic encodings, four of which circumvent no-go theorems due to the intrinsic infinite-dimensionality of bosonic systems.

%8 11/10/2022 %G eng %U https://arxiv.org/abs/2211.05714 %R 10.48550/ARXIV.2211.05714 %0 Journal Article %J Phys. Rev. Lett. %D 2022 %T Chiral central charge from a single bulk wave function %A Isaac H. Kim %A Bowen Shi %A Kohtaro Kato %A Victor V. Albert %X

A (2+1)-dimensional gapped quantum many-body system can have a topologically protected energy current at its edge. The magnitude of this current is determined entirely by the temperature and the chiral central charge, a quantity associated with the effective field theory of the edge. We derive a formula for the chiral central charge that, akin to the topological entanglement entropy, is completely determined by the many-body ground state wave function in the bulk. According to our formula, nonzero chiral central charge gives rise to a topological obstruction that prevents the ground state wave function from being real-valued in any local product basis.

%B Phys. Rev. Lett. %V 128 %P 176402 %8 4/28/2022 %G eng %U https://arxiv.org/abs/2110.06932 %N 17 %R 10.1103/PhysRevLett.128.176402 %0 Journal Article %D 2022 %T Continuous-variable quantum state designs: theory and applications %A Iosue, Joseph T. %A Sharma, Kunal %A Gullans, Michael J. %A Victor V. Albert %K FOS: Physical sciences %K Mathematical Physics (math-ph) %K Optics (physics.optics) %K Quantum Physics (quant-ph) %X

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

%8 11/9/2022 %G eng %U https://arxiv.org/abs/2211.05127 %R 10.48550/ARXIV.2211.05127 %0 Journal Article %D 2022 %T Continuous-Variable Shadow Tomography %A Gandhari, Srilekha %A Victor V. Albert %A Gerrits, Thomas %A Taylor, Jacob M. %A Gullans, Michael J. %K FOS: Physical sciences %K Quantum Physics (quant-ph) %X

Shadow tomography is a framework for constructing succinct descriptions of quantum states, called classical shadows, with powerful methods to bound the estimators used. We recast existing experimental protocols for continuous-variable tomography in the classical-shadow framework, obtaining rigorous bounds on the sample complexity for estimating density matrices from these protocols. We analyze the efficiency of homodyne, heterodyne, photon number resolving (PNR), and photon-parity protocols. To reach a desired precision on the classical shadow of an N-photon density matrix with a high probability, we show that homodyne detection requires an order O(N5) measurements in the worst case, whereas PNR and photon-parity detection require O(N4) measurements in the worst case (both up to logarithmic corrections). We benchmark these results against numerical simulation as well as experimental data from optical homodyne experiments. We find that numerical and experimental homodyne tomography significantly outperforms our bounds, exhibiting a more typical scaling of the number of measurements that is close to linear in N. We extend our single-mode results to an efficient construction of multimode shadows based on local measurements.

%8 11/9/2022 %G eng %U https://arxiv.org/abs/2211.05149 %R 10.48550/ARXIV.2211.05149 %0 Journal Article %D 2022 %T Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation %A Dong An %A Di Fang %A Stephen Jordan %A Jin-Peng Liu %A Guang Hao Low %A Jiasu Wang %X

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.

%8 5/2/2022 %G eng %U https://arxiv.org/abs/2205.01141 %0 Journal Article %D 2022 %T Group coset monogamy games and an application to device-independent continuous-variable QKD %A Culf, Eric %A Vidick, Thomas %A Victor V. Albert %K Cryptography and Security (cs.CR) %K FOS: Computer and information sciences %K FOS: Physical sciences %K Quantum Physics (quant-ph) %X

We develop an extension of a recently introduced subspace coset state monogamy-of-entanglement game [Coladangelo, Liu, Liu, and Zhandry; Crypto'21] to general group coset states, which are uniform superpositions over elements of a subgroup to which has been applied a group-theoretic generalization of the quantum one-time pad. We give a general bound on the winning probability of a monogamy game constructed from subgroup coset states that applies to a wide range of finite and infinite groups. To study the infinite-group case, we use and further develop a measure-theoretic formalism that allows us to express continuous-variable measurements as operator-valued generalizations of probability measures.
We apply the monogamy game bound to various physically relevant groups, yielding realizations of the game in continuous-variable modes as well as in rotational states of a polyatomic molecule. We obtain explicit strong bounds in the case of specific group-space and subgroup combinations. As an application, we provide the first proof of one sided-device independent security of a squeezed-state continuous-variable quantum key distribution protocol against general coherent attacks.

%8 12/7/2022 %G eng %U https://arxiv.org/abs/2212.03935 %R 10.48550/ARXIV.2212.03935 %0 Journal Article %D 2022 %T Lattice-Based Quantum Advantage from Rotated Measurements %A Yusuf Alnawakhtha %A Mantri, Atul %A Carl Miller %A Wang, Daochen %K Cryptography and Security (cs.CR) %K Emerging Technologies (cs.ET) %K FOS: Computer and information sciences %K FOS: Physical sciences %K Quantum Physics (quant-ph) %X

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.

%8 10/18/2022 %G eng %U https://arxiv.org/abs/2210.10143 %R 10.48550/ARXIV.2210.10143 %0 Journal Article %J Physical Review B %D 2022 %T Modular commutator in gapped quantum many-body systems %A Isaac H. Kim %A Bowen Shi %A Kohtaro Kato %A Victor V. Albert %X

In arXiv:2110.06932, we argued that the chiral central charge -- a topologically protected quantity characterizing the edge theory of a gapped (2+1)-dimensional system -- can be extracted from the bulk by using an order parameter called the modular commutator. In this paper, we reveal general properties of the modular commutator and strengthen its relationship with the chiral central charge. First, we identify connections between the modular commutator and conditional mutual information, time reversal, and modular flow. Second, we prove, within the framework of the entanglement bootstrap program, that two topologically ordered media connected by a gapped domain wall must have the same modular commutator in their respective bulk. Third, we numerically calculate the value of the modular commutator for a bosonic lattice Laughlin state for finite sizes and extrapolate to the infinite-volume limit. The result of this extrapolation is consistent with the proposed formula up to an error of about 0.7%.

%B Physical Review B %V 106 %8 8/26/2022 %G eng %U https://arxiv.org/abs/2110.10400 %R 10.1103/physrevb.106.075147 %0 Journal Article %J Phys. Rev. Lett. %D 2022 %T Negative Quasiprobabilities Enhance Phase Estimation in Quantum-Optics Experiment %A Lupu-Gladstein, Noah %A Yilmaz, Y. Batuhan %A Arvidsson-Shukur, David R. M. %A Brodutch, Aharon %A Pang, Arthur O. T. %A Steinberg, Aephraim M. %A Nicole Yunger Halpern %X

Operator noncommutation, a hallmark of quantum theory, limits measurement precision, according to uncertainty principles. Wielded correctly, though, noncommutation can boost precision. A recent foundational result relates a metrological advantage with negative quasiprobabilities—quantum extensions of probabilities—engendered by noncommuting operators. We crystallize the relationship in an equation that we prove theoretically and observe experimentally. Our proof-of-principle optical experiment features a filtering technique that we term partially postselected amplification (PPA). Using PPA, we measure a wave plate’s birefringent phase. PPA amplifies, by over two orders of magnitude, the information obtained about the phase per detected photon. In principle, PPA can boost the information obtained from the average filtered photon by an arbitrarily large factor. The filter’s amplification of systematic errors, we find, bounds the theoretically unlimited advantage in practice. PPA can facilitate any phase measurement and mitigates challenges that scale with trial number, such as proportional noise and detector saturation. By quantifying PPA’s metrological advantage with quasiprobabilities, we reveal deep connections between quantum foundations and precision measurement.

%B Phys. Rev. Lett. %V 128 %P 220504 %8 6/2/2022 %G eng %U https://link.aps.org/doi/10.1103/PhysRevLett.128.220504 %R 10.1103/PhysRevLett.128.220504 %0 Journal Article %D 2022 %T Optical conductivity and orbital magnetization of Floquet vortex states %A Ahmadabadi, Iman %A Dehghani, Hossein %A Hafezi, Mohammad %K FOS: Physical sciences %K Mesoscale and Nanoscale Physics (cond-mat.mes-hall) %K Other Condensed Matter (cond-mat.other) %X

Motivated by recent experimental demonstrations of Floquet topological insulators, there have been several theoretical proposals for using structured light, either spatial or spectral, to create other properties such as flat band and vortex states. In particular, the generation of vortex states in a massive Dirac fermion insulator irradiated by light carrying nonzero orbital angular momentum (OAM) has been proposed [Kim et al. Phys. Rev. B 105, L081301(2022)]. Here, we evaluate the orbital magnetization and optical conductivity as physical observables for such a system. We show that the OAM of light induces nonzero orbital magnetization and current density. The orbital magnetization density increases linearly as a function of OAM degree. In certain regimes, we find that orbital magnetization density is independent of the system size, width, and Rabi frequency of light. It is shown that the orbital magnetization arising from our Floquet theory is large and can be probed by magnetometry measurements. Furthermore, we study the optical conductivity for various types of electron transitions between different states such as vortex, edge, and bulk that are present in the system. Based on conductance frequency peaks, a scheme for the detection of vortex states is proposed.

%8 4/20/2022 %G eng %U https://arxiv.org/abs/2204.09488 %R 10.48550/ARXIV.2204.09488 %0 Journal Article %J PRX Quantum %D 2022 %T Optimal scaling quantum linear systems solver via discrete adiabatic theorem %A Costa, Pedro C. S. %A An, Dong %A Sanders, Yuval R. %A Su, Yuan %A Babbush, Ryan %A Berry, Dominic W. %K FOS: Physical sciences %K Quantum Physics (quant-ph) %X

Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian. Such approaches enabled near-linear scaling in the condition number κ of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedures is still asymptotically sub-optimal by a factor of log(κ). Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete time evolutions. We use this discrete adiabatic theorem to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in κ, matching a known lower bound on the complexity. Our O(κlog(1/ϵ)) complexity is also optimal in terms of the combined scaling in κ and the precision ϵ. Compared to existing suboptimal methods, our algorithm is simpler and easier to implement. Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific applications.

%B PRX Quantum %V 3 %P 040303 %8 10/7/2022 %G eng %U https://arxiv.org/abs/2111.08152 %N 4 %R https://journals.aps.org/prxquantum/pdf/10.1103/PRXQuantum.3.040303 %0 Journal Article %J Eurocrypt %D 2022 %T Post-Quantum Security of the Even-Mansour Cipher %A Gorjan Alagic %A Chen Bai %A Jonathan Katz %A Christian Majenz %X

The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation E from a public random permutation~P:{0,1}n→{0,1}n. It is secure against classical attacks, with optimal attacks requiring qE queries to E and qP queries to P such that qE⋅qP≈2n. If the attacker is given \emph{quantum} access to both E and P, however, the cipher is completely insecure, with attacks using qE,qP=O(n) queries known. In any plausible real-world setting, however, a quantum attacker would have only \emph{classical} access to the keyed permutation~E implemented by honest parties, even while retaining quantum access to~P. Attacks in this setting with qE⋅q2P≈2n are known, showing that security degrades as compared to the purely classical case, but leaving open the question as to whether the Even-Mansour cipher can still be proven secure in this natural, "post-quantum" setting. We resolve this question, showing that any attack in that setting requires qE⋅q2P+qP⋅q2E≈2n. Our results apply to both the two-key and single-key variants of Even-Mansour. Along the way, we establish several generalizations of results from prior work on quantum-query lower bounds that may be of independent interest. 

%B Eurocrypt %8 12/14/2021 %G eng %U https://arxiv.org/abs/2112.07530 %R https://doi.org/10.48550/arXiv.2112.07530 %0 Journal Article %D 2022 %T Post-Quantum Security of the (Tweakable) FX Construction, and Applications %A Gorjan Alagic %A Chen Bai %A Jonathan Katz %A Christian Majenz %A Patrick Struck %X

The FX construction provides a way to increase the effective key length of a block cipher E. We prove security of a tweakable version of the FX construction in the post-quantum setting, i.e., against a quantum attacker given only classical access to the secretly keyed construction while retaining quantum access to E, a setting that seems to be the most relevant one for real-world applications. We then use our results to prove post-quantum security—in the same model—of the (plain) FX construction, Elephant (a finalist of NIST's lightweight cryptography standardization effort), and Chaskey (an ISO-standardized lightweight MAC

%8 8/29/2022 %G eng %U https://eprint.iacr.org/2022/1097 %0 Journal Article %J Quantum %D 2022 %T Provably accurate simulation of gauge theories and bosonic systems %A Yu Tong %A Victor V. Albert %A Jarrod R. McClean %A John Preskill %A Yuan Su %X

Quantum many-body systems involving bosonic modes or gauge fields have infinite-dimensional local Hilbert spaces which must be truncated to perform simulations of real-time dynamics on classical or quantum computers. To analyze the truncation error, we develop methods for bounding the rate of growth of local quantum numbers such as the occupation number of a mode at a lattice site, or the electric field at a lattice link. Our approach applies to various models of bosons interacting with spins or fermions, and also to both abelian and non-abelian gauge theories. We show that if states in these models are truncated by imposing an upper limit Λ on each local quantum number, and if the initial state has low local quantum numbers, then an error at most ϵ can be achieved by choosing Λ to scale polylogarithmically with ϵ−1, an exponential improvement over previous bounds based on energy conservation. For the Hubbard-Holstein model, we numerically compute a bound on Λ that achieves accuracy ϵ, obtaining significantly improved estimates in various parameter regimes. We also establish a criterion for truncating the Hamiltonian with a provable guarantee on the accuracy of time evolution. Building on that result, we formulate quantum algorithms for dynamical simulation of lattice gauge theories and of models with bosonic modes; the gate complexity depends almost linearly on spacetime volume in the former case, and almost quadratically on time in the latter case. We establish a lower bound showing that there are systems involving bosons for which this quadratic scaling with time cannot be improved. By applying our result on the truncation error in time evolution, we also prove that spectrally isolated energy eigenstates can be approximated with accuracy ϵ by truncating local quantum numbers at Λ=polylog(ϵ−1).

%B Quantum %V 6 %P 816 %8 9/20/2022 %G eng %U https://arxiv.org/abs/2110.06942 %R https://doi.org/10.22331%2Fq-2022-09-22-816 %0 Journal Article %J Science %D 2022 %T Provably efficient machine learning for quantum many-body problems %A Hsin-Yuan Huang %A Richard Kueng %A Giacomo Torlai %A Victor V. Albert %A John Preskill %X

Classical machine learning (ML) provides a potentially powerful approach to solving challenging quantum many-body problems in physics and chemistry. However, the advantages of ML over more traditional methods have not been firmly established. In this work, we prove that classical ML algorithms can efficiently predict ground state properties of gapped Hamiltonians in finite spatial dimensions, after learning from data obtained by measuring other Hamiltonians in the same quantum phase of matter. In contrast, under widely accepted complexity theory assumptions, classical algorithms that do not learn from data cannot achieve the same guarantee. We also prove that classical ML algorithms can efficiently classify a wide range of quantum phases of matter. Our arguments are based on the concept of a classical shadow, a succinct classical description of a many-body quantum state that can be constructed in feasible quantum experiments and be used to predict many properties of the state. Extensive numerical experiments corroborate our theoretical results in a variety of scenarios, including Rydberg atom systems, 2D random Heisenberg models, symmetry-protected topological phases, and topologically ordered phases.

%B Science %V 377 %8 9/26/2022 %G eng %U https://arxiv.org/abs/2106.12627 %R 10.1126/science.abk3333 %0 Journal Article %D 2022 %T Quantum Depth in the Random Oracle Model %A Arora, Atul Singh %A Coladangelo, Andrea %A Coudron, Matthew %A Gheorghiu, Alexandru %A Singh, Uttam %A Waldner, Hendrik %K Computational Complexity (cs.CC) %K Cryptography and Security (cs.CR) %K FOS: Computer and information sciences %K FOS: Physical sciences %K Quantum Physics (quant-ph) %X

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

%8 10/12/2022 %G eng %U https://arxiv.org/abs/2210.06454 %R 10.48550/ARXIV.2210.06454 %0 Journal Article %D 2022 %T Self-Testing of a Single Quantum System: Theory and Experiment %A Hu, Xiao-Min %A Xie, Yi %A Arora, Atul Singh %A Ai, Ming-Zhong %A Bharti, Kishor %A Zhang, Jie %A Wu, Wei %A Chen, Ping-Xing %A Cui, Jin-Ming %A Liu, Bi-Heng %A Huang, Yun-Feng %A Li, Chuan-Feng %A Guo, Guang-Can %A Roland, Jérémie %A Cabello, Adán %A Kwek, Leong-Chuan %K Atomic Physics (physics.atom-ph) %K FOS: Physical sciences %K Quantum Physics (quant-ph) %X

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.

%8 3/17/2022 %G eng %U https://arxiv.org/abs/2203.09003 %R https://doi.org/10.48550/arXiv.2203.09003 %0 Journal Article %D 2022 %T Simulation Complexity of Many-Body Localized Systems %A Adam Ehrenberg %A Abhinav Deshpande %A Christopher L. Baldwin %A Dmitry A. Abanin %A Alexey V. Gorshkov %X

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

%8 5/25/2022 %G eng %U https://arxiv.org/abs/2205.12967 %0 Journal Article %D 2022 %T Snowmass 2021 White Paper: The Windchime Project %A The Windchime Collaboration %A Attanasio, Alaina %A Bhave, Sunil A. %A Blanco, Carlos %A Carney, Daniel %A Demarteau, Marcel %A Elshimy, Bahaa %A Febbraro, Michael %A Feldman, Matthew A. %A Ghosh, Sohitri %A Hickin, Abby %A Hong, Seongjin %A Lang, Rafael F. %A Lawrie, Benjamin %A Li, Shengchao %A Liu, Zhen %A Maldonado, Juan P. A. %A Marvinney, Claire %A Oo, Hein Zay Yar %A Pai, Yun-Yi %A Pooser, Raphael %A Qin, Juehang %A Sparmann, Tobias J. %A Taylor, Jacob M. %A Tian, Hao %A Tunnell, Christopher %K Cosmology and Nongalactic Astrophysics (astro-ph.CO) %K FOS: Physical sciences %K High Energy Physics - Experiment (hep-ex) %K High Energy Physics - Phenomenology (hep-ph) %X

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

%8 3/14/2022 %G eng %U https://arxiv.org/abs/2203.07242 %R 10.48550/ARXIV.2203.07242 %0 Journal Article %J NIST %D 2022 %T Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process %A Gorjan Alagic %A Daniel Apon %A David Cooper %A Quynh Dang %A Thinh Dang %A John Kelsey %A Jacob Lichtinger %A Carl Miller %A Dustin Moody %A Rene Peralta %A Ray Perlner %A Angela Robinson %X

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

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

%B NIST %8 7/2022 %G eng %R https://doi.org/10.6028/NIST.IR.8413-upd1 %0 Journal Article %D 2022 %T A theory of quantum differential equation solvers: limitations and fast-forwarding %A An, Dong %A Liu, Jin-Peng %A Wang, Daochen %A Zhao, Qi %K FOS: Mathematics %K FOS: Physical sciences %K Numerical Analysis (math.NA) %K Quantum Physics (quant-ph) %X

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.

%8 11/9/2022 %G eng %U https://arxiv.org/abs/2211.05246 %R 10.48550/ARXIV.2211.05246 %0 Journal Article %J Quantum %D 2022 %T Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation %A Dong An %A Di Fang %A Lin Lin %X

We propose a simple quantum algorithm for simulating highly oscillatory quantum dynamics, which does not require complicated quantum control logic for handling time-ordering operators. To our knowledge, this is the first quantum algorithm that is both insensitive to the rapid changes of the time-dependent Hamiltonian and exhibits commutator scaling. Our method can be used for efficient Hamiltonian simulation in the interaction picture. In particular, we demonstrate that for the simulation of the Schrödinger equation, our method exhibits superconvergence and achieves a surprising second order convergence rate, of which the proof rests on a careful application of pseudo-differential calculus. Numerical results verify the effectiveness and the superconvergence property of our method.

%B Quantum %V 6 %P 690 %8 apr %G eng %U https://arxiv.org/abs/2111.03103v2 %R 10.22331/q-2022-04-15-690 %0 Journal Article %J Nature Physics %D 2022 %T Where we are with quantum %A Yusuf Alnawakhtha %A Carl Miller %X

A theoretical analysis shows how a person’s location in space could be verified by the transmission of single photons. A vital application of quantum networks may be within reach.

%B Nature Physics %8 4/28/2022 %G eng %! Nat. Phys. %R https://doi.org/10.1038/s41567-022-01597-w %0 Journal Article %J v4: version for publication in Quantum, v5: CC license %D 2021 %T Can you sign a quantum state? %A Gorjan Alagic %A Tommaso Gagliardoni %A Christian Majenz %X

Cryptography with quantum states exhibits a number of surprising and counterintuitive features. In a 2002 work, Barnum et al. argued informally that these strange features should imply that digital signatures for quantum states are impossible (Barnum et al., FOCS 2002). In this work, we perform the first rigorous study of the problem of signing quantum states. We first show that the intuition of Barnum et al. was correct, by proving an impossibility result which rules out even very weak forms of signing quantum states. Essentially, we show that any non-trivial combination of correctness and security requirements results in negligible security. This rules out all quantum signature schemes except those which simply measure the state and then sign the outcome using a classical scheme. In other words, only classical signature schemes exist. We then show a positive result: it is possible to sign quantum states, provided that they are also encrypted with the public key of the intended recipient. Following classical nomenclature, we call this notion quantum signcryption. Classically, signcryption is only interesting if it provides superior efficiency to simultaneous encryption and signing. Our results imply that, quantumly, it is far more interesting: by the laws of quantum mechanics, it is the only signing method available. We develop security definitions for quantum signcryption, ranging from a simple one-time two-user setting, to a chosen-ciphertext-secure many-time multi-user setting. We also give secure constructions based on post-quantum public-key primitives. Along the way, we show that a natural hybrid method of combining classical and quantum schemes can be used to "upgrade" a secure classical scheme to the fully-quantum setting, in a wide range of cryptographic settings including signcryption, authenticated encryption, and chosen-ciphertext security.

%B v4: version for publication in Quantum, v5: CC license %8 12/6/2021 %G eng %U https://arxiv.org/abs/1811.11858 %0 Journal Article %D 2021 %T Chiral transport of hot carriers in graphene in the quantum Hall regime %A Bin Cao %A Tobias Grass %A Olivier Gazzano %A Kishan Ashokbhai Patel %A Jiuning Hu %A Markus Müller %A Tobias Huber %A Luca Anzi %A Kenji Watanabe %A Takashi Taniguchi %A David Newell %A Michael Gullans %A Roman Sordan %A Mohammad Hafezi %A Glenn Solomon %X

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. 

%8 10/3/2021 %G eng %U https://arxiv.org/abs/2110.01079 %0 Journal Article %D 2021 %T Constructing quantum many-body scar Hamiltonians from Floquet automata %A Pierre-Gabriel Rozon %A Michael Gullans %A Kartiek Agarwal %X

We provide a systematic approach for constructing approximate quantum many-body scars(QMBS) starting from two-layer Floquet automaton circuits that exhibit trivial many-body revivals. We do so by applying successively more restrictions that force local gates of the automaton circuit to commute concomitantly more accurately when acting on select scar states. With these rules in place, an effective local, Floquet Hamiltonian is seen to capture dynamics of the automata over a long prethermal window, and neglected terms can be used to estimate the relaxation of revivals. We provide numerical evidence for such a picture and use our construction to derive several QMBS models, including the celebrated PXP model.

%8 12/22/2021 %G eng %U https://arxiv.org/abs/2112.12153 %0 Journal Article %D 2021 %T Cross-Platform Comparison of Arbitrary Quantum Computations %A Daiwei Zhu %A Ze-Pei Cian %A Crystal Noel %A Andrew Risinger %A Debopriyo Biswas %A Laird Egan %A Yingyue Zhu %A Alaina M. Green %A Cinthia Huerta Alderete %A Nhung H. Nguyen %A Qingfeng Wang %A Andrii Maksymov %A Yunseong Nam %A Marko Cetina %A Norbert M. Linke %A Mohammad Hafezi %A Christopher Monroe %X

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.

%8 7/27/2021 %G eng %U https://arxiv.org/abs/2107.11387 %0 Journal Article %J Nat. Phys. %D 2021 %T Device-independent Randomness Expansion with Entangled Photons %A Lynden K. Shalm %A Yanbao Zhang %A Joshua C. Bienfang %A Collin Schlager %A Martin J. Stevens %A Michael D. Mazurek %A Carlos Abellán %A Waldimar Amaya %A Morgan W. Mitchell %A Mohammad A. Alhejji %A Honghao Fu %A Joel Ornstein %A Richard P. Mirin %A Sae Woo Nam %A Emanuel Knill %X

With the growing availability of experimental loophole-free Bell tests, it has become possible to implement a new class of device-independent random number generators whose output can be certified to be uniformly random without requiring a detailed model of the quantum devices used. However, all of these experiments require many input bits in order to certify a small number of output bits, and it is an outstanding challenge to develop a system that generates more randomness than is used. Here, we devise a device-independent spot-checking protocol which uses only uniform bits as input. Implemented with a photonic loophole-free Bell test, we can produce 24% more certified output bits (1,181,264,237) than consumed input bits (953,301,640), which is 5 orders of magnitude more efficient than our previous work [arXiv:1812.07786]. The experiment ran for 91.0 hours, creating randomness at an average rate of 3606 bits/s with a soundness error bounded by 5.7×10−7 in the presence of classical side information. Our system will allow for greater trust in public sources of randomness, such as randomness beacons, and the protocols may one day enable high-quality sources of private randomness as the device footprint shrinks.

%B Nat. Phys. %8 01/28/2021 %G eng %U https://arxiv.org/abs/1912.11158 %R https://doi.org/10.1038/s41567-020-01153-4 %0 Journal Article %D 2021 %T Estimating distinguishability measures on quantum computers %A Rochisha Agarwal %A Soorya Rethinasamy %A Kunal Sharma %A Mark M. Wilde %X

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. 

%8 8/18/2021 %G eng %U https://arxiv.org/abs/2108.08406 %0 Journal Article %J Physical Review X %D 2021 %T Maximum Refractive Index of an Atomic Medium %A Andreoli, Francesco %A Michael Gullans %A High, Alexander A. %A Browaeys, Antoine %A Chang, Darrick E. %X

It is interesting to observe that all optical materials with a positive refractive index have a value of index that is of order unity. Surprisingly, though, a deep understanding of the mechanisms that lead to this universal behavior seems to be lacking. Moreover, this observation is difficult to reconcile with the fact that a single, isolated atom is known to have a giant optical response, as characterized by a resonant scattering cross section that far exceeds its physical size. Here, we theoretically and numerically investigate the evolution of the optical properties of an ensemble of ideal atoms as a function of density, starting from the dilute gas limit, including the effects of multiple scattering and near-field interactions. Interestingly, despite the giant response of an isolated atom, we find that the maximum index does not indefinitely grow with increasing density, but rather reaches a limiting value n≈1.7. We propose an explanation based upon strong-disorder renormalization group theory, in which the near-field interaction combined with random atomic positions results in an inhomogeneous broadening of atomic resonance frequencies. This mechanism ensures that regardless of the physical atomic density, light at any given frequency only interacts with at most a few near-resonant atoms per cubic wavelength, thus limiting the maximum index attainable. Our work is a promising first step to understand the limits of refractive index from a bottom-up, atomic physics perspective, and also introduces renormalization group as a powerful tool to understand the generally complex problem of multiple scattering of light overall.

%B Physical Review X %V 11 %8 2/18/2021 %G eng %U https://arxiv.org/abs/2006.01680 %N 1 %! Phys. Rev. X %R 10.1103/PhysRevX.11.011026 %0 Journal Article %D 2021 %T Optimal scaling quantum linear systems solver via discrete adiabatic theorem %A Pedro C. S. Costa %A Dong An %A Yuval R. Sanders %A Yuan Su %A Ryan Babbush %A Dominic W. Berry %X

Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian. Such approaches enabled near-linear scaling in the condition number κ of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedures is still asymptotically sub-optimal by a factor of log(κ). Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete time evolutions. We use this discrete adiabatic theorem to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in κ, matching a known lower bound on the complexity. Our O(κlog(1/ε)) complexity is also optimal in terms of the combined scaling in κ and the precision ε. Compared to existing suboptimal methods, our algorithm is simpler and easier to implement. Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific applications. 

%8 11/15/2021 %G eng %U https://arxiv.org/abs/2111.08152 %0 Journal Article %J Physical Review A %D 2021 %T Phase-engineered bosonic quantum codes %A Linshu Li %A Dylan J Young %A Victor V. Albert %A Kyungjoo Noh %A Chang-Ling Zou %A Liang Jiang %X

Continuous-variable systems protected by bosonic quantum codes have emerged as a promising platform for quantum information. To date, the design of code words has centered on optimizing the state occupation in the relevant basis to generate the distance needed for error correction. Here, we show tuning the phase degree of freedom in the design of code words can affect, and potentially enhance, the protection against Markovian errors that involve excitation exchange with the environment. As illustrations, we first consider phase engineering bosonic codes with uniform spacing in the Fock basis that correct excitation loss with a Kerr unitary and show that these modified codes feature destructive interference between error code words and, with an adapted “two-level” recovery, the error protection is significantly enhanced. We then study protection against energy decay with the presence of mode nonlinearities …

%B Physical Review A %V 103 %P 062427 %8 6/29/2021 %G eng %U https://authors.library.caltech.edu/109764/2/1901.05358.pdf %N 6 %0 Journal Article %J Physical Review A %D 2021 %T Quantum circuits for the realization of equivalent forms of one-dimensional discrete-time quantum walks on near-term quantum hardware %A Singh, Shivani %A Alderete, C. Huerta %A Balu, Radhakrishnan %A Monroe, Christopher %A Linke, Norbert M. %A Chandrashekar, C. M. %X

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

%B Physical Review A %V 104 %8 12/8/2021 %G eng %U https://arxiv.org/abs/2001.11197 %R https://doi.org/10.1103/PhysRevA.104.062401 %0 Journal Article %D 2021 %T Quantum Machine Learning for Finance %A Marco Pistoia %A Syed Farhan Ahmad %A Akshay Ajagekar %A Alexander Buts %A Shouvanik Chakrabarti %A Dylan Herman %A Shaohan Hu %A Andrew Jena %A Pierre Minssen %A Pradeep Niroula %A Arthur Rattew %A Yue Sun %A Romina Yalovetzky %X

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

%8 9/9/2021 %G eng %U https://arxiv.org/abs/2109.04298 %0 Journal Article %J Quantum 5, 481 (2021) %D 2021 %T Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance %A Dong An %A Noah Linden %A Jin-Peng Liu %A Ashley Montanaro %A Changpeng Shao %A Jiasu Wang %X

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.

%B Quantum 5, 481 (2021) %V 5 %P 481 %8 6/22/2021 %G eng %U https://arxiv.org/abs/2012.06283 %R https://doi.org/10.22331/q-2021-06-24-481 %0 Journal Article %D 2021 %T Relaxation of non-integrable systems and correlation functions %A Riddell, Jonathon %A García-Pintos, Luis Pedro %A Alhambra, Álvaro M. %K FOS: Physical sciences %K Quantum Physics (quant-ph) %K Statistical Mechanics (cond-mat.stat-mech) %K Strongly Correlated Electrons (cond-mat.str-el) %X

We investigate early-time equilibration rates of observables in closed many-body quantum systems and compare them to those of two correlation functions, first introduced by Kubo and Srednicki. We explore whether these different rates coincide at a universal value that sets the timescales of processes at a finite energy density. We find evidence for this coincidence when the initial conditions are sufficiently generic, or typical. We quantify this with the effective dimension of the state and with a state-observable effective dimension, which estimate the number of energy levels that participate in the dynamics. Our findings are confirmed by proving that these different timescales coincide for dynamics generated by Haar-random Hamiltonians. This also allows to quantitatively understand the scope of previous theoretical results on equilibration timescales and on random matrix formalisms. We approach this problem with exact, full spectrum diagonalization. The numerics are carried out in a non-integrable Heisenberg-like Hamiltonian, and the dynamics are investigated for several pairs of observables and states.

%8 12/17/2021 %G eng %U https://arxiv.org/abs/2112.09475 %R 10.48550/ARXIV.2112.09475 %0 Journal Article %D 2021 %T Spin chains, defects, and quantum wires for the quantum-double edge %A Victor V. Albert %A David Aasen %A Wenqing Xu %A Wenjie Ji %A Jason Alicea %A John Preskill %X

Non-Abelian defects that bind Majorana or parafermion zero modes are prominent in several topological quantum computation schemes. Underpinning their established understanding is the quantum Ising spin chain, which can be recast as a fermionic model or viewed as a standalone effective theory for the surface-code edge -- both of which harbor non-Abelian defects. We generalize these notions by deriving an effective Ising-like spin chain describing the edge of quantum-double topological order. Relating Majorana and parafermion modes to anyonic strings, we introduce quantum-double generalizations of non-Abelian defects. We develop a way to embed finite-group valued qunits into those valued in continuous groups. Using this embedding, we provide a continuum description of the spin chain and recast its non-interacting part as a quantum wire via addition of a Wess-Zumino-Novikov-Witten term and non-Abelian bosonization.

%8 11/23/2021 %G eng %U https://arxiv.org/abs/2111.12096 %0 Journal Article %J Phys. Rev. X %D 2020 %T Continuous symmetries and approximate quantum error correction %A Philippe Faist %A Sepehr Nezami %A Victor V. Albert %A Grant Salton %A Fernando Pastawski %A Patrick Hayden %A John Preskill %X

Quantum error correction and symmetry arise in many areas of physics, including many-body systems, metrology in the presence of noise, fault-tolerant computation, and holographic quantum gravity. Here we study the compatibility of these two important principles. If a logical quantum system is encoded into n physical subsystems, we say that the code is covariant with respect to a symmetry group G if a G transformation on the logical system can be realized by performing transformations on the individual subsystems. For a G-covariant code with G a continuous group, we derive a lower bound on the error correction infidelity following erasure of a subsystem. This bound approaches zero when the number of subsystems n or the dimension d of each subsystem is large. We exhibit codes achieving approximately the same scaling of infidelity with n or d as the lower bound. Leveraging tools from representation theory, we prove an approximate version of the Eastin-Knill theorem: If a code admits a universal set of transversal gates and corrects erasure with fixed accuracy, then, for each logical qubit, we need a number of physical qubits per subsystem that is inversely proportional to the error parameter. We construct codes covariant with respect to the full logical unitary group, achieving good accuracy for large d (using random codes) or n (using codes based on W-states). We systematically construct codes covariant with respect to general groups, obtaining natural generalizations of qubit codes to, for instance, oscillators and rotors. In the context of the AdS/CFT correspondence, our approach provides insight into how time evolution in the bulk corresponds to time evolution on the boundary without violating the Eastin-Knill theorem, and our five-rotor code can be stacked to form a covariant holographic code.

%B Phys. Rev. X %V 10 %8 10/26/2020 %G eng %U https://arxiv.org/abs/1902.07714 %N 041018 %R https://journals.aps.org/prx/abstract/10.1103/PhysRevX.10.041018 %0 Journal Article %J In: Canteaut A., Ishai Y. (eds) Advances in Cryptology – EUROCRYPT 2020. Lecture Notes in Computer Science, Springer, Cham %D 2020 %T Efficient Simulation of Random States and Random Unitaries %A Gorjan Alagic %A Christian Majenz %A Alexander Russell %X

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

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

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

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

%B In: Canteaut A., Ishai Y. (eds) Advances in Cryptology – EUROCRYPT 2020. Lecture Notes in Computer Science, Springer, Cham %V 12107 %P 759-787 %8 5/1/2020 %G eng %9 inproceedings %R https://doi.org/10.1007/978-3-030-45727-3_26 %0 Journal Article %J Phys. Rev. Lett. %D 2020 %T Experimental Low-Latency Device-Independent Quantum Randomness %A Yanbao Zhang %A Lynden K. Shalm %A Joshua C. Bienfang %A Martin J. Stevens %A Michael D. Mazurek %A Sae Woo Nam %A Carlos Abellán %A Waldimar Amaya %A Morgan W. Mitchell %A Honghao Fu %A Carl Miller %A Alan Mink %A Emanuel Knill %X

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

%B Phys. Rev. Lett. %V 124 %8 12/24/2019 %G eng %U https://arxiv.org/abs/1812.07786 %N 010505 %R https://doi.org/10.1103/PhysRevLett.124.010505 %0 Magazine Article %D 2020 %T Impossibility of Quantum Virtual Black-Box Obfuscation of Classical Circuits %A Gorjan Alagic %A Zvika Brakerski %A Yfke Dulek %A Christian Schaffner %X

Virtual black-box obfuscation is a strong cryptographic primitive: it encrypts a circuit while maintaining its full input/output functionality. A remarkable result by Barak et al. (Crypto 2001) shows that a general obfuscator that obfuscates classical circuits into classical circuits cannot exist. A promising direction that circumvents this impossibility result is to obfuscate classical circuits into quantum states, which would potentially be better capable of hiding information about the obfuscated circuit. We show that, under the assumption that learning-with-errors (LWE) is hard for quantum computers, this quantum variant of virtual black-box obfuscation of classical circuits is generally impossible. On the way, we show that under the presence of dependent classical auxiliary input, even the small class of classical point functions cannot be quantum virtual black-box obfuscated.

%8 5/13/2020 %G eng %U https://arxiv.org/abs/2005.06432 %0 Journal Article %D 2020 %T Mechanical Quantum Sensing in the Search for Dark Matter %A D. Carney %A G. Krnjaic %A D. C. Moore %A C. A. Regal %A G. Afek %A S. Bhave %A B. Brubaker %A T. Corbitt %A J. Cripe %A N. Crisosto %A A.Geraci %A S. Ghosh %A J. G. E. Harris %A A. Hook %A E. W. Kolb %A J. Kunjummen %A R. F. Lang %A T. Li %A T. Lin %A Z. Liu %A J. Lykken %A L. Magrini %A J. Manley %A N. Matsumoto %A A. Monte %A F. Monteiro %A T. Purdy %A C. J. Riedel %A R. Singh %A S. Singh %A K. Sinha %A J. M. Taylor %A J. Qin %A D. J. Wilson %A Y. Zhao %X

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.

%8 8/13/2020 %G eng %U https://arxiv.org/abs/2008.06074 %9 FERMILAB-PUB-20-378-QIS-T %0 Journal Article %J Theory of Cryptography Conference (TCC) %D 2020 %T Non-interactive classical verification of quantum computation %A Gorjan Alagic %A Andrew M. Childs %A Alex B. Grilo %A Shih-Han Hung %X

In a recent breakthrough, Mahadev constructed an interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. In this work, we show that this same task can in fact be performed non-interactively and in zero-knowledge.
Our protocols result from a sequence of significant improvements to the original four-message protocol of Mahadev. We begin by making the first message instance-independent and moving it to an offline setup phase. We then establish a parallel repetition theorem for the resulting three-message protocol, with an asymptotically optimal rate. This, in turn, enables an application of the Fiat-Shamir heuristic, eliminating the second message and giving a non-interactive protocol. Finally, we employ classical non-interactive zero-knowledge (NIZK) arguments and classical fully homomorphic encryption (FHE) to give a zero-knowledge variant of this construction. This yields the first purely classical NIZK argument system for QMA, a quantum analogue of NP.
We establish the security of our protocols under standard assumptions in quantum-secure cryptography. Specifically, our protocols are secure in the Quantum Random Oracle Model, under the assumption that Learning with Errors is quantumly hard. The NIZK construction also requires circuit-private FHE.

%B Theory of Cryptography Conference (TCC) %V Lecture Notes in Computer Science 12552 %P 153-180 %8 3/9/2020 %G eng %U https://arxiv.org/abs/1911.08101 %0 Journal Article %D 2020 %T Probing many-body localization on a noisy quantum computer %A D. Zhu %A S. Johri %A N. H. Nguyen %A C. Huerta Alderete %A K. A. Landsman %A N. M. Linke %A C. Monroe %A A. Y. Matsuura %X

A disordered system of interacting particles exhibits localized behavior when the disorder is large compared to the interaction strength. Studying this phenomenon on a quantum computer without error correction is challenging because even weak coupling to a thermal environment destroys most signatures of localization. Fortunately, spectral functions of local operators are known to contain features that can survive the presence of noise. In these spectra, discrete peaks and a soft gap at low frequencies compared to the thermal phase indicate localization. Here, we present the computation of spectral functions on a trapped-ion quantum computer for a one-dimensional Heisenberg model with disorder. Further, we design an error-mitigation technique which is effective at removing the noise from the measurement allowing clear signatures of localization to emerge as the disorder increases. Thus, we show that spectral functions can serve as a robust and scalable diagnostic of many-body localization on the current generation of quantum computers. 

%8 6/22/2020 %G eng %U https://arxiv.org/abs/2006.12355 %0 Journal Article %D 2020 %T Probing XY phase transitions in a Josephson junction array with tunable frustration %A R. Cosmic %A K. Kawabata %A Y. Ashida %A H. Ikegami %A S. Furukawa %A P. Patil %A J. M. Taylor %A Y. Nakamura %X

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

%8 1/22/2020 %G eng %U https://arxiv.org/abs/2001.07877 %0 Journal Article %J Cryptography %D 2020 %T On Quantum Chosen-Ciphertext Attacks and Learning with Errors %A Gorjan Alagic %A Stacey Jeffery %A Maris Ozols %A Alexander Poremba %X

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

%B Cryptography %V 4 %P 10 %8 3/21/2020 %G eng %N 1 %R https://doi.org/10.3390/cryptography4010010 %0 Journal Article %J Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics %D 2020 %T Quantum Coupon Collector %A Srinivasan Arunachalam %A Aleksandrs Belovs %A Andrew M. Childs %A Robin Kothari %A Ansis Rosmanis %A Ronald de Wolf %X

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

%B Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics %V 158 %P 10:1-10:17 %8 2/18/2020 %G eng %U https://arxiv.org/abs/2002.07688 %R 10.4230/LIPIcs.TQC.2020.10 %0 Journal Article %D 2020 %T Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer %A C. Huerta Alderete %A Shivani Singh %A Nhung H. Nguyen %A Daiwei Zhu %A Radhakrishnan Balu %A Christopher Monroe %A C. M. Chandrashekar %A Norbert M. Linke %X

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

%8 2/6/2020 %G eng %U https://arxiv.org/abs/2002.02537 %0 Journal Article %J In: Canteaut A., Ishai Y. (eds) Advances in Cryptology – EUROCRYPT 2020. Lecture Notes in Computer Science, Springer, Cham %D 2020 %T Quantum-Access-Secure Message Authentication via Blind-Unforgeability %A Gorjan Alagic %A Christian Majenz %A Alexander Russell %A Fang Song %X

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

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

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

%B In: Canteaut A., Ishai Y. (eds) Advances in Cryptology – EUROCRYPT 2020. Lecture Notes in Computer Science, Springer, Cham %V 12-17 %P 788-817 %8 5/1/2020 %G eng %9 inproceedings %R https://doi.org/10.1007/978-3-030-45727-3_27 %0 Journal Article %J Phys. Rev. X %D 2020 %T Robust Encoding of a Qubit in a Molecule %A Victor V. Albert %A Jacob P. Covey %A John Preskill %X

We construct quantum error-correcting codes that embed a finite-dimensional code space in the infinite-dimensional Hilbert space of rotational states of a rigid body. These codes, which protect against both drift in the body’s orientation and small changes in its angular momentum, may be well suited for robust storage and coherent processing of quantum information using rotational states of a polyatomic molecule. Extensions of such codes to rigid bodies with a symmetry axis are compatible with rotational states of diatomic molecules as well as nuclear states of molecules and atoms. We also describe codes associated with general non-Abelian groups and develop orthogonality relations for coset spaces, laying the groundwork for quantum information processing with exotic configuration spaces.

%B Phys. Rev. X %V 10 %8 9/1/2020 %G eng %U https://arxiv.org/abs/1911.00099 %N 031050 %R https://journals.aps.org/prx/abstract/10.1103/PhysRevX.10.031050 %0 Journal Article %J Phys. Rev. Lett. %D 2020 %T Search for composite dark matter with optically levitated sensors %A Fernando Monteiro %A Gadi Afek %A Daniel Carney %A Gordan Krnjaic %A Jiaxiang Wang %A David C. Moore %X

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. 

%B Phys. Rev. Lett. %V 125 %8 11/2/2020 %G eng %U https://arxiv.org/abs/2007.12067 %N 181102 %R https://doi.org/10.1103/PhysRevLett.125.181102 %0 Journal Article %J NISTIR 8309 %D 2020 %T Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process %A Gorjan Alagic %A Jacob Alperin-Sheriff %A Daniel Apon %A David Cooper %A Quynh Dang %A John Kelsey %A Yi-Kai Liu %A Carl Miller %A Dustin Moody %A Rene Peralta %A Ray Perlner %A Angela Robinson %A Daniel Smith-Tone %X

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

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

%B NISTIR 8309 %8 07/2020 %G eng %R https://doi.org/10.6028/NIST.IR.8309 %0 Journal Article %J Phys. Rev. Lett. %D 2020 %T Symmetry breaking and error correction in open quantum systems %A Simon Lieu %A Ron Belyansky %A Jeremy T. Young %A Rex Lundgren %A Victor V. Albert %A Alexey V. Gorshkov %X

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

%B Phys. Rev. Lett. %V 125 %P 240405 %8 8/6/2020 %G eng %U https://arxiv.org/abs/2008.02816 %R https://doi.org/10.1103/PhysRevLett.125.240405 %0 Journal Article %J Phys. Rev. Lett %D 2020 %T Time evolution of correlation functions in quantum many-body systems %A Álvaro M. Alhambra %A Jonathon Riddell %A Luis Pedro García-Pintos %X

We give rigorous analytical results on the temporal behavior of two-point correlation functions --also known as dynamical response functions or Green's functions-- in closed many-body quantum systems. We show that in a large class of translation-invariant models the correlation functions factorize at late times ⟨A(t)B⟩β→⟨A⟩β⟨B⟩β, thus proving that dissipation emerges out of the unitary dynamics of the system. We also show that for systems with a generic spectrum the fluctuations around this late-time value are bounded by the purity of the thermal ensemble, which generally decays exponentially with system size. For auto-correlation functions we provide an upper bound on the timescale at which they reach the factorized late time value. Remarkably, this bound is only a function of local expectation values, and does not increase with system size. We give numerical examples that show that this bound is a good estimate in non-integrable models, and argue that the timescale that appears can be understood in terms of an emergent fluctuation-dissipation theorem. Our study extends to further classes of two point functions such as the symmetrized ones and the Kubo function that appears in linear response theory, for which we give analogous results.

%B Phys. Rev. Lett %V 124 %8 3/19/2020 %G eng %U https://arxiv.org/abs/1906.11280 %N 110605 %R https://doi.org/10.1103/PhysRevLett.124.110605 %0 Journal Article %D 2020 %T Universal one-dimensional discrete-time quantum walks and their implementation on near term quantum hardware %A Shivani Singh %A Cinthia H. Alderete %A Radhakrishnan Balu %A Christopher Monroe %A Norbert M. Linke %A C. M. Chandrashekar %X

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

%8 1/30/2020 %G eng %U https://arxiv.org/abs/2001.11197 %0 Journal Article %D 2019 %T Development of Quantum InterConnects for Next-Generation Information Technologies %A David Awschalom %A Karl K. Berggren %A Hannes Bernien %A Sunil Bhave %A Lincoln D. Carr %A Paul Davids %A Sophia E. Economou %A Dirk Englund %A Andrei Faraon %A Marty Fejer %A Saikat Guha %A Martin V. Gustafsson %A Evelyn Hu %A Liang Jiang %A Jungsang Kim %A Boris Korzh %A Prem Kumar %A Paul G. Kwiat %A Marko Lončar %A Mikhail D. Lukin %A David A. B. Miller %A Christopher Monroe %A Sae Woo Nam %A Prineha Narang %A Jason S. Orcutt %X

Just as classical information technology rests on a foundation built of interconnected information-processing systems, quantum information technology (QIT) must do the same. A critical component of such systems is the interconnect, a device or process that allows transfer of information between disparate physical media, for example, semiconductor electronics, individual atoms, light pulses in optical fiber, or microwave fields. While interconnects have been well engineered for decades in the realm of classical information technology, quantum interconnects (QuICs) present special challenges, as they must allow the transfer of fragile quantum states between different physical parts or degrees of freedom of the system. The diversity of QIT platforms (superconducting, atomic, solid-state color center, optical, etc.) that will form a quantum internet poses additional challenges. As quantum systems scale to larger size, the quantum interconnect bottleneck is imminent, and is emerging as a grand challenge for QIT. For these reasons, it is the position of the community represented by participants of the NSF workshop on Quantum Interconnects that accelerating QuIC research is crucial for sustained development of a national quantum science and technology program. Given the diversity of QIT platforms, materials used, applications, and infrastructure required, a convergent research program including partnership between academia, industry and national laboratories is required. This document is a summary from a U.S. National Science Foundation supported workshop held on 31 October - 1 November 2019 in Alexandria, VA. Attendees were charged to identify the scientific and community needs, opportunities, and significant challenges for quantum interconnects over the next 2-5 years. 

%8 12/13/2019 %G eng %U https://arxiv.org/abs/1912.06642 %0 Journal Article %D 2019 %T Ground-state energy estimation of the water molecule on a trapped ion quantum computer %A Yunseong Nam %A Jwo-Sy Chen %A Neal C. Pisenti %A Kenneth Wright %A Conor Delaney %A Dmitri Maslov %A Kenneth R. Brown %A Stewart Allen %A Jason M. Amini %A Joel Apisdorf %A Kristin M. Beck %A Aleksey Blinov %A Vandiver Chaplin %A Mika Chmielewski %A Coleman Collins %A Shantanu Debnath %A Andrew M. Ducore %A Kai M. Hudek %A Matthew Keesan %A Sarah M. Kreikemeier %A Jonathan Mizrahi %A Phil Solomon %A Mike Williams %A Jaime David Wong-Campos %A Christopher Monroe %A Jungsang Kim %X

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.

%8 03/07/2019 %G eng %U https://arxiv.org/abs/1902.10171 %0 Journal Article %J Phys. Rev. A %D 2019 %T Locality and Heating in Periodically Driven, Power-law Interacting Systems %A Minh C. Tran %A Adam Ehrenberg %A Andrew Y. Guo %A Paraj Titum %A Dmitry A. Abanin %A Alexey V. Gorshkov %X

We study the heating time in periodically driven D-dimensional systems with interactions that decay with the distance r as a power-law 1/rα. Using linear response theory, we show that the heating time is exponentially long as a function of the drive frequency for α>D. For systems that may not obey linear response theory, we use a more general Magnus-like expansion to show the existence of quasi-conserved observables, which imply exponentially long heating time, for α>2D. We also generalize a number of recent state-of-the-art Lieb-Robinson bounds for power-law systems from two-body interactions to k-body interactions and thereby obtain a longer heating time than previously established in the literature. Additionally, we conjecture that the gap between the results from the linear response theory and the Magnus-like expansion does not have physical implications, but is, rather, due to the lack of tight Lieb-Robinson bounds for power-law interactions. We show that the gap vanishes in the presence of a hypothetical, tight bound. 

%B Phys. Rev. A %V 100 %8 2019/11/12 %G eng %U https://arxiv.org/abs/1908.02773 %N 052103 %R https://doi.org/10.1103/PhysRevA.100.052103 %0 Journal Article %J 14th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2019, June 3-5, 2019, University of Maryland, College Park, Maryland, USA %D 2019 %T On non-adaptive quantum chosen-ciphertext attacks and Learning with Errors %A Gorjan Alagic %A Stacey Jeffery %A Maris Ozols %A Alexander Poremba %X

Large-scale quantum computing is a significant threat to classical public-key cryptography. In strong "quantum access" security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum random-access codes, we show that the standard PRF- and PRP-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives. We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key uses a linear number of decryption queries, and this is optimal. The algorithm at the core of our attack is a (large-modulus version of) the well-known Bernstein-Vazirani algorithm. We emphasize that our results should *not* be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones. 

%B 14th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2019, June 3-5, 2019, University of Maryland, College Park, Maryland, USA %P 1:1-1:23 %G eng %U https://arxiv.org/abs/1808.09655 %R https://doi.org/10.4230/LIPIcs.TQC.2019.1 %0 Journal Article %D 2019 %T Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits %A Matthew Amy %A Andrew N. Glaudell %A Neil J. Ross %X

Kliuchnikov, Maslov, and Mosca proved in 2012 that a 2×2 unitary matrix V can be exactly represented by a single-qubit Clifford+T circuit if and only if the entries of V belong to the ring Z[1/2–√,i]. Later that year, Giles and Selinger showed that the same restriction applies to matrices that can be exactly represented by a multi-qubit Clifford+T circuit. These number-theoretic characterizations shed new light upon the structure of Clifford+T circuits and led to remarkable developments in the field of quantum compiling. In the present paper, we provide number-theoretic characterizations for certain restricted Clifford+T circuits by considering unitary matrices over subrings of Z[1/2–√,i]. We focus on the subrings Z[1/2], Z[1/2–√], Z[1/-2−−√], and Z[1/2,i], and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates {X,CX,CCX} with an analogue of the Hadamard gate and an optional phase gate.

%8 8/16/2019 %G eng %U https://arxiv.org/abs/1908.06076 %0 Journal Article %D 2019 %T Opportunities for Nuclear Physics & Quantum Information Science %A I. C. Cloët %A Matthew R. Dietrich %A John Arrington %A Alexei Bazavov %A Michael Bishof %A Adam Freese %A Alexey V. Gorshkov %A Anna Grassellino %A Kawtar Hafidi %A Zubin Jacob %A Michael McGuigan %A Yannick Meurice %A Zein-Eddine Meziani %A Peter Mueller %A Christine Muschik %A James Osborn %A Matthew Otten %A Peter Petreczky %A Tomas Polakovic %A Alan Poon %A Raphael Pooser %A Alessandro Roggero %A Mark Saffman %A Brent VanDevender %A Jiehang Zhang %A Erez Zohar %X

his whitepaper is an outcome of the workshop Intersections between Nuclear Physics and Quantum Information held at Argonne National Laboratory on 28-30 March 2018 [www.phy.anl.gov/npqi2018/]. The workshop brought together 116 national and international experts in nuclear physics and quantum information science to explore opportunities for the two fields to collaborate on topics of interest to the U.S. Department of Energy (DOE) Office of Science, Office of Nuclear Physics, and more broadly to U.S. society and industry. The workshop consisted of 22 invited and 10 contributed talks, as well as three panel discussion sessions. Topics discussed included quantum computation, quantum simulation, quantum sensing, nuclear physics detectors, nuclear many-body problem, entanglement at collider energies, and lattice gauge theories.

%8 03/13/2019 %G eng %U https://arxiv.org/abs/1903.05453 %0 Journal Article %D 2019 %T Quantum Computer Systems for Scientific Discovery %A Yuri Alexeev %A Dave Bacon %A Kenneth R. Brown %A Robert Calderbank %A Lincoln D. Carr %A Frederic T. Chong %A Brian DeMarco %A Dirk Englund %A Edward Farhi %A Bill Fefferman %A Alexey V. Gorshkov %A Andrew Houck %A Jungsang Kim %A Shelby Kimmel %A Michael Lange %A Seth Lloyd %A Mikhail D. Lukin %A Dmitri Maslov %A Peter Maunz %A Christopher Monroe %A John Preskill %A Martin Roetteler %A Martin Savage %A Jeff Thompson %A Umesh Vazirani %X

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

%8 12/16/2019 %G eng %U https://arxiv.org/abs/1912.07577 %0 Journal Article %D 2019 %T Quantum Computing at the Frontiers of Biological Sciences %A Prashant S. Emani %A Jonathan Warrell %A Alan Anticevic %A Stefan Bekiranov %A Michael Gandal %A Michael J. McConnell %A Guillermo Sapiro %A Alán Aspuru-Guzik %A Justin Baker %A Matteo Bastiani %A Patrick McClure %A John Murray %A Stamatios N Sotiropoulos %A J. M. Taylor %A Geetha Senthil %A Thomas Lehner %A Mark B. Gerstein %A Aram W. Harrow %X

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. 

%8 2019/11/16 %G eng %U https://arxiv.org/abs/1911.07127 %0 Journal Article %D 2019 %T Quantum hardness of learning shallow classical circuits %A Srinivasan Arunachalam %A Alex B. Grilo %A Aarthi Sundaram %X

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

%8 03/07/2019 %G eng %U https://arxiv.org/abs/1903.02840 %0 Journal Article %D 2019 %T Quantum Simulators: Architectures and Opportunities %A Ehud Altman %A Kenneth R. Brown %A Giuseppe Carleo %A Lincoln D. Carr %A Eugene Demler %A Cheng Chin %A Brian DeMarco %A Sophia E. Economou %A Mark A. Eriksson %A Kai-Mei C. Fu %A Markus Greiner %A Kaden R. A. Hazzard %A Randall G. Hulet %A Alicia J. Kollár %A Benjamin L. Lev %A Mikhail D. Lukin %A Ruichao Ma %A Xiao Mi %A Shashank Misra %A Christopher Monroe %A Kater Murch %A Zaira Nazario %A Kang-Kuen Ni %A Andrew C. Potter %A Pedram Roushan %X

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

%8 12/14/2019 %G eng %U https://arxiv.org/abs/1912.06938 %0 Journal Article %J School: National Institute for Standards and Technology %D 2019 %T Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process %A Gorjan Alagic %A J. Alperin-Sheriff %A D. Apon %A D. Cooper %A Q. Dang %A Carl Miller %A D. Moody %A R. Peralta %A R. Perlner %A A. Robinson %A D. Smith-Tone %A Yi-Kai Liu %X

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

%B School: National Institute for Standards and Technology %G eng %U https://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8240.pdf %9 techreport %0 Journal Article %D 2019 %T Universal Constraints on Energy Flow and SYK Thermalization %A Ahmed Almheiri %A Alexey Milekhin %A Brian Swingle %8 12/10/2019 %G eng %U https://arxiv.org/abs/1912.04912 %0 Journal Article %J New Journal of Physics %D 2018 %T Optimization of photon storage fidelity in ordered atomic arrays %A M. T. Manzoni %A M. Moreno-Cardoner %A A. Asenjo-Garcia %A J. V. Porto %A Alexey V. Gorshkov %A D. E. Chang %X

A major application for atomic ensembles consists of a quantum memory for light, in which an optical state can be reversibly converted to a collective atomic excitation on demand. There exists a well-known fundamental bound on the storage error, when the ensemble is describable by a continuous medium governed by the Maxwell-Bloch equations. The validity of this model can break down, however, in systems such as dense, ordered atomic arrays, where strong interference in emission can give rise to phenomena such as subradiance and "selective" radiance. Here, we develop a general formalism that finds the maximum storage efficiency for a collection of atoms with discrete, known positions, and a given spatial mode in which an optical field is sent. As an example, we apply this technique to study a finite two-dimensional square array of atoms. We show that such a system enables a storage error that scales with atom number Na like ∼(logNa)2/N2a, and that, remarkably, an array of just 4×4 atoms in principle allows for an efficiency comparable to a disordered ensemble with optical depth of around 600.

%B New Journal of Physics %V 20 %8 2018/08/31 %G eng %U https://arxiv.org/abs/1710.06312 %N 083048 %R https://doi.org/10.1088/1367-2630/aadb74 %0 Journal Article %D 2018 %T Quantum-secure message authentication via blind-unforgeability %A Gorjan Alagic %A Christian Majenz %A Alexander Russell %A Fang Song %X

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

%G eng %U https://arxiv.org/abs/1803.03761 %0 Journal Article %D 2018 %T Spectrum estimation of density operators with alkaline-earth atoms %A Michael E. Beverland %A Jeongwan Haah %A Gorjan Alagic %A Gretchen K. Campbell %A Ana Maria Rey %A Alexey V. Gorshkov %X

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

%V 120 %8 2018/01/09 %G eng %U http://arxiv.org/abs/1608.02045 %N 025301 %R https://doi.org/10.1103/PhysRevLett.120.025301 %0 Journal Article %D 2018 %T Study of radon reduction in gases for rare event search experiments %A K. Pushkin %A C. Akerlof %A D. Anbajagane %A J. Armstrong %A M. Arthurs %A Jacob Bringewatt %A T. Edberg %A C. Hall %A M. Lei %A R. Raymond %A M. Reh %A D. Saini %A A. Sander %A J. Schaefer %A D. Seymour %A N. Swanson %A Y. Wang %A W. Lorenzon %X

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.

%G eng %U https://arxiv.org/abs/1805.11306 %R https://doi.org/10.1016/j.nima.2018.06.076 %0 Journal Article %D 2018 %T Subsystem Complexity and Holography %A Cesar A. Agón %A Matthew Headrick %A Brian Swingle %X

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

%G eng %U https://arxiv.org/abs/1804.01561 %0 Journal Article %J In: Nielsen J., Rijmen V. (eds) Advances in Cryptology – EUROCRYPT 2018. Lecture Notes in Computer Science, Springer, Cham %D 2018 %T Unforgeable Quantum Encryption %A Gorjan Alagic %A Tommaso Gagliardoni %A Christian Majenz %X

We study the problem of encrypting and authenticating quantum data in the presence of adversaries making adaptive chosen plaintext and chosen ciphertext queries. Classically, security games use string copying and comparison to detect adversarial cheating in such scenarios. Quantumly, this approach would violate no-cloning. We develop new techniques to overcome this problem: we use entanglement to detect cheating, and rely on recent results for characterizing quantum encryption schemes. We give definitions for (i) ciphertext unforgeability, (ii) indistinguishability under adaptive chosen-ciphertext attack, and (iii) authenticated encryption. The restriction of each definition to the classical setting is at least as strong as the corresponding classical notion: (i) implies   INT-CTXT , (ii) implies   IND-CCA2 , and (iii) implies   AE . All of our new notions also imply   QIND-CPA  privacy. Combining one-time authentication and classical pseudorandomness, we construct symmetric-key quantum encryption schemes for each of these new security notions, and provide several separation examples. Along the way, we also give a new definition of one-time quantum authentication which, unlike all previous approaches, authenticates ciphertexts rather than plaintexts.

%B In: Nielsen J., Rijmen V. (eds) Advances in Cryptology – EUROCRYPT 2018. Lecture Notes in Computer Science, Springer, Cham %V 10822 %G eng %R https://doi.org/10.1007/978-3-319-78372-7_16 %0 Journal Article %J Quantum Information & Computation %D 2017 %T 3-manifold diagrams and NP vs P %A Gorjan Alagic %A C. Lo %X

The computational complexity class #P captures the di_culty of counting the satisfying assignments to a boolean formula. In this work, we use basic tools from quantum computation to give a proof that the SO(3) Witten-Reshetikhin-Turaev (WRT) invariant of 3-manifolds is #P-hard to calculate. We then apply this result to a question about the combinatorics of Heegaard splittings, motivated by analogous work on link diagrams by M. Freedman. We show that, if #P ⊆ FPNP, then there exist infinitely many Heegaard splittings which cannot be made logarithmically thin by local WRT-preserving moves, except perhaps via a superpolynomial number of steps. We also outline two extensions of the above results. First, adapting a result of Kuperberg, we show that any presentation-independent approximation of WRT is also #P-hard. Second, we sketch out how all of our results can be translated to the setting of triangulations and Turaev-Viro invariants.

%B Quantum Information & Computation %V 17 %P 125-141 %G eng %U https://dl.acm.org/doi/abs/10.5555/3179483.3179491 %N (1{\&}2) %0 Journal Article %J Proceedings of ASIACRYPT 2017 %D 2017 %T Quantum Fully Homomorphic Encryption With Verification %A Gorjan Alagic %A Yfke Dulek %A Christian Schaffner %A Florian Speelman %X

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

%B Proceedings of ASIACRYPT 2017 %P 438-467 %8 2017/11/30 %G eng %U https://arxiv.org/abs/1708.09156 %R 10.1007/978-3-319-70694-8_16 %0 Journal Article %J In: Katz J., Shacham H. (eds) Advances in Cryptology – CRYPTO 2017. Lecture Notes in Computer Science. Springer, Cham %D 2017 %T Quantum Non-malleability and Authentication %A Gorjan Alagic %A Christian Majenz %X

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

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

%B In: Katz J., Shacham H. (eds) Advances in Cryptology – CRYPTO 2017. Lecture Notes in Computer Science. Springer, Cham %V 10402 %G eng %R https://doi.org/10.1007/978-3-319-63715-0_11 %0 Journal Article %J In: Coron JS., Nielsen J. (eds) Advances in Cryptology – EUROCRYPT 2017. Lecture Notes in Computer Science, Springer, Cham %D 2017 %T Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts %A Gorjan Alagic %A Alexander Russell %X

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

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

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

%B In: Coron JS., Nielsen J. (eds) Advances in Cryptology – EUROCRYPT 2017. Lecture Notes in Computer Science, Springer, Cham %V 10212 %G eng %R https://doi.org/10.1007/978-3-319-56617-7_3 %0 Journal Article %J Physical Review Letters %D 2017 %T A solvable family of driven-dissipative many-body systems %A Michael Foss-Feig %A Jeremy T. Young %A Victor V. Albert %A Alexey V. Gorshkov %A Mohammad F. Maghrebi %X

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

%B Physical Review Letters %V 119 %8 2017/11/10 %G eng %U https://arxiv.org/abs/1703.04626 %N 19 %R 10.1103/PhysRevLett.119.190402 %0 Journal Article %D 2017 %T Unforgeable Quantum Encryption %A Gorjan Alagic %A Tommaso Gagliardoni %A Christian Majenz %X

We study the problem of encrypting and authenticating quantum data in the presence of adversaries making adaptive chosen plaintext and chosen ciphertext queries. Classically, security games use string copying and comparison to detect adversarial cheating in such scenarios. Quantumly, this approach would violate no-cloning. We develop new techniques to overcome this problem: we use entanglement to detect cheating, and rely on recent results for characterizing quantum encryption schemes. We give definitions for (i.) ciphertext unforgeability , (ii.) indistinguishability under adaptive chosen-ciphertext attack, and (iii.) authenticated encryption. The restriction of each definition to the classical setting is at least as strong as the corresponding classical notion: (i) implies INT-CTXT, (ii) implies IND-CCA2, and (iii) implies AE. All of our new notions also imply QIND-CPA privacy. Combining one-time authentication and classical pseudorandomness, we construct schemes for each of these new quantum security notions, and provide several separation examples. Along the way, we also give a new definition of one-time quantum authentication which, unlike all previous approaches, authenticates ciphertexts rather than plaintexts.

%8 2017/09/19 %G eng %U https://arxiv.org/abs/1709.06539 %0 Conference Paper %B Computational Security of Quantum Encryption. In: Nascimento A., Barreto P. (eds) Information Theoretic Security. %D 2016 %T Computational Security of Quantum Encryption %A Gorjan Alagic %A Anne Broadbent %A Bill Fefferman %A Tommaso Gagliardoni %A Christian Schaffner %A Michael St. Jules %X

Quantum-mechanical devices have the potential to transform cryptography. Most research in this area has focused either on the information-theoretic advantages of quantum protocols or on the security of classical cryptographic schemes against quantum attacks. In this work, we initiate the study of another relevant topic: the encryption of quantum data in the computational setting. In this direction, we establish quantum versions of several fundamental classical results. First, we develop natural definitions for private-key and public-key encryption schemes for quantum data. We then define notions of semantic security and indistinguishability, and, in analogy with the classical work of Goldwasser and Micali, show that these notions are equivalent. Finally, we construct secure quantum encryption schemes from basic primitives. In particular, we show that quantum-secure one-way functions imply IND-CCA1-secure symmetric-key quantum encryption, and that quantum-secure trapdoor one-way permutations imply semantically-secure public-key quantum encryption.

%B Computational Security of Quantum Encryption. In: Nascimento A., Barreto P. (eds) Information Theoretic Security. %8 2016/11/10 %G eng %U https://link.springer.com/chapter/10.1007%2F978-3-319-49175-2_3 %0 Conference Paper %B 20th Annual Conference on Quantum Information Processing (QIP) %D 2016 %T Exponential Separation of Quantum Communication and Classical Information %A Anurag Anshu %A Dave Touchette %A Penghui Yao %A Nengkun Yu %X
We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. The function we use to present such a separation is the Symmetric k-ary Pointer Jumping function introduced by Rao and Sinha [ECCC TR15-057], whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence of round-elimination arguments, allowing us to simplify further the approach of Rao and Sinha. 
As another application of the techniques that we develop, we give a simple proof for an optimal trade-off between Alice's and Bob's communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/exp(O(b)) bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.
 
 
%B 20th Annual Conference on Quantum Information Processing (QIP) %8 2016/11/28 %G eng %U https://arxiv.org/abs/1611.08946 %0 Journal Article %D 2016 %T A finite presentation of CNOT-dihedral operators %A Matthew Amy %A Jianxin Chen %A Neil J. Ross %X

We give a finite presentation by generators and relations of unitary operators expressible over the {CNOT, T, X} gate set, also known as CNOT-dihedral operators. To this end, we introduce a notion of normal form for CNOT-dihedral circuits and prove that every CNOT-dihedral operator admits a unique normal form. Moreover, we show that in the presence of certain structural rules only finitely many circuit identities are required to reduce an arbitrary CNOT-dihedral circuit to its normal form. By appropriately restricting our relations, we obtain a finite presentation of unitary operators expressible over the {CNOT, T } gate set as a corollary.

%8 2016/12/31 %G eng %U https://arxiv.org/abs/1701.00140 %0 Journal Article %D 2016 %T On Quantum Obfuscation %A Gorjan Alagic %A Bill Fefferman %X Encryption of data is fundamental to secure communication in the modern world. Beyond encryption of data lies obfuscation, i.e., encryption of functionality. It is well-known that the most powerful means of obfuscating classical programs, so-called ``black-box obfuscation',' is provably impossible [Barak et al '12]. However, several recent results have yielded candidate schemes that satisfy a definition weaker than black-box, and yet still have numerous applications. In this work, we initialize the rigorous study of obfuscating programs via quantum-mechanical means. We define notions of quantum obfuscation which encompass several natural variants. The input to the obfuscator can describe classical or quantum functionality, and the output can be a circuit description or a quantum state. The obfuscator can also satisfy one of a number of obfuscation conditions: black-box, information-theoretic black-box, indistinguishability, and best possible; the last two conditions come in three variants: perfect, statistical, and computational. We discuss many applications, including CPA-secure quantum encryption, quantum fully-homomorphic encryption, and public-key quantum money. We then prove several impossibility results, extending a number of foundational papers on classical obfuscation to the quantum setting. We prove that quantum black-box obfuscation is impossible in a setting where adversaries can possess more than one output of the obfuscator. In particular, generic transformation of quantum circuits into black-box-obfuscated quantum circuits is impossible. We also show that statistical indistinguishability obfuscation is impossible, up to an unlikely complexity-theoretic collapse. Our proofs involve a new tool: chosen-ciphertext-secure encryption of quantum data, which was recently shown to be possible assuming quantum-secure one-way functions exist [Alagic et al '16]. %8 2016/02/04 %G eng %U http://arxiv.org/abs/1602.01771 %0 Journal Article %J Physical Review A %D 2016 %T Realizing Exactly Solvable SU(N) Magnets with Thermal Atoms %A Michael E. Beverland %A Gorjan Alagic %A Michael J. Martin %A Andrew P. Koller %A Ana M. Rey %A Alexey V. Gorshkov %X

We show that n thermal fermionic alkaline-earth-metal atoms in a flat-bottom trap allow one to robustly implement a spin model displaying two symmetries: the Sn symmetry that permutes atoms occupying different vibrational levels of the trap and the SU(N) symmetry associated with N nuclear spin states. The symmetries make the model exactly solvable, which, in turn, enables the analytic study of dynamical processes such as spin diffusion in this SU(N) system. We also show how to use this system to generate entangled states that allow for Heisenberg-limited metrology. This highly symmetric spin model should be experimentally realizable even when the vibrational levels are occupied according to a high-temperature thermal or an arbitrary nonthermal distribution.

%B Physical Review A %V 93 %8 2016/05/06 %G eng %U http://journals.aps.org/pra/abstract/10.1103/PhysRevA.93.051601 %N 5 %R 10.1103/PhysRevA.93.051601 %0 Journal Article %J Journal of Physics A %D 2016 %T Yang-Baxter operators need quantum entanglement to distinguish knots %A Gorjan Alagic %A Michael Jarret %A Stephen P. Jordan %X Any solution to the Yang-Baxter equation yields a family of representations of braid groups. Under certain conditions, identified by Turaev, the appropriately normalized trace of these representations yields a link invariant. Any Yang-Baxter solution can be interpreted as a two-qudit quantum gate. Here we show that if this gate is non-entangling, then the resulting invariant of knots is trivial. We thus obtain a general connection between topological entanglement and quantum entanglement, as suggested by Kauffman et al. %B Journal of Physics A %V 49 %P 075203 %8 2016/01/12 %G eng %U http://arxiv.org/abs/1507.05979 %N 7 %R 10.1088/1751-8113/49/7/075203 %0 Journal Article %J Physical Review B %D 2015 %T A chemical potential for light %A M. Hafezi %A P. Adhikari %A J. M. Taylor %X Photons are not conserved in interactions with other matter. Consequently, when understanding the equation of state and thermodynamics of photons, while we have a concept of temperature for energy conservation, there is no equivalent chemical potential for particle number conservation. However, the notion of a chemical potential is crucial in understanding a wide variety of single- and many-body effects, from transport in conductors and semi-conductors to phase transitions in electronic and atomic systems. Here we show how a direct modification of the system-bath coupling via parametric oscillation creates an effective chemical potential for photons even in the thermodynamic limit. Specific implementations, using circuit-QED or optomechanics, are feasible using current technologies, and we show a detailed example demonstrating the emergence of Mott Insulator-superfluid transition in a lattice of nonlinear oscillators. Our approach paves the way for quantum simulation, quantum sources and even electron-like circuits with light. %B Physical Review B %V 92 %P 174305 %8 2014/05/22 %G eng %U http://arxiv.org/abs/1405.5821v2 %N 17 %R 10.1103/PhysRevB.92.174305 %0 Journal Article %J Communications of the ACM %D 2015 %T Programming the Quantum Future %A D. Scott Alexander %A Neil J. Ross %A Peter Selinger %A Jonathan M. Smith %A Benoît Valiron %X The earliest computers, like the ENIAC, were rare and heroically difficult to program. That difficulty stemmed from the requirement that algorithms be expressed in a "vocabulary" suited to the particular hardware available, ranging from function tables for the ENIAC to more conventional arithmetic and movement operations on later machines. Introduction of symbolic programming languages, exemplified by FORTRAN, solved a major difficulty for the next generation of computing devices by enabling specification of an algorithm in a form more suitable for human understanding, then translating this specification to a form executable by the machine. The "programming language" used for such specification bridged a semantic gap between the human and the computing device. It provided two important features: high-level abstractions, taking care of automated bookkeeping, and modularity, making it easier to reason about sub-parts of programs. %B Communications of the ACM %V 58 %P 52-61 %8 2015/08/01 %G eng %U http://cacm.acm.org/magazines/2015/8/189851-programming-the-quantum-future/fulltext#comments %N 8 %R 10.1145/2699415 %0 Journal Article %J Journal of Computational Physics %D 2014 %T Adaptive change of basis in entropy-based moment closures for linear kinetic equations %A Graham W. Alldredge %A Cory D. Hauck %A Dianne P. O'Leary %A André L. Tits %X Entropy-based (M_N) moment closures for kinetic equations are defined by a constrained optimization problem that must be solved at every point in a space-time mesh, making it important to solve these optimization problems accurately and efficiently. We present a complete and practical numerical algorithm for solving the dual problem in one-dimensional, slab geometries. The closure is only well-defined on the set of moments that are realizable from a positive underlying distribution, and as the boundary of the realizable set is approached, the dual problem becomes increasingly difficult to solve due to ill-conditioning of the Hessian matrix. To improve the condition number of the Hessian, we advocate the use of a change of polynomial basis, defined using a Cholesky factorization of the Hessian, that permits solution of problems nearer to the boundary of the realizable set. We also advocate a fixed quadrature scheme, rather than adaptive quadrature, since the latter introduces unnecessary expense and changes the computationally realizable set as the quadrature changes. For very ill-conditioned problems, we use regularization to make the optimization algorithm robust. We design a manufactured solution and demonstrate that the adaptive-basis optimization algorithm reduces the need for regularization. This is important since we also show that regularization slows, and even stalls, convergence of the numerical simulation when refining the space-time mesh. We also simulate two well-known benchmark problems. There we find that our adaptive-basis, fixed-quadrature algorithm uses less regularization than alternatives, although differences in the resulting numerical simulations are more sensitive to the regularization strategy than to the choice of basis. %B Journal of Computational Physics %V 258 %P 489 - 508 %8 2014/02/01 %G eng %U http://arxiv.org/abs/1306.2881v1 %! Journal of Computational Physics %R 10.1016/j.jcp.2013.10.049 %0 Journal Article %J 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) %D 2014 %T Classical simulation of Yang-Baxter gates %A Gorjan Alagic %A Aniruddha Bapat %A Stephen P. Jordan %X A unitary operator that satisfies the constant Yang-Baxter equation immediately yields a unitary representation of the braid group B n for every $n \ge 2$. If we view such an operator as a quantum-computational gate, then topological braiding corresponds to a quantum circuit. A basic question is when such a representation affords universal quantum computation. In this work, we show how to classically simulate these circuits when the gate in question belongs to certain families of solutions to the Yang-Baxter equation. These include all of the qubit (i.e., $d = 2$) solutions, and some simple families that include solutions for arbitrary $d \ge 2$. Our main tool is a probabilistic classical algorithm for efficient simulation of a more general class of quantum circuits. This algorithm may be of use outside the present setting. %B 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) %V 27 %P 161-175 %8 2014/07/05 %G eng %U http://arxiv.org/abs/1407.1361v1 %! 9th Conference on the Theory of Quantum Computation %R 10.4230/LIPIcs.TQC.2014.161 %0 Journal Article %J Nature %D 2014 %T Optical detection of radio waves through a nanomechanical transducer %A T. Bagci %A A. Simonsen %A S. Schmid %A L. G. Villanueva %A E. Zeuthen %A J. Appel %A J. M. Taylor %A A. Sørensen %A K. Usami %A A. Schliesser %A E. S. Polzik %X Low-loss transmission and sensitive recovery of weak radio-frequency (rf) and microwave signals is an ubiquitous technological challenge, crucial in fields as diverse as radio astronomy, medical imaging, navigation and communication, including those of quantum states. Efficient upconversion of rf-signals to an optical carrier would allow transmitting them via optical fibers dramatically reducing losses, and give access to the mature toolbox of quantum optical techniques, routinely enabling quantum-limited signal detection. Research in the field of cavity optomechanics has shown that nanomechanical oscillators can couple very strongly to either microwave or optical fields. An oscillator accommodating both functionalities would bear great promise as the intermediate platform in a radio-to-optical transduction cascade. Here, we demonstrate such an opto-electro-mechanical transducer utilizing a high-Q nanomembrane. A moderate voltage bias (<10V) is sufficient to induce strong coupling between the voltage fluctuations in a rf resonance circuit and the membrane's displacement, which is simultaneously coupled to light reflected off its metallized surface. The circuit acts as an antenna; the voltage signals it induces are detected as an optical phase shift with quantum-limited sensitivity. The half-wave voltage is in the microvolt range, orders of magnitude below that of standard optical modulators. The noise added by the membrane is suppressed by the electro-mechanical cooperativity C~6800 and has a temperature of 40mK, far below 300K where the entire device is operated. This corresponds to a sensitivity limit as low as 5 pV/Hz^1/2, or -210dBm/Hz in a narrow band around 1 MHz. Our work introduces an entirely new approach to all-optical, ultralow-noise detection of classical electronic signals, and sets the stage for coherent upconversion of low-frequency quantum signals to the optical domain. %B Nature %V 507 %P 81 - 85 %8 2014/3/5 %G eng %U http://arxiv.org/abs/1307.3467v2 %N 7490 %! Nature %R 10.1038/nature13029 %0 Conference Proceedings %B In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC14) %D 2014 %T Partial-indistinguishability obfuscation using braids %A Gorjan Alagic %A Stacey Jeffery %A Stephen P. Jordan %X

An obfuscator is an algorithm that translates circuits into functionally-equivalent similarly-sized circuits that are hard to understand. Efficient obfuscators would have many applications in cryptography. Until recently, theoretical progress has mainly been limited to no-go results. Recent works have proposed the first efficient obfuscation algorithms for classical logic circuits, based on a notion of indistinguishability against polynomial-time adversaries. In this work, we propose a new notion of obfuscation, which we call partial-indistinguishability. This notion is based on computationally universal groups with efficiently computable normal forms, and appears to be incomparable with existing definitions. We describe universal gate sets for both classical and quantum computation, in which our definition of obfuscation can be met by polynomial-time algorithms. We also discuss some potential applications to testing quantum computers. We stress that the cryptographic security of these obfuscators, especially when composed with translation from other gate sets, remains an open question.

%B In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC14) %8 2014/08/21 %G eng %U http://arxiv.org/abs/1212.6358 %0 Journal Article %J Quantum Info. Comput. Vol. %D 2012 %T Quantum Algorithms for Invariants of Triangulated Manifolds %A Gorjan Alagic %A E. A. Bering %X

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

%B Quantum Info. Comput. Vol. %V 12 %P 843-863 %G eng %U http://dl.acm.org/citation.cfm?id=2481580.2481588 %N 9-10 %0 Journal Article %J Algorithmica %D 2012 %T A Spectral Algorithm for Latent Dirichlet Allocation %A Animashree Anandkumar %A Dean P. Foster %A Daniel Hsu %A Sham M. Kakade %A Yi-Kai Liu %X The problem of topic modeling can be seen as a generalization of the clustering problem, in that it posits that observations are generated due to multiple latent factors (e.g., the words in each document are generated as a mixture of several active topics, as opposed to just one). This increased representational power comes at the cost of a more challenging unsupervised learning problem of estimating the topic probability vectors (the distributions over words for each topic), when only the words are observed and the corresponding topics are hidden. We provide a simple and efficient learning procedure that is guaranteed to recover the parameters for a wide class of mixture models, including the popular latent Dirichlet allocation (LDA) model. For LDA, the procedure correctly recovers both the topic probability vectors and the prior over the topics, using only trigram statistics (i.e., third order moments, which may be estimated with documents containing just three words). The method, termed Excess Correlation Analysis (ECA), is based on a spectral decomposition of low order moments (third and fourth order) via two singular value decompositions (SVDs). Moreover, the algorithm is scalable since the SVD operations are carried out on $k\times k$ matrices, where $k$ is the number of latent factors (e.g. the number of topics), rather than in the $d$-dimensional observed space (typically $d \gg k$). %B Algorithmica %P 193-214 %8 2012/04/30 %G eng %U http://arxiv.org/abs/1204.6703v4 %0 Conference Proceedings %B In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC11) %D 2011 %T Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit %A Stephen P. Jordan %A Gorjan Alagic %X

The Turaev-Viro invariants are scalar topological invariants of three-dimensional manifolds. Here we show that the problem of estimating the Fibonacci version of the Turaev-Viro invariant of a mapping torus is a complete problem for the one clean qubit complexity class (DQC1). This complements a previous result showing that estimating the Turaev-Viro invariant for arbitrary manifolds presented as Heegaard splittings is a complete problem for the standard quantum computation model (BQP). We also discuss a beautiful analogy between these results and previously known results on the computational complexity of approximating the Jones polynomial.

%B In Proceedings of the Sixth Conference on Theory of Quantum Computation, Communication and Cryptography (TQC11) %8 2011/05/31 %G eng %U http://arxiv.org/abs/1105.5100 %0 Journal Article %J Physical Review D %D 2011 %T Implications of the Babinet Principle for Casimir Interactions %A Mohammad F. Maghrebi %A Ronen Abravanel %A Robert L. Jaffe %X We formulate the Babinet Principle (BP) as a relation between the scattering amplitudes for electromagnetic waves, and combine it with multiple scattering techniques to derive new properties of Casimir forces. We show that the Casimir force exerted by a planar conductor or dielectric on a self- complementary perforated planar mirror is approximately half that on a uniform mirror independent of the distance between them. The BP suggests that Casimir edge effects are anomalously small, supporting results obtained earlier in special cases. Finally, we illustrate how the BP can be used to estimate Casimir forces between perforated planar mirrors. %B Physical Review D %V 84 %8 2011/9/1 %G eng %U http://arxiv.org/abs/1103.5395v1 %N 6 %! Phys. Rev. D %R 10.1103/PhysRevD.84.061701 %0 Journal Article %J Physical Review A %D 2011 %T Interferometry with Synthetic Gauge Fields %A Brandon M. Anderson %A J. M. Taylor %A Victor M. Galitski %X We propose a compact atom interferometry scheme for measuring weak, time-dependent accelerations. Our proposal uses an ensemble of dilute trapped bosons with two internal states that couple to a synthetic gauge field with opposite charges. The trapped gauge field couples spin to momentum to allow time dependent accelerations to be continuously imparted on the internal states. We generalize this system to reduce noise and estimate the sensitivity of such a system to be S~10^-7 m / s^2 / Hz^1/2. %B Physical Review A %V 83 %8 2011/3/3 %G eng %U http://arxiv.org/abs/1008.3910v2 %N 3 %! Phys. Rev. A %R 10.1103/PhysRevA.83.031602 %0 Journal Article %J Journal of Fourier Analysis and Applications %D 2011 %T Spectral Concentration of Positive Functions on Compact Groups %A Gorjan Alagic %A Alexander Russell %X

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

%B Journal of Fourier Analysis and Applications %V 17 %P 355-373 %G eng %N 3 %R https://doi.org/10.1007/s00041-011-9174-5 %0 Journal Article %J Physical Review A %D 2010 %T Adiabatic preparation of many-body states in optical lattices %A Anders S. Sorensen %A Ehud Altman %A Michael Gullans %A J. V. Porto %A Mikhail D. Lukin %A Eugene Demler %X We analyze a technique for the preparation of low entropy many body states of atoms in optical lattices based on adiabatic passage. In particular, we show that this method allows preparation of strongly correlated states as stable highest energy states of Hamiltonians that have trivial ground states. As an example, we analyze the generation of antiferromagnetically ordered states by adiabatic change of a staggered field acting on the spins of bosonic atoms with ferromagnetic interactions. %B Physical Review A %V 81 %8 2010/6/22 %G eng %U http://arxiv.org/abs/0906.2567v3 %N 6 %! Phys. Rev. A %R 10.1103/PhysRevA.81.061603 %0 Journal Article %J Physical Review A %D 2010 %T Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation %A Gorjan Alagic %A Stephen P. Jordan %A Robert Koenig %A Ben W. Reichardt %X The Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and (2+1)-D topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a novel relation between the task of distinguishing non-homeomorphic 3-manifolds and the power of a general quantum computer. %B Physical Review A %V 82 %8 2010/10/8 %G eng %U http://arxiv.org/abs/1003.0923v1 %N 4 %! Phys. Rev. A %R 10.1103/PhysRevA.82.040302 %0 Journal Article %J ACM Trans. Algorithms %D 2010 %T Quantum Algorithms for Simon’s Problem over Nonabelian Groups %A Gorjan Alagic %A Cristopher Moore %A Alexander Russell %X

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

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

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

%B ACM Trans. Algorithms %V 6 %G eng %N 1 %R https://doi.org/10.1145/1644015.1644034 %0 Journal Article %J Proc. RANDOM %D 2010 %T Quantum property testing for bounded-degree graphs %A Andris Ambainis %A Andrew M. Childs %A Yi-Kai Liu %X We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound. For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph structure. %B Proc. RANDOM %P 365-376 %8 2010/12/14 %G eng %U http://arxiv.org/abs/1012.3174v3 %! Proceedings of RANDOM 2011 %R 10.1007/978-3-642-22935-0_31 %0 Journal Article %D 2009 %T Efficient quantum processing of ideals in finite rings %A Pawel M. Wocjan %A Stephen P. Jordan %A Hamed Ahmadi %A Joseph P. Brennan %X 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. %8 2009/07/31 %G eng %U http://arxiv.org/abs/0908.0022v1 %0 Journal Article %D 2009 %T The quantum query complexity of certification %A Andris Ambainis %A Andrew M. Childs %A François Le Gall %A Seiichiro Tani %X We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem. %8 2009/03/06 %G eng %U http://arxiv.org/abs/0903.1291v2 %! Quantum Information and Computation 10 %0 Journal Article %J Physical Review B %D 2008 %T Multilevel effects in the Rabi oscillations of a Josephson phase qubit %A S. K. Dutta %A Frederick W. Strauch %A R. M. Lewis %A Kaushik Mitra %A Hanhee Paik %A T. A. Palomaki %A Eite Tiesinga %A J. R. Anderson %A Alex J. Dragt %A C. J. Lobb %A F. C. Wellstood %X 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. %B Physical Review B %V 78 %8 2008/9/15 %G eng %U http://arxiv.org/abs/0806.4711v2 %N 10 %! Phys. Rev. B %R 10.1103/PhysRevB.78.104510 %0 Journal Article %J Proceedings of the National Academy of Sciences %D 2008 %T Polynomial-time quantum algorithm for the simulation of chemical dynamics %A Ivan Kassal %A Stephen P. Jordan %A Peter J. Love %A Masoud Mohseni %A Alán Aspuru-Guzik %X The computational cost of exact methods for quantum simulation using classical computers grows exponentially with system size. As a consequence, these techniques can only be applied to small systems. By contrast, we demonstrate that quantum computers could exactly simulate chemical reactions in polynomial time. Our algorithm uses the split-operator approach and explicitly simulates all electron-nuclear and inter-electronic interactions in quadratic time. Surprisingly, this treatment is not only more accurate than the Born-Oppenheimer approximation, but faster and more efficient as well, for all reactions with more than about four atoms. This is the case even though the entire electronic wavefunction is propagated on a grid with appropriately short timesteps. Although the preparation and measurement of arbitrary states on a quantum computer is inefficient, here we demonstrate how to prepare states of chemical interest efficiently. We also show how to efficiently obtain chemically relevant observables, such as state-to-state transition probabilities and thermal reaction rates. Quantum computers using these techniques could outperform current classical computers with one hundred qubits. %B Proceedings of the National Academy of Sciences %V 105 %P 18681 - 18686 %8 2008/11/24 %G eng %U http://arxiv.org/abs/0801.2986v3 %N 48 %! Proceedings of the National Academy of Sciences %R 10.1073/pnas.0808245105 %0 Journal Article %D 2008 %T The Power of Unentanglement %A Scott Aaronson %A Salman Beigi %A Andrew Drucker %A Bill Fefferman %A Peter Shor %X The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Does QMA(k)=QMA(2) for k>=2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. First, we give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given ~O(sqrt(n)) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on the existence of very short PCPs. Second, we show that assuming a weak version of the Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all k>=2. Third, we prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one. %8 2008/04/04 %G eng %U http://arxiv.org/abs/0804.0802v2 %0 Journal Article %J Physical Review B %D 2008 %T Quantum behavior of the dc SQUID phase qubit %A Kaushik Mitra %A F. W. Strauch %A C. J. Lobb %A J. R. Anderson %A F. C. Wellstood %A Eite Tiesinga %X 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. %B Physical Review B %V 77 %8 2008/6/13 %G eng %U http://arxiv.org/abs/0805.3680v1 %N 21 %! Phys. Rev. B %R 10.1103/PhysRevB.77.214512 %0 Journal Article %J Illinois J. Math. %D 2008 %T Uncertainty principles for compact groups %A Gorjan Alagic %A Alexander Russell %X

We establish an uncertainty principle over arbitrary compact groups, generalizing several previous results. Specifically, we show that if P and R are operators on L2(G) such that P commutes with projection onto every measurable subset of G and R commutes with left-multiplication by elements of G, then ∥PR∥≤∥P⋅χG∥2∥R∥2, where χG:g↦1 is the characteristic function of G. As a consequence, we show that every nonzero function f in L2(G) satisfies μ(suppf)⋅∑ρ∈G^dρrankf^(ρ)≥1.

%B Illinois J. Math. %V 52 %P 1315-1324 %G eng %U http://projecteuclid.org/euclid.ijm/1258554365 %N 4 %R doi:10.1215/ijm/1258554365 %0 Journal Article %J Journal of Algebraic Combinatorics %D 2007 %T The limitations of nice mutually unbiased bases %A Michael Aschbacher %A Andrew M. Childs %A Pawel Wocjan %X 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. %B Journal of Algebraic Combinatorics %V 25 %P 111 - 123 %8 2006/7/11 %G eng %U http://arxiv.org/abs/quant-ph/0412066v1 %N 2 %! J Algebr Comb %R 10.1007/s10801-006-0002-y %0 Journal Article %J Physical Review A %D 2007 %T Photon storage in Lambda-type optically dense atomic media. I. Cavity model %A Alexey V. Gorshkov %A Axel Andre %A Mikhail D. Lukin %A Anders S. Sorensen %X In a recent paper [Gorshkov et al., Phys. Rev. Lett. 98, 123601 (2007)], we used a universal physical picture to optimize and demonstrate equivalence between a wide range of techniques for storage and retrieval of photon wave packets in Lambda-type atomic media in free space, including the adiabatic reduction of the photon group velocity, pulse-propagation control via off-resonant Raman techniques, and photon-echo-based techniques. In the present paper, we perform the same analysis for the cavity model. In particular, we show that the retrieval efficiency is equal to C/(1+C) independent of the retrieval technique, where C is the cooperativity parameter. We also derive the optimal strategy for storage and, in particular, demonstrate that at any detuning one can store, with the optimal efficiency of C/(1+C), any smooth input mode satisfying T C gamma >> 1 and a certain class of resonant input modes satisfying T C gamma ~ 1, where T is the duration of the input mode and 2 gamma is the transition linewidth. In the two subsequent papers of the series, we present the full analysis of the free-space model and discuss the effects of inhomogeneous broadening on photon storage. %B Physical Review A %V 76 %8 2007/9/7 %G eng %U http://arxiv.org/abs/quant-ph/0612082v2 %N 3 %! Phys. Rev. A %R 10.1103/PhysRevA.76.033804 %0 Journal Article %J Physical Review A %D 2007 %T Photon storage in Lambda-type optically dense atomic media. II. Free-space model %A Alexey V. Gorshkov %A Axel Andre %A Mikhail D. Lukin %A Anders S. Sorensen %X In a recent paper [Gorshkov et al., Phys. Rev. Lett. 98, 123601 (2007)], we presented a universal physical picture for describing a wide range of techniques for storage and retrieval of photon wave packets in Lambda-type atomic media in free space, including the adiabatic reduction of the photon group velocity, pulse-propagation control via off-resonant Raman techniques, and photon-echo based techniques. This universal picture produced an optimal control strategy for photon storage and retrieval applicable to all approaches and yielded identical maximum efficiencies for all of them. In the present paper, we present the full details of this analysis as well some of its extensions, including the discussion of the effects of non-degeneracy of the two lower levels of the Lambda system. The analysis in the present paper is based on the intuition obtained from the study of photon storage in the cavity model in the preceding paper [Gorshkov et al., Phys. Rev. A 76, 033804 (2007)]. %B Physical Review A %V 76 %8 2007/9/7 %G eng %U http://arxiv.org/abs/quant-ph/0612083v2 %N 3 %! Phys. Rev. A %R 10.1103/PhysRevA.76.033805 %0 Journal Article %J Physical Review A %D 2007 %T Photon storage in Lambda-type optically dense atomic media. III. Effects of inhomogeneous broadening %A Alexey V. Gorshkov %A Axel Andre %A Mikhail D. Lukin %A Anders S. Sorensen %X In a recent paper [Gorshkov et al., Phys. Rev. Lett. 98, 123601 (2007)] and in the two preceding papers [Gorshkov et al., Phys. Rev. A 76, 033804 (2007); 76, 033805 (2007)], we used a universal physical picture to optimize and demonstrate equivalence between a wide range of techniques for storage and retrieval of photon wave packets in homogeneously broadened Lambda-type atomic media, including the adiabatic reduction of the photon group velocity, pulse-propagation control via off-resonant Raman techniques, and photon-echo-based techniques. In the present paper, we generalize this treatment to include inhomogeneous broadening. In particular, we consider the case of Doppler-broadened atoms and assume that there is a negligible difference between the Doppler shifts of the two optical transitions. In this situation, we show that, at high enough optical depth, all atoms contribute coherently to the storage process as if the medium were homogeneously broadened. We also discuss the effects of inhomogeneous broadening in solid state samples. In this context, we discuss the advantages and limitations of reversing the inhomogeneous broadening during the storage time, as well as suggest a way for achieving high efficiencies with a nonreversible inhomogeneous profile. %B Physical Review A %V 76 %8 2007/9/7 %G eng %U http://arxiv.org/abs/quant-ph/0612084v2 %N 3 %! Phys. Rev. A %R 10.1103/PhysRevA.76.033806 %0 Journal Article %J SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms %D 2007 %T Quantum Algorithms for Simon’s Problem over General Groups %A Gorjan Alagic %A Cristopher Moore %A Alexander Russell %X

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

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

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

%B SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms %P 1217–1224 %8 1/25/2007 %G eng %U https://arxiv.org/abs/quant-ph/0603251 %R https://dl.acm.org/doi/10.5555/1283383.1283514 %0 Journal Article %J Bulletin of the EATCS %D 2007 %T Quantum Computing and the Hunt for Hidden Symmetry %A Gorjan Alagic %A Alexander Russell %X

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

%B Bulletin of the EATCS %V 93 %P 53-75 %G eng %U https://pdfs.semanticscholar.org/08f7/abc04ca0bd38c1351ee1179139d8b0fc172b.pdf?_ga=2.210619804.800377824.1595266095-1152452310.1595266095 %0 Journal Article %J Physical Review Letters %D 2007 %T Universal Approach to Optimal Photon Storage in Atomic Media %A Alexey V. Gorshkov %A Axel Andre %A Michael Fleischhauer %A Anders S. Sorensen %A Mikhail D. Lukin %X We present a universal physical picture for describing storage and retrieval of photon wave packets in a Lambda-type atomic medium. This physical picture encompasses a variety of different approaches to pulse storage ranging from adiabatic reduction of the photon group velocity and pulse-propagation control via off-resonant Raman fields to photon-echo based techniques. Furthermore, we derive an optimal control strategy for storage and retrieval of a photon wave packet of any given shape. All these approaches, when optimized, yield identical maximum efficiencies, which only depend on the optical depth of the medium. %B Physical Review Letters %V 98 %8 2007/3/19 %G eng %U http://arxiv.org/abs/quant-ph/0604037v3 %N 12 %! Phys. Rev. Lett. %R 10.1103/PhysRevLett.98.123601 %0 Journal Article %J Phys. Rev. A %D 2005 %T Decoherence in Quantum Walks on the Hypercube %A Gorjan Alagic %A Alexander Russell %X

We study a natural notion of decoherence on quantum random walks over the hypercube. We prove that in this model there is a decoherence threshold beneath which the essential properties of the hypercubic quantum walk, such as linear mixing times, are preserved. Beyond the threshold, we prove that the walks behave like their classical counterparts.

%B Phys. Rev. A %V 76 %P 062304 %8 12/5/2005 %G eng %U https://arxiv.org/abs/quant-ph/0501169 %N 6 %R https://doi.org/10.1103/PhysRevA.72.062304 %0 Journal Article %J Physical Review A %D 2005 %T Sodium Bose-Einstein Condensates in an Optical Lattice %A K. Xu %A Y. Liu %A J. R. Abo-Shaeer %A T. Mukaiyama %A J. K. Chin %A D. E. Miller %A W. Ketterle %A Kevin M. Jones %A Eite Tiesinga %X The phase transition from a superfluid to a Mott insulator has been observed in a $^{23}$Na Bose-Einstein condensate. A dye laser detuned $\approx 5$nm red of the Na $3^2$S$ \to 3^2$P$_{1/2}$ transition was used to form the three dimensional optical lattice. The heating effects of the small detuning as well as the three-body decay processes constrained the timescale of the experiment. Certain lattice detunings were found to induce a large loss of atoms. These loss features were shown to be due to photoassociation of atoms to vibrational levels in the Na$_2$ $(1) ^3\Sigma_g^+$ state. %B Physical Review A %V 72 %8 2005/10/10 %G eng %U http://arxiv.org/abs/cond-mat/0507288v1 %N 4 %! Phys. Rev. A %R 10.1103/PhysRevA.72.043604 %0 Journal Article %D 2005 %T Strong Fourier Sampling Fails over Gn %A Gorjan Alagic %A Cristopher Moore %A Alexander Russell %X

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

%8 11/7/2005 %G eng %U https://arxiv.org/abs/quant-ph/0511054