QuICS seminar

Abstract: Can the current generation quantum computers solve science problems that conventional computers cannot? The jury is still out on this, but key to achieving this goal is the ability to perform robust quantum computation on near-term hardware. In this talk, I will describe three different types of robust computation that we have successfully completed: (i) computing topological properties (ii) simulating driven-dissipative systems and (iii) performing coherent time evolution with constant depth circuits.

Abstract: Over the past 6 years, a series of works have shown unconditional separations between the computational power of constant depth quantum and classical circuits. This talk will begin with a review of these circuit classes and separations. Then we'll discuss some tips and tricks -- essentially circuit identities -- which are useful when constructing constant depth quantum circuits with superclassical computational power.

Abstract: Quantum query complexity is a fundamental model in quantum computation, which captures known quantum algorithms such as Grover's search algorithm, and also enables rigorous comparison between classical and quantum models of computation. The polynomial method has become one of the main paradigms for proving lower bounds on quantum query complexity.

Abstract: Despite much work on quantum algorithms, there are few examples of practically relevant computational tasks that are known to admit substantial quantum speedups for practical instance sizes after all hidden costs and caveats are considered. Portfolio optimization (PO) is a practically important problem that can be solved via Quantum Interior Point Methods (QIPMs) via a standard mapping to a Second-Order Cone Programs (SOCP). Preliminary numerical evidence in prior literature was consistent with an asymptotic quantum speedup. But will this solution be practical?

Abstract: Public verification of quantum money has been one of the central objects in quantum cryptography ever since Wiesner's pioneering idea of using quantum mechanics to construct banknotes against counterfeiting. So far, we do not know any publicly-verifiable quantum money scheme that is provably secure from standard assumptions.

In this talk, we provide both negative and positive results for publicly verifiable quantum money.

Abstract: I will describe a recent quantum algorithm (arXiv:2303.13012) for simulating the classical dynamics of 2^n coupled oscillators (e.g., 2^n masses coupled by springs). The algorithm is based on a mapping between the Schr\"odinger equation and Newton's equations for harmonic potentials such that the amplitudes of the evolved quantum state encode the momenta and displacements of the classical oscillators.

Abstract: Quantum pseudorandom states are efficiently constructable states which nevertheless masquerade as Haar-random states to poly-time observers. First defined by Ji, Liu and Song, such states have found a number of applications ranging from cryptography to the AdS/CFT correspondence. A fundamental question is exactly how much entanglement is required to create such states. Haar-random states, as well as t-designs for t≥2, exhibit near-maximal entanglement.

Abstract: Large machine learning models are revolutionary technologies of artificial intelligence whose bottlenecks include huge computational expenses, power, and time used both in the pre-training and fine-tuning process. Based on quantum Carleman linearization and shadow tomography (QRAM is not necessary), we design the first quantum algorithm for training classical sparse neural networks with end-to-end settings.

Abstract: In recent years Gottesman-Kitaev-Preskill (GKP) codes have witnessed an increasing amount of interest for both their theoretically interesting features and as a possible route towards scalable hardware-efficient error correction.

Abstract: A fundamental distinction between many-body quantum states are those with short- and long-range entanglement (SRE and LRE). The latter, such as cat states, topological order, or critical states cannot be created by finite-depth circuits. Remarkably, examples are known where LRE is obtained by performing single-site measurements on SRE states such as preparing the toric code from measuring a sublattice of a 2D cluster state.