1Boston University
2Microsoft Kwantum
3Georgetown University
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
We geven nieuwe kwantumalgoritmen voor het evalueren van samengestelde functies waarvan de invoer kan worden gedeeld tussen poorten op het laagste niveau. Laat $f$ een $m$-bit Booleaanse functie zijn en beschouw een $n$-bit functie $F$ verkregen door $f$ toe te passen op voegwoorden van mogelijk overlappende subsets van $n$ variabelen. Als $f$ kwantumquery-complexiteit $Q(f)$ heeft, geven we een algoritme voor het evalueren van $F$ met behulp van $tilde{O}(sqrt{Q(f) cdot n})$ kwantumquery's. Dit verbetert de grens van $O(Q(f) cdot sqrt{n})$ die volgt door elke conjunctie afzonderlijk te behandelen, en onze grens is krap voor de worst-case keuzes van $f$. Met behulp van totaal verschillende technieken bewijzen we een vergelijkbare strakke samenstellingsstelling voor de geschatte graad van $f$.
Door recursief onze compositiestellingen toe te passen, verkrijgen we een bijna optimale $tilde{O}(n^{1-2^{-d}})$ bovengrens voor de complexiteit van de kwantumquery en de geschatte mate van lineaire diepte-$d $ AC$^0$ circuits. Als gevolg hiervan kunnen dergelijke circuits PAC worden geleerd in subexponentiële tijd, zelfs in de uitdagende agnostische omgeving. Voorafgaand aan ons werk was een algoritme met subexponentiële tijd niet bekend, zelfs niet voor AC$^3$-circuits met een lineaire grootte van diepte-0.
Als een bijkomend gevolg laten we zien dat AC$^0 circ oplus$ circuits met diepte $d+1$ size $tilde{Omega}(n^{1/(1- 2^{-d})}) geq omega vereisen (n^{1+ 2^{-d}} )$ om de Inner Product-functie zelfs gemiddeld te berekenen. De vorige beste ondergrens was $Omega(n^{1+4^{-(d+1)}})$ en werd alleen in het ergste geval aangehouden (Cheraghchi et al., JCSS 2018).
► BibTeX-gegevens
► Referenties
[1] Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath en Alon Rosen. Kandidaat zwakke pseudo-willekeurige functies in AC$^0 circ mathsf{MOD}_2$. In Proceedings van de 5e conferentie over innovaties in theoretische informatica, ITCS '14, pagina's 251-260, 2014.
https: / / doi.org/ 10.1145 / 2554797.2554821
[2] Miklos Ajtai en Michael Ben-Or. Een stelling over probabilistische berekeningen met constante diepte. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC '84, pagina's 471-474, 1984.
https: / / doi.org/ 10.1145 / 800057.808715
[3] Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek en Shengyu Zhang. Elke AND-OR-formule met de grootte $N$ kan worden geëvalueerd in de tijd $N^{1/2 + o(1)}$ op een kwantumcomputer. SIAM Journal on Computing, 39(6):2513-2530, 2010.
https: / / doi.org/ 10.1137 / 080712167
[4] Charles H. Bennett, Ethan Bernstein, Gilles Brassard en Umesh Vazirani. Sterke en zwakke punten van quantum computing. SIAM Journal on Computing, 26(5):1510-1523, 1997.
https: / / doi.org/ 10.1137 / S0097539796300933
[5] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca en Ronald de Wolf. Quantum ondergrenzen door polynomen. Tijdschrift van de ACM, 48(4):778-797, 2001.
https: / / doi.org/ 10.1145 / 502090.502097
[6] Michel Boyer, Gilles Brassard, Peter Høyer en Alain Tapp. Strakke grenzen aan het zoeken naar kwantum. Fortschritte der Physik, 46(4-5):493-505, 1998.
[7] Harry Buhrman, Richard Cleve, Ronald de Wolf en Christof Zalka. Grenzen voor kwantumalgoritmen met kleine fouten en nulfouten. In het 40e jaarlijkse symposium over de grondslagen van de informatica, pagina's 358-368, 1999.
https://doi.org/10.1109/sffcs.1999.814607
[8] Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler en Prashant Nalini Vasudevan. Over de kracht van statistische nulkennis. In 58e jaarlijkse symposium over fundamenten van computerwetenschappen (FOCS 2017), pagina's 708-719, 2017.
https: / / doi.org/ 10.1109 / focs.2017.71
[9] Harry Buhrman en Ronald de Wolf. Complexiteitsmaatregelen en beslisboomcomplexiteit: een overzicht. Theoretische informatica, 288(1):21-43, 2002.
https://doi.org/10.1016/S0304-3975(01)00144-X
[10] Mark Bun, Robin Kothari en Justin Thaler. De polynomiale methode slaat terug: strakke kwantumquerygrenzen via dubbele polynomen. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pagina's 297-310, 2018.
https: / / doi.org/ 10.1145 / 3188745.3188784
[11] Mark Bun, Robin Kothari en Justin Thaler. Quantumalgoritmen en benaderende polynomen voor samengestelde functies met gedeelde ingangen. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pagina's 662-678, 2019.
https: / / doi.org/ 10.1137 / 1.9781611975482.42
[12] Paul Beame en Widad Machmouchi. De complexiteit van de kwantumquery van AC$^0$. Kwantuminformatie en berekeningen, 12(7-8):670-676, 2012.
[13] Harry Buhrman, Ilan Newman, Hein Röhrig en Ronald de Wolf. Robuuste polynomen en kwantumalgoritmen. Theorie van computersystemen, 40 (4): 379-395, 2007.
https: / / doi.org/ 10.1007 / s00224-006-1313-z
[14] Jehoshua Bruck en Roman Smolensky. Polynomiale drempelfuncties, AC$^0$-functies en spectrale normen. SIAM Journal on Computing, 21(1):33-42, 1992.
https: / / doi.org/ 10.1137 / 0221003
[15] Mark Bun en Justin Thaler. Een bijna optimale ondergrens op de geschatte graad van AC$^0$. In IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), pagina's 1-12, 2017.
https: / / doi.org/ 10.1109 / FOCS.2017.10
[16] Mark Bun en Justin Thaler. Gastkolom: Geschatte graad in klassieke en kwantumcomputers. SIGACT News, 51(4):48-72, januari 2021.
https: / / doi.org/ 10.1145 / 3444815.3444825
[17] Andrew M. Childs, Richard Cleve, Stephen P. Jordan en David Yonge-Mallo. Kwantumalgoritme voor discrete query's voor NAND-bomen. Theory of Computing, 5: 119-123, 2009.
https: / / doi.org/ 10.4086 / toc.2009.v005a005
[18] Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer en Ning Xie. AC0 $circ$ MOD2 ondergrenzen voor het Booleaanse inproduct. In LIPIcs-Leibniz International Proceedings in Informatics, volume 55. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2016.35
[19] Chris Calabro, Russel Impagliazzo en Ramamohan Paturi. De complexiteit van vervulbaarheid van circuits met kleine diepte. In International Workshop on Parameterized and Exact Computation, pagina's 75-85, 2009.
https://doi.org/10.1007/978-3-642-11269-0_6
[20] Andrew M. Childs, Shelby Kimmel en Robin Kothari. De complexiteit van kwantumquery's van read-many-formules. In het 20e jaarlijkse Europese symposium over algoritmen (ESA 2012), pagina's 337-348, 2012.
https://doi.org/10.1007/978-3-642-33090-2_30
[21] Shiva Chaudhuri en Jaikumar Radhakrishnan. Deterministische beperkingen in circuitcomplexiteit. In Proceedings van het achtentwintigste jaarlijkse ACM-symposium over Theory of computing, STOC '96, pagina's 30-36, 1996.
https: / / doi.org/ 10.1145 / 237814.237824
[22] Gil Cohen en Igor Shinkar. De complexiteit van DNF van pariteiten. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pagina's 47-58, 2016.
https: / / doi.org/ 10.1145 / 2840728.2840734
[23] Ning Ding, Yanli Ren en Dawu Gu. PAC leerdiepte-3 AC$^0$ circuits van begrensde top fanin. In Proceedings of the 28th International Conference on Algorithmic Learning Theory, volume 76 van Proceedings of Machine Learning Research, pagina's 667-680, 2017. URL: http://proceedings.mlr.press/v76/ding17a.html.
http:///proceedings.mlr.press/v76/ding17a.html
[24] Michael Ezra en Ron D. Rothblum. Kleine circuits impliceren efficiënte Arthur-Merlin-protocollen. Technisch rapport TR21-127, Electronic Colloquium on Computational Complexity (ECCC), 2021. URL: https://eccc.weizmann.ac.il/report/2021/127/.
https: / / eccc.weizmann.ac.il/ report / 2021/127 /
[25] Edward Farhi, Jeffrey Goldstone en Sam Gutmann. Een kwantumalgoritme voor de Hamiltoniaanse NAND-boom. Theory of Computing, 4 (1): 169-190, 2008.
https: / / doi.org/ 10.4086 / toc.2008.v004a008
[26] Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O'Donnell, Sushant Sachdeva, Andrew Wan en Karl Wimmer. Real analysis in computer science: A collection of open problems, 2014. URL: https://simons.berkeley.edu/sites/default/files/openprobsmerged.pdf.
https:///simons.berkeley.edu/sites/default/files/openprobsmerged.pdf
[27] Liefs K. Grover. Een snel kwantummechanisch algoritme voor het doorzoeken van databases. In Proceedings of the Twenty-eight Annual ACM Symposium on Theory of Computing, STOC '96, pagina's 212-219, 1996.
https: / / doi.org/ 10.1145 / 237814.237866
[28] Peter Høyer, Troy Lee en Robert Špalek. Negatieve gewichten maken tegenstanders sterker. In Proceedings of the 39th Symposium on Theory of Computing (STOC 2007), pagina's 526-535, 2007.
https: / / doi.org/ 10.1145 / 1250790.1250867
[29] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour en Rocco A. Servedio. Agnostisch leren van halfruimten. SIAM Journal on Computing, 37 (6): 1777-1805, 2008.
https: / / doi.org/ 10.1137 / 060649057
[30] Adam Klivans, Pravesh Kothari en Igor C. Oliveira. Het construeren van harde functies met behulp van leeralgoritmen. In IEEE Conference on Computational Complexity (CCC 2013), pagina's 86-97, 2013.
https: / / doi.org/ 10.1109 / CCC.2013.18
[31] Michal Koucký, Clemens Lautemann, Sebastian Poloczek en Denis Therien. Circuit ondergrenzen via Ehrenfeucht-Fraisse games. In de 21e jaarlijkse IEEE Conference on Computational Complexity (CCC 2006), pagina's 190-201, 07 2006.
https: / / doi.org/ 10.1109 / CCC.2006.12
[32] Swastik Kopfeest. AC0 ondergrenzen en pseudowillekeur. Collegenota's van "Topics in Complexity Theory and Pseudorandomness (lente 2013)" aan de Rutgers University. http:///sites.math.rutgers.edu/sk1233/courses/topics-S13/lec4.pdf (Ontvangen op 12 juli 2018), 2013.
http:///sites.math.rutgers.edu/~sk1233/courses/topics-S13/lec4.pdf
[33] Michal Koucký. Circuitcomplexiteit van reguliere talen. Theorie van computersystemen, 45 (4): 865-879, 2009.
https: / / doi.org/ 10.1007 / s00224-009-9180-z
[34] Adam R. Klivans en Rocco A. Servedio. DNF op tijd leren $2^{{tilde O}(n^{1/3})}$. Journal of Computer and System Sciences, 68 (2): 303-318, 2004.
https: / / doi.org/ 10.1016 / j.jcss.2003.07.007
[35] Michael J. Kearns, Robert E. Schapire en Linda M. Sellie. Op weg naar efficiënt agnostisch leren. Machinaal leren, 17 (2-3): 115-141, 1994.
https: / / doi.org/ 10.1007 / bf00993468
[36] Wee Sun Lee, Peter L. Bartlett en Robert C. Williamson. Over efficiënt agnostisch leren van lineaire combinaties van basisfuncties. In Proceedings van de achtste jaarlijkse conferentie over computationele leertheorie, pagina's 369-376, 1995.
https: / / doi.org/ 10.1145 / 225298.225343
[37] Troje Lee. Dia's voor het artikel "verbeterde kwantumquery-algoritmen voor het vinden van driehoeken en associativiteitstests" door T. Lee, F. Magniez, M. Santha. Beschikbaar op http:///research.cs.rutgers.edu/ troyjlee/troy_triangle.pdf (Ontvangen op 11 juli 2018), 2012.
http:///research.cs.rutgers.edu/~troyjlee/troy_triangle.pdf
[38] Troy Lee en Adi Shraibman. Ondergrenzen in communicatiecomplexiteit. Grondslagen en trends in theoretische informatica, 3 (4): 263-399, 2009.
https: / / doi.org/ 10.1561 / 0400000040
[39] Noam Nisan. Kortste formule voor een monotone CNF van $n$-termijn. Theoretical Computer Science Stack Exchange, 2011. https://cstheory.stackexchange.com/q/7087 (versie: 2011-06-23).
https:///cstheory.stackexchange.com/q/7087
[40] Noam Nisan en Mario Szegedy. Op de graad van Booleaanse functies als echte veeltermen. Computationele complexiteit, 4:301-313, 1994.
https: / / doi.org/ 10.1007 / BF01263419
[41] Igor C. Carboni Oliveira en Rahul Santhanam. Samenzweringen tussen leeralgoritmen, ondergrenzen van circuits en pseudo-willekeur. In 32nd Computational Complexity Conference (CCC 2017), volume 79 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 18:1–18:49, 2017.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.18
[42] Alexander A Razborov. Ondergrenzen op de grootte van begrensde dieptecircuits over een volledige basis met logische toevoeging. Wiskundige aantekeningen van de Academie van Wetenschappen van de USSR, 41 (4): 333-338, 1987.
[43] Ben Reichardt. Reflecties voor algoritmen voor kwantumquery's. In SODA '11: Proceedings van het 22e ACM-SIAM-symposium over discrete algoritmen, pagina's 560-569, 2011.
https: / / doi.org/ 10.1137 / 1.9781611973082.44
[44] Alexander A. Razborov en Alexander A. Sherstov. De tekenrang van AC$^0$. SIAM Journal on Computing, 39 (5): 1833-1855, 2010.
https: / / doi.org/ 10.1137 / 080744037
[45] Prabhakar Ragde en Avi Wigderson. Lineaire-grootte constante diepte polylog-drempelcircuits. Informatieverwerkingsbrieven, 39(3):143-146, 1991.
https://doi.org/10.1016/0020-0190(91)90110-4
[46] Alexander A. Sherstov. De patroonmatrixmethode. SIAM Journal on Computing, 40 (6): 1969-2000, 2011.
https: / / doi.org/ 10.1137 / 080733644
[47] Alexander A. Sherstov. Sterke directe productstellingen voor kwantumcommunicatie en vraagcomplexiteit. In Proceedings van het 43e jaarlijkse ACM-symposium over Theory of computing (STOC 2011), pagina's 41-50, 2011.
https: / / doi.org/ 10.1145 / 1993636.1993643
[48] Alexander A. Sherstov. Het snijpunt van twee halfspaces heeft een hoge drempelgraad. SIAM Journal on Computing, 42(6):2329-2374, 2013.
https: / / doi.org/ 10.1137 / 100785260
[49] Alexander A. Sherstov. Polynomen robuust maken tegen ruis. Theory of Computing, 9:593-615, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a018
[50] Alexander A. Sherstov. De kracht van asymmetrie in circuits met constante diepte. In IEEE 56th Annual Symposium on Foundations of Computer Science, pagina's 431-450, 2015.
https: / / doi.org/ 10.1109 / FOCS.2015.34
[51] Alexander A. Sherstov. Algoritmische veeltermen. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), 2018.
https: / / doi.org/ 10.1145 / 3188745.3188958
[52] Rahul Santhanam en Srikanth Srinivasan. Over de grenzen van sparsificatie. In internationaal colloquium over automaten, talen en programmeren, pagina's 774-785. Springer, 2012.
https://doi.org/10.1007/978-3-642-31594-7_65
[53] Rocco A. Servedio en Li-Yang Tan. Welke circuitklassen kunnen worden geleerd met niet-triviale besparingen? In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 30:1–30:21, 2017.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2017.30
[54] Rocco A Servedio en Emanuele Viola. Op een speciaal geval van stijfheid. Technisch rapport TR12-144, Electronic Colloquium on Computational Complexity (ECCC), 2012. URL: https://eccc.weizmann.ac.il/report/2012/144/.
https: / / eccc.weizmann.ac.il/ report / 2012/144 /
[55] Avishay Tal. De bipartiete formule complexiteit van inproduct is kwadratisch. Technisch rapport TR16-181, Electronic Colloquium on Computational Complexity (ECCC), 2016. URL: https://eccc.weizmann.ac.il/report/2016/181/.
https: / / eccc.weizmann.ac.il/ report / 2016/181 /
[56] Avishay Tal. Formule ondergrenzen via de kwantummethode. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pagina's 1256-1268, 2017.
https: / / doi.org/ 10.1145 / 3055399.3055472
[57] Avishay Tal. Persoonlijke communicatie, 2018.
[58] Leslie G. Valiant. Een theorie van het leerbare. Mededelingen van de ACM, 27(11):1134-1142, november 1984.
https: / / doi.org/ 10.1145 / 1968.1972
Geciteerd door
[1] Scott Aaronson, Daniel Grier en Luke Schaeffer, "A Quantum Query Complexity Trichotomy for Regular Languages", arXiv: 1812.04219.
[2] Kamil Khadiev en Liliya Safina, "Quantum Algorithm for Dynamic Programming Approach for DAG's. Aanvragen voor Zhegalkin Polynomial Evaluation en enkele problemen op DAG's”, arXiv: 1804.09950.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2021-09-16 14:44:06). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
Kon niet ophalen Door Crossref geciteerde gegevens tijdens laatste poging 2021-09-16 14:44:04: kon niet geciteerde gegevens voor 10.22331 / q-2021-09-16-543 niet ophalen van Crossref. Dit is normaal als de DOI recent is geregistreerd.
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
PlatoAi. Web3 opnieuw uitgevonden. Gegevensintelligentie versterkt.
Klik hier om toegang te krijgen.
