Mit Harry Buhrman und anderen entwickelte er eine allgemeine Methode um die Grenzen von Quantenrechnern zu bestimmen, die Quanten-Polynom-Methode. Ebenfalls mit Buhrman zeigte er, dass Quantenrechner bei einigen Problemen sehr viel effizienter sind (wie der Bestimmung von Quanten-Fingerabdrücken). Mit Kerenidis wandte er die Quanteninformatik auf ein klassisches Informatikproblem an und fand exponentielle Untergrenzen für die Länge von lokal dekodierbaren fehlerkorrigierenden Codes (mit 2 Bits des Codewortes für die Dekodierung eines Bits). Mit klassischen Informatik-Methoden waren davor nur polynomiale Untergrenzen gefunden worden. Das Verfahren lieferte auch neue kryptographische Protokolle.
2003 erhielt er den Cor Baayen Award des ERCIM (European Research Consortium for Informatics and Mathematics). 2014 erhielt er einen Consolidator Grant des European Research Council und einen TOP-Grant der niederländischen Forschungsorganisation NWO. Für 2023 wurde de Wolf und Mitautoren der Gödel-Preis zugesprochen.
Er ist nicht mit dem US-amerikanischen Scientology-Kritiker Ronald DeWolf zu verwechseln.
Schriften (Auswahl)
mit S. H. Nienhuys-Cheng: Foundations of Inductive Logic Programming, Lecture Notes in Artificial Intelligence 1228, Springer 1997
mit R. Beals, H. Buhrman, R. Cleve, Michele Mosca: Quantum lower bounds by polynomials, FOCS 1998, Arxiv 1998, und Journal of the ACM, Band 48, 2001, S. 778–797
mit Harry Buhrman, Richard Cleve, John Watrous: Quantum fingerprinting, Physical Review Letters, Band 87, 2001, S. 167902, Arxiv
mit Iordanis Kerenidis: Exponential lower bound for 2-query locally decodable codes via a quantum argument, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (STOC '03). ACM, New York, 2003, S. 106–115, endgültige Version: Journal of Computer Systems Science, Band 69, 2004, S. 395–420
mit Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz: Exponential separations for one-way quantum communication complexity, with applications to cryptography, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (STOC '07). ACM, New York, 2007, S. 516–525, endgültige Version: SIAM J. Computing, Band 38, 2008, S. 1695–1708
mit D. Gavinsky, J. Kempe, O. Regev: Bounded-error quantum state identication and exponential separations in communication complexity, SIAM Journal on Computing, Band 39, 2009, S. 1–39 (frühere Version in STOC 2006).
mit Harry Buhrman, Richard Cleve, Serge Massar: Nonlocality and communication complexity, Rev. Mod. Phys., Band 82, 2010, S. 665–698, Arxiv
mit S. Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC '12). ACM, New York 2012, S. 95–106, spätere Version: Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Journal of the ACM, Band 62, 2015, S. 17,
mit V. Chen, E. Grigorescu: Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation, SIAM Journal on Computing, Band 42, 2013, S. 84–111