Quantum Merlin-Arthur proof systems for synthesizing quantum states

Complexity theory typically focuses on the difficulty of solving computational problems using classical inputs and outputs, even with a quantum computer. In the quantum world, it is natural to apply a different notion of complexity, namely the complexity of synthesizing quantum states. We investigate a state-synthesizing counterpart of the class <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">N</mml:mi><mml:mi mathvariant="sans-serif">P</mml:mi></mml:mrow></mml:math>, referred to as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">s</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">a</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">e</mml:mi><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:math>, which is concerned with preparing certain quantum states through a polynomial-time quantum verifier with the aid of a single quantum message from an all-powerful but untrusted prover. This is a subclass of the class <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">s</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">a</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">e</mml:mi><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">I</mml:mi><mml:mi mathvariant="sans-serif">P</mml:mi></mml:mrow></mml:math> recently introduced by Rosenthal and Yuen (ITCS 2022) \cite{RY22}, which permits polynomially many interactions between the prover and the verifier. Our main result consists of error reduction of this class and its variants with an exponentially small gap or bounded space, as well as how this class relates to other fundamental state synthesizing classes, i.e., states generated by uniform polynomial-time quantum circuits (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">s</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">a</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">e</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 space-uniform polynomial-space quantum circuits (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">s</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">a</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">e</mml:mi><mml:mi mathvariant="sans-serif">P</mml:mi><mml:mi mathvariant="sans-serif">S</mml:mi><mml:mi mathvariant="sans-serif">P</mml:mi><mml:mi mathvariant="sans-serif">A</mml:mi><mml:mi mathvariant="sans-serif">C</mml:mi><mml:mi mathvariant="sans-serif">E</mml:mi></mml:mrow></mml:math>). Furthermore, we establish that the family of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">U</mml:mi><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:math> witnesses, considered as one of the most natural candidates for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">s</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">a</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">e</mml:mi><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:math> containments, is in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">s</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">a</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">e</mml:mi><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:math>. Additionally, we demonstrate that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">s</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">a</mml:mi><mml:mi mathvariant="sans-serif">t</mml:mi><mml:mi mathvariant="sans-serif">e</mml:mi><mml:mi mathvariant="sans-serif">Q</mml:mi><mml:mi mathvariant="sans-serif">C</mml:mi><mml:mi mathvariant="sans-serif">M</mml:mi><mml:mi mathvariant="sans-serif">A</mml:mi></mml:mrow></mml:math> achieves perfect completeness.