Norman Yao

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.

Fault-tolerant logical entangling gates are essential for scalable quantum computing, but are limited by the error rates and overheads of physical two-qubit gates and measurements. To address this limitation we introduce phantom codes---quantum error-correcting codes that realize entangling gates between all logical qubits in a codeblock purely through relabelling of physical qubits during compilation, yielding perfect fidelity with no spatial or temporal overhead. We present a systematic study of such codes. First, we identify phantom codes using complementary numerical and analytical approaches. We exhaustively enumerate all 2.71 x 10^{10} inequivalent CSS codes up to n=14 and identify additional instances up to n=21 via SAT-based methods. We then construct higher-distance phantom-code families using quantum Reed--Muller codes and the binarization of qudit codes. Across all identified codes, we characterize other supported fault-tolerant logical Clifford and non-Clifford operations. Second, through end-to-end noisy simulations with state preparation, full QEC cycles, and realistic physical error rates, we demonstrate scalable advantages of phantom codes over the surface code across multiple tasks. We observe one–to–two–order-of-magnitude reduction in logical infidelity at comparable qubit overhead for GHZ-state preparation and Trotterized many-body simulation tasks, given a modest preselection acceptance rate. Our work establishes phantom codes as a viable architectural route to fault-tolerant quantum computation with scalable benefits for workloads with dense local entangling structure, and introduces general tools for systematically exploring the broader landscape of quantum error-correcting codes.