QuICS seminar

This presentation will overview several results concerning tasks, some computational and some information theoretic, at which quantum hardware can outperform classical hardware.  A common mathematical theme in the design of each of these tasks is a quantum mechanical phenomenon called non-locality.  The first result is a modification of a breakthrough work of Bravyi, Gosset, and Koenig, wherein we achieve an improved soundness scaling for the circuit separation established in that work, and also develop an application of their framework to a cryptographic task known as

In the area of quantum state learning, one is given a small number of "samples" of a quantum state, and the goal is use them to determine a feature of the state.  Examples include learning the entire state ("quantum state tomography"), determining whether it equals a target state ("quantum state certification"), or estimating its von Neumann entropy.  These are problems which are not only of theoretical interest, but are also commonly used in current-day implementation and verification of quantum technologies.

Compactifying one direction of the cubic code results in a family of two dimensional topological orders, equivalent to stacks of toric code enriched by translation symmetry. Surprisingly, some of these models have unbroken rigid 1D subsystem symmetries that lead to spurious contributions to the topological entanglement entropy. These spurious contributions can appear in a bulk computation of the topological entanglement entropy from a linear combination of subregion entropies with cancelling boundary terms.

Previously, Bravyi, Gosset and Konig (2018) showed a separation between constant depth quantum circuits and constant depth classical circuits. We find a related problem which separates shallow classical and quantum circuits even if the classical circuit has unbounded fan-in AND gates. We will also show average-case hardness for the new problem.
 

I will present several developments that collectively give us a fruitful new perspective on a fundamental result in quantum information theory, the strong sub-additivity of quantum entropy. I will start by discussing quantum entropy and other information measures, and explain why they are emphatically more interesting and delicate than their commutative analogues.

Could the no-cloning property of quantum information be used to protect ciphertexts against copying?  In 2002, Gottesman answered this question in the positive, proposing a quantum encryption scheme for classical messages, with a decryption process that detects any attempt to copy the ciphertext. Clearly, classical information alone does not allow such a functionality, since it is always possible to perfectly copy a classical ciphertext while avoiding detection.

In this presentation, I will first recall the Fiat-Shamir
transformation, which is an important design principle for
non-interactive zero-knowledge proofs and for digital signature schemes.
In order to rigorously analyze the security of this transformation, one
typically considers an idealized model, the so-called random oracle
model (ROM), which treats cryptographic hash functions as ideal objects.
It is well known that (in the ROM) the Fiat-Shamir transformation

In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret X in order to establish a shared private key K by exchanging messages over an insecure communication channel. If the channel

The theory of alpha-bits is a natural generalisation of approximate quantum error correction that proves fundamental to the study of asymptotic quantum communication resources. In particular, it leads to an asymptotically reversible version of quantum teleportation, called zero-bit teleportation, which decomposes qubits of communication into correlation and transmission components.

We discuss basic notions of quantum entanglement relevant for the study of quantum matter. Entanglement is simultaneously a blessing for quantum computation and a curse for classical simulation of matter. In recent years, there has been a surge of activities in proposing exactly solvable quantum spin chains with the surprisingly high amount of ground state entanglement entropies--beyond what one expects from critical systems describable by conformal field theories (i.e., super-logarithmic violations of the area law).