QuICS seminar

How hard is it to compress a quantum state? To fast-forward the evolution of a local Hamiltonian? To unscramble the Hawking radiation of a black hole? Traditional complexity theory -- which is centered around decision problems and tasks with classical inputs and outputs -- appears inadequate for reasoning about the complexity of such tasks involving quantum inputs and outputs.

In an isolated quantum many-body system undergoing unitary evolution, the entropy of a subsystem (smaller than half the system size) thermalizes if at long times, it is to leading order equal to the thermodynamic entropy of the subsystem at the same energy. We prove entropy thermalization for a nearly integrable Sachdev-Ye-Kitaev model initialized in a pure product state. The model is obtained by adding random all-to-all 4-body interactions as a perturbation to a random free-fermion model.

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.

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.

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.

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?

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.

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.

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.