Resource-efficient algorithm for estimating the trace of quantum state powers

Estimating the trace of quantum state powers, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>Tr</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>&amp;#x03C1;</mml:mi><mml:mi>k</mml:mi></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math>, for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math> identical quantum states is a fundamental task with numerous applications in quantum information processing, including nonlinear function estimation of quantum states and entanglement detection. On near-term quantum devices, reducing the required quantum circuit depth, the number of multi-qubit quantum operations, and the copies of the quantum state needed for such computations is crucial. In this work, inspired by the Newton-Girard method, we significantly improve upon existing results by introducing an algorithm that requires only <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:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>r</mml:mi><mml:mo>&amp;#x007E;</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:math> qubits and <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:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>r</mml:mi><mml:mo>&amp;#x007E;</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:math> multi-qubit gates, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>r</mml:mi><mml:mo>&amp;#x007E;</mml:mo></mml:mover></mml:mrow><mml:mo>=</mml:mo><mml:mo movablelimits="true" form="prefix">min</mml:mo><mml:mrow><mml:mo>{</mml:mo><mml:mrow><mml:mtext>rank</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:mi>&amp;#x03C1;</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mrow><mml:mo>&amp;#x2308;</mml:mo><mml:mrow><mml:mi>ln</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>&amp;#x03F5;</mml:mi></mml:mrow></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mo>&amp;#x2309;</mml:mo></mml:mrow></mml:mrow><mml:mo>}</mml:mo></mml:mrow></mml:math>. This approach is efficient, as it employs the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>r</mml:mi><mml:mo stretchy="false">&amp;#x007E;</mml:mo></mml:mover></mml:mrow></mml:math>-entangled copy measurement instead of the conventional <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>-entangled copy measurement, while asymptotically preserving the known sample complexity upper bound. Furthermore, we prove that estimating <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mtext>Tr</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>&amp;#x03C1;</mml:mi><mml:mi>i</mml:mi></mml:msup><mml:mo stretchy="false">)</mml:mo><mml:msubsup><mml:mo fence="false" stretchy="false">}</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>r</mml:mi><mml:mo stretchy="false">&amp;#x007E;</mml:mo></mml:mover></mml:mrow></mml:mrow></mml:msubsup></mml:math> is sufficient to approximate <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>Tr</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>&amp;#x03C1;</mml:mi><mml:mi>k</mml:mi></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> even for large integers <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi><mml:mo>&amp;#x003E;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>r</mml:mi><mml:mo>&amp;#x007E;</mml:mo></mml:mover></mml:mrow></mml:math>. This leads to a rank-dependent complexity for solving the problem, providing an efficient algorithm for low-rank quantum states while also improving existing methods when the rank is unknown or when the state is not low-rank. Building upon these advantages, we extend our algorithm to the estimation of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>Tr</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:mi>M</mml:mi><mml:msup><mml:mi>&amp;#x03C1;</mml:mi><mml:mi>k</mml:mi></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> for arbitrary observables and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>Tr</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>&amp;#x03C1;</mml:mi><mml:mi>k</mml:mi></mml:msup><mml:msup><mml:mi>&amp;#x03C3;</mml:mi><mml:mi>l</mml:mi></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> for multiple quantum states.