Quantum singular value transformation: Difference between revisions

Revision as of 21:19, 28 June 2024

Latest revision as of 19:06, 28 May 2025

(9 intermediate revisions by 6 users not shown)

Line 1:

{{Short description|Quantum algorithm framework}}

'''Quantum singular value transformation''' is a framework for designing [[quantum algorithm]]s. It encompasses a variety of quantum algorithms for linearproblems algebraicthat taskscan be solved with [[linear algebra]], including [[Hamiltonian simulation]], [[Grover's algorithm|search problems]], and [[HHL algorithm|linear system solving]].<ref name=qsvt2019>{{Cite bookconference |arxiv last= 1806.01838Gilyén |last1 first= Gilyén|first1 = András |last2= Su |first2 = Yuan |last3 = Low |first3= Guang Hao |last4=Wiebe |first4=Nathan |date=June chapter2019 |title=Quantum singular value transformation and beyond: Exponentialexponential improvements for quantum matrix arithmetics |title conference=STOC Proceedings2019 of|url=https://dl.acm.org/doi/10.1145/3313276.3316366 the|language=en 51st Annual ACM SIGACT Symposium on Theory of Computing| journalpublisher=AssociationACM for Computing Machinery|pages = 193–204|year = 2019 |doi = 10.1145/3313276.3316366 | isbn=978-1-4503-6705-9 |chapter-urlarxiv=https://doi1806.org/10.1145/3313276.331636601838 }}</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.aiundefinedai/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==

Line 5 ⟶ 6:

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|Eigendecompositioneigendecomposition 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==

Line 15 ⟶ 16:

# 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 />