Parallel Quantum Signal Processing Via Polynomial Factorization

Abstract

Quantum signal processing (QSP) is a methodology for constructing polynomial transformations of a linear operator encoded in a unitary. Applied to an encoding of a state $\rho$, QSP enables the evaluation of nonlinear functions of the form $\text{tr}(P(\rho ))$ for a polynomial $P(x)$, which encompasses relevant properties like entropies and fidelity. However, QSP is a sequential algorithm: implementing a degree-$d$ polynomial necessitates $d$ queries to the encoding, equating to a query depth $d$. Here, we reduce the depth of these property estimation algorithms by developing Parallel Quantum Signal Processing. Our algorithm parallelizes the computation of $\text{tr}(P(\rho ))$ over $k$ systems and reduces the query depth to $d/k$, thus enabling a family of time-space tradeoffs for QSP. This furnishes a property estimation algorithm suitable for distributed quantum computers, and is realized at the expense of increasing the number of measurements by a factor $O(\text{poly}(d)2^{O(k)})$. We achieve this result by factorizing $P(x)$ into a product of $k$ smaller polynomials of degree $O(d/k)$, which are each implemented in parallel with QSP, and subsequently multiplied together with a swap test to reconstruct $P(x)$. We characterize the achievable class of polynomials by appealing to the fundamental theorem of algebra, and demonstrate application to canonical problems including entropy estimation and partition function evaluation.

References in corpus (48)

• Quantum principal component analysis
• Quantum state tomography via compressed sensing
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Probing entanglement entropy via randomized measurements
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Measuring Renyi Entanglement Entropy with Quantum Monte Carlo
• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Hamiltonian simulation with nearly optimal dependence on all parameters
• The randomized measurement toolbox
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Rényi Entropies from Random Quenches in Atomic Hubbard and Spin Models
• Fixed-point quantum search with an optimal number of queries
• Distributed Quantum Computing: a Survey
• Exponential improvement in precision for simulating sparse Hamiltonians
• Efficient phase-factor evaluation in quantum signal processing
• The methodology of resonant equiangular composite quantum gates
• Measuring the Renyi entropy of a two-site Fermi-Hubbard model on a trapped ion quantum computer
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Hamiltonian Simulation with Optimal Sample Complexity
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Fast quantum circuit cutting with randomized measurements
• Entanglement spectroscopy on a quantum computer
• Entanglement spectroscopy with a depth-two quantum circuit
• Quantum algorithm for estimating Renyi entropies of quantum states
• Matrix product states for quantum metrology
• Realization of quantum signal processing on a noisy quantum computer
• Qubit-efficient entanglement spectroscopy using qubit resets
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Quantum algorithms for estimating quantum entropies
• Multivariate trace estimation in constant quantum depth
• Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle
• Low-rank quantum state preparation
• Quantum Phase Processing and its Applications in Estimating Phase and Entropies
• Stable factorization for phase factors of quantum signal processing
• Bootstrap Embedding on a Quantum Computer
• Experimental quantum channel discrimination using metastable states of a trapped ion
• Infinite quantum signal processing
• Spectral thresholding quantum tomography for low rank states
• Halving the Cost of Quantum Algorithms with Randomization
• Quantum and classical query complexities of functions of matrices
• Complementary polynomials in quantum signal processing
• Randomized semi-quantum matrix processing
• Optimal Low-Depth Quantum Signal-Processing Phase Estimation

Cited by in corpus (2)

• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
• An adversary bound for quantum signal processing