@article {3482, title = {Integrability of Goldilocks quantum cellular automata}, year = {2024}, month = {4/3/2024}, abstract = {

Goldilocks quantum cellular automata (QCA) have been simulated on quantum hardware and produce emergent small-world correlation networks. In Goldilocks QCA, a single-qubit unitary is applied to each qubit in a one-dimensional chain subject to a balance constraint: a qubit is updated if its neighbors are in opposite basis states. Here, we prove that a subclass of Goldilocks QCA -- including the one implemented experimentally -- map onto free fermions and therefore can be classically simulated efficiently. We support this claim with two independent proofs, one involving a Jordan--Wigner transformation and one mapping the integrable six-vertex model to QCA. We compute local conserved quantities of these QCA and predict experimentally measurable expectation values. These calculations can be applied to test large digital quantum computers against known solutions. In contrast, typical Goldilocks QCA have equilibration properties and quasienergy-level statistics that suggest nonintegrability. Still, the latter QCA conserve one quantity useful for error mitigation. Our work provides a parametric quantum circuit with tunable integrability properties with which to test quantum hardware.

}, url = {https://arxiv.org/abs/2404.02994}, author = {Logan E. Hillberry and Lorenzo Piroli and Eric Vernier and Nicole Yunger Halpern and Toma{\v z} Prosen and Lincoln D. Carr} } @article {3505, title = {Ultrastrong light-matter interaction in a multimode photonic crystal}, year = {2024}, month = {2/21/2024}, abstract = {

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

}, url = {https://arxiv.org/abs/2209.14972}, author = {Andrei Vrajitoarea and Ron Belyansky and Rex Lundgren and Seth Whitsitt and Alexey V. Gorshkov and Andrew A. Houck} } @article {3367, title = {Critical phase and spin sharpening in SU(2)-symmetric monitored quantum circuits}, journal = {Physical Review B}, volume = {108}, year = {2023}, month = {8/17/2023}, abstract = {

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\&$\#$39;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\&$\#$39;s total spin quantum number; on the other side is a phase in which measurements cannot.

}, doi = {10.1103/physrevb.108.054307}, url = {https://arxiv.org/abs/2305.13356}, author = {Shayan Majidy and Utkarsh Agrawal and Sarang Gopalakrishnan and Andrew C. Potter and Romain Vasseur and Nicole Yunger Halpern} } @article {3401, title = {Logical quantum processor based on reconfigurable atom arrays}, journal = {Nature}, year = {2023}, month = {12/7/2023}, issn = {1476-4687}, doi = {10.1038/s41586-023-06927-3}, url = {https://arxiv.org/abs/2312.03982}, author = {Bluvstein, Dolev and Evered, Simon J. and Geim, Alexandra A. and Li, Sophie H. and Zhou, Hengyun and Manovitz, Tom and Ebadi, Sepehr and Cain, Madelyn and Kalinowski, Marcin and Dominik Hangleiter and Ataides, J. Pablo Bonilla and Maskara, Nishad and Cong, Iris and Gao, Xun and Rodriguez, Pedro Sales and Karolyshyn, Thomas and Semeghini, Giulia and Michael Gullans and Greiner, Markus and Vuletic, Vladan and Lukin, Mikhail D.} } @article {3397, title = {Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions}, year = {2023}, month = {12/14/2023}, abstract = {

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.

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

Quantum state purification is the task of recovering a nearly pure copy of an unknown pure quantum state using multiple noisy copies of the state. This basic task has applications to quantum communication over noisy channels and quantum computation with imperfect devices, but has only been studied previously for the case of qubits. We derive an efficient purification procedure based on the swap test for qudits of any dimension, starting with any initial error parameter. Treating the initial error parameter and the dimension as constants, we show that our procedure has sample complexity asymptotically optimal in the final error parameter. Our protocol has a simple recursive structure that can be applied when the states are provided one at a time in a streaming fashion, requiring only a small quantum memory to implement.

}, url = {https://arxiv.org/abs/2309.16387}, author = {Andrew M. Childs and Honghao Fu and Debbie Leung and Zhi Li and Maris Ozols and Vedang Vyas} } @article {3007, title = {Convex optimization for non-equilibrium steady states on a hybrid quantum processor}, year = {2022}, month = {4/7/2022}, abstract = {

Finding the transient and steady state properties of open quantum systems is a central problem in various fields of quantum technologies. Here, we present a quantum-assisted algorithm to determine the steady states of open system dynamics. By reformulating the problem of finding the fixed point of Lindblad dynamics as a feasibility semi-definite program, we bypass several well known issues with variational quantum approaches to solving for steady states. We demonstrate that our hybrid approach allows us to estimate the steady states of higher dimensional open quantum systems and discuss how our method can find multiple steady states for systems with symmetries.

}, keywords = {FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {https://doi.org/10.48550/arXiv.2204.03203}, url = {https://arxiv.org/abs/2204.03203}, author = {Lau, Jonathan Wei Zhong and Lim, Kian Hwee and Bharti, Kishor and Kwek, Leong-Chuan and Vinjanampathy, Sai} } @article {3139, title = {Experimental Implementation of an Efficient Test of Quantumness}, year = {2022}, month = {9/28/2022}, abstract = {

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

}, keywords = {FOS: Physical sciences, Other Condensed Matter (cond-mat.other), Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2209.14316}, url = {https://arxiv.org/abs/2209.14316}, author = {Lewis, Laura and Zhu, Daiwei and Gheorghiu, Alexandru and Noel, Crystal and Katz, Or and Harraz, Bahaa and Wang, Qingfeng and Risinger, Andrew and Feng, Lei and Biswas, Debopriyo and Egan, Laird and Vidick, Thomas and Cetina, Marko and Monroe, Christopher} } @article {3179, title = {Group coset monogamy games and an application to device-independent continuous-variable QKD}, year = {2022}, month = {12/7/2022}, abstract = {

We develop an extension of a recently introduced subspace coset state monogamy-of-entanglement game [Coladangelo, Liu, Liu, and Zhandry; Crypto\&$\#$39;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.

}, keywords = {Cryptography and Security (cs.CR), FOS: Computer and information sciences, FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2212.03935}, url = {https://arxiv.org/abs/2212.03935}, author = {Culf, Eric and Vidick, Thomas and Victor V. Albert} } @article {3070, title = {Infinite-randomness criticality in monitored quantum dynamics with static disorder}, year = {2022}, month = {5/27/2022}, abstract = {

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

}, url = {https://arxiv.org/abs/2205.14002}, author = {Aidan Zabalo and Justin H. Wilson and Michael Gullans and Romain Vasseur and Sarang Gopalakrishnan and David A. Huse and J. H. Pixley} } @article {3024, title = {Monitoring-induced Entanglement Entropy and Sampling Complexity}, year = {2022}, month = {1/29/2022}, abstract = {

The dynamics of open quantum systems is generally described by a master equation, which describes the loss of information into the environment. By using a simple model of uncoupled emitters, we illustrate how the recovery of this information depends on the monitoring scheme applied to register the decay clicks. The dissipative dynamics, in this case, is described by pure-state stochastic trajectories and we examine different unravelings of the same master equation. More precisely, we demonstrate how registering the sequence of clicks from spontaneously emitted photons through a linear optical interferometer induces entanglement in the trajectory states. Since this model consists of an array of single-photon emitters, we show a direct equivalence with Fock-state boson sampling and link the hardness of sampling the outcomes of the quantum jumps with the scaling of trajectory entanglement.

}, keywords = {FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2201.12672}, url = {https://arxiv.org/abs/2201.12672}, author = {Van Regemortel, Mathias and Shtanko, Oles and Garc{\'\i}a-Pintos, Luis Pedro and Deshpande, Abhinav and Dehghani, Hossein and Alexey V. Gorshkov and Hafezi, Mohammad} } @article {3006, title = {Operator Scaling Dimensions and Multifractality at Measurement-Induced Transitions}, journal = {Physical Review Letters}, volume = {128}, year = {2022}, month = {2/11/2022}, abstract = {

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

}, doi = {10.1103/physrevlett.128.050602}, url = {https://arxiv.org/abs/2107.03393}, author = {Aidan Zabalo and Michael Gullans and Justin H. Wilson and Romain Vasseur and Andreas W. W. Ludwig and Sarang Gopalakrishnan and David A. Huse and J. H. Pixley} } @article {2983, title = {Quantum computational advantage via high-dimensional Gaussian boson sampling}, journal = {Science Advances}, volume = {8}, year = {2022}, month = {1/5/2022}, pages = {eabi7894}, abstract = {

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

}, doi = {10.1126/sciadv.abi7894}, url = {https://www.science.org/doi/abs/10.1126/sciadv.abi7894}, author = {Abhinav Deshpande and Arthur Mehta and Trevor Vincent and Nicolas Quesada and Marcel Hinsche and Marios Ioannou and Lars Madsen and Jonathan Lavoie and Haoyu Qi and Jens Eisert and Dominik Hangleiter and Bill Fefferman and Ish Dhand} } @article {2997, title = {Quantum Simulation for High Energy Physics}, year = {2022}, month = {4/7/2022}, abstract = {

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

}, keywords = {FOS: Physical sciences, High Energy Physics - Lattice (hep-lat), High Energy Physics - Phenomenology (hep-ph), High Energy Physics - Theory (hep-th), Nuclear Theory (nucl-th), Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2204.03381}, url = {https://arxiv.org/abs/2204.03381}, author = {Bauer, Christian W. and Zohreh Davoudi and Balantekin, A. Baha and Bhattacharya, Tanmoy and Carena, Marcela and de Jong, Wibe A. and Draper, Patrick and El-Khadra, Aida and Gemelke, Nate and Hanada, Masanori and Kharzeev, Dmitri and Lamm, Henry and Li, Ying-Ying and Liu, Junyu and Lukin, Mikhail and Meurice, Yannick and Monroe, Christopher and Nachman, Benjamin and Pagano, Guido and Preskill, John and Rinaldi, Enrico and Roggero, Alessandro and Santiago, David I. and Savage, Martin J. and Siddiqi, Irfan and Siopsis, George and Van Zanten, David and Wiebe, Nathan and Yamauchi, Yukari and Yeter-Aydeniz, K{\"u}bra and Zorzetti, Silvia} } @article {3186, title = {Qunity: A Unified Language for Quantum and Classical Computing (Extended Version)}, year = {2022}, month = {4/26/2022}, abstract = {

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

}, keywords = {FOS: Computer and information sciences, FOS: Physical sciences, Logic in Computer Science (cs.LO), Programming Languages (cs.PL), Quantum Physics (quant-ph)}, doi = {https://doi.org/10.48550/arXiv.2204.12384}, url = {https://arxiv.org/abs/2204.12384}, author = {Voichick, Finn and Li, Liyi and Rand, Robert and Hicks, Michael} } @article {3199, title = {Tailoring three-dimensional topological codes for biased noise}, year = {2022}, month = {11/3/2022}, abstract = {

Tailored topological stabilizer codes in two dimensions have been shown to exhibit high storage threshold error rates and improved subthreshold performance under biased Pauli noise. Three-dimensional (3D) topological codes can allow for several advantages including a transversal implementation of non-Clifford logical gates, single-shot decoding strategies, parallelized decoding in the case of fracton codes as well as construction of fractal lattice codes. Motivated by this, we tailor 3D topological codes for enhanced storage performance under biased Pauli noise. We present Clifford deformations of various 3D topological codes, such that they exhibit a threshold error rate of 50\% under infinitely biased Pauli noise. Our examples include the 3D surface code on the cubic lattice, the 3D surface code on a checkerboard lattice that lends itself to a subsystem code with a single-shot decoder, the 3D color code, as well as fracton models such as the X-cube model, the Sierpinski model and the Haah code. We use the belief propagation with ordered statistics decoder (BP-OSD) to study threshold error rates at finite bias. We also present a rotated layout for the 3D surface code, which uses roughly half the number of physical qubits for the same code distance under appropriate boundary conditions. Imposing coprime periodic dimensions on this rotated layout leads to logical operators of weight O(n) at infinite bias and a corresponding exp[\−O(n)] subthreshold scaling of the logical failure rate, where n is the number of physical qubits in the code. Even though this scaling is unstable due to the existence of logical representations with O(1) low-rate Pauli errors, the number of such representations scales only polynomially for the Clifford-deformed code, leading to an enhanced effective distance.

}, keywords = {FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2211.02116}, url = {https://arxiv.org/abs/2211.02116}, author = {Huang, Eric and Pesah, Arthur and Chubb, Christopher T. and Vasmer, Michael and Dua, Arpit} } @article {3120, title = {Ultrastrong light-matter interaction in a photonic crystal}, year = {2022}, month = {9/29/2022}, abstract = {

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

}, keywords = {FOS: Physical sciences, Quantum Gases (cond-mat.quant-gas), Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2209.14972}, url = {https://arxiv.org/abs/2209.14972}, author = {Vrajitoarea, Andrei and Belyansky, Ron and Lundgren, Rex and Whitsitt, Seth and Alexey V. Gorshkov and Houck, Andrew A.} } @article {2916, title = {Discovering hydrodynamic equations of many-body quantum systems}, year = {2021}, month = {11/3/2021}, abstract = {

Simulating and predicting dynamics of quantum many-body systems is extremely challenging, even for state-of-the-art computational methods, due to the spread of entanglement across the system. However, in the long-wavelength limit, quantum systems often admit a simplified description, which involves a small set of physical observables and requires only a few parameters such as sound velocity or viscosity. Unveiling the relationship between these hydrodynamic equations and the underlying microscopic theory usually requires a great effort by condensed matter theorists. In the present paper, we develop a new machine-learning framework for automated discovery of effective equations from a limited set of available data, thus bypassing complicated analytical derivations. The data can be generated from numerical simulations or come from experimental quantum simulator platforms. Using integrable models, where direct comparisons can be made, we reproduce previously known hydrodynamic equations, strikingly discover novel equations and provide their derivation whenever possible. We discover new hydrodynamic equations describing dynamics of interacting systems, for which the derivation remains an outstanding challenge. Our approach provides a new interpretable method to study properties of quantum materials and quantum simulators in non-perturbative regimes.

}, url = {https://arxiv.org/abs/2111.02385}, author = {Yaroslav Kharkov and Oles Shtanko and Alireza Seif and Przemyslaw Bienias and Mathias Van Regemortel and Mohammad Hafezi and Alexey V. Gorshkov} } @article {2426, title = {Efficient quantum measurement of Pauli operators}, journal = {Quantum}, volume = {5}, year = {2021}, month = {01/19/2021}, chapter = {385}, abstract = {

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

}, doi = {https://doi.org/10.22331/q-2021-01-20-385}, url = {https://arxiv.org/abs/1908.06942}, author = {Ophelia Crawford and Barnaby van Straaten and Daochen Wang and Thomas Parks and Earl Campbell and Stephen Brierley} } @article {2932, title = {Entangled quantum cellular automata, physical complexity, and Goldilocks rules}, journal = {Quantum Science and Technology}, volume = {6}, year = {2021}, month = {9/29/2021}, pages = {045017}, abstract = {

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

}, issn = {2058-9565}, doi = {10.1088/2058-9565/ac1c41}, url = {http://dx.doi.org/10.1088/2058-9565/ac1c41}, author = {Hillberry, Logan E and Jones, Matthew T and Vargas, David L and Rall, Patrick and Nicole Yunger Halpern and Bao, Ning and Notarnicola, Simone and Montangero, Simone and Carr, Lincoln D} } @article {2762, title = {Frustration-induced anomalous transport and strong photon decay in waveguide QED}, journal = {Phys. Rev. Research}, volume = {3}, year = {2021}, month = {9/16/2021}, abstract = {

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

}, doi = {https://doi.org/10.1103/PhysRevResearch.3.L032058}, url = {https://arxiv.org/abs/2007.03690}, author = {Ron Belyansky and Seth Whitsitt and Rex Lundgren and Yidan Wang and Andrei Vrajitoarea and Andrew A. Houck and Alexey V. Gorshkov} } @article {2908, title = {Interactive Protocols for Classically-Verifiable Quantum Advantage}, year = {2021}, month = {12/9/2021}, abstract = {

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

}, url = {https://arxiv.org/abs/2112.05156}, author = {Daiwei Zhu and Gregory D. Kahanamoku-Meyer and Laura Lewis and Crystal Noel and Or Katz and Bahaa Harraz and Qingfeng Wang and Andrew Risinger and Lei Feng and Debopriyo Biswas and Laird Egan and Alexandru Gheorghiu and Yunseong Nam and Thomas Vidick and Umesh Vazirani and Norman Y. Yao and Marko Cetina and Christopher Monroe} } @article {2773, title = {Quantum Computational Supremacy via High-Dimensional Gaussian Boson Sampling}, year = {2021}, month = {2/24/2021}, abstract = {

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

}, url = {https://arxiv.org/abs/2102.12474}, author = {Abhinav Deshpande and Arthur Mehta and Trevor Vincent and Nicolas Quesada and Marcel Hinsche and Marios Ioannou and Lars Madsen and Jonathan Lavoie and Haoyu Qi and Jens Eisert and Dominik Hangleiter and Bill Fefferman and Ish Dhand} } @article {2870, title = {Subdiffusive hydrodynamics of nearly-integrable anisotropic spin chains}, year = {2021}, month = {9/27/2021}, abstract = {

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

}, url = {https://arxiv.org/abs/2109.13251}, author = {Jacopo De Nardis and Sarang Gopalakrishnan and Romain Vasseur and Brayden Ware} } @article {2775, title = {Trading Locality for Time: Certifiable Randomness from Low-Depth Circuits}, journal = {Communications in Mathematical Physics}, volume = {382}, year = {2021}, month = {2/9/2021}, pages = {49 - 86}, abstract = {

The generation of certifiable randomness is the most fundamental informationtheoretic task that meaningfully separates quantum devices from their classical counterparts. We propose a protocol for exponential certified randomness expansion using a\ single quantum device. The protocol calls for the device to implement a simple quantum circuit of constant depth on a 2D lattice of qubits. The output of the circuit can be\ verified classically in linear time, and is guaranteed to contain a polynomial number of\ certified random bits assuming that the device used to generate the output operated using\ a (classical or quantum) circuit of sub-logarithmic depth. This assumption contrasts with\ the locality assumption used for randomness certification based on Bell inequality violation and more recent proposals for randomness certification based on computational\ assumptions. Furthermore, to demonstrate randomness generation it is sufficient for a\ device to sample from the ideal output distribution within constant statistical distance.\ \ Our procedure is inspired by recent work of Bravyi et al. (Science 362(6412):308\–311,\ 2018), who introduced a relational problem that can be solved by a constant-depth quantum circuit, but provably cannot be solved by any classical circuit of sub-logarithmic\ depth. We develop the discovery of Bravyi et al. into a framework for robust randomness\ expansion. Our results lead to a new proposal for a demonstrated quantum advantage\ that has some advantages compared to existing proposals. First, our proposal does not\ rest on any complexity-theoretic conjectures, but relies on the physical assumption that\ the adversarial device being tested implements a circuit of sub-logarithmic depth. Second, success on our task can be easily verified in classical linear time. Finally, our task\ is more noise-tolerant than most other existing proposals that can only tolerate multiplicative error, or require additional conjectures from complexity theory; in contrast, we\ are able to allow a small constant additive error in total variation distance between the\ sampled and ideal distributions.

}, issn = {0010-3616}, doi = {10.1007/s00220-021-03963-w}, url = {https://link.springer.com/content/pdf/10.1007/s00220-021-03963-w.pdf}, author = {Matthew Coudron and Stark, Jalex and Vidick, Thomas} } @article {2912, title = {Verified Compilation of Quantum Oracles}, year = {2021}, month = {12/13/2021}, abstract = {

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

}, url = {https://arxiv.org/abs/2112.06700}, author = {Liyi Li and Finnegan Voichick and Kesha Hietala and Yuxiang Peng and Xiaodi Wu and Michael Hicks} } @article {2677, title = {Entanglement entropy scaling transition under competing monitoring protocols}, year = {2020}, month = {08/19/2020}, abstract = {

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

}, url = {https://arxiv.org/abs/2008.08619}, author = {Mathias Van Regemortel and Ze-Pei Cian and Alireza Seif and Hossein Dehghani and Mohammad Hafezi} } @article {2726, title = {Programmable Quantum Annealers as Noisy Gibbs Samplers}, year = {2020}, month = {12/16/2020}, abstract = {

Drawing independent samples from high-dimensional probability distributions represents the major computational bottleneck for modern algorithms, including powerful machine learning frameworks such as deep learning. The quest for discovering larger families of distributions for which sampling can be efficiently realized has inspired an exploration beyond established computing methods and turning to novel physical devices that leverage the principles of quantum computation. Quantum annealing embodies a promising computational paradigm that is intimately related to the complexity of energy landscapes in Gibbs distributions, which relate the probabilities of system states to the energies of these states. Here, we study the sampling properties of physical realizations of quantum annealers which are implemented through programmable lattices of superconducting flux qubits. Comprehensive statistical analysis of the data produced by these quantum machines shows that quantum annealers behave as samplers that generate independent configurations from low-temperature noisy Gibbs distributions. We show that the structure of the output distribution probes the intrinsic physical properties of the quantum device such as effective temperature of individual qubits and magnitude of local qubit noise, which result in a non-linear response function and spurious interactions that are absent in the hardware implementation. We anticipate that our methodology will find widespread use in characterization of future generations of quantum annealers and other emerging analog computing devices.

}, url = {https://arxiv.org/abs/2012.08827}, author = {Marc Vuffray and Carleton Coffrin and Yaroslav A. Kharkov and Andrey Y. Lokhov} } @article {2609, title = {Transport and dynamics in the frustrated two-bath spin-boson model}, year = {2020}, month = {7/7/2020}, abstract = {

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

}, url = {https://arxiv.org/abs/2007.03690}, author = {Ron Belyansky and Seth Whitsitt and Rex Lundgren and Yidan Wang and Andrei Vrajitoarea and Andrew A. Houck and Alexey V. Gorshkov} } @article {2362, title = {Opportunities for Nuclear Physics \& Quantum Information Science}, year = {2019}, month = {03/13/2019}, abstract = {

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.

}, url = {https://arxiv.org/abs/1903.05453}, author = {I. C. Clo{\"e}t and Matthew R. Dietrich and John Arrington and Alexei Bazavov and Michael Bishof and Adam Freese and Alexey V. Gorshkov and Anna Grassellino and Kawtar Hafidi and Zubin Jacob and Michael McGuigan and Yannick Meurice and Zein-Eddine Meziani and Peter Mueller and Christine Muschik and James Osborn and Matthew Otten and Peter Petreczky and Tomas Polakovic and Alan Poon and Raphael Pooser and Alessandro Roggero and Mark Saffman and Brent VanDevender and Jiehang Zhang and Erez Zohar} } @article {2530, title = {Quantum Computer Systems for Scientific Discovery}, year = {2019}, month = {12/16/2019}, abstract = {

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.

}, url = {https://arxiv.org/abs/1912.07577}, author = {Yuri Alexeev and Dave Bacon and Kenneth R. Brown and Robert Calderbank and Lincoln D. Carr and Frederic T. Chong and Brian DeMarco and Dirk Englund and Edward Farhi and Bill Fefferman and Alexey V. Gorshkov and Andrew Houck and Jungsang Kim and Shelby Kimmel and Michael Lange and Seth Lloyd and Mikhail D. Lukin and Dmitri Maslov and Peter Maunz and Christopher Monroe and John Preskill and Martin Roetteler and Martin Savage and Jeff Thompson and Umesh Vazirani} } @article {2487, title = {Real-time dynamics of string breaking in quantum spin chains}, year = {2019}, month = {2019/11/26}, abstract = {

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

}, url = {https://arxiv.org/abs/1911.11382}, author = {Roberto Verdel and Fangli Liu and Seth Whitsitt and Alexey V. Gorshkov and Markus Heyl} } @article {2298, title = {Black Hole Microstate Cosmology}, year = {2018}, abstract = {

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

}, url = {https://arxiv.org/abs/1810.10601}, author = {Sean Cooper and Moshe Rozali and Brian Swingle and Mark Van Raamsdonk and Christopher Waddell and David Wakeham} } @article {2109, title = {Geometry of the quantum set of correlations}, journal = {Physical Review A}, volume = {97}, year = {2018}, month = {2018/02/07}, pages = {022104}, abstract = {

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

}, doi = {10.1103/PhysRevA.97.022104}, url = {https://journals.aps.org/pra/abstract/10.1103/PhysRevA.97.022104}, author = {Koon Tong Goh and Jedrzej Kaniewski and Elie Wolfe and Tam{\'a}s V{\'e}rtesi and Xingyao Wu and Yu Cai and Yeong-Cherng Liang and Valerio Scarani} } @article {2060, title = {Observation of three-photon bound states in a quantum nonlinear medium}, journal = {Science}, volume = {359}, year = {2018}, month = {2018/02/16}, pages = {783-786}, abstract = {

Bound states of massive particles, such as nuclei, atoms or molecules, are ubiquitous in nature and constitute the bulk of the visible world around us. In contrast, photons typically only weakly influence each other due to their very weak interactions and vanishing mass. We report the observation of traveling three-photon bound states in a quantum nonlinear medium where the interactions between photons are mediated by atomic Rydberg states. In particular, photon correlation and conditional phase measurements reveal the distinct features associated with three-photon and two-photon bound states. Such photonic trimers and dimers can be viewed as quantum solitons with shape-preserving wavefunctions that depend on the constituent photon number. The observed bunching and strongly nonlinear optical phase are quantitatively described by an effective field theory (EFT) of Rydberg-induced photon-photon interactions, which demonstrates the presence of a substantial effective three-body force between the photons. These observations pave the way towards the realization, studies, and control of strongly interacting quantum many-body states of light.

}, doi = {10.1126/science.aao7293}, url = {http://science.sciencemag.org/content/359/6377/783}, author = {Qi-Yu Liang and Aditya V. Venkatramani and Sergio H. Cantu and Travis L. Nicholson and Michael Gullans and Alexey V. Gorshkov and Jeff D. Thompson and Cheng Chin and Mikhail D. Lukin and Vladan Vuletic} } @article {2311, title = {Quantum Supremacy and the Complexity of Random Circuit Sampling}, year = {2018}, abstract = {

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

}, url = {https://arxiv.org/abs/1803.04402}, author = {Adam Bouland and Bill Fefferman and Chinmay Nirkhe and Umesh Vazirani} } @article {2056, title = {Computational Notions of Quantum Min-Entropy}, year = {2017}, month = {2017/09/09}, abstract = {

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

}, url = {https://arxiv.org/abs/1704.07309}, author = {Yi-Hsiu Chen and Kai-Min Chung and Ching-Yi Lai and Salil P. Vadhan and Xiaodi Wu} } @article {1784, title = {Effective Field Theory for Rydberg Polaritons}, journal = {Physical Review Letters}, volume = {117}, year = {2016}, month = {2016/09/09}, pages = {113601}, abstract = {

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

}, doi = {http://dx.doi.org/10.1103/PhysRevLett.117.113601}, url = {http://arxiv.org/abs/1605.05651}, author = {Michael Gullans and J. D. Thompson and Y. Wang and Q. -Y. Liang and V. Vuletic and M. D. Lukin and Alexey V. Gorshkov} } @article {1554, title = {Optimal quantum algorithm for polynomial interpolation}, journal = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, volume = {55}, year = {2016}, month = {2016/03/01}, pages = {16:1--16:13}, abstract = {

We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm\&$\#$39;s success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability.

}, isbn = {978-3-95977-013-2}, issn = {1868-8969}, doi = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.16}, url = {http://arxiv.org/abs/1509.09271}, author = {Andrew M. Childs and Wim van Dam and Shih-Han Hung and Igor E. Shparlinski} } @article {1565, title = {Programming the Quantum Future}, journal = {Communications of the ACM}, volume = {58}, year = {2015}, month = {2015/08/01}, pages = {52-61}, abstract = {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.}, doi = {10.1145/2699415}, url = {http://cacm.acm.org/magazines/2015/8/189851-programming-the-quantum-future/fulltext$\#$comments}, author = {D. Scott Alexander and Neil J. Ross and Peter Selinger and Jonathan M. Smith and Beno{\^\i}t Valiron} } @article {1518, title = {The computational power of normalizer circuits over black-box groups}, year = {2014}, month = {2014/09/16}, abstract = { This work presents a precise connection between Clifford circuits, Shor{\textquoteright}s factoring algorithm and several other famous quantum algorithms with exponential quantum speed-ups for solving Abelian hidden subgroup problems. We show that all these different forms of quantum computation belong to a common new restricted model of quantum operations that we call \emph{black-box normalizer circuits}. To define these, we extend the previous model of normalizer circuits [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], which are built of quantum Fourier transforms, group automorphism and quadratic phase gates associated to an Abelian group $G$. In previous works, the group $G$ is always given in an explicitly decomposed form. In our model, we remove this assumption and allow $G$ to be a black-box group. While standard normalizer circuits were shown to be efficiently classically simulable [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], we find that normalizer circuits are powerful enough to factorize and solve classically-hard problems in the black-box setting. We further set upper limits to their computational power by showing that decomposing finite Abelian groups is complete for the associated complexity class. In particular, solving this problem renders black-box normalizer circuits efficiently classically simulable by exploiting the generalized stabilizer formalism in [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208]. Lastly, we employ our connection to draw a few practical implications for quantum algorithm design: namely, we give a no-go theorem for finding new quantum algorithms with black-box normalizer circuits, a universality result for low-depth normalizer circuits, and identify two other complete problems. }, url = {http://arxiv.org/abs/1409.4800v1}, author = {Juan Bermejo-Vega and Cedric Yen-Yu Lin and Maarten Van den Nest} } @article {1177, title = {Kitaev chains with long-range pairing}, journal = {Physical Review Letters}, volume = {113}, year = {2014}, month = {2014/10/9}, abstract = { We propose and analyze a generalization of the Kitaev chain for fermions with long-range $p$-wave pairing, which decays with distance as a power-law with exponent $\alpha$. Using the integrability of the model, we demonstrate the existence of two types of gapped regimes, where correlation functions decay exponentially at short range and algebraically at long range ($\alpha > 1$) or purely algebraically ($\alpha < 1$). Most interestingly, along the critical lines, long-range pairing is found to break conformal symmetry for sufficiently small $\alpha$. This is accompanied by a violation of the area law for the entanglement entropy in large parts of the phase diagram in the presence of a gap, and can be detected via the dynamics of entanglement following a quench. Some of these features may be relevant for current experiments with cold atomic ions. }, doi = {10.1103/PhysRevLett.113.156402}, url = {http://arxiv.org/abs/1405.5440v2}, author = {Davide Vodola and Luca Lepori and Elisa Ercolessi and Alexey V. Gorshkov and Guido Pupillo} } @article {1519, title = {Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems }, year = {2014}, month = {2014/09/10}, abstract = { $\textit{Normalizer circuits}$ [1,2] are generalized Clifford circuits that act on arbitrary finite-dimensional systems $\mathcal{H}_{d_1}\otimes ... \otimes \mathcal{H}_{d_n}$ with a standard basis labeled by the elements of a finite Abelian group $G=\mathbb{Z}_{d_1}\times... \times \mathbb{Z}_{d_n}$. Normalizer gates implement operations associated with the group $G$ and can be of three types: quantum Fourier transforms, group automorphism gates and quadratic phase gates. In this work, we extend the normalizer formalism [1,2] to infinite dimensions, by allowing normalizer gates to act on systems of the form $\mathcal{H}_\mathbb{Z}^{\otimes a}$: each factor $\mathcal{H}_\mathbb{Z}$ has a standard basis labeled by $\textit{integers}$ $\mathbb{Z}$, and a Fourier basis labeled by $\textit{angles}$, elements of the circle group $\mathbb{T}$. Normalizer circuits become hybrid quantum circuits acting both on continuous- and discrete-variable systems. We show that infinite-dimensional normalizer circuits can be efficiently simulated classically with a generalized $\textit{stabilizer formalism}$ for Hilbert spaces associated with groups of the form $\mathbb{Z}^a\times \mathbb{T}^b \times \mathbb{Z}_{d_1}\times...\times \mathbb{Z}_{d_n}$. We develop new techniques to track stabilizer-groups based on normal forms for group automorphisms and quadratic functions. We use our normal forms to reduce the problem of simulating normalizer circuits to that of finding general solutions of systems of mixed real-integer linear equations [3] and exploit this fact to devise a robust simulation algorithm: the latter remains efficient even in pathological cases where stabilizer groups become infinite, uncountable and non-compact. The techniques developed in this paper might find applications in the study of fault-tolerant quantum computation with superconducting qubits [4,5]. }, url = {http://arxiv.org/abs/1409.3208v2}, author = {Juan Bermejo-Vega and Cedric Yen-Yu Lin and Maarten Van den Nest} } @article {1342, title = {Optical detection of radio waves through a nanomechanical transducer}, journal = {Nature}, volume = {507}, year = {2014}, month = {2014/3/5}, pages = {81 - 85}, abstract = {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{\textquoteright}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. }, doi = {10.1038/nature13029}, url = {http://arxiv.org/abs/1307.3467v2}, author = {T. Bagci and A. Simonsen and S. Schmid and L. G. Villanueva and E. Zeuthen and J. Appel and J. M. Taylor and A. S{\o}rensen and K. Usami and A. Schliesser and E. S. Polzik} } @article {1478, title = {Quantum correlations and entanglement in far-from-equilibrium spin systems }, journal = {Physical Review A}, volume = {90}, year = {2014}, month = {2014/12/15}, abstract = { By applying complementary analytic and numerical methods, we investigate the dynamics of spin-$1/2$ XXZ models with variable-range interactions in arbitrary dimensions. The dynamics we consider is initiated from uncorrelated states that are easily prepared in experiments, and can be equivalently viewed as either Ramsey spectroscopy or a quantum quench. Our primary focus is the dynamical emergence of correlations and entanglement in these far-from-equilibrium interacting quantum systems: we characterize these correlations by the entanglement entropy, concurrence, and squeezing, which are inequivalent measures of entanglement corresponding to different quantum resources. In one spatial dimension, we show that the time evolution of correlation functions manifests a non-perturbative dynamic singularity. This singularity is characterized by a universal power-law exponent that is insensitive to small perturbations. Explicit realizations of these models in current experiments using polar molecules, trapped ions, Rydberg atoms, magnetic atoms, and alkaline-earth and alkali atoms in optical lattices, along with the relative merits and limitations of these different systems, are discussed. }, doi = {10.1103/PhysRevA.90.063622}, url = {http://arxiv.org/abs/1406.0937v1}, author = {Kaden R. A. Hazzard and Mauritz van den Worm and Michael Foss-Feig and Salvatore R. Manmana and Emanuele Dalla Torre and Tilman Pfau and Michael Kastner and Ana Maria Rey} } @article {1534, title = {Quipper: Concrete Resource Estimation in Quantum Algorithms}, year = {2014}, month = {2014/12/01}, abstract = {

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

}, url = {http://arxiv.org/abs/1412.0625v1}, author = {Jonathan M. Smith and Neil J. Ross and Peter Selinger and Beno{\^\i}t Valiron} } @article {1505, title = {All-Optical Switch and Transistor Gated by One Stored Photon}, journal = {Science}, volume = {341}, year = {2013}, month = {2013/07/04}, pages = {768 - 770}, abstract = { The realization of an all-optical transistor where one {\textquoteright}gate{\textquoteright} photon controls a {\textquoteright}source{\textquoteright} light beam, is a long-standing goal in optics. By stopping a light pulse in an atomic ensemble contained inside an optical resonator, we realize a device in which one stored gate photon controls the resonator transmission of subsequently applied source photons. A weak gate pulse induces bimodal transmission distribution, corresponding to zero and one gate photons. One stored gate photon produces fivefold source attenuation, and can be retrieved from the atomic ensemble after switching more than one source photon. Without retrieval, one stored gate photon can switch several hundred source photons. With improved storage and retrieval efficiency, our work may enable various new applications, including photonic quantum gates, and deterministic multiphoton entanglement. }, doi = {10.1126/science.1238169}, url = {http://arxiv.org/abs/1401.3194v1}, author = {Wenlan Chen and Kristin M. Beck and Robert B{\"u}cker and Michael Gullans and Mikhail D. Lukin and Haruka Tanji-Suzuki and Vladan Vuletic} } @article {1841, title = {Attractive Photons in a Quantum Nonlinear Medium}, journal = {Nature (London)}, volume = {502}, year = {2013}, pages = {71}, url = {http://dx.doi.org/10.1038/nature12512}, author = {Ofer Firstenberg and Thibault Peyronel and Qi-Yu Liang and Alexey V. Gorshkov and Mikhail D. Lukin and Vladan Vuletic} } @article {1536, title = {An Introduction to Quantum Programming in Quipper}, journal = {Lecture Notes in Computer Science}, volume = {7948}, year = {2013}, month = {2013/07/05}, pages = {110-124}, abstract = { Quipper is a recently developed programming language for expressing quantum computations. This paper gives a brief tutorial introduction to the language, through a demonstration of how to make use of some of its key features. We illustrate many of Quipper{\textquoteright}s language features by developing a few well known examples of Quantum computation, including quantum teleportation, the quantum Fourier transform, and a quantum circuit for addition. }, isbn = {978-3-642-38986-3}, doi = {10.1007/978-3-642-38986-3_10}, url = {http://arxiv.org/abs/1304.5485v1}, author = {Alexander S. Green and Peter LeFanu Lumsdaine and Neil J. Ross and Peter Selinger and Beno{\^\i}t Valiron} } @article {1842, title = {A quantum many-body spin system in an optical lattice clock}, journal = {Science}, volume = {341}, year = {2013}, pages = {632}, url = {http://www.sciencemag.org/content/341/6146/632.abstract}, author = {M J Martin and Bishof, M and Swallows, M D and X Zhang and C Benko and J von-Stecher and Alexey V. Gorshkov and Rey, A M and Jun Ye} } @article {1843, title = {Quantum Nonlinear Optics: Strongly Interacting Photons}, journal = {Opt. Photonics News}, volume = {24}, year = {2013}, pages = {48}, url = {http://www.osa-opn.org/abstract.cfm?URI=opn-24-12-48}, author = {Firstenberg, O and Lukin, M D and Peyronel, T and Liang, Q -Y and Vuletic, V and Alexey V. Gorshkov and Hofferberth, S and Pohl, T} } @article {1535, title = {Quipper: A Scalable Quantum Programming Language}, journal = {ACM SIGPLAN Notices}, volume = {48}, year = {2013}, month = {2013/06/23}, pages = {333-342}, abstract = {

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

}, doi = {10.1145/2499370.2462177}, url = {http://arxiv.org/abs/1304.3390v1}, author = {Alexander S. Green and Peter LeFanu Lumsdaine and Neil J. Ross and Peter Selinger and Beno{\^\i}t Valiron} } @article {1549, title = {On Beating the Hybrid Argument}, journal = {Proceedings, ITCS}, volume = {9}, year = {2012}, month = {2013/11/14}, pages = {809-843}, abstract = {The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor k equal to the bit-length of the distributions: -distinguishability implies only /k-predictability. This paper studies the consequences of avoiding this loss {\textendash} what we call {\textquotedblleft}beating the hybrid argument{\textquotedblright} {\textendash} and develops new proof techniques that circumvent the loss in certain natural settings. Specifically, we obtain the following results: 1. We give an instantiation of the Nisan-Wigderson generator (JCSS {\textquoteright}94) that can be broken by quantum computers, and that is o(1)-unpredictable against AC0 . This is not enough to imply indistinguishability via the hybrid argument because of the hybrid-argument loss; nevertheless, we conjecture that this generator indeed fools AC0 , and we prove this statement for a simplified version of the problem. Our conjecture implies the existence of an oracle relative to which BQP is not in the PH, a longstanding open problem. 2. We show that the {\textquotedblleft}INW{\textquotedblright} generator by Impagliazzo, Nisan, and Wigderson (STOC {\textquoteright}94) with seed length O(log n log log n) produces a distribution that is 1/ log n-unpredictable against poly-logarithmic width (general) read-once oblivious branching programs. Thus avoiding the hybrid-argument loss would lead to a breakthrough in generators against small space. 3. We study pseudorandom generators obtained from a hard function by repeated sampling. We identify a property of functions, {\textquotedblleft}resamplability,{\textquotedblright} that allows us to beat the hybrid argument, leading to new pseudorandom generators for AC0 [p] and similar classes. Although the generators have sub-linear stretch, they represent the best-known generators for these classes. Thus we establish that {\textquotedblleft}beating{\textquotedblright} or bypassing the hybrid argument would have two significant consequences in complexity, and we take steps toward that goal by developing techniques that indeed beat the hybrid argument in related (but simpler) settings, leading to best-known PRGs for certain complexity classes. }, url = {http://users.cms.caltech.edu/~umans/papers/FSUV10.pdf}, author = {Bill Fefferman and Ronen Shaltiel and Christopher Umans and Emanuele Viola} } @article {1792, title = {Gluon chain formation in presence of static charges}, journal = {Physical Review D}, volume = {86}, year = {2012}, month = {2012/12/10}, pages = {114015}, abstract = {We consider the origins of the gluon chain model. The model serves as a realization of the dynamics of the chromoelectric flux between static quark-antiquark sources. The derivation is based on the large-NC limit of the Coulomb gauge Hamiltonian in the presence of a background field introduced to model magnetic charge condensation inducing electric confinement.}, doi = {10.1103/PhysRevD.86.114015}, url = {http://link.aps.org/doi/10.1103/PhysRevD.86.114015}, author = {Aaron Ostrander and Santopinto, E. and Szczepaniak, A. P. and Vassallo, A.} } @article {1845, title = {Quantum nonlinear optics with single photons enabled by strongly interacting atoms}, journal = {Nature (London)}, volume = {488}, year = {2012}, pages = {57}, url = {http://www.nature.com/nature/journal/v488/n7409/full/nature11361.html}, author = {Peyronel, Thibault and Firstenberg, Ofer and Liang, Qi-Yu and Hofferberth, Sebastian and Alexey V. Gorshkov and Pohl, Thomas and Lukin, Mikhail D. and Vuletic, Vladan} } @article {1182, title = {Fast Entanglement Distribution with Atomic Ensembles and Fluorescent Detection }, journal = {Physical Review A}, volume = {81}, year = {2010}, month = {2010/2/12}, abstract = { Quantum repeaters based on atomic ensemble quantum memories are promising candidates for achieving scalable distribution of entanglement over long distances. Recently, important experimental progress has been made towards their implementation. However, the entanglement rates and scalability of current approaches are limited by relatively low retrieval and single-photon detector efficiencies. We propose a scheme, which makes use of fluorescent detection of stored excitations to significantly increase the efficiency of connection and hence the rate. Practical performance and possible experimental realizations of the new protocol are discussed. }, doi = {10.1103/PhysRevA.81.020303}, url = {http://arxiv.org/abs/0907.3839v2}, author = {Jonatan B. Brask and Liang Jiang and Alexey V. Gorshkov and Vladan Vuletic and Anders S. Sorensen and Mikhail D. Lukin} } @article {1218, title = {Quantum algorithms for algebraic problems}, journal = {Reviews of Modern Physics}, volume = {82}, year = {2010}, month = {2010/1/15}, pages = {1 - 52}, abstract = { Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation, and in particular, on problems with an algebraic flavor. }, doi = {10.1103/RevModPhys.82.1}, url = {http://arxiv.org/abs/0812.0380v1}, author = {Andrew M. Childs and Wim van Dam} } @article {1588, title = {N-representability is QMA-complete}, journal = {Phys. Rev. Lett.}, volume = {98}, year = {2007}, month = {2007/03/16}, abstract = {We study the computational complexity of the N-representability problem in quantum chemistry. We show that this problem is quantum Merlin-Arthur complete, which is the quantum generalization of nondeterministic polynomial time complete. Our proof uses a simple mapping from spin systems to fermionic systems, as well as a convex optimization technique that reduces the problem of finding ground states to N representability.}, doi = {10.1103/PhysRevLett.98.110503}, url = {http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.98.110503}, author = {Yi-Kai Liu and Matthias Christandl and F. Verstraete} } @article {1257, title = {Quantum algorithms for hidden nonlinear structures}, year = {2007}, month = {2007/05/21}, abstract = { Attempts to find new quantum algorithms that outperform classical computation have focused primarily on the nonabelian hidden subgroup problem, which generalizes the central problem solved by Shor{\textquoteright}s factoring algorithm. We suggest an alternative generalization, namely to problems of finding hidden nonlinear structures over finite fields. We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures. }, doi = {10.1109/FOCS.2007.18}, url = {http://arxiv.org/abs/0705.2784v1}, author = {Andrew M. Childs and Leonard J. Schulman and Umesh V. Vazirani} } @article {1590, title = {Designing Incentives for Peer-to-Peer Routing}, journal = {Proc. INFOCOM}, year = {2005}, month = {2005/03/13}, pages = {374-385}, abstract = {In a peer-to-peer network, nodes are typically required to route packets for each other. This leads to a problem of {\textquotedblleft}free-loaders,{\textquotedblright} nodes that use the network but refuse to route other nodes{\textquoteright} packets. In this paper we study ways of designing incentives to discourage free-loading. We model the interactions between nodes as a {\textquotedblleft}random matching game,{\textquotedblright} and describe a simple reputation system that provides incentives for good behavior. Under certain assumptions, we obtain a stable subgame-perfect equilibrium. We use simulations to investigate the robustness of this scheme in the presence of noise and malicious nodes, and we examine some of the design trade-offs. We also evaluate some possible adversarial strategies, and discuss how our results might apply to real peer-to-peer systems.}, url = {http://cseweb.ucsd.edu/~vahdat/papers/infocom05.pdf}, author = {Alberto Blanc and Yi-Kai Liu and Amin Vahda} } @article {1240, title = {From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups }, year = {2005}, month = {2005/04/11}, abstract = { We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form (Z_p)^r X| Z_p for fixed r (including the Heisenberg group, r=2). In particular, our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP. }, doi = {10.1109/SFCS.2005.38}, url = {http://arxiv.org/abs/quant-ph/0504083v2}, author = {Dave Bacon and Andrew M. Childs and Wim van Dam} } @article {1239, title = {Optimal measurements for the dihedral hidden subgroup problem}, year = {2005}, month = {2005/01/10}, abstract = { We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement. }, url = {http://arxiv.org/abs/quant-ph/0501044v2}, author = {Dave Bacon and Andrew M. Childs and Wim van Dam} } @article {1215, title = {Quantum algorithm for a generalized hidden shift problem}, year = {2005}, month = {2005/07/19}, abstract = { Consider the following generalized hidden shift problem: given a function f on {0,...,M-1} x Z_N satisfying f(b,x)=f(b+1,x+s) for b=0,1,...,M-2, find the unknown shift s in Z_N. For M=N, this problem is an instance of the abelian hidden subgroup problem, which can be solved efficiently on a quantum computer, whereas for M=2, it is equivalent to the dihedral hidden subgroup problem, for which no efficient algorithm is known. For any fixed positive epsilon, we give an efficient (i.e., poly(log N)) quantum algorithm for this problem provided M > N^epsilon. The algorithm is based on the "pretty good measurement" and uses H. Lenstra{\textquoteright}s (classical) algorithm for integer programming as a subroutine. }, url = {http://arxiv.org/abs/quant-ph/0507190v1}, author = {Andrew M. Childs and Wim van Dam} } @article {1238, title = {Reversible simulation of bipartite product Hamiltonians}, journal = {IEEE Transactions on Information Theory}, volume = {50}, year = {2004}, month = {2004/06/01}, pages = {1189 - 1197}, abstract = { Consider two quantum systems A and B interacting according to a product Hamiltonian H = H_A x H_B. We show that any two such Hamiltonians can be used to simulate each other reversibly (i.e., without efficiency losses) with the help of local unitary operations and local ancillas. Accordingly, all non-local features of a product Hamiltonian -- including the rate at which it can be used to produce entanglement, transmit classical or quantum information, or simulate other Hamiltonians -- depend only upon a single parameter. We identify this parameter and use it to obtain an explicit expression for the entanglement capacity of all product Hamiltonians. Finally, we show how the notion of simulation leads to a natural formulation of measures of the strength of a nonlocal Hamiltonian. }, doi = {10.1109/TIT.2004.828069}, url = {http://arxiv.org/abs/quant-ph/0303097v1}, author = {Andrew M. Childs and Debbie W. Leung and Guifre Vidal} } @article {1296, title = {Ultracold Cs$_2$ Feshbach Spectroscopy}, year = {2003}, month = {2003/12/23}, abstract = { We have observed and located more than 60 magnetic field-induced Feshbach resonances in ultracold collisions of ground-state $^{133}$Cs atoms. These resonances are associated with molecular states with up to four units of rotational angular momentum, and are detected through variations in the elastic, inelastic, and radiative collision cross sections. These observations allow us to greatly improve upon the interaction potentials between two cesium atoms and to reproduce the positions of most resonances to accuracies better than 0.5\%. Based on the relevant coupling scheme between the electron spin, nuclear spin, and orbital angular momenta of the nuclei, quantum numbers and energy structure of the molecular states beneath the dissociation continuum are revealed. Finally, we predict the relevant collision properties for cesium Bose-Einstein condensation experiments. }, url = {http://arxiv.org/abs/cond-mat/0312613v2}, author = {Cheng Chin and Vladan Vuletic and Andrew J. Kerman and Steven Chu and Eite Tiesinga and Paul J. Leo and Carl J. Williams} } @article {1210, title = {Asymptotic entanglement capacity of the Ising and anisotropic Heisenberg interactions }, year = {2002}, month = {2002/07/10}, abstract = { We compute the asymptotic entanglement capacity of the Ising interaction ZZ, the anisotropic Heisenberg interaction XX + YY, and more generally, any two-qubit Hamiltonian with canonical form K = a XX + b YY. We also describe an entanglement assisted classical communication protocol using the Hamiltonian K with rate equal to the asymptotic entanglement capacity. }, url = {http://arxiv.org/abs/quant-ph/0207052v2}, author = {Andrew M. Childs and D. W. Leung and F. Verstraete and G. Vidal} }