Norman Y. Yao

Helia Kamal, Dominik Kufel, DinhDuy Vu et al.

A recent article [Phys. Rev. X 15, 011047 (2025)] utilizes group-equivariant convolutional neural networks to study the ground state of the kagome Heisenberg antiferromagnet. On the largest finite-size cluster studied to date ($N=108$), the authors report variational energies significantly lower than other numerical methods, including state-of-the-art density matrix renormalization group (DMRG) calculations. In contrast to previous results suggesting a possible spin-liquid ground state, the authors observe a spinon pair-density-wave ground state. We find that: (i) the reported low energies are artifacts of broken ergodicity in the Metropolis--Hastings sampling, since the single-spin-flip update rule utilized by the authors effectively freezes the Markov chains; and (ii) when ergodic sampling is enforced via spin-exchange updates, the neural network converges to energies significantly higher than existing DMRG results, calling the paper's claims into question.

Thomas Schuster, Dominik Kufel, Norman Y. Yao et al.

We prove that recognizing the phase of matter of an unknown quantum state is quantum computationally hard. More specifically, we show that the quantum computational time of any phase recognition algorithm must grow exponentially in the range of correlations $ξ$ of the unknown state. This exponential growth renders the problem practically infeasible for even moderate correlation ranges, and leads to super-polynomial quantum computational time in the system size $n$ whenever $ξ= ω(\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 (PRUs) to quantum systems with symmetries. We prove that symmetric PRUs exist under standard cryptographic conjectures, and can be constructed in extremely low circuit depths. We also establish hardness for systems with translation invariance and purely classical phases of matter. A key technical limitation is that the locality of the parent Hamiltonians of the states we consider is linear in $ξ$; the complexity of phase recognition for Hamiltonians with constant locality remains an important open question.

Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani et al.

We propose and analyze a novel interactive protocol for demonstrating quantum computational advantage, which is efficiently classically verifiable. Our protocol relies upon the cryptographic hardness of trapdoor claw-free functions (TCFs). Through a surprising connection to Bell's inequality, our protocol avoids the need for an adaptive hardcore bit, with essentially no increase in the quantum circuit complexity and no extra cryptographic assumptions. Crucially, this expands the set of compatible TCFs, and we propose two new constructions: one based upon the decisional Diffie-Hellman problem and the other based upon Rabin's function, $x^2 \bmod N$. We also describe two independent innovations which improve the efficiency of our protocol's implementation: (i) a scheme to discard so-called "garbage bits", thereby removing the need for reversibility in the quantum circuits, and (ii) a natural way of performing post-selection which significantly reduces the fidelity needed to demonstrate quantum advantage. These two constructions may also be of independent interest, as they may be applicable to other TCF-based quantum cryptography such as certifiable random number generation. Finally, we design several efficient circuits for $x^2 \bmod N$ and describe a blueprint for their implementation on a Rydberg-atom-based quantum computer.