QuICS seminar

Abstract: Quantum complexity is a measure of the minimal number of elementary operations required to approximately prepare a given state or unitary channel. Recently this concept has found applications beyond quantum computing---in the classification of topological phases of matter and in the description of chaotic many-body systems. Furthermore, within the context of the AdS/CFT correspondence, it has been postulated that the complexity of a specific time-evolved many-body quantum state is sensitive to the long-time properties of AdS-black hole interiors.

Finding ways to connect quantum systems in a controlled and flexible fashion lies at the core of constructing quantum information processing systems. Superconducting quantum circuits present a particularly promising platform for engineering quantum systems from the ground up: the strong light-matter interactions in these circuits can readily be used to realize interactions between different components. There remain interesting questions, however, about what types of interactions we can realize.

Quantum computations promise the ability to solve problems intractable in the classical setting. Restricting the types of computations considered often allows to establish a provable theoretical quantum advantage, and later demonstrate it experimentally.  I will discuss space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on. We show that any n-bit symmetric Boolean function can be implemented exactly through the use of quantum signal processing as a space-restricted quantum computation using O(n^2) gates.

A linear optical approach to quantum computing offers highly coherent qubits, high fidelity single qubit gates, and probabilistic entangling operations that can be implemented using well-known quantum optical methods.

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function f, deg(f) = O(~deg(f)^2): The degree of f is at most quadratic in the approximate degree of f. This is optimal as witnessed by the OR function.  D(f) = O(Q(f)^4): The deterministic query complexity of f is at most quartic in the quantum query complexity of f.  This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017).  We apply these results to resolve the quantum analogue of the Aanderaa--Karp--Rosenberg conjecture.

Solving quantum chemistry problems on the quantum computer faces several hurdles in practical implementation [1]. Nevertheless, even incremental improvements in finding exact solutions for quantum chemistry can lead to real improvements in everyday life, so exploring the capabilities for quantum computers is worthwhile.  In this talk, I discuss how to export solutions from a quantum computer to a classical user as a machine learned model [2,3].

Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f : {-1, 1}^n to {-1, 1}, the two-party bounded-error quantum communication complexity of 2-bit distributed versions of f is O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is in contrast to the classical randomized analogue of this statement, where the log n factor is absent. A natural question is if this O(log n) factor can be avoided. Aaronson and Ambainis (FOCS'03) showed that this factor is avoidable when f = OR.

The past decade of research in quantum information theory has witnessed  extraordinary progress in understanding communication over quantum channels, due in large part to quantum generalizations of the classical Renyi relative entropy. One generalization is known as the sandwiched Renyi relative entropy and finds its use in characterizing asymptotic behavior in quantum hypothesis testing. It has also found use in establishing strong converse theorems (fundamental communication capacity limitations) for a variety of quantum communication tasks.

The Hartree-Fock problem provides the conceptual and mathematical underpinning of a large portion of quantum chemistry. As efforts in quantum technology aim to enhance computational chemistry algorithms, the fundamental Hartree-Fock problem is a natural target. While quantum computers and quantum simulation offer many prospects for the future of modern chemistry, the Hartree-Fock problem is not a likely candidate.

We present the first leveled fully homomorphic encryption scheme for quantum circuits with classical keys. The scheme allows a classical client to blindly delegate a quantum computation to a quantum server: an honest server is able to run the computation while a malicious server is unable to learn any information about the computation. We show that it is possible to construct such a scheme directly from a quantum secure classical homomorphic encryption scheme with certain properties.