Knowledge (XXG)

Hidden linear function problem

Source đź“ť

2418: 2408: 778: 599: 1134: 1340: 610: 1206: 904: 399: 407: 244: 1484:
Watts, Adam Bene; Kothari, Robin; Schaeffer, Luke; Tal, Avishay (June 2019). "Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits".
821: 317: 190: 1004: 1375: 277: 109: 140: 1607: 1231: 1569: 1395: 995: 975: 955: 927: 341: 2299: 2200: 1861: 773:{\displaystyle {\mathcal {L}}_{q}={\Big \{}x\in \mathbb {F} _{2}^{n}:q(x\oplus y)=(q(x)+q(y)){\bmod {4}}~~\forall y\in \mathbb {F} _{2}^{n}{\Big \}}.} 2452: 1762: 2087: 2411: 1597: 2369: 1489: 47:(2D HLF), the hidden function is explicitly specified by a matrix and a binary vector. 2D HLF can be solved exactly by a constant-depth 1142: 2447: 1945: 2421: 2309: 1562: 1515: 829: 1895: 36: 2237: 349: 2232: 1960: 1940: 1739: 2227: 1542: 594:{\displaystyle q(x)=(2x^{T}Ax+b^{T}x){\bmod {4}}=\left(2\sum _{i,j}A_{i,j}x_{i}x_{j}+\sum _{i}b_{i}x_{i}\right){\bmod {4}},} 2260: 2082: 1985: 1646: 2265: 2133: 1724: 1555: 2045: 1905: 1679: 203: 2442: 2289: 1634: 1578: 1734: 2161: 2033: 1930: 1806: 1641: 1970: 1935: 1831: 1774: 2055: 1669: 2143: 2116: 2092: 1846: 1779: 1714: 1699: 786: 282: 55:
gates but can't be solved by any sub-exponential size, constant-depth classical circuit using unbounded fan-in
1592: 146: 2294: 2028: 1920: 1890: 1689: 2364: 2128: 2121: 1868: 2284: 1836: 1801: 1910: 1129:{\displaystyle U_{q}=\prod _{1<i<j<n}CZ_{ij}^{A_{ij}}\cdot \bigotimes _{j=1}^{n}S_{j}^{b_{j}}} 1421:
Bravyi, Sergey; Gosset, David; Robert, König (2018-10-19). "Quantum advantage with shallow circuits".
2074: 1823: 1674: 1442: 2176: 2393: 2346: 1950: 1704: 1684: 1619: 1614: 2109: 1757: 1694: 1521: 1493: 1466: 1432: 1225: 1221: 998: 1955: 1345: 256: 2373: 2018: 1925: 1882: 1813: 1729: 1709: 1664: 1624: 1602: 1511: 1458: 1423: 247: 17: 1335:{\displaystyle p(z)=\left|\langle z|H^{\otimes n}U_{q}H^{\otimes n}|0^{n}\rangle \right|^{2}} 81: 67:
gates. While Bernstein–Vazirani's problem was designed to prove an oracle separation between
2040: 1990: 1767: 1503: 1450: 115: 75: 68: 2166: 2104: 1794: 1789: 112: 48: 1446: 2275: 2252: 2219: 2023: 1900: 1380: 980: 960: 940: 912: 326: 39:. In the Bernstein–Vazirani problem, the hidden function is implicitly specified in an 32: 2436: 2097: 1915: 1841: 1525: 1213: 250: 1470: 2317: 2242: 78:, 2D HLF was designed to prove an explicit separation between the circuit classes 2327: 2181: 1719: 2388: 2322: 2186: 1547: 2171: 1507: 1454: 320: 1462: 1486:
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
2356: 2332: 2191: 2156: 64: 56: 2383: 2000: 60: 2360: 1856: 52: 40: 1498: 1437: 1629: 1201:{\displaystyle H^{\otimes n}U_{q}H^{\otimes n}\mid 0^{n}\rangle } 2378: 1851: 1784: 1551: 1995: 1980: 899:{\displaystyle q(x)=2z^{T}x~~\forall x\in {\mathcal {L}}_{q}.} 71: 719: 579: 468: 882: 617: 51:
restricted to a 2-dimensional grid of qubits using bounded
1416: 1414: 1412: 1410: 394:{\displaystyle q:\mathbb {F} _{2}^{n}\to \mathbb {Z} _{4}} 1383: 1348: 1234: 1145: 1007: 983: 963: 943: 915: 832: 789: 613: 410: 352: 329: 285: 259: 206: 149: 118: 84: 1543:
Implementation of the hidden linear function problem
2345: 2308: 2274: 2251: 2218: 2209: 2142: 2071: 2009: 1969: 1881: 1822: 1748: 1657: 1585: 1389: 1369: 1334: 1200: 1128: 989: 969: 949: 921: 898: 815: 772: 593: 393: 335: 311: 271: 238: 184: 134: 103: 1139:This problem can be solved by a quantum circuit, 762: 633: 239:{\displaystyle A\in \mathbb {F} _{2}^{n\times n}} 1563: 8: 1318: 1256: 1228:. It is solved by this circuit because with 1195: 1136:from the first two registers to the third. 2215: 1819: 1570: 1556: 1548: 1497: 1436: 1382: 1347: 1326: 1312: 1303: 1294: 1284: 1271: 1262: 1233: 1189: 1173: 1163: 1150: 1144: 1118: 1113: 1108: 1098: 1087: 1069: 1064: 1056: 1025: 1012: 1006: 982: 962: 942: 914: 887: 881: 880: 855: 831: 816:{\displaystyle z\in \mathbb {F} _{2}^{n}} 807: 802: 798: 797: 788: 761: 760: 754: 749: 745: 744: 722: 718: 655: 650: 646: 645: 632: 631: 622: 616: 615: 612: 582: 578: 567: 557: 547: 534: 524: 508: 492: 471: 467: 455: 436: 409: 385: 381: 380: 370: 365: 361: 360: 351: 328: 312:{\displaystyle b\in \mathbb {F} _{2}^{n}} 303: 298: 294: 293: 284: 258: 224: 219: 215: 214: 205: 176: 160: 148: 126: 117: 95: 83: 185:{\displaystyle QNC^{0}\nsubseteq NC^{0}} 2088:Continuous-variable quantum information 1406: 7: 937:With 3 registers; the first holding 1490:Association for Computing Machinery 870: 734: 25: 45:2D hidden linear function problem 2417: 2416: 2407: 2406: 2453:Computational complexity theory 1358: 1352: 1304: 1263: 1244: 1238: 997:-qubit state, the circuit has 842: 836: 715: 712: 706: 697: 691: 685: 679: 667: 464: 426: 420: 414: 376: 29:hidden linear function problem 18:Hidden Linear Function problem 1: 2083:Adiabatic quantum computation 2134:Topological quantum computer 2412:Quantum information science 1579:Quantum information science 2469: 1807:quantum gate teleportation 977:and the third carrying an 37:Bernstein–Vazirani problem 2448:Quantum complexity theory 2402: 1936:Quantum Fourier transform 1832:Post-quantum cryptography 1775:Entanglement distillation 1370:{\displaystyle p(z)>0} 272:{\displaystyle n\times n} 2422:Quantum mechanics topics 2117:Quantum machine learning 2093:One-way quantum computer 1946:Quantum phase estimation 1847:Quantum key distribution 1780:Monogamy of entanglement 957:, the second containing 196:2D HLF problem statement 2029:Randomized benchmarking 1891:Amplitude amplification 1508:10.1145/3313276.3316404 1455:10.1126/science.aar3106 104:{\displaystyle QNC^{0}} 2129:Quantum Turing machine 2122:quantum neural network 1869:Quantum secret sharing 1391: 1371: 1336: 1202: 1130: 1103: 991: 971: 951: 923: 900: 817: 774: 595: 395: 337: 313: 273: 240: 186: 136: 135:{\displaystyle NC^{0}} 105: 2201:Entanglement-assisted 2162:quantum convolutional 1837:Quantum coin flipping 1802:Quantum teleportation 1763:entanglement-assisted 1593:DiVincenzo's criteria 1392: 1372: 1337: 1203: 1131: 1083: 992: 972: 952: 924: 901: 818: 775: 596: 396: 338: 314: 274: 241: 187: 137: 106: 35:that generalizes the 2012:processor benchmarks 1941:Quantum optimization 1824:Quantum cryptography 1635:physical vs. logical 1492:. pp. 515–526. 1381: 1346: 1232: 1143: 1005: 981: 961: 941: 913: 830: 787: 611: 408: 350: 327: 283: 257: 204: 147: 116: 82: 1725:Quantum speed limit 1620:Quantum programming 1615:Quantum information 1447:2018Sci...362..308B 1125: 1079: 812: 759: 660: 375: 308: 235: 2443:Quantum algorithms 2374:Forest/Rigetti QCS 2110:quantum logic gate 1896:Bernstein–Vazirani 1883:Quantum algorithms 1758:Classical capacity 1642:Quantum processors 1625:Quantum simulation 1387: 1367: 1332: 1198: 1126: 1104: 1052: 1048: 987: 967: 947: 919: 896: 813: 796: 770: 743: 644: 591: 552: 503: 391: 359: 346:define a function 333: 309: 292: 269: 236: 213: 182: 132: 101: 69:complexity classes 2430: 2429: 2341: 2340: 2238:Linear optical QC 2019:Quantum supremacy 1973:complexity theory 1926:Quantum annealing 1877: 1876: 1814:Superdense coding 1603:Quantum computing 1488:. Vol. 362. 1431:(6412): 308–311. 1390:{\displaystyle z} 1021: 1001:which implement 990:{\displaystyle n} 970:{\displaystyle b} 950:{\displaystyle A} 922:{\displaystyle z} 869: 866: 733: 730: 543: 488: 336:{\displaystyle n} 16:(Redirected from 2460: 2420: 2419: 2410: 2409: 2216: 2146:error correction 2075:computing models 2041:Relaxation times 1931:Quantum counting 1820: 1768:quantum capacity 1715:No-teleportation 1700:No-communication 1572: 1565: 1558: 1549: 1530: 1529: 1501: 1481: 1475: 1474: 1440: 1418: 1396: 1394: 1393: 1388: 1376: 1374: 1373: 1368: 1341: 1339: 1338: 1333: 1331: 1330: 1325: 1321: 1317: 1316: 1307: 1302: 1301: 1289: 1288: 1279: 1278: 1266: 1207: 1205: 1204: 1199: 1194: 1193: 1181: 1180: 1168: 1167: 1158: 1157: 1135: 1133: 1132: 1127: 1124: 1123: 1122: 1112: 1102: 1097: 1078: 1077: 1076: 1063: 1047: 1017: 1016: 999:controlled gates 996: 994: 993: 988: 976: 974: 973: 968: 956: 954: 953: 948: 933:2D HLF algorithm 928: 926: 925: 920: 905: 903: 902: 897: 892: 891: 886: 885: 867: 864: 860: 859: 822: 820: 819: 814: 811: 806: 801: 779: 777: 776: 771: 766: 765: 758: 753: 748: 731: 728: 727: 726: 659: 654: 649: 637: 636: 627: 626: 621: 620: 600: 598: 597: 592: 587: 586: 577: 573: 572: 571: 562: 561: 551: 539: 538: 529: 528: 519: 518: 502: 476: 475: 460: 459: 441: 440: 400: 398: 397: 392: 390: 389: 384: 374: 369: 364: 342: 340: 339: 334: 318: 316: 315: 310: 307: 302: 297: 278: 276: 275: 270: 245: 243: 242: 237: 234: 223: 218: 191: 189: 188: 183: 181: 180: 165: 164: 141: 139: 138: 133: 131: 130: 110: 108: 107: 102: 100: 99: 21: 2468: 2467: 2463: 2462: 2461: 2459: 2458: 2457: 2433: 2432: 2431: 2426: 2398: 2348: 2337: 2310:Superconducting 2304: 2270: 2261:Neutral atom QC 2253:Ultracold atoms 2247: 2212:implementations 2211: 2205: 2145: 2138: 2105:Quantum circuit 2073: 2067: 2061: 2051: 2011: 2005: 1972: 1965: 1921:Hidden subgroup 1873: 1862:other protocols 1818: 1795:quantum network 1790:Quantum channel 1750: 1744: 1690:No-broadcasting 1680:Gottesman–Knill 1653: 1581: 1576: 1539: 1534: 1533: 1518: 1483: 1482: 1478: 1420: 1419: 1408: 1403: 1397:is a solution. 1379: 1378: 1344: 1343: 1308: 1290: 1280: 1267: 1255: 1251: 1250: 1230: 1229: 1185: 1169: 1159: 1146: 1141: 1140: 1114: 1065: 1008: 1003: 1002: 979: 978: 959: 958: 939: 938: 935: 911: 910: 879: 851: 828: 827: 785: 784: 783:There exists a 614: 609: 608: 563: 553: 530: 520: 504: 484: 480: 451: 432: 406: 405: 379: 348: 347: 325: 324: 281: 280: 255: 254: 202: 201: 198: 172: 156: 145: 144: 122: 114: 113: 91: 80: 79: 49:quantum circuit 43:; while in the 23: 22: 15: 12: 11: 5: 2466: 2464: 2456: 2455: 2450: 2445: 2435: 2434: 2428: 2427: 2425: 2424: 2414: 2403: 2400: 2399: 2397: 2396: 2394:many others... 2391: 2386: 2381: 2376: 2367: 2353: 2351: 2343: 2342: 2339: 2338: 2336: 2335: 2330: 2325: 2320: 2314: 2312: 2306: 2305: 2303: 2302: 2297: 2292: 2287: 2281: 2279: 2272: 2271: 2269: 2268: 2266:Trapped-ion QC 2263: 2257: 2255: 2249: 2248: 2246: 2245: 2240: 2235: 2230: 2224: 2222: 2220:Quantum optics 2213: 2207: 2206: 2204: 2203: 2198: 2197: 2196: 2189: 2184: 2179: 2174: 2169: 2164: 2159: 2150: 2148: 2140: 2139: 2137: 2136: 2131: 2126: 2125: 2124: 2114: 2113: 2112: 2102: 2101: 2100: 2090: 2085: 2079: 2077: 2069: 2068: 2066: 2065: 2064: 2063: 2059: 2053: 2049: 2038: 2037: 2036: 2026: 2024:Quantum volume 2021: 2015: 2013: 2007: 2006: 2004: 2003: 1998: 1993: 1988: 1983: 1977: 1975: 1967: 1966: 1964: 1963: 1958: 1953: 1948: 1943: 1938: 1933: 1928: 1923: 1918: 1913: 1908: 1903: 1901:Boson sampling 1898: 1893: 1887: 1885: 1879: 1878: 1875: 1874: 1872: 1871: 1866: 1865: 1864: 1859: 1854: 1844: 1839: 1834: 1828: 1826: 1817: 1816: 1811: 1810: 1809: 1799: 1798: 1797: 1787: 1782: 1777: 1772: 1771: 1770: 1765: 1754: 1752: 1746: 1745: 1743: 1742: 1737: 1735:Solovay–Kitaev 1732: 1727: 1722: 1717: 1712: 1707: 1702: 1697: 1692: 1687: 1682: 1677: 1672: 1667: 1661: 1659: 1655: 1654: 1652: 1651: 1650: 1649: 1639: 1638: 1637: 1627: 1622: 1617: 1612: 1611: 1610: 1600: 1595: 1589: 1587: 1583: 1582: 1577: 1575: 1574: 1567: 1560: 1552: 1546: 1545: 1538: 1537:External links 1535: 1532: 1531: 1516: 1476: 1405: 1404: 1402: 1399: 1386: 1366: 1363: 1360: 1357: 1354: 1351: 1329: 1324: 1320: 1315: 1311: 1306: 1300: 1297: 1293: 1287: 1283: 1277: 1274: 1270: 1265: 1261: 1258: 1254: 1249: 1246: 1243: 1240: 1237: 1197: 1192: 1188: 1184: 1179: 1176: 1172: 1166: 1162: 1156: 1153: 1149: 1121: 1117: 1111: 1107: 1101: 1096: 1093: 1090: 1086: 1082: 1075: 1072: 1068: 1062: 1059: 1055: 1051: 1046: 1043: 1040: 1037: 1034: 1031: 1028: 1024: 1020: 1015: 1011: 986: 966: 946: 934: 931: 918: 907: 906: 895: 890: 884: 878: 875: 872: 863: 858: 854: 850: 847: 844: 841: 838: 835: 810: 805: 800: 795: 792: 781: 780: 769: 764: 757: 752: 747: 742: 739: 736: 725: 721: 717: 714: 711: 708: 705: 702: 699: 696: 693: 690: 687: 684: 681: 678: 675: 672: 669: 666: 663: 658: 653: 648: 643: 640: 635: 630: 625: 619: 602: 601: 590: 585: 581: 576: 570: 566: 560: 556: 550: 546: 542: 537: 533: 527: 523: 517: 514: 511: 507: 501: 498: 495: 491: 487: 483: 479: 474: 470: 466: 463: 458: 454: 450: 447: 444: 439: 435: 431: 428: 425: 422: 419: 416: 413: 388: 383: 378: 373: 368: 363: 358: 355: 332: 306: 301: 296: 291: 288: 268: 265: 262: 233: 230: 227: 222: 217: 212: 209: 197: 194: 179: 175: 171: 168: 163: 159: 155: 152: 129: 125: 121: 98: 94: 90: 87: 33:search problem 24: 14: 13: 10: 9: 6: 4: 3: 2: 2465: 2454: 2451: 2449: 2446: 2444: 2441: 2440: 2438: 2423: 2415: 2413: 2405: 2404: 2401: 2395: 2392: 2390: 2387: 2385: 2382: 2380: 2377: 2375: 2371: 2368: 2366: 2362: 2358: 2355: 2354: 2352: 2350: 2344: 2334: 2331: 2329: 2326: 2324: 2321: 2319: 2316: 2315: 2313: 2311: 2307: 2301: 2298: 2296: 2293: 2291: 2290:Spin qubit QC 2288: 2286: 2283: 2282: 2280: 2277: 2273: 2267: 2264: 2262: 2259: 2258: 2256: 2254: 2250: 2244: 2241: 2239: 2236: 2234: 2231: 2229: 2226: 2225: 2223: 2221: 2217: 2214: 2208: 2202: 2199: 2195: 2194: 2190: 2188: 2185: 2183: 2180: 2178: 2175: 2173: 2170: 2168: 2165: 2163: 2160: 2158: 2155: 2154: 2152: 2151: 2149: 2147: 2141: 2135: 2132: 2130: 2127: 2123: 2120: 2119: 2118: 2115: 2111: 2108: 2107: 2106: 2103: 2099: 2098:cluster state 2096: 2095: 2094: 2091: 2089: 2086: 2084: 2081: 2080: 2078: 2076: 2070: 2062: 2058: 2054: 2052: 2048: 2044: 2043: 2042: 2039: 2035: 2032: 2031: 2030: 2027: 2025: 2022: 2020: 2017: 2016: 2014: 2008: 2002: 1999: 1997: 1994: 1992: 1989: 1987: 1984: 1982: 1979: 1978: 1976: 1974: 1968: 1962: 1959: 1957: 1954: 1952: 1949: 1947: 1944: 1942: 1939: 1937: 1934: 1932: 1929: 1927: 1924: 1922: 1919: 1917: 1914: 1912: 1909: 1907: 1906:Deutsch–Jozsa 1904: 1902: 1899: 1897: 1894: 1892: 1889: 1888: 1886: 1884: 1880: 1870: 1867: 1863: 1860: 1858: 1855: 1853: 1850: 1849: 1848: 1845: 1843: 1842:Quantum money 1840: 1838: 1835: 1833: 1830: 1829: 1827: 1825: 1821: 1815: 1812: 1808: 1805: 1804: 1803: 1800: 1796: 1793: 1792: 1791: 1788: 1786: 1783: 1781: 1778: 1776: 1773: 1769: 1766: 1764: 1761: 1760: 1759: 1756: 1755: 1753: 1751:communication 1747: 1741: 1738: 1736: 1733: 1731: 1728: 1726: 1723: 1721: 1718: 1716: 1713: 1711: 1708: 1706: 1703: 1701: 1698: 1696: 1693: 1691: 1688: 1686: 1683: 1681: 1678: 1676: 1673: 1671: 1668: 1666: 1663: 1662: 1660: 1656: 1648: 1645: 1644: 1643: 1640: 1636: 1633: 1632: 1631: 1628: 1626: 1623: 1621: 1618: 1616: 1613: 1609: 1606: 1605: 1604: 1601: 1599: 1596: 1594: 1591: 1590: 1588: 1584: 1580: 1573: 1568: 1566: 1561: 1559: 1554: 1553: 1550: 1544: 1541: 1540: 1536: 1527: 1523: 1519: 1517:9781450367059 1513: 1509: 1505: 1500: 1495: 1491: 1487: 1480: 1477: 1472: 1468: 1464: 1460: 1456: 1452: 1448: 1444: 1439: 1434: 1430: 1426: 1425: 1417: 1415: 1413: 1411: 1407: 1400: 1398: 1384: 1364: 1361: 1355: 1349: 1327: 1322: 1313: 1309: 1298: 1295: 1291: 1285: 1281: 1275: 1272: 1268: 1259: 1252: 1247: 1241: 1235: 1227: 1223: 1219: 1215: 1214:Hadamard gate 1211: 1190: 1186: 1182: 1177: 1174: 1170: 1164: 1160: 1154: 1151: 1147: 1137: 1119: 1115: 1109: 1105: 1099: 1094: 1091: 1088: 1084: 1080: 1073: 1070: 1066: 1060: 1057: 1053: 1049: 1044: 1041: 1038: 1035: 1032: 1029: 1026: 1022: 1018: 1013: 1009: 1000: 984: 964: 944: 932: 930: 916: 893: 888: 876: 873: 861: 856: 852: 848: 845: 839: 833: 826: 825: 824: 808: 803: 793: 790: 767: 755: 750: 740: 737: 723: 709: 703: 700: 694: 688: 682: 676: 673: 670: 664: 661: 656: 651: 641: 638: 628: 623: 607: 606: 605: 588: 583: 574: 568: 564: 558: 554: 548: 544: 540: 535: 531: 525: 521: 515: 512: 509: 505: 499: 496: 493: 489: 485: 481: 477: 472: 461: 456: 452: 448: 445: 442: 437: 433: 429: 423: 417: 411: 404: 403: 402: 386: 371: 366: 356: 353: 344: 330: 322: 321:binary vector 304: 299: 289: 286: 266: 263: 260: 252: 251:binary matrix 249: 231: 228: 225: 220: 210: 207: 195: 193: 177: 173: 169: 166: 161: 157: 153: 150: 142: 127: 123: 119: 96: 92: 88: 85: 77: 73: 70: 66: 62: 58: 54: 50: 46: 42: 38: 34: 30: 19: 2318:Charge qubit 2243:KLM protocol 2192: 2056: 2046: 1740:Purification 1670:Eastin–Knill 1485: 1479: 1428: 1422: 1217: 1209: 1138: 936: 908: 782: 603: 345: 199: 44: 28: 26: 2349:programming 2328:Phase qubit 2233:Circuit QED 1705:No-deleting 1647:cloud-based 2437:Categories 2389:libquantum 2323:Flux qubit 2228:Cavity QED 2177:Bacon–Shor 2167:stabilizer 1695:No-cloning 1499:1906.08890 1438:1704.00690 1401:References 1224:and CZ is 823:such that 323:of length 248:triangular 246:(an upper- 2295:NV center 1730:Threshold 1710:No-hiding 1675:Gleason's 1526:195259496 1319:⟩ 1296:⊗ 1273:⊗ 1257:⟨ 1196:⟩ 1183:∣ 1175:⊗ 1152:⊗ 1085:⨂ 1081:⋅ 1023:∏ 877:∈ 871:∀ 794:∈ 741:∈ 735:∀ 674:⊕ 642:∈ 545:∑ 490:∑ 377:→ 290:∈ 264:× 229:× 211:∈ 167:⊈ 2357:OpenQASM 2333:Transmon 2210:Physical 2010:Quantum 1911:Grover's 1685:Holevo's 1658:Theorems 1608:timeline 1598:NISQ era 1471:16308940 1463:30337404 1208:, where 253:of size 2347:Quantum 2285:Kane QC 2144:Quantum 2072:Quantum 2001:PostBQP 1971:Quantum 1956:Simon's 1749:Quantum 1586:General 1443:Bibcode 1424:Science 1226:CZ gate 1220:is the 1212:is the 31:, is a 2365:IBM QX 2361:Qiskit 2300:NMR QC 2278:-based 2182:Steane 2153:Codes 1951:Shor's 1857:SARG04 1665:Bell's 1524:  1514:  1469:  1461:  1222:S gate 868:  865:  732:  729:  279:) and 200:Given 63:, and 53:fan-in 41:oracle 2187:Toric 1630:Qubit 1522:S2CID 1494:arXiv 1467:S2CID 1433:arXiv 909:Find 2379:Cirq 2370:Quil 2276:Spin 2172:Shor 1852:BB84 1785:LOCC 1512:ISBN 1459:PMID 1377:iff 1362:> 1042:< 1036:< 1030:< 604:and 111:and 74:and 27:The 2193:gnu 2157:CSS 2034:XEB 1996:QMA 1991:QIP 1986:EQP 1981:BQP 1961:VQE 1916:HHL 1720:PBR 1504:doi 1451:doi 1429:362 720:mod 580:mod 469:mod 343:), 319:(a 192:). 76:BPP 72:BQP 65:NOT 57:AND 2439:: 2384:Q# 1520:. 1510:. 1502:. 1465:. 1457:. 1449:. 1441:. 1427:. 1409:^ 1342:, 1216:, 929:. 401:: 61:OR 59:, 2372:– 2363:– 2359:– 2060:2 2057:T 2050:1 2047:T 1571:e 1564:t 1557:v 1528:. 1506:: 1496:: 1473:. 1453:: 1445:: 1435:: 1385:z 1365:0 1359:) 1356:z 1353:( 1350:p 1328:2 1323:| 1314:n 1310:0 1305:| 1299:n 1292:H 1286:q 1282:U 1276:n 1269:H 1264:| 1260:z 1253:| 1248:= 1245:) 1242:z 1239:( 1236:p 1218:S 1210:H 1191:n 1187:0 1178:n 1171:H 1165:q 1161:U 1155:n 1148:H 1120:j 1116:b 1110:j 1106:S 1100:n 1095:1 1092:= 1089:j 1074:j 1071:i 1067:A 1061:j 1058:i 1054:Z 1050:C 1045:n 1039:j 1033:i 1027:1 1019:= 1014:q 1010:U 985:n 965:b 945:A 917:z 894:. 889:q 883:L 874:x 862:x 857:T 853:z 849:2 846:= 843:) 840:x 837:( 834:q 809:n 804:2 799:F 791:z 768:. 763:} 756:n 751:2 746:F 738:y 724:4 716:) 713:) 710:y 707:( 704:q 701:+ 698:) 695:x 692:( 689:q 686:( 683:= 680:) 677:y 671:x 668:( 665:q 662:: 657:n 652:2 647:F 639:x 634:{ 629:= 624:q 618:L 589:, 584:4 575:) 569:i 565:x 559:i 555:b 549:i 541:+ 536:j 532:x 526:i 522:x 516:j 513:, 510:i 506:A 500:j 497:, 494:i 486:2 482:( 478:= 473:4 465:) 462:x 457:T 453:b 449:+ 446:x 443:A 438:T 434:x 430:2 427:( 424:= 421:) 418:x 415:( 412:q 387:4 382:Z 372:n 367:2 362:F 357:: 354:q 331:n 305:n 300:2 295:F 287:b 267:n 261:n 232:n 226:n 221:2 216:F 208:A 178:0 174:C 170:N 162:0 158:C 154:N 151:Q 143:( 128:0 124:C 120:N 97:0 93:C 89:N 86:Q 20:)

Index

Hidden Linear Function problem
search problem
Bernstein–Vazirani problem
oracle
quantum circuit
fan-in
AND
OR
NOT
complexity classes
BQP
BPP
N C 0 {\displaystyle NC^{0}}
triangular
binary matrix
binary vector
controlled gates
Hadamard gate
S gate
CZ gate




Science
arXiv
1704.00690
Bibcode
2018Sci...362..308B
doi

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

↑