Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$

Abstract

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 $U(N)$, which realizes multiple polynomials simultaneously from a block-encoded input, as a generalization of those on $U(2)$ 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 $N$-interval decision achieving $O(d)$ query complexity with a ${\log }_{2}N$ improvement over iterative $U(2)$-QSP requiring $O(d{\log }_{2}N)$ queries, and present a quantum amplitude estimation algorithm achieving the Heisenberg limit without adaptive measurements.

19 pages, 8 figures

References in corpus (27)

• A variational eigenvalue solver on a quantum processor
• Advances in Quantum Metrology
• Quantum-enhanced measurements: beating the standard quantum limit
• Quantum metrology
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Quantum speedup of Monte Carlo methods
• Fixed-point quantum search with an optimal number of queries
• Optimal Quantum Measurements of Expectation Values of Observables
• Efficient phase-factor evaluation in quantum signal processing
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Optimal quantum circuits for general phase estimation
• $\pi$-Corrected Heisenberg Limit
• Simulating Open Quantum Systems Using Hamiltonian Simulations
• Realization of quantum signal processing on a noisy quantum computer
• Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle
• Optimising the Solovay-Kitaev algorithm
• Amplitude Estimation from Quantum Signal Processing
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Stable factorization for phase factors of quantum signal processing
• On efficient quantum block encoding of pseudo-differential operators
• Optimal phase estimation in quantum networks
• Single-shot Quantum Signal Processing Interferometry
• On multivariate polynomials achievable with quantum signal processing