Ronald de Wolf

Ronald de Wolf

Auto-generated profile, based on publicly available information

Ronald de Wolf

QuSoft CWI University of Amsterdam the Netherlands

Research Focus & Metrics

Academic Career Length

29Years (1998-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
26 September 2001 in Physical Review Letters
Verified
Journal Article
Closed access
PDF file
HBHarry Buhrman
Harry Buhrman
RCRichard Cleve
Richard Cleve
JWJohn Watrous
John Watrous
RWRonald de Wolf
Ronald de Wolf
Classical fingerprinting associates with each string a shorter string (its fingerprint), such that any two distinct strings can be distinguished with small error by comparing their fingerprints alone. The fingerprints cannot be made exponentially smaller than the original strings unless the parties preparing the fingerprints have access to correlated random sources. We show that fingerprints consisting of quantum information can be made exponentially smaller than the original strings without any correlations or entanglement between the parties. This implies an exponential quantum/classical gap for the equality problem in the simultaneous message passing model of communication complexity.

14 February 2020 in Quantum
Verified
Journal Article
Open access
PDF file
JAJoran van Apeldoorn
Joran van Apeldoorn
AGAndrás Gilyén
András Gilyén
SGSander Gribling
Sander Gribling
RWRonald de Wolf
Ronald de Wolf
Brandão and Svore \cite{brandao2016QSDPSpeedup} recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension n of the problem and the number m of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimization problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with mn when m≈n, which is the same as classical.

15 September 2017 in Ethics and Information Technology
Verified
Journal Article
Closed access
PDF file
RWRonald de Wolf
Ronald de Wolf

13 January 2020 in Quantum
Verified
Journal Article
Open access
PDF file
JAJoran van Apeldoorn
Joran van Apeldoorn
AGAndrás Gilyén
András Gilyén
SGSander Gribling
Sander Gribling
RWRonald de Wolf
Ronald de Wolf
We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using O~(1) quantum queries to a membership oracle, which is an exponential quantum speed-up over the Ω(n) membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that O~(n) quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: Ω(n) quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and Ω(n) quantum separation queries are needed if it does not.

13 September 2007 in Algorithmica
Verified
Journal Article
Closed access
PDF file
AAAndris Ambainis
Andris Ambainis
RŠRobert Špalek
Robert Špalek
RWRonald de Wolf
Ronald de Wolf

8 September 2016 in Algorithmica
Verified
Journal Article
Closed access
PDF file
SJStacey Jeffery
Stacey Jeffery
FMFrederic Magniez
Frederic Magniez
RWRonald de Wolf
Ronald de Wolf