skip to content

Department of Computer Science and Technology

Date: 
Tuesday, 10 December, 2024 - 14:00 to 15:00
Speaker: 
Natalie Parham (Columbia University)
Venue: 
Computer Laboratory, William Gates Building, Room FW26

Abstract:

Proving circuit lower bounds for preparing explicit quantum states has long relied on the lightcone argument, which restricts correlations between qubits based on the circuit depth. However, this approach assumes that the input state is a product state, such as $\ket{0}^{\otimes n}$. In this talk, I will introduce new techniques to prove circuit lower bounds for state preparation even when the initial state is entangled.

These techniques allow us to prove logarithmic depth circuit lower bounds even when starting with any stabilizer state. This includes all stabilizer quantum error correcting code states, many of which have topological order. Circuit lower bounds of this type have interesting motivations from both Hamiltonian complexity and condensed matter physics.

We will discuss two different new lower bound techniques: one based on quantum mutual information properties of the state, and the other for states that are locally unique and highly pairwise entangled. Time permitting, I will also introduce a few more examples of state transformation problems where these techniques can be used.

This talk is based on work soon to be on arxiv.

Seminar series: 
Quantum Computing Seminar

Upcoming seminars