LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
A Complexity Lower Bound on Algebra Isomorphisms
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

A Complexity Lower Bound on Algebra Isomorphisms

130 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Jeongwan Haah, a researcher at Stanford University, presents this Institute for Advanced Study Computer Science/Discrete Mathematics seminar on the circuit complexity of isomorphisms between operator algebras in quantum computing. He starts from the basic fact that two vector spaces of equal dimension are related by a linear isomorphism, then moves to simple subalgebras over the complex numbers that are closed under conjugate transpose, which are related by a unitary conjugation when their dimensions match. On many-qubit systems that conjugation can be written as a quantum circuit, and Haah asks how deep that circuit must be. He reviews the known lightcone argument showing that the logical operators of any nontrivial quantum error-correcting code require a deep circuit to match unencoded qubits, then presents a new example on a two-dimensional grid of 2n qubits where any geometrically local circuit realizing the isomorphism must have depth linear in the grid's diameter. The talk is a technical research seminar aimed at specialists in quantum information and complexity theory.

At a glance

Lecture facts

Runtime compared with the other 119 Computer Science lectures
Runtime2 h 10 m
Compared with Computer ScienceLonger than 97%
Source channelInstitute for Advanced Study (YouTube)