1442:
1010:
1161:
660:
160:
783:
415:
351:
891:
1199:
1048:
843:
494:
217:
896:
1055:
252:
514:
1521:
805:
724:
704:
684:
585:
565:
540:
451:
39:. 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
590:
77:
1487:
1249:
729:
356:
295:
1480:
454:
1511:
1516:
1506:
850:
1418:
1413:
1473:
1166:
1015:
810:
460:
28:
1223:
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
1005:{\displaystyle \prod _{k=1}^{\frac {d-1}{2}}\Pi _{\phi _{2k}}U^{\dagger }{\tilde {\Pi }}_{\phi _{2k+1}}U}
1156:{\displaystyle \prod _{k=1}^{\frac {d}{2}}\Pi _{\phi _{2k}-1}U^{\dagger }{\tilde {\Pi }}_{\phi _{2k}}U}
180:
32:
1358:
1339:
Low, Guang Hao; Chuang, Isaac (2017). "Optimal
Hamiltonian Simulation by Quantum Signal Processing".
1291:
262:
applications of the circuit and one ancilla qubit. This can be done for a large class of polynomials
255:
230:
1382:
1348:
1281:
1227:
290:
1403:
1374:
1245:
20:
499:
1366:
1299:
1237:
282:
52:
1362:
1295:
1457:
1453:
1269:
790:
709:
689:
669:
570:
550:
525:
436:
267:
60:
24:
23:. It encompasses a variety of quantum algorithms for problems which can be solved with
285:, corresponding to an "eigenvalue transformation". That is, given a block-encoding of
51:
The basic primitive of quantum singular value transformation is the block-encoding. A
1500:
1408:
36:
655:{\displaystyle {\begin{bmatrix}WP(\Sigma )V^{\dagger }&.\\.&.\end{bmatrix}}}
1386:
1370:
40:
1221:
1303:
155:{\displaystyle (\langle 0|\otimes I)U(|0\rangle |\phi \rangle )=A|\phi \rangle }
1449:
1241:
1378:
173:
The fundamental algorithm of QSVT is one that converts a block-encoding of
1430:
1268:
Martyn, John M.; Rossi, Zane M; Tan, Andrew K.; Chuang, Isaac L. (2021).
1441:
1431:
Implementation of the QSVT algorithm for matrix inversion with
Classiq
1220:
Gilyén, András; Su, Yuan; Low, Guang Hao; Wiebe, Nathan (June 2019).
1353:
1286:
1232:
1318:
778:{\displaystyle U={\begin{bmatrix}A&.\\.&.\end{bmatrix}}}
410:{\displaystyle \sum p(\lambda _{i})u_{i}u_{i}^{\dagger }}
346:{\displaystyle A=\sum \lambda _{i}u_{i}u_{i}^{\dagger }}
1461:
1263:
1261:
277:
A variant of this algorithm can also be performed when
744:
599:
1169:
1058:
1018:
899:
853:
813:
793:
732:
712:
692:
672:
593:
573:
553:
528:
502:
463:
439:
359:
298:
233:
183:
80:
1193:
1155:
1042:
1004:
885:
837:
799:
777:
718:
698:
678:
654:
579:
559:
534:
508:
488:
445:
409:
345:
246:
211:
154:
266:which correspond to applying a polynomial to the
1481:
8:
1179:
1028:
886:{\displaystyle {\tilde {\Pi }}_{\phi _{1}}U}
823:
274:, giving a "singular value transformation".
149:
129:
118:
84:
567:has been applied to the singular values of
74:in a specified sub-matrix. For example, if
1488:
1474:
1352:
1285:
1270:"Grand Unification of Quantum Algorithms"
1231:
1182:
1170:
1168:
1139:
1134:
1123:
1122:
1115:
1094:
1089:
1074:
1063:
1057:
1031:
1019:
1017:
982:
977:
966:
965:
958:
943:
938:
915:
904:
898:
872:
867:
856:
855:
852:
826:
814:
812:
792:
739:
731:
711:
691:
671:
621:
594:
592:
572:
552:
527:
501:
480:
462:
438:
401:
396:
386:
373:
358:
337:
332:
322:
312:
297:
238:
232:
200:
182:
141:
121:
110:
90:
79:
1334:
1332:
1280:(4). American Physical Society: 040203.
1212:
1194:{\displaystyle |0\rangle ^{\otimes n}}
1043:{\displaystyle |0\rangle ^{\otimes n}}
847:If the polynomial is odd, first apply
838:{\displaystyle |0\rangle ^{\otimes n}}
489:{\displaystyle A=W\Sigma V^{\dagger }}
17:Quantum singular value transformation
7:
1522:Algorithms and data structures stubs
1438:
1436:
1317:Arrazola, Juan Miguel (2023-05-23).
1226:. STOC 2019. ACM. pp. 193–204.
353:, one can get a block-encoding for
1125:
1086:
968:
935:
858:
611:
503:
473:
14:
212:{\displaystyle p(A,A^{\dagger })}
1440:
1052:If the polynomial is even apply
55:is a block-encoding of a matrix
43:inspired by signal processing.
1371:10.1103/PhysRevLett.118.010501
1171:
1128:
1020:
971:
861:
815:
614:
608:
379:
366:
291:Eigendecomposition of a matrix
206:
187:
142:
132:
122:
111:
107:
101:
91:
81:
1:
19:is a framework for designing
1460:. You can help Knowledge by
516:are the singular values of A
455:singular value decomposition
247:{\displaystyle A^{\dagger }}
1304:10.1103/PRXQuantum.2.040203
1538:
1435:
223:is a polynomial of degree
1419:Digital signal processing
1414:Quantum machine learning
706:on the top left side of
1341:Physical Review Letters
1242:10.1145/3313276.3316366
509:{\displaystyle \Sigma }
177:to a block-encoding of
166:is a block-encoding of
1456:-related article is a
1195:
1157:
1084:
1044:
1006:
933:
887:
839:
801:
779:
720:
700:
680:
656:
581:
561:
536:
510:
490:
447:
411:
347:
248:
213:
156:
47:High-level description
29:Hamiltonian simulation
1196:
1158:
1059:
1045:
1007:
900:
888:
840:
802:
780:
721:
701:
681:
657:
582:
562:
537:
511:
491:
448:
412:
348:
249:
214:
157:
37:linear system solving
1167:
1056:
1016:
897:
851:
811:
791:
730:
710:
690:
670:
591:
571:
551:
526:
500:
461:
437:
357:
296:
231:
181:
78:
1363:2017PhRvL.118a0501L
1296:2021PRXQ....2d0203M
406:
342:
256:conjugate transpose
59:if it implements a
1512:Quantum algorithms
1191:
1153:
1040:
1002:
883:
835:
797:
775:
769:
716:
696:
676:
666:Prepare a unitary
652:
646:
577:
557:
547:: A unitary where
532:
506:
486:
443:
407:
392:
343:
328:
244:
209:
152:
21:quantum algorithms
1517:Signal processing
1507:Quantum computing
1469:
1468:
1404:Quantum algorithm
1251:978-1-4503-6705-9
1131:
1082:
974:
931:
864:
800:{\displaystyle n}
719:{\displaystyle U}
699:{\displaystyle A}
679:{\displaystyle U}
580:{\displaystyle A}
560:{\displaystyle P}
535:{\displaystyle P}
446:{\displaystyle A}
1529:
1490:
1483:
1476:
1444:
1437:
1391:
1390:
1356:
1336:
1327:
1326:
1314:
1308:
1307:
1289:
1265:
1256:
1255:
1235:
1217:
1200:
1198:
1197:
1192:
1190:
1189:
1174:
1162:
1160:
1159:
1154:
1149:
1148:
1147:
1146:
1133:
1132:
1124:
1120:
1119:
1110:
1109:
1102:
1101:
1083:
1075:
1073:
1049:
1047:
1046:
1041:
1039:
1038:
1023:
1011:
1009:
1008:
1003:
998:
997:
996:
995:
976:
975:
967:
963:
962:
953:
952:
951:
950:
932:
927:
916:
914:
892:
890:
889:
884:
879:
878:
877:
876:
866:
865:
857:
844:
842:
841:
836:
834:
833:
818:
806:
804:
803:
798:
784:
782:
781:
776:
774:
773:
725:
723:
722:
717:
705:
703:
702:
697:
685:
683:
682:
677:
661:
659:
658:
653:
651:
650:
626:
625:
586:
584:
583:
578:
566:
564:
563:
558:
541:
539:
538:
533:
515:
513:
512:
507:
495:
493:
492:
487:
485:
484:
452:
450:
449:
444:
416:
414:
413:
408:
405:
400:
391:
390:
378:
377:
352:
350:
349:
344:
341:
336:
327:
326:
317:
316:
253:
251:
250:
245:
243:
242:
218:
216:
215:
210:
205:
204:
161:
159:
158:
153:
145:
125:
114:
94:
1537:
1536:
1532:
1531:
1530:
1528:
1527:
1526:
1497:
1496:
1495:
1494:
1454:data structures
1427:
1400:
1395:
1394:
1338:
1337:
1330:
1323:PennyLane Demos
1319:"Intro to QSVT"
1316:
1315:
1311:
1267:
1266:
1259:
1252:
1219:
1218:
1214:
1209:
1178:
1165:
1164:
1135:
1121:
1111:
1090:
1085:
1054:
1053:
1027:
1014:
1013:
978:
964:
954:
939:
934:
917:
895:
894:
868:
854:
849:
848:
822:
809:
808:
789:
788:
768:
767:
762:
756:
755:
750:
740:
728:
727:
708:
707:
688:
687:
668:
667:
645:
644:
639:
633:
632:
627:
617:
595:
589:
588:
569:
568:
549:
548:
524:
523:
522:: A polynomial
498:
497:
476:
459:
458:
435:
434:
427:
382:
369:
355:
354:
318:
308:
294:
293:
268:singular values
234:
229:
228:
196:
179:
178:
76:
75:
53:quantum circuit
49:
33:search problems
12:
11:
5:
1535:
1533:
1525:
1524:
1519:
1514:
1509:
1499:
1498:
1493:
1492:
1485:
1478:
1470:
1467:
1466:
1445:
1434:
1433:
1426:
1425:External links
1423:
1422:
1421:
1416:
1411:
1406:
1399:
1396:
1393:
1392:
1328:
1309:
1257:
1250:
1211:
1210:
1208:
1205:
1202:
1201:
1188:
1185:
1181:
1177:
1173:
1152:
1145:
1142:
1138:
1130:
1127:
1118:
1114:
1108:
1105:
1100:
1097:
1093:
1088:
1081:
1078:
1072:
1069:
1066:
1062:
1050:
1037:
1034:
1030:
1026:
1022:
1001:
994:
991:
988:
985:
981:
973:
970:
961:
957:
949:
946:
942:
937:
930:
926:
923:
920:
913:
910:
907:
903:
882:
875:
871:
863:
860:
845:
832:
829:
825:
821:
817:
796:
787:Initialize an
785:
772:
766:
763:
761:
758:
757:
754:
751:
749:
746:
745:
743:
738:
735:
715:
695:
675:
663:
662:
649:
643:
640:
638:
635:
634:
631:
628:
624:
620:
616:
613:
610:
607:
604:
601:
600:
598:
576:
556:
542:
531:
517:
505:
483:
479:
475:
472:
469:
466:
442:
426:
423:
404:
399:
395:
389:
385:
381:
376:
372:
368:
365:
362:
340:
335:
331:
325:
321:
315:
311:
307:
304:
301:
241:
237:
208:
203:
199:
195:
192:
189:
186:
151:
148:
144:
140:
137:
134:
131:
128:
124:
120:
117:
113:
109:
106:
103:
100:
97:
93:
89:
86:
83:
61:unitary matrix
48:
45:
25:linear algebra
13:
10:
9:
6:
4:
3:
2:
1534:
1523:
1520:
1518:
1515:
1513:
1510:
1508:
1505:
1504:
1502:
1491:
1486:
1484:
1479:
1477:
1472:
1471:
1465:
1463:
1459:
1455:
1451:
1446:
1443:
1439:
1432:
1429:
1428:
1424:
1420:
1417:
1415:
1412:
1410:
1409:HHL algorithm
1407:
1405:
1402:
1401:
1397:
1388:
1384:
1380:
1376:
1372:
1368:
1364:
1360:
1355:
1350:
1347:(1): 010501.
1346:
1342:
1335:
1333:
1329:
1324:
1320:
1313:
1310:
1305:
1301:
1297:
1293:
1288:
1283:
1279:
1275:
1271:
1264:
1262:
1258:
1253:
1247:
1243:
1239:
1234:
1229:
1225:
1224:
1216:
1213:
1206:
1204:
1186:
1183:
1175:
1150:
1143:
1140:
1136:
1116:
1112:
1106:
1103:
1098:
1095:
1091:
1079:
1076:
1070:
1067:
1064:
1060:
1051:
1035:
1032:
1024:
999:
992:
989:
986:
983:
979:
959:
955:
947:
944:
940:
928:
924:
921:
918:
911:
908:
905:
901:
880:
873:
869:
846:
830:
827:
819:
794:
786:
770:
764:
759:
752:
747:
741:
736:
733:
713:
693:
686:that encodes
673:
665:
664:
647:
641:
636:
629:
622:
618:
605:
602:
596:
574:
554:
546:
543:
529:
521:
518:
481:
477:
470:
467:
464:
456:
440:
432:
429:
428:
424:
422:
420:
402:
397:
393:
387:
383:
374:
370:
363:
360:
338:
333:
329:
323:
319:
313:
309:
305:
302:
299:
292:
288:
284:
280:
275:
273:
269:
265:
261:
257:
239:
235:
226:
222:
201:
197:
193:
190:
184:
176:
171:
169:
165:
146:
138:
135:
126:
115:
104:
98:
95:
87:
73:
69:
65:
62:
58:
54:
46:
44:
42:
38:
34:
30:
26:
22:
18:
1462:expanding it
1447:
1344:
1340:
1322:
1312:
1277:
1273:
1222:
1215:
1203:
807:qubit state
544:
519:
430:
421:is bounded.
418:
286:
278:
276:
271:
263:
259:
258:, with only
254:denotes the
224:
220:
174:
172:
167:
163:
71:
67:
63:
56:
50:
41:Isaac Chuang
27:, including
16:
15:
1274:PRX Quantum
433:: A matrix
417:, provided
1501:Categories
1450:algorithms
1354:1606.02685
1287:2105.02859
1233:1806.01838
1207:References
726:, that is
66:such that
1184:⊗
1180:⟩
1137:ϕ
1129:~
1126:Π
1117:†
1104:−
1092:ϕ
1087:Π
1061:∏
1033:⊗
1029:⟩
980:ϕ
972:~
969:Π
960:†
941:ϕ
936:Π
922:−
902:∏
893:and then
870:ϕ
862:~
859:Π
828:⊗
824:⟩
623:†
612:Σ
504:Σ
482:†
474:Σ
425:Algorithm
403:†
371:λ
361:∑
339:†
310:λ
306:∑
283:Hermitian
240:†
202:†
150:⟩
147:ϕ
130:⟩
127:ϕ
119:⟩
96:⊗
85:⟨
70:contains
1398:See also
1379:28106413
219:, where
1387:1118993
1359:Bibcode
1292:Bibcode
162:, then
1385:
1377:
1248:
545:Output
496:where
453:whose
35:, and
1448:This
1383:S2CID
1349:arXiv
1282:arXiv
1228:arXiv
520:Input
431:Input
289:with
1458:stub
1375:PMID
1246:ISBN
227:and
1452:or
1367:doi
1345:118
1300:doi
1238:doi
1163:to
1012:to
457:is
281:is
270:of
1503::
1381:.
1373:.
1365:.
1357:.
1343:.
1331:^
1321:.
1298:.
1290:.
1276:.
1272:.
1260:^
1244:.
1236:.
587::
170:.
31:,
1489:e
1482:t
1475:v
1464:.
1389:.
1369::
1361::
1351::
1325:.
1306:.
1302::
1294::
1284::
1278:2
1254:.
1240::
1230::
1187:n
1176:0
1172:|
1151:U
1144:k
1141:2
1113:U
1107:1
1099:k
1096:2
1080:2
1077:d
1071:1
1068:=
1065:k
1036:n
1025:0
1021:|
1000:U
993:1
990:+
987:k
984:2
956:U
948:k
945:2
929:2
925:1
919:d
912:1
909:=
906:k
881:U
874:1
831:n
820:0
816:|
795:n
771:]
765:.
760:.
753:.
748:A
742:[
737:=
734:U
714:U
694:A
674:U
648:]
642:.
637:.
630:.
619:V
615:)
609:(
606:P
603:W
597:[
575:A
555:P
530:P
478:V
471:W
468:=
465:A
441:A
419:p
398:i
394:u
388:i
384:u
380:)
375:i
367:(
364:p
334:i
330:u
324:i
320:u
314:i
303:=
300:A
287:A
279:A
272:A
264:p
260:d
236:A
225:d
221:p
207:)
198:A
194:,
191:A
188:(
185:p
175:A
168:A
164:U
143:|
139:A
136:=
133:)
123:|
116:0
112:|
108:(
105:U
102:)
99:I
92:|
88:0
82:(
72:A
68:U
64:U
57:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.