Many Body Theory 2

Abstract: We prove that recognizing the phase of matter of an unknown quantum state is quantum computationally hard. More specifically, we show that the worst-case runtime of any phase recognition algorithm must grow exponentially in the correlation length $\xi$ of the state. This exponential growth renders the problem practically infeasible even for moderate constant values of the correlation length $\xi$, and leads to super-polynomial quantum computational time in the system size $n$ whenever $\xi = \omega(\log n)$. Our results apply to a substantial portion of all known phases of matter, including symmetry-breaking phases and symmetry-protected topological phases for any discrete on-site symmetry group in any spatial dimension. To establish this hardness, we extend the study of pseudorandom unitaries to quantum systems with symmetries. We prove that symmetric pseudorandom unitaries exist under standard cryptographic conjectures, and can be constructed in extremely low circuit depths for any discrete on-site group. We also provide extensions of our results to systems with translation invariance and purely classical phases of matter. A key technical limitation is that the locality of the parent Hamiltonian of the states we consider is linear in $\xi$; removing this constraint remains an important open question.

Abstract: Understanding nonstabilizerness (aka quantum magic) in many-body quantum systems, particularly its interplay with entanglement, represents an important quest in quantum computation and many-body physics. Drawing motivation from the study of quantum phases of matter and entanglement, we develop a systematic and rigorous theory of the notion of long-range magic (LRM)---nonstabilizerness that cannot be (approximately) erased by shallow local unitary circuits. By establishing connections to the theory of fault-tolerant logical gates, we show the emergence of LRM state families from quantum error-correcting codes. Then, denoting phases whose ground states all exhibit LRM as LRM phases, we prove concrete conditions under which a topological order constitutes an LRM phase, with prominent examples including certain non-Abelian topological orders. Finally, from the computational complexity perspective, we discuss the intrinsic quantumness of long-range magic from e.g. preparation and learning perspectives, and formulate a "no low-energy trivial magic" (NLTM) conjecture that has key motivation in the quantum PCP context for which our LRM results suggest a promising route. We also show how correlation functions can serve as diagnostics for LRM, demonstrating certain LRM state families by correlation properties. Our concepts and results admit nontrivial extensions to approximate (robust) versions and settings without geometric locality. This work leverages and sheds new light on the interplay between quantum resources, error correction and fault tolerance, many-body physics, and complexity theory.

Abstract: Despite recent advances in the lattice representation theory of (generalized) symmetries, many simple quantum spin chains of physical interest are not included in the rigid framework of fusion categories and weak Hopf algebras. We demonstrate that this problem can be overcome by relaxing the requirements on the underlying algebraic structure, and show that general matrix product operator symmetries are described by a pre-bialgebra. As a guiding example, we focus on the anomalous $\mathbb Z_2$ symmetry of the XX model, which manifests the mixed anomaly between its $U(1)$ momentum and winding symmetry. We show how this anomaly is embedded into the non-semisimple corepresentation category, providing a novel mechanism for realizing such anomalous symmetries on the lattice. Additionally, the representation category which describes the renormalization properties is semisimple and semi-monoidal, which provides a new class of mixed state renormalization fixed points. Finally, we show that up to a quantum channel, this anomalous $\mathbb Z_2$ symmetry is equivalent to a more conventional MPO symmetry obtained on the boundary of a double semion model. In this way, our work provides a bridge between well-understood topological defect symmetries and those that arise in more realistic models.