Computer Science

Theory shows that arbitrary-sized quantum computers may offer computational advantages for many problems. However, quantum computers on a reasonable horizon will be restricted in many ways, including size. Motivated by this, we investigate how a smaller quantum computer can genuinely speed up interesting algorithms, even when the problem size is much larger than the computer itself. To do so, we study hybrid classical-quantum divide-and-conquer strategies, and prove that if certain conditions on the structure and complexities of the underlying classical and quantum algorithms are met, then genuine speed-ups can be obtained. We will demonstrate how these conditions are met for a few exact constraint satisfaction algorithms (for SAT and Hamilton cycles). In closing we will discuss some of the more recent ideas showing how the hybrid methods can be expanded to the heuristic domain, and (hopefully) achieve practically relevant speed-ups in optimization with near-term devices. This talk will be based on the following papers: -VD, Y. Ge, J. I. Cirac, Computational speedups using small quantum devices, Phys. Rev. Lett. 121, 250501 (2018); -Y. Ge, VD, A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles, J. Math. Phys. 61, 012201 (2020); -C. Moussa, H. Calandra, VD, To quantum or not to quantum: towards algorithm selection in near-term quantum optimization, arXiv:2001.08271 (2020);

Quantum mean value problem is the task of estimating the expected value of a tensor product observable on the output state of a quantum circuit. This task is a common step of NISQ era quantum algorithms such as VQE or QAOA. I will consider the complexity of the quantum mean value problem as a function of circuit depth, qubit connectivity, and the structure of observables to be measured. Polynomial-time classical algorithms are described solving the quantum mean value problem in two special cases: (a) 2D constant-depth variational circuits relevant for VQE, (b) level-1 and level-2 QAOA circuits associated with graph-based optimization problems. As an application, I will describe a classical simulation of the recently proposed Recursive QAOA algorithm applied to graph coloring problems. Based on arXiv:1909.11485 arXiv:1910.08980

