20:
1974:
3521:
3511:
2371:
1606:
2033:
719:
1969:{\displaystyle |0\rangle ^{n}\xrightarrow {H^{\otimes n}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}|x\rangle \xrightarrow {U_{f}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)}|x\rangle \xrightarrow {H^{\otimes n}} {\frac {1}{2^{n}}}\sum _{x,y\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}|y\rangle =|s\rangle }
2495:
A generalization of
Bernstein–Vazirani problem has been proposed that involves finding one or more secret keys using a probabilistic oracle. This is an interesting problem for which a quantum algorithm can provide efficient solutions with certainty or with a high degree of confidence, while
2366:{\displaystyle {\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot s+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot (s\oplus y)}=1{\text{ if }}s\oplus y={\vec {0}},\,0{\text{ otherwise}}.}
506:
355:
1292:
914:
1093:
1157:
134:
1014:
714:{\displaystyle {\begin{aligned}f(1000\cdots 0_{n})&=s_{1}\\f(0100\cdots 0_{n})&=s_{2}\\f(0010\cdots 0_{n})&=s_{3}\\&\,\,\,\vdots \\f(0000\cdots 1_{n})&=s_{n}\\\end{aligned}}}
511:
46:
where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function. The
Bernstein–Vazirani algorithm was designed to prove an
1545:
827:
2415:
498:
236:
1578:
2469:
2005:
1473:
1445:
1384:
1356:
2607:
1417:
1328:
1177:
436:
2710:
944:
163:
2441:
2672:
2489:
2025:
1598:
1493:
789:
762:
742:
403:
375:
191:
244:
3402:
1185:
3303:
2964:
3555:
2865:
3190:
2621:
Alok Shukla and
Prakash Vedula (2023). "A generalization of Bernstein--Vazirani algorithm with multiple secret keys and a probabilistic oracle".
835:
1019:
3514:
2700:
1098:
3472:
3550:
3048:
3524:
3412:
2665:
3340:
3335:
3063:
3043:
2842:
3330:
2505:
76:
3363:
3185:
3088:
2749:
949:
3368:
3236:
2827:
2658:
3148:
3008:
2782:
43:
3545:
3392:
2737:
2681:
2837:
3264:
3136:
3033:
2909:
2744:
3073:
3038:
2934:
2877:
3158:
2772:
3246:
3219:
3195:
2949:
2882:
2817:
2802:
1502:
2695:
3397:
3131:
3023:
2993:
2792:
794:
3467:
3231:
3224:
2971:
2379:
441:
3387:
2939:
2904:
2601:
3013:
47:
19:
196:
3177:
2926:
2777:
3279:
3496:
3449:
3053:
2807:
2787:
2722:
2717:
1553:
3212:
2860:
2797:
2626:
2577:
768:
238:
3058:
2446:
1982:
1450:
1422:
1361:
1333:
385:
Classically, the most efficient method to find the secret string is by evaluating the function
3476:
3121:
3028:
2985:
2916:
2832:
2812:
2767:
2727:
2705:
2471:. So, measuring the output of the circuit in the computational basis yields the secret string
35:
1389:
1300:
1162:
408:
3143:
3093:
2870:
2636:
2587:
2541:
1297:
Another
Hadamard transform is applied to each qubit which makes it so that for qubits where
58:
51:
922:
3269:
3207:
2897:
2892:
764:, only one query is needed using quantum computing. The quantum algorithm is as follows:
166:
139:
2420:
350:{\displaystyle f(x)=x\cdot s=x_{1}s_{1}\oplus x_{2}s_{2}\oplus \cdots \oplus x_{n}s_{n}}
3378:
3355:
3322:
3126:
3003:
2529:
2474:
2010:
1583:
1496:
1478:
774:
747:
727:
388:
360:
176:
70:
39:
3539:
3200:
3018:
2944:
1287:{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle .}
3420:
3345:
2564:
S D Fallek, C D Herold, B J McMahon, K M Maller, K R Brown, and J M Amini (2016).
3430:
3284:
2822:
170:
2640:
2592:
2565:
2496:
classical algorithms completely fail to solve the problem in the general case.
3491:
3425:
3289:
2650:
2566:"Transport implementation of the Bernstein–Vazirani algorithm with ion qubits"
2545:
1550:
Graphically, the algorithm may be represented by the following diagram, where
3274:
909:{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle .}
3459:
3435:
3294:
3259:
3486:
3103:
1088:{\displaystyle |b\rangle |x\rangle \to |b\oplus f(x)\rangle |x\rangle }
3463:
2959:
1827:
1717:
1632:
1152:{\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}|x\rangle }
1016:. This can be simulated through the standard oracle that transforms
2631:
2582:
2732:
1179:
denotes addition mod two.) This transforms the superposition into
18:
3481:
2954:
2887:
2654:
3098:
3083:
54:
724:
In contrast to the classical solution which needs at least
129:{\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}
2477:
2449:
2423:
2382:
2036:
2013:
1985:
1609:
1586:
1556:
1505:
1481:
1453:
1425:
1392:
1364:
1336:
1303:
1188:
1165:
1101:
1022:
952:
925:
838:
797:
777:
750:
730:
509:
444:
411:
391:
363:
247:
199:
179:
142:
79:
2443:, this means that the only non-zero amplitude is on
3448:
3411:
3377:
3354:
3321:
3312:
3245:
3174:
3112:
3072:
2984:
2925:
2851:
2760:
2688:
1009:{\displaystyle |x\rangle \to (-1)^{f(x)}|x\rangle }
2483:
2463:
2435:
2409:
2365:
2019:
1999:
1968:
1592:
1572:
1539:
1487:
1467:
1439:
1411:
1378:
1350:
1322:
1286:
1171:
1151:
1087:
1008:
938:
908:
821:
783:
756:
736:
713:
492:
430:
397:
369:
349:
230:
185:
157:
128:
2666:
8:
2606:: CS1 maint: multiple names: authors list (
2458:
2265:
2252:
2173:
2160:
2078:
2065:
1994:
1963:
1949:
1890:
1877:
1820:
1773:
1760:
1710:
1691:
1678:
1619:
1534:
1531:
1517:
1506:
1462:
1434:
1373:
1345:
1278:
1146:
1127:
1113:
1082:
1071:
1042:
1031:
1003:
961:
900:
807:
487:
451:
219:
206:
123:
111:
99:
86:
2559:
2557:
2555:
42:in 1997. It is a restricted version of the
3318:
2922:
2673:
2659:
2651:
2630:
2591:
2581:
2476:
2450:
2448:
2422:
2396:
2395:
2381:
2355:
2351:
2337:
2336:
2319:
2289:
2268:
2245:
2233:
2224:
2197:
2176:
2153:
2141:
2132:
2102:
2081:
2058:
2046:
2037:
2035:
2012:
1986:
1984:
1955:
1941:
1914:
1893:
1864:
1852:
1843:
1832:
1812:
1797:
1776:
1753:
1740:
1730:
1722:
1702:
1694:
1671:
1658:
1648:
1637:
1622:
1610:
1608:
1585:
1561:
1555:
1540:{\displaystyle \{|0\rangle ,|1\rangle \}}
1523:
1509:
1504:
1480:
1454:
1452:
1426:
1424:
1397:
1391:
1365:
1363:
1337:
1335:
1308:
1302:
1270:
1255:
1228:
1223:
1212:
1199:
1189:
1187:
1164:
1138:
1119:
1105:
1102:
1100:
1074:
1048:
1034:
1023:
1021:
995:
980:
953:
951:
930:
924:
892:
878:
873:
862:
849:
839:
837:
810:
798:
796:
776:
749:
729:
701:
681:
657:
656:
655:
642:
622:
596:
576:
550:
530:
510:
508:
443:
422:
410:
390:
362:
341:
331:
312:
302:
289:
279:
246:
222:
198:
178:
141:
102:
78:
3191:Continuous-variable quantum information
2517:
2599:
2523:
2521:
822:{\displaystyle |0\rangle ^{\otimes n}}
2532:(1997). "Quantum Complexity Theory".
7:
2410:{\displaystyle s\oplus y={\vec {0}}}
493:{\displaystyle i\in \{0,1,...,n-1\}}
1979:The reason that the last state is
1580:denotes the Hadamard transform on
14:
3520:
3519:
3510:
3509:
744:queries of the function to find
231:{\displaystyle s\in \{0,1\}^{n}}
38:invented by Ethan Bernstein and
3556:Computational complexity theory
2623:Quantum Information Processing
2506:Hidden Linear Function problem
2451:
2401:
2342:
2308:
2296:
2286:
2276:
2194:
2184:
2112:
2106:
2099:
2089:
1987:
1956:
1942:
1924:
1918:
1911:
1901:
1813:
1807:
1801:
1794:
1784:
1703:
1611:
1547:) is performed on the qubits.
1524:
1510:
1455:
1427:
1419:, its state is converted from
1366:
1338:
1330:, its state is converted from
1271:
1265:
1259:
1252:
1242:
1139:
1120:
1106:
1075:
1068:
1062:
1049:
1045:
1035:
1024:
996:
990:
984:
977:
967:
964:
954:
893:
799:
687:
668:
628:
609:
582:
563:
536:
517:
257:
251:
152:
146:
108:
1:
3186:Adiabatic quantum computation
2007:is because, for a particular
1573:{\displaystyle H^{\otimes n}}
3237:Topological quantum computer
405:times with the input values
28:Bernstein–Vazirani algorithm
3515:Quantum information science
2682:Quantum information science
1095:by applying this oracle to
73:that implements a function
3572:
2910:quantum gate teleportation
2641:10.1007/s11128-023-03978-3
2464:{\displaystyle |s\rangle }
2000:{\displaystyle |s\rangle }
1468:{\displaystyle |0\rangle }
1440:{\displaystyle |+\rangle }
1379:{\displaystyle |1\rangle }
1351:{\displaystyle |-\rangle }
32:Bernstein–Vazirani problem
3551:Quantum complexity theory
3505:
3039:Quantum Fourier transform
2935:Post-quantum cryptography
2878:Entanglement distillation
2546:10.1137/S0097539796300921
2534:SIAM Journal on Computing
3525:Quantum mechanics topics
3220:Quantum machine learning
3196:One-way quantum computer
3049:Quantum phase estimation
2950:Quantum key distribution
2883:Monogamy of entanglement
2593:10.1088/1367-2630/aab341
3132:Randomized benchmarking
2994:Amplitude amplification
1495:, a measurement in the
1412:{\displaystyle s_{i}=0}
1323:{\displaystyle s_{i}=1}
1172:{\displaystyle \oplus }
919:Next, apply the oracle
431:{\displaystyle x=2^{i}}
44:Deutsch–Jozsa algorithm
3232:Quantum Turing machine
3225:quantum neural network
2972:Quantum secret sharing
2570:New Journal of Physics
2485:
2465:
2437:
2411:
2367:
2021:
2001:
1970:
1594:
1574:
1541:
1489:
1469:
1441:
1413:
1380:
1352:
1324:
1288:
1241:
1173:
1153:
1089:
1010:
940:
910:
891:
823:
785:
758:
738:
715:
494:
432:
399:
371:
351:
232:
187:
159:
130:
23:
3304:Entanglement-assisted
3265:quantum convolutional
2940:Quantum coin flipping
2905:Quantum teleportation
2866:entanglement-assisted
2696:DiVincenzo's criteria
2486:
2466:
2438:
2412:
2368:
2022:
2002:
1971:
1595:
1575:
1542:
1490:
1470:
1442:
1414:
1386:and for qubits where
1381:
1353:
1325:
1289:
1208:
1174:
1154:
1090:
1011:
941:
939:{\displaystyle U_{f}}
911:
858:
824:
786:
759:
739:
716:
495:
433:
400:
372:
352:
233:
188:
160:
131:
22:
3115:processor benchmarks
3044:Quantum optimization
2927:Quantum cryptography
2738:physical vs. logical
2625:. 22:244 (6): 1–18.
2528:Ethan Bernstein and
2475:
2447:
2421:
2380:
2034:
2011:
1983:
1607:
1584:
1554:
1503:
1479:
1451:
1423:
1390:
1362:
1334:
1301:
1186:
1163:
1099:
1020:
950:
923:
836:
795:
775:
748:
728:
507:
442:
409:
389:
361:
245:
197:
193:and a secret string
177:
158:{\displaystyle f(x)}
140:
77:
2828:Quantum speed limit
2723:Quantum programming
2718:Quantum information
2436:{\displaystyle s=y}
1841:
1728:
1646:
30:, which solves the
3546:Quantum algorithms
3477:Forest/Rigetti QCS
3213:quantum logic gate
2999:Bernstein–Vazirani
2986:Quantum algorithms
2861:Classical capacity
2745:Quantum processors
2728:Quantum simulation
2481:
2461:
2433:
2417:is only true when
2407:
2363:
2275:
2183:
2088:
2017:
1997:
1966:
1900:
1783:
1701:
1590:
1570:
1537:
1485:
1465:
1437:
1409:
1376:
1348:
1320:
1284:
1169:
1149:
1085:
1006:
936:
906:
819:
781:
769:Hadamard transform
754:
734:
711:
709:
490:
428:
395:
367:
347:
228:
183:
155:
126:
52:complexity classes
24:
3533:
3532:
3444:
3443:
3341:Linear optical QC
3122:Quantum supremacy
3076:complexity theory
3029:Quantum annealing
2980:
2979:
2917:Superdense coding
2706:Quantum computing
2484:{\displaystyle s}
2404:
2358:
2345:
2322:
2241:
2239:
2149:
2147:
2054:
2052:
2020:{\displaystyle y}
1860:
1858:
1842:
1749:
1747:
1746:
1729:
1667:
1665:
1664:
1647:
1593:{\displaystyle n}
1488:{\displaystyle s}
1206:
1205:
1136:
1135:
946:which transforms
856:
855:
784:{\displaystyle n}
757:{\displaystyle s}
737:{\displaystyle n}
398:{\displaystyle n}
370:{\displaystyle s}
186:{\displaystyle x}
65:Problem statement
48:oracle separation
36:quantum algorithm
16:Quantum algorithm
3563:
3523:
3522:
3513:
3512:
3319:
3249:error correction
3178:computing models
3144:Relaxation times
3034:Quantum counting
2923:
2871:quantum capacity
2818:No-teleportation
2803:No-communication
2675:
2668:
2661:
2652:
2645:
2644:
2634:
2618:
2612:
2611:
2605:
2597:
2595:
2585:
2561:
2550:
2549:
2540:(5): 1411–1473.
2525:
2490:
2488:
2487:
2482:
2470:
2468:
2467:
2462:
2454:
2442:
2440:
2439:
2434:
2416:
2414:
2413:
2408:
2406:
2405:
2397:
2372:
2370:
2369:
2364:
2359:
2356:
2347:
2346:
2338:
2323:
2320:
2312:
2311:
2274:
2273:
2272:
2240:
2238:
2237:
2225:
2220:
2219:
2182:
2181:
2180:
2148:
2146:
2145:
2133:
2128:
2127:
2087:
2086:
2085:
2053:
2051:
2050:
2038:
2026:
2024:
2023:
2018:
2006:
2004:
2003:
1998:
1990:
1975:
1973:
1972:
1967:
1959:
1945:
1940:
1939:
1899:
1898:
1897:
1859:
1857:
1856:
1844:
1840:
1839:
1823:
1816:
1811:
1810:
1782:
1781:
1780:
1748:
1745:
1744:
1735:
1731:
1727:
1726:
1713:
1706:
1700:
1699:
1698:
1666:
1663:
1662:
1653:
1649:
1645:
1644:
1628:
1627:
1626:
1614:
1599:
1597:
1596:
1591:
1579:
1577:
1576:
1571:
1569:
1568:
1546:
1544:
1543:
1538:
1527:
1513:
1494:
1492:
1491:
1486:
1474:
1472:
1471:
1466:
1458:
1446:
1444:
1443:
1438:
1430:
1418:
1416:
1415:
1410:
1402:
1401:
1385:
1383:
1382:
1377:
1369:
1357:
1355:
1354:
1349:
1341:
1329:
1327:
1326:
1321:
1313:
1312:
1293:
1291:
1290:
1285:
1274:
1269:
1268:
1240:
1233:
1232:
1222:
1207:
1204:
1203:
1194:
1190:
1178:
1176:
1175:
1170:
1158:
1156:
1155:
1150:
1142:
1137:
1131:
1130:
1123:
1109:
1103:
1094:
1092:
1091:
1086:
1078:
1052:
1038:
1027:
1015:
1013:
1012:
1007:
999:
994:
993:
957:
945:
943:
942:
937:
935:
934:
915:
913:
912:
907:
896:
890:
883:
882:
872:
857:
854:
853:
844:
840:
828:
826:
825:
820:
818:
817:
802:
790:
788:
787:
782:
763:
761:
760:
755:
743:
741:
740:
735:
720:
718:
717:
712:
710:
706:
705:
686:
685:
651:
647:
646:
627:
626:
601:
600:
581:
580:
555:
554:
535:
534:
499:
497:
496:
491:
437:
435:
434:
429:
427:
426:
404:
402:
401:
396:
376:
374:
373:
368:
356:
354:
353:
348:
346:
345:
336:
335:
317:
316:
307:
306:
294:
293:
284:
283:
237:
235:
234:
229:
227:
226:
192:
190:
189:
184:
164:
162:
161:
156:
135:
133:
132:
127:
107:
106:
3571:
3570:
3566:
3565:
3564:
3562:
3561:
3560:
3536:
3535:
3534:
3529:
3501:
3451:
3440:
3413:Superconducting
3407:
3373:
3364:Neutral atom QC
3356:Ultracold atoms
3350:
3315:implementations
3314:
3308:
3248:
3241:
3208:Quantum circuit
3176:
3170:
3164:
3154:
3114:
3108:
3075:
3068:
3024:Hidden subgroup
2976:
2965:other protocols
2921:
2898:quantum network
2893:Quantum channel
2853:
2847:
2793:No-broadcasting
2783:Gottesman–Knill
2756:
2684:
2679:
2649:
2648:
2620:
2619:
2615:
2598:
2563:
2562:
2553:
2527:
2526:
2519:
2514:
2502:
2494:
2473:
2472:
2445:
2444:
2419:
2418:
2378:
2377:
2357: otherwise
2285:
2264:
2229:
2193:
2172:
2137:
2098:
2077:
2042:
2032:
2031:
2009:
2008:
1981:
1980:
1910:
1889:
1848:
1828:
1793:
1772:
1736:
1718:
1690:
1654:
1633:
1618:
1605:
1604:
1582:
1581:
1557:
1552:
1551:
1501:
1500:
1477:
1476:
1449:
1448:
1421:
1420:
1393:
1388:
1387:
1360:
1359:
1332:
1331:
1304:
1299:
1298:
1251:
1224:
1195:
1184:
1183:
1161:
1160:
1104:
1097:
1096:
1018:
1017:
976:
948:
947:
926:
921:
920:
874:
845:
834:
833:
806:
793:
792:
773:
772:
746:
745:
726:
725:
708:
707:
697:
690:
677:
662:
661:
649:
648:
638:
631:
618:
603:
602:
592:
585:
572:
557:
556:
546:
539:
526:
505:
504:
440:
439:
418:
407:
406:
387:
386:
383:
359:
358:
337:
327:
308:
298:
285:
275:
243:
242:
218:
195:
194:
175:
174:
138:
137:
98:
75:
74:
67:
17:
12:
11:
5:
3569:
3567:
3559:
3558:
3553:
3548:
3538:
3537:
3531:
3530:
3528:
3527:
3517:
3506:
3503:
3502:
3500:
3499:
3497:many others...
3494:
3489:
3484:
3479:
3470:
3456:
3454:
3446:
3445:
3442:
3441:
3439:
3438:
3433:
3428:
3423:
3417:
3415:
3409:
3408:
3406:
3405:
3400:
3395:
3390:
3384:
3382:
3375:
3374:
3372:
3371:
3369:Trapped-ion QC
3366:
3360:
3358:
3352:
3351:
3349:
3348:
3343:
3338:
3333:
3327:
3325:
3323:Quantum optics
3316:
3310:
3309:
3307:
3306:
3301:
3300:
3299:
3292:
3287:
3282:
3277:
3272:
3267:
3262:
3253:
3251:
3243:
3242:
3240:
3239:
3234:
3229:
3228:
3227:
3217:
3216:
3215:
3205:
3204:
3203:
3193:
3188:
3182:
3180:
3172:
3171:
3169:
3168:
3167:
3166:
3162:
3156:
3152:
3141:
3140:
3139:
3129:
3127:Quantum volume
3124:
3118:
3116:
3110:
3109:
3107:
3106:
3101:
3096:
3091:
3086:
3080:
3078:
3070:
3069:
3067:
3066:
3061:
3056:
3051:
3046:
3041:
3036:
3031:
3026:
3021:
3016:
3011:
3006:
3004:Boson sampling
3001:
2996:
2990:
2988:
2982:
2981:
2978:
2977:
2975:
2974:
2969:
2968:
2967:
2962:
2957:
2947:
2942:
2937:
2931:
2929:
2920:
2919:
2914:
2913:
2912:
2902:
2901:
2900:
2890:
2885:
2880:
2875:
2874:
2873:
2868:
2857:
2855:
2849:
2848:
2846:
2845:
2840:
2838:Solovay–Kitaev
2835:
2830:
2825:
2820:
2815:
2810:
2805:
2800:
2795:
2790:
2785:
2780:
2775:
2770:
2764:
2762:
2758:
2757:
2755:
2754:
2753:
2752:
2742:
2741:
2740:
2730:
2725:
2720:
2715:
2714:
2713:
2703:
2698:
2692:
2690:
2686:
2685:
2680:
2678:
2677:
2670:
2663:
2655:
2647:
2646:
2613:
2551:
2530:Umesh Vazirani
2516:
2515:
2513:
2510:
2509:
2508:
2501:
2498:
2480:
2460:
2457:
2453:
2432:
2429:
2426:
2403:
2400:
2394:
2391:
2388:
2385:
2374:
2373:
2362:
2354:
2350:
2344:
2341:
2335:
2332:
2329:
2326:
2321: if
2318:
2315:
2310:
2307:
2304:
2301:
2298:
2295:
2292:
2288:
2284:
2281:
2278:
2271:
2267:
2263:
2260:
2257:
2254:
2251:
2248:
2244:
2236:
2232:
2228:
2223:
2218:
2215:
2212:
2209:
2206:
2203:
2200:
2196:
2192:
2189:
2186:
2179:
2175:
2171:
2168:
2165:
2162:
2159:
2156:
2152:
2144:
2140:
2136:
2131:
2126:
2123:
2120:
2117:
2114:
2111:
2108:
2105:
2101:
2097:
2094:
2091:
2084:
2080:
2076:
2073:
2070:
2067:
2064:
2061:
2057:
2049:
2045:
2041:
2016:
1996:
1993:
1989:
1977:
1976:
1965:
1962:
1958:
1954:
1951:
1948:
1944:
1938:
1935:
1932:
1929:
1926:
1923:
1920:
1917:
1913:
1909:
1906:
1903:
1896:
1892:
1888:
1885:
1882:
1879:
1876:
1873:
1870:
1867:
1863:
1855:
1851:
1847:
1838:
1835:
1831:
1826:
1822:
1819:
1815:
1809:
1806:
1803:
1800:
1796:
1792:
1789:
1786:
1779:
1775:
1771:
1768:
1765:
1762:
1759:
1756:
1752:
1743:
1739:
1734:
1725:
1721:
1716:
1712:
1709:
1705:
1697:
1693:
1689:
1686:
1683:
1680:
1677:
1674:
1670:
1661:
1657:
1652:
1643:
1640:
1636:
1631:
1625:
1621:
1617:
1613:
1589:
1567:
1564:
1560:
1536:
1533:
1530:
1526:
1522:
1519:
1516:
1512:
1508:
1497:standard basis
1484:
1464:
1461:
1457:
1436:
1433:
1429:
1408:
1405:
1400:
1396:
1375:
1372:
1368:
1347:
1344:
1340:
1319:
1316:
1311:
1307:
1295:
1294:
1283:
1280:
1277:
1273:
1267:
1264:
1261:
1258:
1254:
1250:
1247:
1244:
1239:
1236:
1231:
1227:
1221:
1218:
1215:
1211:
1202:
1198:
1193:
1168:
1148:
1145:
1141:
1134:
1129:
1126:
1122:
1118:
1115:
1112:
1108:
1084:
1081:
1077:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1051:
1047:
1044:
1041:
1037:
1033:
1030:
1026:
1005:
1002:
998:
992:
989:
986:
983:
979:
975:
972:
969:
966:
963:
960:
956:
933:
929:
917:
916:
905:
902:
899:
895:
889:
886:
881:
877:
871:
868:
865:
861:
852:
848:
843:
816:
813:
809:
805:
801:
780:
753:
733:
722:
721:
704:
700:
696:
693:
691:
689:
684:
680:
676:
673:
670:
667:
664:
663:
660:
654:
652:
650:
645:
641:
637:
634:
632:
630:
625:
621:
617:
614:
611:
608:
605:
604:
599:
595:
591:
588:
586:
584:
579:
575:
571:
568:
565:
562:
559:
558:
553:
549:
545:
542:
540:
538:
533:
529:
525:
522:
519:
516:
513:
512:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
425:
421:
417:
414:
394:
382:
379:
366:
344:
340:
334:
330:
326:
323:
320:
315:
311:
305:
301:
297:
292:
288:
282:
278:
274:
271:
268:
265:
262:
259:
256:
253:
250:
225:
221:
217:
214:
211:
208:
205:
202:
182:
154:
151:
148:
145:
125:
122:
119:
116:
113:
110:
105:
101:
97:
94:
91:
88:
85:
82:
66:
63:
40:Umesh Vazirani
15:
13:
10:
9:
6:
4:
3:
2:
3568:
3557:
3554:
3552:
3549:
3547:
3544:
3543:
3541:
3526:
3518:
3516:
3508:
3507:
3504:
3498:
3495:
3493:
3490:
3488:
3485:
3483:
3480:
3478:
3474:
3471:
3469:
3465:
3461:
3458:
3457:
3455:
3453:
3447:
3437:
3434:
3432:
3429:
3427:
3424:
3422:
3419:
3418:
3416:
3414:
3410:
3404:
3401:
3399:
3396:
3394:
3393:Spin qubit QC
3391:
3389:
3386:
3385:
3383:
3380:
3376:
3370:
3367:
3365:
3362:
3361:
3359:
3357:
3353:
3347:
3344:
3342:
3339:
3337:
3334:
3332:
3329:
3328:
3326:
3324:
3320:
3317:
3311:
3305:
3302:
3298:
3297:
3293:
3291:
3288:
3286:
3283:
3281:
3278:
3276:
3273:
3271:
3268:
3266:
3263:
3261:
3258:
3257:
3255:
3254:
3252:
3250:
3244:
3238:
3235:
3233:
3230:
3226:
3223:
3222:
3221:
3218:
3214:
3211:
3210:
3209:
3206:
3202:
3201:cluster state
3199:
3198:
3197:
3194:
3192:
3189:
3187:
3184:
3183:
3181:
3179:
3173:
3165:
3161:
3157:
3155:
3151:
3147:
3146:
3145:
3142:
3138:
3135:
3134:
3133:
3130:
3128:
3125:
3123:
3120:
3119:
3117:
3111:
3105:
3102:
3100:
3097:
3095:
3092:
3090:
3087:
3085:
3082:
3081:
3079:
3077:
3071:
3065:
3062:
3060:
3057:
3055:
3052:
3050:
3047:
3045:
3042:
3040:
3037:
3035:
3032:
3030:
3027:
3025:
3022:
3020:
3017:
3015:
3012:
3010:
3009:Deutsch–Jozsa
3007:
3005:
3002:
3000:
2997:
2995:
2992:
2991:
2989:
2987:
2983:
2973:
2970:
2966:
2963:
2961:
2958:
2956:
2953:
2952:
2951:
2948:
2946:
2945:Quantum money
2943:
2941:
2938:
2936:
2933:
2932:
2930:
2928:
2924:
2918:
2915:
2911:
2908:
2907:
2906:
2903:
2899:
2896:
2895:
2894:
2891:
2889:
2886:
2884:
2881:
2879:
2876:
2872:
2869:
2867:
2864:
2863:
2862:
2859:
2858:
2856:
2854:communication
2850:
2844:
2841:
2839:
2836:
2834:
2831:
2829:
2826:
2824:
2821:
2819:
2816:
2814:
2811:
2809:
2806:
2804:
2801:
2799:
2796:
2794:
2791:
2789:
2786:
2784:
2781:
2779:
2776:
2774:
2771:
2769:
2766:
2765:
2763:
2759:
2751:
2748:
2747:
2746:
2743:
2739:
2736:
2735:
2734:
2731:
2729:
2726:
2724:
2721:
2719:
2716:
2712:
2709:
2708:
2707:
2704:
2702:
2699:
2697:
2694:
2693:
2691:
2687:
2683:
2676:
2671:
2669:
2664:
2662:
2657:
2656:
2653:
2642:
2638:
2633:
2628:
2624:
2617:
2614:
2609:
2603:
2594:
2589:
2584:
2579:
2575:
2571:
2567:
2560:
2558:
2556:
2552:
2547:
2543:
2539:
2535:
2531:
2524:
2522:
2518:
2511:
2507:
2504:
2503:
2499:
2497:
2492:
2478:
2455:
2430:
2427:
2424:
2398:
2392:
2389:
2386:
2383:
2360:
2352:
2348:
2339:
2333:
2330:
2327:
2324:
2316:
2313:
2305:
2302:
2299:
2293:
2290:
2282:
2279:
2269:
2261:
2258:
2255:
2249:
2246:
2242:
2234:
2230:
2226:
2221:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2190:
2187:
2177:
2169:
2166:
2163:
2157:
2154:
2150:
2142:
2138:
2134:
2129:
2124:
2121:
2118:
2115:
2109:
2103:
2095:
2092:
2082:
2074:
2071:
2068:
2062:
2059:
2055:
2047:
2043:
2039:
2030:
2029:
2028:
2014:
1991:
1960:
1952:
1946:
1936:
1933:
1930:
1927:
1921:
1915:
1907:
1904:
1894:
1886:
1883:
1880:
1874:
1871:
1868:
1865:
1861:
1853:
1849:
1845:
1836:
1833:
1829:
1824:
1817:
1804:
1798:
1790:
1787:
1777:
1769:
1766:
1763:
1757:
1754:
1750:
1741:
1737:
1732:
1723:
1719:
1714:
1707:
1695:
1687:
1684:
1681:
1675:
1672:
1668:
1659:
1655:
1650:
1641:
1638:
1634:
1629:
1623:
1615:
1603:
1602:
1601:
1587:
1565:
1562:
1558:
1548:
1528:
1520:
1514:
1498:
1482:
1459:
1431:
1406:
1403:
1398:
1394:
1370:
1342:
1317:
1314:
1309:
1305:
1281:
1275:
1262:
1256:
1248:
1245:
1237:
1234:
1229:
1225:
1219:
1216:
1213:
1209:
1200:
1196:
1191:
1182:
1181:
1180:
1166:
1143:
1132:
1124:
1116:
1110:
1079:
1065:
1059:
1056:
1053:
1039:
1028:
1000:
987:
981:
973:
970:
958:
931:
927:
903:
897:
887:
884:
879:
875:
869:
866:
863:
859:
850:
846:
841:
832:
831:
830:
814:
811:
803:
778:
770:
765:
751:
731:
702:
698:
694:
692:
682:
678:
674:
671:
665:
658:
653:
643:
639:
635:
633:
623:
619:
615:
612:
606:
597:
593:
589:
587:
577:
573:
569:
566:
560:
551:
547:
543:
541:
531:
527:
523:
520:
514:
503:
502:
501:
484:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
448:
445:
423:
419:
415:
412:
392:
380:
378:
364:
342:
338:
332:
328:
324:
321:
318:
313:
309:
303:
299:
295:
290:
286:
280:
276:
272:
269:
266:
263:
260:
254:
248:
240:
223:
215:
212:
209:
203:
200:
180:
172:
168:
149:
143:
120:
117:
114:
103:
95:
92:
89:
83:
80:
72:
64:
62:
60:
56:
53:
49:
45:
41:
37:
33:
29:
21:
3421:Charge qubit
3346:KLM protocol
3295:
3159:
3149:
2998:
2843:Purification
2773:Eastin–Knill
2622:
2616:
2602:cite journal
2573:
2569:
2537:
2533:
2493:
2375:
1978:
1549:
1475:. To obtain
1296:
918:
791:qubit state
766:
723:
384:
68:
31:
27:
25:
3452:programming
3431:Phase qubit
3336:Circuit QED
2808:No-deleting
2750:cloud-based
171:dot product
3540:Categories
3492:libquantum
3426:Flux qubit
3331:Cavity QED
3280:Bacon–Shor
3270:stabilizer
2798:No-cloning
2632:2301.10014
2583:1710.01378
2512:References
169:to be the
3398:NV center
2833:Threshold
2813:No-hiding
2778:Gleason's
2459:⟩
2402:→
2387:⊕
2343:→
2328:⊕
2303:⊕
2294:⋅
2280:−
2250:∈
2243:∑
2214:⋅
2202:⋅
2188:−
2158:∈
2151:∑
2122:⋅
2093:−
2063:∈
2056:∑
1995:⟩
1964:⟩
1950:⟩
1934:⋅
1905:−
1875:∈
1862:∑
1834:⊗
1821:⟩
1788:−
1758:∈
1751:∑
1711:⟩
1676:∈
1669:∑
1639:⊗
1620:⟩
1563:⊗
1532:⟩
1518:⟩
1463:⟩
1435:⟩
1374:⟩
1346:⟩
1343:−
1279:⟩
1246:−
1235:−
1210:∑
1167:⊕
1147:⟩
1128:⟩
1117:−
1114:⟩
1083:⟩
1072:⟩
1057:⊕
1046:→
1043:⟩
1032:⟩
1004:⟩
971:−
965:→
962:⟩
901:⟩
885:−
860:∑
812:⊗
808:⟩
675:⋯
659:⋮
616:⋯
570:⋯
524:⋯
482:−
449:∈
381:Algorithm
325:⊕
322:⋯
319:⊕
296:⊕
267:⋅
204:∈
136:in which
109:→
84::
69:Given an
3460:OpenQASM
3436:Transmon
3313:Physical
3113:Quantum
3014:Grover's
2788:Holevo's
2761:Theorems
2711:timeline
2701:NISQ era
2500:See also
1825:→
1715:→
1630:→
1600:qubits:
829:to get
767:Apply a
438:for all
173:between
167:promised
50:between
34:, is a
3450:Quantum
3388:Kane QC
3247:Quantum
3175:Quantum
3104:PostBQP
3074:Quantum
3059:Simon's
2852:Quantum
2689:General
771:to the
357:, find
3468:IBM QX
3464:Qiskit
3403:NMR QC
3381:-based
3285:Steane
3256:Codes
3054:Shor's
2960:SARG04
2768:Bell's
2376:Since
239:modulo
71:oracle
3290:Toric
2733:Qubit
2627:arXiv
2578:arXiv
3482:Cirq
3473:Quil
3379:Spin
3275:Shor
2955:BB84
2888:LOCC
2608:link
672:0000
613:0010
567:0100
521:1000
57:and
26:The
3296:gnu
3260:CSS
3137:XEB
3099:QMA
3094:QIP
3089:EQP
3084:BQP
3064:VQE
3019:HHL
2823:PBR
2637:doi
2588:doi
2542:doi
1447:to
1358:to
1159:. (
500::
241:2,
165:is
59:BPP
55:BQP
3542::
3487:Q#
2635:.
2604:}}
2600:{{
2586:.
2576:.
2574:18
2572:.
2568:.
2554:^
2538:26
2536:.
2520:^
2491:.
2027:,
377:.
61:.
3475:–
3466:–
3462:–
3163:2
3160:T
3153:1
3150:T
2674:e
2667:t
2660:v
2643:.
2639::
2629::
2610:)
2596:.
2590::
2580::
2548:.
2544::
2479:s
2456:s
2452:|
2431:y
2428:=
2425:s
2399:0
2393:=
2390:y
2384:s
2361:.
2353:0
2349:,
2340:0
2334:=
2331:y
2325:s
2317:1
2314:=
2309:)
2306:y
2300:s
2297:(
2291:x
2287:)
2283:1
2277:(
2270:n
2266:}
2262:1
2259:,
2256:0
2253:{
2247:x
2235:n
2231:2
2227:1
2222:=
2217:y
2211:x
2208:+
2205:s
2199:x
2195:)
2191:1
2185:(
2178:n
2174:}
2170:1
2167:,
2164:0
2161:{
2155:x
2143:n
2139:2
2135:1
2130:=
2125:y
2119:x
2116:+
2113:)
2110:x
2107:(
2104:f
2100:)
2096:1
2090:(
2083:n
2079:}
2075:1
2072:,
2069:0
2066:{
2060:x
2048:n
2044:2
2040:1
2015:y
1992:s
1988:|
1961:s
1957:|
1953:=
1947:y
1943:|
1937:y
1931:x
1928:+
1925:)
1922:x
1919:(
1916:f
1912:)
1908:1
1902:(
1895:n
1891:}
1887:1
1884:,
1881:0
1878:{
1872:y
1869:,
1866:x
1854:n
1850:2
1846:1
1837:n
1830:H
1818:x
1814:|
1808:)
1805:x
1802:(
1799:f
1795:)
1791:1
1785:(
1778:n
1774:}
1770:1
1767:,
1764:0
1761:{
1755:x
1742:n
1738:2
1733:1
1724:f
1720:U
1708:x
1704:|
1696:n
1692:}
1688:1
1685:,
1682:0
1679:{
1673:x
1660:n
1656:2
1651:1
1642:n
1635:H
1624:n
1616:0
1612:|
1588:n
1566:n
1559:H
1535:}
1529:1
1525:|
1521:,
1515:0
1511:|
1507:{
1499:(
1483:s
1460:0
1456:|
1432:+
1428:|
1407:0
1404:=
1399:i
1395:s
1371:1
1367:|
1339:|
1318:1
1315:=
1310:i
1306:s
1282:.
1276:x
1272:|
1266:)
1263:x
1260:(
1257:f
1253:)
1249:1
1243:(
1238:1
1230:n
1226:2
1220:0
1217:=
1214:x
1201:n
1197:2
1192:1
1144:x
1140:|
1133:2
1125:1
1121:|
1111:0
1107:|
1080:x
1076:|
1069:)
1066:x
1063:(
1060:f
1054:b
1050:|
1040:x
1036:|
1029:b
1025:|
1001:x
997:|
991:)
988:x
985:(
982:f
978:)
974:1
968:(
959:x
955:|
932:f
928:U
904:.
898:x
894:|
888:1
880:n
876:2
870:0
867:=
864:x
851:n
847:2
842:1
815:n
804:0
800:|
779:n
752:s
732:n
703:n
699:s
695:=
688:)
683:n
679:1
669:(
666:f
644:3
640:s
636:=
629:)
624:n
620:0
610:(
607:f
598:2
594:s
590:=
583:)
578:n
574:0
564:(
561:f
552:1
548:s
544:=
537:)
532:n
528:0
518:(
515:f
488:}
485:1
479:n
476:,
473:.
470:.
467:.
464:,
461:1
458:,
455:0
452:{
446:i
424:i
420:2
416:=
413:x
393:n
365:s
343:n
339:s
333:n
329:x
314:2
310:s
304:2
300:x
291:1
287:s
281:1
277:x
273:=
270:s
264:x
261:=
258:)
255:x
252:(
249:f
224:n
220:}
216:1
213:,
210:0
207:{
201:s
181:x
153:)
150:x
147:(
144:f
124:}
121:1
118:,
115:0
112:{
104:n
100:}
96:1
93:,
90:0
87:{
81:f
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
