quantum singular value transformation

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 $(\backslash langle\; 0\; |\; \backslash otimes\; I)\; U\; (|0\backslash rangle\; |\backslash phi\backslash rangle)\; =\; A|\backslash phi\backslash 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 $p(A,\; A^\backslash dagger)$, where p is a polynomial of degree d and $A^\backslash 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 $A\; =\; \backslash sum\; \backslash lambda\_i\; u\_iu\_i^\backslash dagger$, one can get a block-encoding for $\backslash sum\; p(\backslash lambda\_i)\; u\_iu\_i^\backslash dagger$, provided p is bounded.

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

: Input: A polynomial $P$

: Output: A unitary where $P$ has been applied to the singular values of $A$:

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

{{reflist}}

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

• [https://short.classiq.io/qsvt_inversion Implementation of the QSVT algorithm for matrix inversion with Classiq]

Category:Quantum computing

Category:Quantum algorithms

Category:Signal processing

{{Algorithm-stub}}