Quantum singular value transformation: Difference between revisions

Revision as of 22:44, 4 February 2024

Latest revision as of 19:06, 28 May 2025

(21 intermediate revisions by 9 users not shown)

Line 1:

{{Short description|Quantum algorithm framework}}

'''Quantum singular value transformation''' is a [[quantum algorithm]] primitive that unifies all existing quantum algorithms into a single framework thus simplifying quantum algorithm design and implementation.<ref>{{cite news |author=<!--not stated--> |date=17 January 2023 |title=Xanadu and Rolls-Royce to Build Quantum Computing Tools with PennyLane |url=https://www.mbtmag.com/industry-4-0/news/22657552/xanadu-and-rollsroyce-to-build-quantum-computing-tools-with-pennylane |access-date=4 February 2024}}</ref><ref name=grand_unification2021>{{Cite journal |arxiv = 2105.02859 |last1 = Martyn|first1 = John M. |last2= Rossi |first2 = Zane M |last3=Tan |first3=Andrew K. |last4=Chuang |first4=Isaac L. |title = Grand Unification of Quantum Algorithms|journal = PRX Quantum|volume = 2|pages = 040203|year = 2021| issue=4 |publisher=American Physical Society|doi =10.1103/PRXQuantum.2.040203|url=https://link.aps.org/doi/10.1103/PRXQuantum.2.040203}}</ref> It applies [[Polynomial|polynomial functions]] to the [[singular values]] of matrices.<ref name=qsvt2019>{{Cite journal |arxiv = 1806.01838 |last1 = Gilyén|first1 = András |last2= Su |first2 = Yuan |last3 = Low |first3= Guang Hao |last4=Wiebe |first4=Nathan |title = Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics| journal=Association for Computing Machinery|pages = 193–204|year = 2019 |doi = 10.1145/3313276.3316366 |url=https://doi.org/10.1145/3313276.3316366}}</ref>

'''Quantum singular value transformation''' is a framework for designing [[quantum algorithm]]s. It encompasses a variety of quantum algorithms for problems that can be solved with [[linear algebra]], including [[Hamiltonian simulation]], [[Grover's algorithm|search problems]], and [[HHL algorithm|linear system solving]].<ref name=qsvt2019>{{Cite conference |last=Gilyén |first=András |last2=Su |first2=Yuan |last3=Low |first3=Guang Hao |last4=Wiebe |first4=Nathan |date=June 2019 |title=Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics |conference=STOC 2019 |url=https://dl.acm.org/doi/10.1145/3313276.3316366 |language=en |publisher=ACM |pages=193–204 |doi=10.1145/3313276.3316366 |isbn=978-1-4503-6705-9|arxiv=1806.01838 }}</ref><ref name=grand_unification2021>{{Cite journal |arxiv = 2105.02859 |last1 = Martyn|first1 = John M. |last2= Rossi |first2 = Zane M |last3=Tan |first3=Andrew K. |last4=Chuang |first4=Isaac L. |title = Grand Unification of Quantum Algorithms|journal = PRX Quantum|volume = 2|pages = 040203|year = 2021| issue=4 |publisher=American Physical Society|doi =10.1103/PRXQuantum.2.040203| bibcode=2021PRXQ....2d0203M |url=https://link.aps.org/doi/10.1103/PRXQuantum.2.040203}}</ref><ref>{{Cite journal |last=Arrazola |first=Juan Miguel |date=2023-05-23 |title=Intro to QSVT |url=https://pennylane.ai/qml/demos/tutorial_intro_qsvt/ |journal=PennyLane Demos |language=en}}</ref> 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.<ref name=LC2016>{{Cite journal |arxiv = 1606.02685 |last1 = Low|first1 = Guang Hao |last2= Chuang |first2 = Isaac |title = Optimal Hamiltonian Simulation by Quantum Signal Processing|journal = Physical Review Letters|volume = 118|pages = 010501|year = 2017| issue=1 |bibcode = 2017PhRvL.118a0501L|doi = 10.1103/PhysRevLett.118.010501|pmid = 28106413| s2cid=1118993 }}</ref>

==High-level description==

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 <math>(\langle 0 | \otimes I) U (|0\rangle |\phi\rangle) = A|\phi\rangle</math>, 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 <math>p(A, A^\dagger)</math>, where ''p'' is a polynomial of degree ''d'' and <math>A^\dagger</math> 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 value]]s of ''A'', giving a "singular value transformation".

A variant of this algorithm can also be performed when ''A'' is [[Hermitian matrix|Hermitian]], corresponding to an "eigenvalue transformation". That is, given a block-encoding of ''A'' with [[eigendecomposition|eigendecomposition of a matrix]] <math>A = \sum \lambda_i u_iu_i^\dagger</math>, one can get a block-encoding for <math>\sum p(\lambda_i) u_iu_i^\dagger</math>, provided ''p'' is bounded.<ref name=LC2016 />

==Algorithm==

: ''Input'': A matrix <math>A</math> whose [[Singularsingular value decomposition]] is <math>A = W\Sigma V^{\dagger}</math> where <math>\Sigma</math> are the singular values of A

: ''Input'': A polynomial <math>P</math>

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

# Prepare a unitary <math>U</math> that encodes <math>A</math> on the top left side of <math>U</math>, that is <math>U = \begin{bmatrix}A & . \\. & . \end{bmatrix}</math>

# Initialize an <math>n</math> qubit state <math>|0\rangle^{\otimes n}</math>

# If the polynomial is odd, first apply <math>\tilde{\Pi}_{\phi_{1}} U </math> and then <math> \prod_{k=1}^{\frac{d-1}{2}} \Pi_{\phi_{2k}}U^{\dagger}\tilde{\Pi}_{\phi_{2k+1}} U </math> to <math>|0\rangle^{\otimes n}</math>

# If the polynomial is even apply <math> \prod_{k=1}^{\frac{d}{2}} \Pi_{\phi_{2k}-1}U^{\dagger}\tilde{\Pi}_{\phi_{2k}} U </math> to <math>|0\rangle^{\otimes n}</math>

<ref name=grand_unification2021 />

== See also ==

* [[Quantum signal processing]]

== References==

{{reflist}}

== See also ==

* [[Quantum algorithm]]

* [[HHL algorithm]]

* [[Quantum machine learning]]

* [[QuantumDigital signal processing]]

== External links ==

* [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}}