
A Complexity Lower Bound on Algebra Isomorphisms
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.