Quantum circuit lower bounds with entangled inputs

Add to your list(s) Download to your calendar using vCal

• Natalie Parham (Columbia University)
• Tuesday 10 December 2024, 14:00-15:00
• Computer Laboratory, William Gates Building, Room FW26.

If you have a question about this talk, please contact Tom Gur.

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.

This talk is part of the Quantum Computing Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room FW26
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Quantum Computing Seminar
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ki287

Note that ex-directory lists are not shown.