Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

By András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe. Symposium on the Theory of Computing, 2018

1,255 citations recorded by the source corpus.

An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/fa00b2c3d2fe8326470c47a3e5f5d1e716e58cb3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Generalized Quantum Signal Processing (2023, methodology): “QSP’s applicability was then further extended to the case of non-square matrices by the QSVT technique [11].”
The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation (2018, methodology): “ndence on precision in several applications. In this framework we will represents a subnormalised matrix as the top-left block of a unitary. U= A/α : : : Following the exposition of Gilyén et al. [GSLW18] we use the following deﬁnition: Deﬁnition 3 (Block-encoding). Suppose that Ais an s-qubit ope”
A quantum-inspired classical algorithm for recommendation systems (2018, result): “2The analysis of the phase estimation in the original paper has some ambiguities, but subsequent work [13] demonstrates that essentially the same result can be achieved with a different algorithm.”
Hamiltonian Simulation by Qubitization (2016, background): “Singular value transformations: The standard-form encoding, qubitization, and quantum signal processing of Hermitian or normal matrices has been extended to perform polynomial transformations on the singular value of arbitrary matrices [43].”
Grand Unification of Quantum Algorithms (2021, methodology): “While some of these applications have been covered in the seminal work on QSVT [12], here we aim to present these constructions as pedagogically clearly as possible, providing detailed procedures and intuition for each, and including explicit examples to support abstract ideas where appropriate.”