Quantum singular value transformation

Quantum singular value transformation is a framework for designing quantum algorithms. It encompasses a variety of quantum algorithms for problems that can be solved with linear algebra, including Hamiltonian simulation, search problems, and linear system solving.^{[1] [2] [3]} It was introduced in 2018 by András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, generalizing algorithms for Hamiltonian simulation of Guang Hao Low and Isaac Chuang inspired by signal processing.^[4]

The basic primitive of quantum singular value transformation is the block-encoding. A quantum circuit is a block-encoding of a matrix A if it implements a unitary matrix U such that U contains A in a specified sub-matrix. For example, if ${\displaystyle (\langle 0|\otimes I)U(|0\rangle \otimes |\phi \rangle )=A|\phi \rangle }${\displaystyle (\langle 0|\otimes I)U(|0\rangle \otimes |\phi \rangle )=A|\phi \rangle }, then U is a block-encoding of A.

The fundamental algorithm of QSVT is one that converts a block-encoding of A to a block-encoding of ${\displaystyle p(A,A^{\dagger })}${\displaystyle p(A,A^{\dagger })}, where p is a polynomial of degree d and ${\displaystyle A^{\dagger }}${\displaystyle A^{\dagger }} denotes the conjugate transpose, with only d applications of the circuit and one ancilla qubit. This can be done for a large class of polynomials p which correspond to applying a polynomial to the singular values of A, giving a "singular value transformation".

A variant of this algorithm can also be performed when A is Hermitian, corresponding to an "eigenvalue transformation". That is, given a block-encoding of A with eigendecomposition of a matrix ${\displaystyle A=\sum \lambda _{i}u_{i}u_{i}^{\dagger }}${\displaystyle A=\sum \lambda _{i}u_{i}u_{i}^{\dagger }}, one can get a block-encoding for ${\displaystyle \sum p(\lambda _{i})u_{i}u_{i}^{\dagger }}${\displaystyle \sum p(\lambda _{i})u_{i}u_{i}^{\dagger }}, provided p is bounded.^[4]

Input: A matrix ${\displaystyle A}${\displaystyle A} whose singular value decomposition is ${\displaystyle A=W\Sigma V^{\dagger }}${\displaystyle A=W\Sigma V^{\dagger }} where ${\displaystyle \Sigma }${\displaystyle \Sigma } are the singular values of A

Input: A polynomial ${\displaystyle P}${\displaystyle P}

Output: A unitary where ${\displaystyle P}${\displaystyle P} has been applied to the singular values of ${\displaystyle A}${\displaystyle A}: ${\displaystyle {\begin{bmatrix}WP(\Sigma )V^{\dagger }&.\\.&.\end{bmatrix}}}${\displaystyle {\begin{bmatrix}WP(\Sigma )V^{\dagger }&.\\.&.\end{bmatrix}}}

1. Prepare a unitary ${\displaystyle U}${\displaystyle U} that encodes ${\displaystyle A}${\displaystyle A} on the top left side of ${\displaystyle U}${\displaystyle U}, that is ${\displaystyle U={\begin{bmatrix}A&.\\.&.\end{bmatrix}}}${\displaystyle U={\begin{bmatrix}A&.\\.&.\end{bmatrix}}}
2. Initialize an ${\displaystyle n}${\displaystyle n} qubit state ${\displaystyle |0\rangle ^{\otimes n}}${\displaystyle |0\rangle ^{\otimes n}}
3. If the polynomial is odd, apply ${\displaystyle {\tilde {\Pi }}_{\phi _{1}}U\prod _{k=1}^{\frac {d-1}{2}}\Pi _{\phi _{2k}}U^{\dagger }{\tilde {\Pi }}_{\phi _{2k+1}}U}${\displaystyle {\tilde {\Pi }}_{\phi _{1}}U\prod _{k=1}^{\frac {d-1}{2}}\Pi _{\phi _{2k}}U^{\dagger }{\tilde {\Pi }}_{\phi _{2k+1}}U} to ${\displaystyle |0\rangle ^{\otimes n}}${\displaystyle |0\rangle ^{\otimes n}}
4. If the polynomial is even apply ${\displaystyle \prod _{k=1}^{\frac {d}{2}}\Pi _{\phi _{2k}-1}U^{\dagger }{\tilde {\Pi }}_{\phi _{2k}}U}${\displaystyle \prod _{k=1}^{\frac {d}{2}}\Pi _{\phi _{2k}-1}U^{\dagger }{\tilde {\Pi }}_{\phi _{2k}}U} to ${\displaystyle |0\rangle ^{\otimes n}}${\displaystyle |0\rangle ^{\otimes n}}

^[2]

• Quantum algorithm
• HHL algorithm
• Quantum machine learning
• Digital signal processing

• Implementation of the QSVT algorithm for matrix inversion with Classiq

• Quantum computing
• Quantum algorithms
• Signal processing
• Algorithms and data structures stubs

• Articles with short description
• Short description matches Wikidata
• All stub articles