A critical goal for the field of quantum computing is quantum supremacy -- a demonstration of a quantum computation that is prohibitively hard for classical computers. Besides dispelling any skepticism about the experimental viability of quantum computers, quantum supremacy also provides a test of quantum theory in the realm of high complexity. A leading near-term candidate, put forth and recently implemented experimentally by the Google/UCSB team is sampling from the probability distributions of randomly chosen quantum circuits, called Random Circuit Sampling (RCS). In this talk we'll discuss the power of random quantum circuits from two perspectives.  First we'll talk about classical hardness evidence (joint work with Adam Bouland, Chinmay Nirkhe and Umesh Vazirani, https://arxiv.org/abs/1803.04402) and second we'll discuss very new easiness evidence concerning a restrictive subclass of random quantum circuits (joint work with Kyungjoo Noh and Liang Jiang, https://arxiv.org/abs/2003.13163).

We describe the recent advances involving programmable, coherent manipulation of quantum many-body systems using atom arrays excited into Rydberg states.  Within this system we performed quantum simulations of 1D spin models, created large-scale entangled states and   realized high-fidelity, parallel multi-qubit logic operations. We will also describe our recent technical upgrades that now allow the control over 200 atoms in two-dimensional arrays.   Ongoing efforts  to study exotic many-body phenomena and to realize and test quantum optimization algorithms within such systems will be discussed. 

The promise of quantum computers is that certain computational tasks might be executed exponentially faster on a quantum processor than on a classical processor. The task of quantum supremacy is to demonstrate that a real quantum computer can outpace the world's most powerful classical computers, and is a key milestone towards practical quantum computing. In this talk, I will discuss the development of our programmable quantum processor named Sycamore, which consists of 53 superconducting qubits with state of the art quantum logic fidelities. We benchmark the performance of Sycamore on randomly generated quantum circuits which are significantly more complex than any previous quantum computation, and the largest of these circuits are intractable on even the world's most powerful supercomputers, thus demonstrating quantum supremacy. We also show that the performance of the Sycamore device is well predicted by a simple model, confirming that the principles of quantum computing work at scale and paving the way for future developments.

Significant global efforts are currently underway to build quantum computers. The two main goals for near-term quantum computers are finding and solving interesting problems in the presence of noise and developing techniques to mitigate errors. In this talk, I will outline and motivate an abstraction layer needed to reliably operate quantum computers under realistic noise models, namely, a cycle consisting of all the primitive gates applied to a quantum computer within a specified time period. I will present recent work showing how errors in a cycle can be efficiently characterized and suppressed, and conclude with future directions.

Trapped atomic ions crystals are among the most promising platforms for fully universal quantum computer systems as well as simulators of Hamiltonian spin models. Trapped ion spins/qubits have no practical limits to their idle coherence times, and because they are perfectly replicable atomic clocks, have the ability to be scaled. Small quantum algorithms with up to about 20 qubits and a universal fully-connected and reconfigurable gate set have been demonstrated, mainly for the benchmarking of the systems. On the other hand, quantum simulations of hard quantum problems with more than 50 quantum bits have been implemented, studying magnetic quench dynamics, oundational aspects of quantum nonequlibrium statistical mechanics, molecular structure eigensolvers, and quantum approximate optimization routines. I will speculate on how things might proceed in the next few years in this system. While it remains a great challenge to build a quantum computer big enough to be useful for society, the good news with a system of trapped atomic ions, there do not appear to be any fundamental limits ahead.

Two years ago, I proposed that near-term, sampling-based quantum supremacy experiments, such as Google's, could be repurposed to generate bits that are certifiably random under computational assumptions.  In this talk, I'll discuss an aspect of that proposal that I haven't had time to go into in earlier talks: namely, how does one actually derive the conclusion that fresh entropy is being generated, from relatively "standard" computational assumptions?  I'll also discuss the major challenges that remain in turning this proposal into a genuine near-term application of quantum computers.

Quantum devices promise the efficient solution of problems out of reach for classical computers. However, before reaching the ultimate goal of realizing full fault tolerant quantum computers, significant effort have been made towards showing an unambiguous quantum advantage. In this talk, we will discuss prospects of achieving a complexity-theoretic quantum advantage that lives up to mathematically rigorous standards and is experimentally practically feasible with translationally invariant quantum simulators [1-4]. On a mathematical technical level, we will see how proof techniques of black-box verification [3] and of average-case complexity and anticoncentration come into play. On a physical level, we will elaborate on how such schemes may be realized with realistic near-term quantum devices reminiscent of quantum simulators. Particular emphasis will be put on showing how to prove anti-concentration, building upon recently developed techniques for random circuit sampling. We develop new techniques that exploit the insight that approximate 2-designs for the unitary group admit anti-concentration. We prove that the 2D translation-invariant, constant depth architectures of quantum simulation form approximate 2-designs, thus obtaining a significantly stronger result [1]. In an interlude interesting in its own right, we will see how higher-order unitary designs can be realized by means of random Clifford gates, into which a number of non-Clifford gates is interspersed that is - remarkably - independent of the system size [5]. If time allows, I will briefly mention ongoing efforts towards proving quantum advantages in distribution learning. [1] Closing gaps of a quantum advantage with short-time Hamiltonian dynamics, J. Haferkamp, D. Hangleiter, A. Bouland, B. Fefferman, J. Eisert, J. Bermejo-Vega, arXiv:1908.08069 (2019). [2] Architectures for quantum simulation showing a quantum speedup, J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, J. Eisert Phys. Rev. X 8, 021010 (2018). [3] Sample complexity of device-independently certified quantum supremacy, D. Hangleiter, M. Kliesch, J. Eisert, C. Gogolin, Phys. Rev. Lett. 122, 210502 (2019). [4] Dynamical structure factors of dynamical quantum simulators, M. Laura Baez, M. Goihl, J. Haferkamp, J. Bermejo-Vega, M. Gluza, J. Eisert, arXiv:1912.06076 (2019). [5] Quantum homeopathy works: Efficient unitary designs with a system-size independent number of non-Clifford gates, J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, D. Gross, I. Roth, arXiv:2002.09524 (2020).

The promise of quantum computers is that certain computational tasks might be executed exponentially faster on a quantum processor than on a classical processor. A fundamental challenge is to build a high-fidelity processor capable of running quantum algorithms in an exponentially large computational space. Here we report the use of a processor with programmable superconducting qubits to create quantum states on 53 qubits, corresponding to a computational state-space of dimension 2^53 (about 10^16). Measurements from repeated experiments sample the resulting probability distribution, which we verify using classical simulations. Our Sycamore processor takes about 200 seconds to sample one instance of a quantum circuit a million times—our benchmarks currently indicate that the equivalent task for a state-of-the-art classical supercomputer would take approximately 10,000 years. This dramatic increase in speed compared to all known classical algorithms is an experimental realization of quantum supremacy for this specific computational task, heralding a much-anticipated computing paradigm.