Quantum singular value transformation: Difference between revisions

Revision as of 00:57, 4 February 2024

Latest revision as of 19:06, 28 May 2025

(26 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|Quantum algorithm framework}}

{{Expert needed|date=February 2024}}

'''Quantum singular value transformation''' is a framework for designing [[Quantum algorithm|quantum algorithm]]s. primitiveIt thatencompasses unifiesa allvariety existingof quantum algorithms intofor aproblems singlethat frameworkcan thusbe simplifyingsolved quantumwith [[linear algebra]], including [[Hamiltonian simulation]], [[Grover's algorithm|search designproblems]], and implementation[[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 Itjournal applies|last=Arrazola [[Polynomial|polynomialfirst=Juan functions]]Miguel |date=2023-05-23 |title=Intro to theQSVT [[Singular|url=https://pennylane.ai/qml/demos/tutorial_intro_qsvt/ values|singularjournal=PennyLane valuesDemos |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]] ofinspired matricesby signal processing.<ref name=qsvt2019LC2016>{{Cite journal |arxiv = 18061606.0183802685 |last1 = GilyénLow|first1 = AndrásGuang Hao |last2= SuChuang |first2 = YuanIsaac |last3title = LowOptimal |first3=Hamiltonian GuangSimulation Haoby |last4=WiebeQuantum |first4=NathanSignal Processing|titlejournal = QuantumPhysical singularReview valueLetters|volume transformation= and118|pages beyond:= exponential improvements for quantum matrix arithmetics010501|year journal=Association for Computing Machinery2017|pages issue=1 193-204|yearbibcode = 2019 2017PhRvL.118a0501L|doi = 10.11451103/3313276PhysRevLett.3316366118.010501|pmid = 28106413|url s2cid=https://doi.org/10.1145/3313276.33163661118993 }}</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 ==

{{Uncategorized|date=February 2024}}

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