Quantum Signal Processing and Quantum Singular Value Transformation on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>U</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math>

Quantum signal processing and quantum singular value transformation are powerful tools to implement polynomial transformations of block-encoded matrices on quantum computers, and has achieved asymptotically optimal complexity in many prominent quantum algorithms. We propose a framework of quantum signal processing and quantum singular value transformation on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>U</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> , which realizes multiple polynomials simultaneously from a block-encoded input, as a generalization of those on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>U</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>2</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:math> in the original frameworks. We provide a comprehensive characterization of achievable polynomial matrices and give recursive algorithms to construct the quantum circuits that realize desired polynomial transformations. As three example applications, we propose a framework to realize bi-variate polynomial functions, demonstrate <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>N</mml:mi> </mml:math> -interval decision achieving <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>d</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> query complexity with a <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>log</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>&amp;#x2061;</mml:mo> <mml:mi>N</mml:mi> </mml:math> improvement over iterative <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>U</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>2</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:math> -QSP requiring <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>d</mml:mi> <mml:msub> <mml:mi>log</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>&amp;#x2061;</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> queries, and present a quantum amplitude estimation algorithm achieving the Heisenberg limit without adaptive measurements.