Optimizing Sparse SYK

Finding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachdev–Ye–Kitaev (SYK) model is a representative example of such a system; it is particularly interesting not only due to the existence of efficient quantum algorithms preparing approximations to the ground state such as Hastings–O'Donnell (STOC 2022), but also known no-go results for many classical ansatzes in preparing low-energy states. However, this quantum-classical separation is known to not persist when the SYK model is sufficiently sparsified, i.e., when terms in the model are discarded with probability <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mn>1</mml:mn> <mml:mo>&amp;#x2212;</mml:mo> <mml:mi>p</mml:mi> </mml:math> , where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> <mml:mo>=</mml:mo> <mml:mi mathvariant="normal">&amp;#x0398;</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> is the system size. This raises the question of how robust the quantum and classical complexities of the SYK model are to sparsification.In this work we initiate the study of the sparse SYK model where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> <mml:mo>&amp;#x2208;</mml:mo> <mml:mo stretchy="false">[</mml:mo> <mml:mi mathvariant="normal">&amp;#x0398;</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">]</mml:mo> </mml:math> and show there indeed exists a certain robustness of sparsification. We prove that with high probability, Gaussian states achieve only a <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi mathvariant="normal">&amp;#x0398;</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> <mml:mo stretchy="false">)</mml:mo> </mml:math> -factor approximation to the true ground state energy of sparse SYK for all <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> <mml:mo>&amp;#x2265;</mml:mo> <mml:mi mathvariant="normal">&amp;#x03A9;</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>&amp;#x2061;</mml:mo> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:math> , and that Gaussian states cannot achieve constant-factor approximations unless <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> <mml:mo>&amp;#x2264;</mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>log</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>&amp;#x2061;</mml:mo> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:math> . Additionally, we prove that the quantum algorithm of Hastings–O'Donnell still achieves a constant-factor approximation to the ground state energy when <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> <mml:mo>&amp;#x2265;</mml:mo> <mml:mi mathvariant="normal">&amp;#x03A9;</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>&amp;#x2061;</mml:mo> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> . Combined, these show a provable separation between classical algorithms outputting Gaussian states and efficient quantum algorithms for the goal of finding approximate sparse SYK ground states whenever <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> <mml:mo>&amp;#x2265;</mml:mo> <mml:mi mathvariant="normal">&amp;#x03A9;</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>&amp;#x2061;</mml:mo> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> , extending the analogous <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:math> result of Hastings–O'Donnell.