Optimal sampling of tensor networks targeting wave function's fast decaying tails

We introduce an optimal strategy to sample quantum outcomes of local measurement strings for isometric tensor network states. Our method generates samples based on an exact cumulative bounding function, without prior knowledge, in the minimal amount of tensor network contractions. The algorithm avoids sample repetition and, thus, is efficient at sampling distribution with exponentially decaying tails. We illustrate the computational advantage provided by our optimal sampling method through various numerical examples, involving condensed matter, optimization problems, and quantum circuit scenarios. Theory predicts up to an exponential speedup reducing the scaling for sampling the space up to an accumulated unknown probability <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&amp;#x03F5;</mml:mi></mml:math> from <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>&amp;#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&amp;#x2212;</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>&amp;#x03F5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&amp;#x2212;</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:math> for a decaying probability distribution. We confirm this in practice with over one order of magnitude speedup or multiple orders improvement in the error depending on the application. Our sampling strategy extends beyond local observables, e.g., to quantum magic.