Lower Bounds for Unitary Property Testing with Proofs and Advice

In unitary property testing a quantum algorithm, also known as a tester, is given query access to a black-box unitary and has to decide whether it satisfies some property. We propose a new technique for proving lower bounds on the quantum query complexity of unitary property testing and related problems, which utilises its connection to unitary channel discrimination. The main advantage of this technique is that all obtained lower bounds hold for any <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">C</mml:mi></mml:mrow></mml:math>-tester with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">C</mml:mi></mml:mrow><mml:mo>&amp;#x2286;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">M</mml:mi><mml:mi mathvariant="sans-serif">A</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">q</mml:mi><mml:mi mathvariant="sans-serif">p</mml:mi><mml:mi mathvariant="sans-serif">o</mml:mi><mml:mi mathvariant="sans-serif">l</mml:mi><mml:mi mathvariant="sans-serif">y</mml:mi></mml:mrow></mml:math>, showing that even having access to both (unentangled) quantum proofs and advice does not help for many unitary property testing problems. We apply our technique to prove lower bounds for problems like quantum phase estimation, the entanglement entropy problem, quantum Gibbs sampling and more, removing all logarithmic factors in the lower bounds obtained by the sample-to-query lifting theorem of Wang and Zhang (2023). As a direct corollary, we show that there exist quantum oracles relative to which <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">M</mml:mi><mml:mi mathvariant="sans-serif">A</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>&amp;#x2285;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">S</mml:mi><mml:mi mathvariant="sans-serif">B</mml:mi><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">P</mml:mi></mml:mrow></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">M</mml:mi><mml:mi mathvariant="sans-serif">A</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">q</mml:mi><mml:mi mathvariant="sans-serif">p</mml:mi><mml:mi mathvariant="sans-serif">o</mml:mi><mml:mi mathvariant="sans-serif">l</mml:mi><mml:mi mathvariant="sans-serif">y</mml:mi></mml:mrow><mml:mo>&amp;#x2285;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">S</mml:mi><mml:mi mathvariant="sans-serif">B</mml:mi><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">P</mml:mi></mml:mrow></mml:math>. The former shows that, at least in a black-box way, having unentangled quantum proofs does not help in solving problems that require high precision.