Ronald de Wolf

SODA Conference 2025 Conference Paper

A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix

• Yanlin Chen 0001
• András Gilyén
• Ronald de Wolf

FOCS Conference 2020 Conference Paper

Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving

• Simon Apers
• Ronald de Wolf

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, “spectral sparsification” reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. The breakthrough work by Benczúr and Karger (STOC'96) and Spielman and Teng (STOC'04) showed that sparsification can be done optimally in time near-linear in the number of edges of the original graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with n nodes and m edges, outputs a classical description of an ε-spectral sparsifier in sublinear time ~O(√{mn/ε). We prove that this is tight up to polylog-factors. The algorithm builds on a string of existing results, most notably sparsification algorithms by Spielman and Srivastava (STOC'08) and Koutis and Xu (TOPC'16), a spanner construction by Thorup and Zwick (STOC'01), a single-source shortest paths quantum algorithm by Dürr et al. (ICALP'04) and an efficient k-wise independent hash construction by Christiani, Pagh and Thorup (STOC'15). Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut.

FOCS Conference 2019 Conference Paper

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

• Makrand Sinha
• Ronald de Wolf

Chattopadhyay, Mande and Sherif (CMS19) recently exhibited a total Boolean function, the sink function, that has polynomial approximate rank and polynomial randomized communication complexity. This gives an exponential separation between randomized communication complexity and logarithm of the approximate rank, refuting the log-approximate-rank conjecture. We show that even the quantum communication complexity of the sink function is polynomial, thus also refuting the quantum log-approximate-rank conjecture. Our lower bound is based on the fooling distribution method introduced by Rao and Sinha (Theory Comput. , 2018) for the classical case and extended by Anshu, Touchette, Yao and Yu (STOC, 2017) for the quantum case. We also give a new proof of the classical lower bound using the fooling distribution method.

JMLR Journal 2018 Journal Article

Optimal Quantum Sample Complexity of Learning Algorithms

• Srinivasan Arunachalam
• Ronald de Wolf

In learning theory, the VC dimension of a concept class $C$ is the most common way to measure its “richness.” A fundamental result says that the number of examples needed to learn an unknown target concept $c\in C$ under an unknown distribution $D$, is tightly determined by the VC dimension $d$ of the concept class $C$. Specifically, in the PAC model $$ \Theta\Big(\frac{d}{\epsilon} + \frac{\log(1/\delta)}{\epsilon}\Big) $$ examples are necessary and sufficient for a learner to output, with probability $1-\delta$, a hypothesis $h$ that is $\epsilon$-close to the target concept $c$ (measured under $D$). In the related agnostic model, where the samples need not come from a $c\in C$, we know that $$ \Theta\Big(\frac{d}{\epsilon^2} + \frac{\log(1/\delta)}{\epsilon^2}\Big) $$ examples are necessary and sufficient to output an hypothesis $h\in C$ whose error is at most $\epsilon$ worse than the error of the best concept in $C$. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson (1999), who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atıcı and Servedio (2005), improved by Zhang (2010), showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is $$ \Omega\Big(\frac{d^{1-\eta}}{\epsilon} + d + \frac{\log(1/\delta)}{\epsilon}\Big)\mbox{ for arbitrarily small constant }\eta>0. $$ Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a $\log(d/\epsilon)$ factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the “Pretty Good Measurement” on the quantum state-identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class $C$. [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

FOCS Conference 2017 Conference Paper

Quantum SDP-Solvers: Better Upper and Lower Bounds

• Joran van Apeldoorn
• András Gilyén
• Sander Gribling
• Ronald de Wolf

Brandao and Svore 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 optimizations 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 is approximately n, which is the same as classical.

SODA Conference 2016 Conference Paper

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

• Andris Ambainis
• Aleksandrs Belovs
• Oded Regev 0001
• Ronald de Wolf

In the k -junta testing problem, a tester has to efficiently decide whether a given function f: {0, 1} n → {0, 1} is a k -junta (i. e. , depends on at most k of its input bits) or is ∊ -far from any k -junta. Our main result is a quantum algorithm for this problem with query complexity and time complexity. This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω( k 1/3 ) queries for junta-testing (for constant ∊ ).

STOC Conference 2012 Conference Paper

Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

• Samuel Fiorini
• Serge Massar
• Sebastian Pokutta
• Hans Raj Tiwary
• Ronald de Wolf

We solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

FOCS Conference 2008 Conference Paper

A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs

• Avraham Ben-Aroya
• Oded Regev 0001
• Ronald de Wolf

The Bonami-Beckner hypercontractive inequality is a powerful tool in Fourier analysis of real-valued functions on the Boolean cube. In this paper we present a version of this inequality for matrix-valued functions on the Boolean cube. Its proof is based on a powerful inequality by Ball, Carlen, and Lieb. We also present a number of applications. First, we analyze maps that encode n classical bits into m qubits, in such a way that each set of k bits can be recovered with some probability by an appropriate measurement on the quantum encoding; we show that if m < 0. 7 n, then the success probability is exponentially small in k. This result may be viewed as a direct product version of Nayak's quantum random access code bound. It in turn implies strong direct product theorems for the one-way quantum communication complexity of Disjointness and other problems. Second, we prove that error-correcting codes that are locally decodable with 2 queries require length exponential in the length of the encoded string. This gives what is arguably the first "non-quantum" proof of a result originally derived by Kerenidis and de Wolf using quantum information theory.

STOC Conference 2007 Conference Paper

Exponential separations for one-way quantum communication complexity, with applications to cryptography

• Dmitry Gavinsky
• Julia Kempe
• Iordanis Kerenidis
• Ran Raz
• Ronald de Wolf

We give an exponential separation between one-way quantum and classical communication protocols for twopartial Boolean functions, both of which are variants of the Boolean Hidden Matching Problem of Bar-Yossef et al. Earlier such an exponential separation was known only for a relational version of the Hidden Matching Problem. Our proofs use the Fourier coefficients inequality of Kahn, Kalai, and Linial. We give a number of applications of this separation. In particular, in the bounded-storage model of cryptography we exhibita scheme that is secure against adversaries with a certain amount of classical storage, but insecure against adversaries with a similar (or even much smaller) amount of quantum storage; in the setting of privacy amplification, we show that there are strong extractors that yield a classically secure key, but are insecure against a quantum adversary.

STOC Conference 2006 Conference Paper

A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs

• Andris Ambainis
• Robert Spalek
• Ronald de Wolf

We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal.

STOC Conference 2006 Conference Paper

Bounded-error quantum state identification and exponential separations in communication complexity

• Dmitry Gavinsky
• Julia Kempe
• Oded Regev 0001
• Ronald de Wolf

We consider the problem of bounded-error quantum state identification: given either state α 0 or state α 1 , we are required to output '0', '1' or 'DONO' ("don't know"), such that conditioned on outputting '0' or '1', our guess is correct with high probability. The goal is to maximize the probability of not outputting 'DONO'. We prove a direct product theorem: if we're given two such problems, with optimal probabilities a and b, respectively, and the states in the first problem are pure, then the optimal probability for the joint bounded-error state identification problem is O(ab). Our proof is based on semidefinite programming duality and may be of wider interest.Using this result, we present two exponential separations in the simultaneous message passing model of communication complexity. First, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared randomness, but needs Ω(n 1/3 ) communication if the parties don't share randomness, even if communication is quantum. This shows the optimality of Yao's recent exponential simulation of shared-randomness protocols by quantum protocols without shared randomness. Second, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared entanglement, but needs Ω((n/log n) 1/3 ) communication if the parties share randomness but no entanglement, even if communication is quantum. This is the first example in communication complexity where entanglement buys you much more than quantum communication does.

FOCS Conference 2004 Conference Paper

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

• Hartmut Klauck
• Robert Spalek
• Ronald de Wolf

A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overall success probability is exponentially small in k. We establish such theorems for the classical as well as quantum query complexity of the OR function. This implies slightly weaker direct product results for all total functions. We prove a similar result for quantum communication protocols computing k instances of the disjointness function. These results imply a time-space tradeoff T/sup 2/S = /spl Omega/(N/sup 3/) for sorting N items on a quantum computer, which is optimal up to polylog factors. They also give several tight time-space and communication-space tradeoffs for the problems of Boolean matrix-vector multiplication and matrix multiplication.

STOC Conference 2003 Conference Paper

Exponential lower bound for 2-query locally decodable codes via a quantum argument

• Iordanis Kerenidis
• Ronald de Wolf

A locally decodable code encodes n -bit strings x in m -bit codewords C(x) , in such a way that one can recover any bit x i from a corrupted codeword by querying only a few bits of that word. We use a quantum argument to prove that LDCs with 2 classical queries need exponential length: m=2 Ω(n) . Previously this was known only for linear codes (Goldreich et al. 02). Our proof shows that a 2-query LDC can be decoded with only 1 quantum query, and then proves an exponential lower bound for such 1-query locally quantum-decodable codes. We also show that q quantum queries allow more succinct LDCs than the best known LDCs with q classical queries. Finally, we give new classical lower bounds and quantum upper bounds for the setting of private information retrieval. In particular, we exhibit a quantum 2 server PIR scheme with O(n 3/10 ) qubits of communication, improving upon the O(n 1/3 ) bits of communication of the best known classical 2-server PIR.

TCS Journal 2002 Journal Article

Complexity measures and decision tree complexity: a survey

• Harry Buhrman
• Ronald de Wolf

We discuss several complexity measures for Boolean functions: certificate complexity, sensitivity, block sensitivity, and the degree of a representing or approximating polynomial. We survey the relations and biggest gaps known between these measures, and show how they give bounds for the decision tree complexity of Boolean functions on deterministic, randomized, and quantum computers.

TCS Journal 2002 Journal Article

Quantum communication and complexity

• Ronald de Wolf

In the setting of communication complexity, two distributed parties want to compute a function depending on both their inputs, using as little communication as possible. The required communication can sometimes be significantly lowered if we allow the parties the use of quantum communication. We survey the main results of the young area of quantum communication complexity: its relation to teleportation and dense coding, the main examples of fast quantum communication protocols, lower bounds, and some applications.

TCS Journal 2001 Journal Article

Marked PCP is decidable

• Vesa Halava
• Mika Hirvensalo
• Ronald de Wolf

We show that the marked version of the Post Correspondence Problem, where the words on a list are required to differ in the first letter, is decidable. On the other hand, we prove that the PCP remains undecidable if we only require the words to differ in the first two letters. Thus we locate the decidability/undecidability-boundary between marked and 2-marked PCP.

FOCS Conference 2000 Conference Paper

Private Quantum Channels

• Andris Ambainis
• Michele Mosca
• Alain Tapp
• Ronald de Wolf

We investigate how a classical private key can be used by two players, connected by an insecure one-way quantum channel, to perform private communication of quantum information. In particular, we show that in order to transmit n qubits privately, 2n bits of shared private key are necessary and sufficient. This result may be viewed as the quantum analogue of the classical one-time pad encryption scheme.

FOCS Conference 1999 Conference Paper

Bounds for Small-Error and Zero-Error Quantum Algorithms

• Harry Buhrman
• Richard Cleve
• Ronald de Wolf
• Christof Zalka

We present a number of results related to quantum algorithms with small error probability and quantum algorithms that are zero-error. First, we give a tight analysis of the trade-offs between the number of queries of quantum search algorithms, their error probability, the size of the search space, and the number of solutions in this space. Using this, we deduce new lower and upper bounds for quantum versions of amplification problems. Next, we establish nearly optimal quantum-classical separations for the query complexity of monotone functions in the zero-error model (where our quantum zero-error model is defined so as to be robust when the quantum gates are noisy). Also, we present a communication complexity problem related to a total function for which there is a quantum-classical communication complexity gap in the zero-error model. Finally, we prove separations for monotone graph properties in the zero-error and other error models which imply that the evasiveness conjecture for such properties does not hold for quantum computers.

FOCS Conference 1998 Conference Paper

Quantum Lower Bounds by Polynomials

• Robert Beals
• Harry Buhrman
• Richard Cleve
• Michele Mosca
• Ronald de Wolf

We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0, 1}/sup N/ in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i. e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T/sup 6/) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.

ECAI Conference 1996 Conference Paper

A Complete Method for Program Specialization Based on Unfolding

• Shan-Hwei Nienhuys-Cheng
• Ronald de Wolf