1742:
1732:
95:
Surprisingly, the quantum threshold theorem shows that if the error to perform each gate is a small enough constant, one can perform arbitrarily long quantum computations to arbitrarily good precision, with only some small added overhead in the number of gates. The formal statement of the threshold
298:
on the order of 1%, though estimates range widely and are difficult to calculate due to the exponential difficulty of simulating large quantum systems. At a 0.1% probability of a depolarizing error, the surface code would require approximately 1,000-10,000 physical qubits per logical data qubit,
262:
Threshold theorems for classical computation have the same form as above, except for classical circuits instead of quantum. The proof strategy for quantum computation is similar to that of classical computation: for any particular error model (such as having each gate fail with independent
276:
is a small-enough constant). Then, one can use these better gates to recursively create even better gates, until one has gates with the desired failure probability, which can be used for the desired quantum circuit. According to quantum information theorist
271:
to build better gates out of existing gates. Though these "better gates" are larger, and so are more prone to errors within them, their error-correction properties mean that they have a lower chance of failing than the original gate (provided
864:«The entire content of the Threshold Theorem is that you're correcting errors faster than they're created. That's the whole point, and the whole non-trivial thing that the theorem shows. That's the problem it solves.»
285:"The entire content of the Threshold Theorem is that you're correcting errors faster than they're created. That's the whole point, and the whole non-trivial thing that the theorem shows. That's the problem it solves."
91:
perfectly, some small constant error is inevitable; hypothetically, this could mean that quantum computers with imperfect gates can only apply a constant number of gates before the computation is destroyed by noise.
86:
The key question that the threshold theorem resolves is whether quantum computers in practice could perform long computations without succumbing to noise. Since a quantum computer will not be able to perform
203:
257:
1776:
931:
59:
893:
712:
Fowler, Austin G.; Stephens, Ashley M.; Groszkowski, Peter (2009-11-11). "High-threshold universal quantum computation on the surface code".
338:
It is widely believed that it is exponentially difficult for classical computers to simulate quantum systems. This problem is known as the
1623:
131:
98:
346:, which is one of the main appeals of quantum computing. This is applicable to chemical simulations, drug discovery, energy production,
1524:
1185:
773:
Campbell, Earl T.; Terhal, Barbara M.; Vuillot, Christophe (2017-09-13). "Roads towards fault-tolerant universal quantum computation".
17:
1086:
354:) as well. Because of this, quantum computers may be better than classical computers at aiding design of further quantum computers.
1411:
1771:
612:
396:
1766:
1735:
921:
1693:
1269:
690:
1745:
1633:
886:
656:
1561:
1219:
54:'s threshold theorem for classical computation. This result was proven (for various error models) by the groups of
46:
schemes, suppress the logical error rate to arbitrarily low levels. This shows that quantum computers can be made
42:) states that a quantum computer with a physical error rate below a certain threshold can, through application of
1556:
1284:
1264:
849:
1551:
1063:
1584:
1406:
1309:
970:
1589:
1457:
1048:
879:
1613:
1369:
1229:
1003:
958:
902:
314:
1485:
1357:
1254:
1130:
1058:
965:
648:
224:
1294:
1259:
1155:
1098:
527:
339:
1467:
1440:
1416:
1379:
1170:
1103:
1038:
1023:
993:
916:
308:
43:
1618:
1352:
1244:
1214:
1013:
1688:
1452:
1445:
1192:
1608:
1234:
1160:
1125:
268:
1398:
1147:
998:
792:
731:
549:
500:
478:
8:
1717:
1670:
1500:
1274:
1028:
1008:
943:
938:
377:"Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components"
96:
theorem depends on the types of error correction codes and error model being considered.
796:
735:
553:
504:
1433:
1279:
1081:
1018:
824:
782:
755:
721:
618:
573:
539:
490:
456:
430:
418:
88:
684:
561:
1697:
1342:
1249:
1206:
1137:
1033:
988:
948:
926:
859:
816:
808:
759:
747:
662:
652:
608:
577:
565:
448:
392:
67:
31:
27:
Quantum error correction schemes can suppress the logical error rate arbitrarily low
1364:
1314:
1091:
828:
800:
739:
622:
600:
557:
508:
460:
440:
384:
63:
51:
1490:
1428:
1118:
1113:
636:
512:
319:
103:
47:
342:. However, quantum computers can simulate many (though not all) Hamiltonians in
1599:
1576:
1543:
1347:
1224:
855:
743:
680:
376:
278:
259:, and given reasonable assumptions about the noise in the underlying hardware.
55:
871:
592:
444:
388:
1760:
1421:
1239:
1165:
812:
751:
666:
604:
569:
452:
347:
71:
1641:
1566:
820:
640:
299:
though more pathological error types could change this figure drastically.
295:
107:
1651:
1505:
1043:
544:
495:
435:
804:
1712:
1646:
1510:
75:
1495:
845:
1680:
1656:
1515:
1480:
787:
726:
1707:
1324:
597:
Proceedings of 37th
Conference on Foundations of Computer Science
599:. Burlington, VT, USA: IEEE Comput. Soc. Press. pp. 56–65.
1684:
1180:
351:
953:
419:"Fault-Tolerant Quantum Computation with Constant Error Rate"
209:) on hardware whose components fail with probability at most
1702:
1175:
1108:
78:, which proved a weaker version of the threshold theorem.
1319:
1304:
711:
383:, Princeton: Princeton University Press, pp. 43–98,
343:
124:
gates may be simulated with probability of error at most
860:"PHYS771 Lecture 14: Skepticism of Quantum Computing"
772:
227:
134:
1146:
198:{\displaystyle O(\log ^{c}(p(n)/\varepsilon )p(n))}
251:
197:
110:, gives the general framework for such a theorem:
74:independently. These results built on a paper of
1758:
901:
679:
417:Aharonov, Dorit; Ben-Or, Michael (2008-01-01).
528:"Fault-tolerant quantum computation by anyons"
416:
289:
887:
685:"Lecture 14: Skepticism of Quantum Computing"
635:
294:Current estimates put the threshold for the
1777:Theorems in computational complexity theory
645:Quantum Computation and Quantum Information
99:Quantum Computation and Quantum Information
894:
880:
114:Threshold theorem for quantum computation:
786:
725:
543:
494:
434:
647:(10th anniversary ed.). Cambridge:
368:
1412:Continuous-variable quantum information
850:"Perpetual Motion of The 21st Century?"
629:
519:
472:
470:
374:
14:
1759:
525:
875:
584:
476:
593:"Fault-tolerant quantum computation"
590:
467:
410:
344:polynomial time with bounded errors
24:
691:Quantum Computing Since Democritus
243:
240:
25:
1788:
839:
252:{\displaystyle p<p_{\rm {th}}}
1741:
1740:
1731:
1730:
350:and fertilizer production (e.g.
766:
479:"Resilient Quantum Computation"
40:quantum fault-tolerance theorem
705:
683:; Granade, Chris (Fall 2006).
673:
375:Neumann, J. von (1956-12-31),
332:
192:
189:
183:
177:
166:
160:
154:
138:
81:
13:
1:
1407:Adiabatic quantum computation
562:10.1016/S0003-4916(02)00018-0
526:Kitaev, A. Yu. (2003-01-01).
361:
1772:Theoretical computer science
1458:Topological quantum computer
513:10.1126/science.279.5349.342
7:
1767:Quantum information science
1736:Quantum information science
903:Quantum information science
315:Physical and logical qubits
302:
290:Threshold value in practice
10:
1793:
1131:quantum gate teleportation
744:10.1103/physreva.80.052312
649:Cambridge University Press
1726:
1669:
1632:
1598:
1575:
1542:
1533:
1466:
1395:
1333:
1293:
1260:Quantum Fourier transform
1205:
1156:Post-quantum cryptography
1099:Entanglement distillation
1072:
981:
909:
445:10.1137/S0097539799359385
423:SIAM Journal on Computing
389:10.1515/9781400882618-003
381:Automata Studies. (AM-34)
340:quantum many body problem
205:gates (for some constant
18:Quantum threshold theorem
1746:Quantum mechanics topics
1441:Quantum machine learning
1417:One-way quantum computer
1270:Quantum phase estimation
1171:Quantum key distribution
1104:Monogamy of entanglement
605:10.1109/SFCS.1996.548464
477:Knill, E. (1998-01-16).
325:
309:Quantum error correction
44:quantum error correction
1353:Randomized benchmarking
1215:Amplitude amplification
217:is below some constant
1453:Quantum Turing machine
1446:quantum neural network
1193:Quantum secret sharing
287:
269:error correcting codes
253:
199:
120:qubits and containing
1525:Entanglement-assisted
1486:quantum convolutional
1161:Quantum coin flipping
1126:Quantum teleportation
1087:entanglement-assisted
917:DiVincenzo's criteria
283:
254:
200:
116:A quantum circuit on
1336:processor benchmarks
1265:Quantum optimization
1148:Quantum cryptography
959:physical vs. logical
225:
132:
58:and Michael Ben-Or;
50:, as an analogue to
1049:Quantum speed limit
944:Quantum programming
939:Quantum information
805:10.1038/nature23460
797:2017Natur.549..172C
736:2009PhRvA..80e2312F
637:Nielsen, Michael A.
591:Shor, P.W. (1996).
554:2003AnPhy.303....2K
505:1998Sci...279..342K
1698:Forest/Rigetti QCS
1434:quantum logic gate
1220:Bernstein–Vazirani
1207:Quantum algorithms
1082:Classical capacity
966:Quantum processors
949:Quantum simulation
694:. Shtetl Optimized
249:
195:
1754:
1753:
1665:
1664:
1562:Linear optical QC
1343:Quantum supremacy
1297:complexity theory
1250:Quantum annealing
1201:
1200:
1138:Superdense coding
927:Quantum computing
781:(7671): 172–179.
714:Physical Review A
614:978-0-8186-7594-2
532:Annals of Physics
489:(5349): 342–345.
398:978-1-4008-8261-8
36:threshold theorem
32:quantum computing
16:(Redirected from
1784:
1744:
1743:
1734:
1733:
1540:
1539:
1470:error correction
1399:computing models
1365:Relaxation times
1255:Quantum counting
1144:
1143:
1092:quantum capacity
1039:No-teleportation
1024:No-communication
896:
889:
882:
873:
872:
833:
832:
790:
770:
764:
763:
729:
709:
703:
702:
700:
699:
677:
671:
670:
641:Chuang, Isaac L.
633:
627:
626:
588:
582:
581:
547:
545:quant-ph/9707021
523:
517:
516:
498:
496:quant-ph/9702058
474:
465:
464:
438:
436:quant-ph/9906129
429:(4): 1207–1282.
414:
408:
407:
406:
405:
372:
355:
348:climate modeling
336:
258:
256:
255:
250:
248:
247:
246:
204:
202:
201:
196:
173:
150:
149:
64:Raymond Laflamme
21:
1792:
1791:
1787:
1786:
1785:
1783:
1782:
1781:
1757:
1756:
1755:
1750:
1722:
1672:
1661:
1634:Superconducting
1628:
1594:
1585:Neutral atom QC
1577:Ultracold atoms
1571:
1536:implementations
1535:
1529:
1469:
1462:
1429:Quantum circuit
1397:
1391:
1385:
1375:
1335:
1329:
1296:
1289:
1245:Hidden subgroup
1197:
1186:other protocols
1142:
1119:quantum network
1114:Quantum channel
1074:
1068:
1014:No-broadcasting
1004:Gottesman–Knill
977:
905:
900:
869:
842:
837:
836:
771:
767:
710:
706:
697:
695:
681:Aaronson, Scott
678:
674:
659:
634:
630:
615:
589:
585:
524:
520:
475:
468:
415:
411:
403:
401:
399:
373:
369:
364:
359:
358:
337:
333:
328:
320:Fault tolerance
305:
292:
239:
238:
234:
226:
223:
222:
169:
145:
141:
133:
130:
129:
104:Michael Nielsen
89:gate operations
84:
28:
23:
22:
15:
12:
11:
5:
1790:
1780:
1779:
1774:
1769:
1752:
1751:
1749:
1748:
1738:
1727:
1724:
1723:
1721:
1720:
1718:many others...
1715:
1710:
1705:
1700:
1691:
1677:
1675:
1667:
1666:
1663:
1662:
1660:
1659:
1654:
1649:
1644:
1638:
1636:
1630:
1629:
1627:
1626:
1621:
1616:
1611:
1605:
1603:
1596:
1595:
1593:
1592:
1590:Trapped-ion QC
1587:
1581:
1579:
1573:
1572:
1570:
1569:
1564:
1559:
1554:
1548:
1546:
1544:Quantum optics
1537:
1531:
1530:
1528:
1527:
1522:
1521:
1520:
1513:
1508:
1503:
1498:
1493:
1488:
1483:
1474:
1472:
1464:
1463:
1461:
1460:
1455:
1450:
1449:
1448:
1438:
1437:
1436:
1426:
1425:
1424:
1414:
1409:
1403:
1401:
1393:
1392:
1390:
1389:
1388:
1387:
1383:
1377:
1373:
1362:
1361:
1360:
1350:
1348:Quantum volume
1345:
1339:
1337:
1331:
1330:
1328:
1327:
1322:
1317:
1312:
1307:
1301:
1299:
1291:
1290:
1288:
1287:
1282:
1277:
1272:
1267:
1262:
1257:
1252:
1247:
1242:
1237:
1232:
1227:
1225:Boson sampling
1222:
1217:
1211:
1209:
1203:
1202:
1199:
1198:
1196:
1195:
1190:
1189:
1188:
1183:
1178:
1168:
1163:
1158:
1152:
1150:
1141:
1140:
1135:
1134:
1133:
1123:
1122:
1121:
1111:
1106:
1101:
1096:
1095:
1094:
1089:
1078:
1076:
1070:
1069:
1067:
1066:
1061:
1059:Solovay–Kitaev
1056:
1051:
1046:
1041:
1036:
1031:
1026:
1021:
1016:
1011:
1006:
1001:
996:
991:
985:
983:
979:
978:
976:
975:
974:
973:
963:
962:
961:
951:
946:
941:
936:
935:
934:
924:
919:
913:
911:
907:
906:
899:
898:
891:
884:
876:
867:
866:
856:Scott Aaronson
853:
841:
840:External links
838:
835:
834:
765:
704:
672:
657:
628:
613:
583:
518:
466:
409:
397:
366:
365:
363:
360:
357:
356:
330:
329:
327:
324:
323:
322:
317:
312:
304:
301:
291:
288:
279:Scott Aaronson
245:
242:
237:
233:
230:
194:
191:
188:
185:
182:
179:
176:
172:
168:
165:
162:
159:
156:
153:
148:
144:
140:
137:
83:
80:
68:Wojciech Zurek
56:Dorit Aharanov
48:fault-tolerant
26:
9:
6:
4:
3:
2:
1789:
1778:
1775:
1773:
1770:
1768:
1765:
1764:
1762:
1747:
1739:
1737:
1729:
1728:
1725:
1719:
1716:
1714:
1711:
1709:
1706:
1704:
1701:
1699:
1695:
1692:
1690:
1686:
1682:
1679:
1678:
1676:
1674:
1668:
1658:
1655:
1653:
1650:
1648:
1645:
1643:
1640:
1639:
1637:
1635:
1631:
1625:
1622:
1620:
1617:
1615:
1614:Spin qubit QC
1612:
1610:
1607:
1606:
1604:
1601:
1597:
1591:
1588:
1586:
1583:
1582:
1580:
1578:
1574:
1568:
1565:
1563:
1560:
1558:
1555:
1553:
1550:
1549:
1547:
1545:
1541:
1538:
1532:
1526:
1523:
1519:
1518:
1514:
1512:
1509:
1507:
1504:
1502:
1499:
1497:
1494:
1492:
1489:
1487:
1484:
1482:
1479:
1478:
1476:
1475:
1473:
1471:
1465:
1459:
1456:
1454:
1451:
1447:
1444:
1443:
1442:
1439:
1435:
1432:
1431:
1430:
1427:
1423:
1422:cluster state
1420:
1419:
1418:
1415:
1413:
1410:
1408:
1405:
1404:
1402:
1400:
1394:
1386:
1382:
1378:
1376:
1372:
1368:
1367:
1366:
1363:
1359:
1356:
1355:
1354:
1351:
1349:
1346:
1344:
1341:
1340:
1338:
1332:
1326:
1323:
1321:
1318:
1316:
1313:
1311:
1308:
1306:
1303:
1302:
1300:
1298:
1292:
1286:
1283:
1281:
1278:
1276:
1273:
1271:
1268:
1266:
1263:
1261:
1258:
1256:
1253:
1251:
1248:
1246:
1243:
1241:
1238:
1236:
1233:
1231:
1230:Deutsch–Jozsa
1228:
1226:
1223:
1221:
1218:
1216:
1213:
1212:
1210:
1208:
1204:
1194:
1191:
1187:
1184:
1182:
1179:
1177:
1174:
1173:
1172:
1169:
1167:
1166:Quantum money
1164:
1162:
1159:
1157:
1154:
1153:
1151:
1149:
1145:
1139:
1136:
1132:
1129:
1128:
1127:
1124:
1120:
1117:
1116:
1115:
1112:
1110:
1107:
1105:
1102:
1100:
1097:
1093:
1090:
1088:
1085:
1084:
1083:
1080:
1079:
1077:
1075:communication
1071:
1065:
1062:
1060:
1057:
1055:
1052:
1050:
1047:
1045:
1042:
1040:
1037:
1035:
1032:
1030:
1027:
1025:
1022:
1020:
1017:
1015:
1012:
1010:
1007:
1005:
1002:
1000:
997:
995:
992:
990:
987:
986:
984:
980:
972:
969:
968:
967:
964:
960:
957:
956:
955:
952:
950:
947:
945:
942:
940:
937:
933:
930:
929:
928:
925:
923:
920:
918:
915:
914:
912:
908:
904:
897:
892:
890:
885:
883:
878:
877:
874:
870:
865:
861:
857:
854:
851:
847:
844:
843:
830:
826:
822:
818:
814:
810:
806:
802:
798:
794:
789:
784:
780:
776:
769:
761:
757:
753:
749:
745:
741:
737:
733:
728:
723:
720:(5): 052312.
719:
715:
708:
693:
692:
686:
682:
676:
668:
664:
660:
658:9780511992773
654:
650:
646:
643:(June 2012).
642:
638:
632:
624:
620:
616:
610:
606:
602:
598:
594:
587:
579:
575:
571:
567:
563:
559:
555:
551:
546:
541:
537:
533:
529:
522:
514:
510:
506:
502:
497:
492:
488:
484:
480:
473:
471:
462:
458:
454:
450:
446:
442:
437:
432:
428:
424:
420:
413:
400:
394:
390:
386:
382:
378:
371:
367:
353:
349:
345:
341:
335:
331:
321:
318:
316:
313:
310:
307:
306:
300:
297:
286:
282:
280:
275:
270:
266:
260:
235:
231:
228:
220:
216:
212:
208:
186:
180:
174:
170:
163:
157:
151:
146:
142:
135:
127:
123:
119:
115:
111:
109:
105:
101:
100:
93:
90:
79:
77:
73:
72:Alexei Kitaev
69:
65:
61:
60:Emanuel Knill
57:
53:
49:
45:
41:
37:
33:
19:
1642:Charge qubit
1567:KLM protocol
1516:
1380:
1370:
1064:Purification
1053:
994:Eastin–Knill
868:
863:
778:
774:
768:
717:
713:
707:
696:. Retrieved
688:
675:
644:
631:
596:
586:
535:
531:
521:
486:
482:
426:
422:
412:
402:, retrieved
380:
370:
334:
296:surface code
293:
284:
273:
264:
263:probability
261:
218:
214:
210:
206:
125:
121:
117:
113:
112:
108:Isaac Chuang
97:
94:
85:
39:
35:
29:
1673:programming
1652:Phase qubit
1557:Circuit QED
1029:No-deleting
971:cloud-based
538:(1): 2–30.
213:, provided
82:Explanation
52:von Neumann
1761:Categories
1713:libquantum
1647:Flux qubit
1552:Cavity QED
1501:Bacon–Shor
1491:stabilizer
1019:No-cloning
788:1612.07330
698:2018-12-27
404:2020-10-10
362:References
76:Peter Shor
1619:NV center
1054:Threshold
1034:No-hiding
999:Gleason's
846:Gil Kalai
813:0028-0836
760:119228385
752:1050-2947
727:0803.0272
689:PHYS771:
667:700706156
578:119087885
570:0003-4916
453:0097-5397
219:threshold
175:ε
152:
1681:OpenQASM
1657:Transmon
1534:Physical
1334:Quantum
1235:Grover's
1009:Holevo's
982:Theorems
932:timeline
922:NISQ era
821:28905902
303:See also
1671:Quantum
1609:Kane QC
1468:Quantum
1396:Quantum
1325:PostBQP
1295:Quantum
1280:Simon's
1073:Quantum
910:General
829:4446310
793:Bibcode
732:Bibcode
623:7508572
550:Bibcode
501:Bibcode
483:Science
461:8969800
311:schemes
267:), use
1689:IBM QX
1685:Qiskit
1624:NMR QC
1602:-based
1506:Steane
1477:Codes
1275:Shor's
1181:SARG04
989:Bell's
827:
819:
811:
775:Nature
758:
750:
665:
655:
621:
611:
576:
568:
459:
451:
395:
352:FeMoco
128:using
70:; and
66:, and
34:, the
1511:Toric
954:Qubit
825:S2CID
783:arXiv
756:S2CID
722:arXiv
619:S2CID
574:S2CID
540:arXiv
491:arXiv
457:S2CID
431:arXiv
326:Notes
102:, by
1703:Cirq
1694:Quil
1600:Spin
1496:Shor
1176:BB84
1109:LOCC
817:PMID
809:ISSN
748:ISSN
663:OCLC
653:ISBN
609:ISBN
566:ISSN
449:ISSN
393:ISBN
232:<
122:p(n)
106:and
38:(or
1517:gnu
1481:CSS
1358:XEB
1320:QMA
1315:QIP
1310:EQP
1305:BQP
1285:VQE
1240:HHL
1044:PBR
801:doi
779:549
740:doi
601:doi
558:doi
536:303
509:doi
487:279
441:doi
385:doi
143:log
30:In
1763::
1708:Q#
862::
858:.
848:.
823:.
815:.
807:.
799:.
791:.
777:.
754:.
746:.
738:.
730:.
718:80
716:.
687:.
661:.
651:.
639:;
617:.
607:.
595:.
572:.
564:.
556:.
548:.
534:.
530:.
507:.
499:.
485:.
481:.
469:^
455:.
447:.
439:.
427:38
425:.
421:.
391:,
379:,
221:,
62:,
1696:–
1687:–
1683:–
1384:2
1381:T
1374:1
1371:T
895:e
888:t
881:v
852:.
831:.
803::
795::
785::
762:.
742::
734::
724::
701:.
669:.
625:.
603::
580:.
560::
552::
542::
515:.
511::
503::
493::
463:.
443::
433::
387::
281::
274:p
265:p
244:h
241:t
236:p
229:p
215:p
211:p
207:c
193:)
190:)
187:n
184:(
181:p
178:)
171:/
167:)
164:n
161:(
158:p
155:(
147:c
139:(
136:O
126:ε
118:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.