Quantum singular value transformation

(Redirected from Quantum Signal Processing)

Quantum singular value transformation is a framework for designing quantum algorithms. It encompasses a variety of quantum algorithms for problems which 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]

High-level description

edit

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  , 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  , where p is a polynomial of degree d and   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  , one can get a block-encoding for  , provided p is bounded.[4]

Algorithm

edit
Input: A matrix   whose singular value decomposition is   where   are the singular values of A
Input: A polynomial  
Output: A unitary where   has been applied to the singular values of  :  
  1. Prepare a unitary   that encodes   on the top left side of  , that is  
  2. Initialize an   qubit state  
  3. If the polynomial is odd, first apply   and then   to  
  4. If the polynomial is even apply   to  

[2]

References

edit
  1. ^ Gilyén, András; Su, Yuan; Low, Guang Hao; Wiebe, Nathan (June 2019). Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. STOC 2019. ACM. pp. 193–204. arXiv:1806.01838. doi:10.1145/3313276.3316366. ISBN 978-1-4503-6705-9.
  2. ^ a b Martyn, John M.; Rossi, Zane M; Tan, Andrew K.; Chuang, Isaac L. (2021). "Grand Unification of Quantum Algorithms". PRX Quantum. 2 (4). American Physical Society: 040203. arXiv:2105.02859. Bibcode:2021PRXQ....2d0203M. doi:10.1103/PRXQuantum.2.040203.
  3. ^ Arrazola, Juan Miguel (2023-05-23). "Intro to QSVT". PennyLane Demos.
  4. ^ a b Low, Guang Hao; Chuang, Isaac (2017). "Optimal Hamiltonian Simulation by Quantum Signal Processing". Physical Review Letters. 118 (1): 010501. arXiv:1606.02685. Bibcode:2017PhRvL.118a0501L. doi:10.1103/PhysRevLett.118.010501. PMID 28106413. S2CID 1118993.

See also

edit
edit