Computer Science/Discrete Mathematics Seminar II

Two vector spaces of the same finite dimension are related by a linear isomorphism; that’s how the dimension is defined. Similarly, two simple subalgebras over complex numbers that are closed under conjugate transpose are related by a unitary conjugation whenever their dimensions are the same. On a many-qubit system, the unitary isomorphism can be written as a unitary quantum circuit, of which we ask about the complexity. For example, a simple lightcone argument proves that the algebra of all logical operators of any nontrivial quantum error correcting code is isomorphic to that of unencoded qubits by a deep unitary circuit. Essentially, this has been the only explicit (rather than random) example pair of isomorphic simple subalgebras where the isomorphism complexity lower bound is proved. Here, we report another kind of an explicit simple subalgebra on a two-dimensional grid of 2n qubits, isomorphic to the algebra of all operators on n qubits, where any geometrically local unitary circuit realizing any such isomorphism must have depth linear in the grid’s diameter.