QuICS seminar

Abstract: I will talk about:

. New efficient algorithms for quantum state tomography (the quantum analogue of estimating a probability distribution).

. Why you should care about the difference between total variation distance and Hellinger distance and KL divergence and chi-squared divergence.

. Quantum-inspired improvements to the classical problem of independence testing.

Includes joint work with Steven T. Flammia (Amazon)

Abstract: In the last few years, a number of works have proposed and improved provably efficient algorithms for learning the Hamiltonian from real-time dynamics. In this talk, I will first provide an overview of these developments, and then discuss how the Heisenberg limit, the fundamental precision limit imposed by quantum mechanics, can be reached for this task. I will show that reaching the Heisenberg limit requires techniques that are fundamentally different from previous ones.

Abstract: Quantum cryptography leverages unique features of quantum mechanics in order to construct cryptographic primitives which are oftentimes impossible for digital computers. Cryptographic applications of quantum computers therefore have the potential for useful quantum advantage – entirely without computational speed-ups. In this talk, I will focus on two fundamental questions: First, is it possible to certify that private data has been deleted? And second, is it possible to revoke a cryptographic key?

Abstract: 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.

Abstract: 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.

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.