Author name cluster

Stacey Jeffery

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

STOC Conference 2023 Conference Paper

Multidimensional Quantum Walks

Stacey Jeffery
Sebastian Zur

While the quantum query complexity of k -distinctness is known to be O ( n 3/4 − 1/4(2 k −1) ) for any constant k ≥ 4 [Belovs, FOCS 2012], the best previous upper bound on the time complexity was O ( n 1−1/ k ). We give a new upper bound of O ( n 3/4 − 1/4(2 k −1) ) on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in O ( n ) queries and O ( n 2 ) time using this new technique, showing that the new quantum walk framework can achieve exponential speedups.

Details

STOC Conference 2020 Conference Paper

Quadratic speedup for finding marked vertices by quantum walks

Andris Ambainis
András Gilyén
Stacey Jeffery
Martins Kokainis

A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.

Details

MFCS Conference 2020 Conference Paper

Span Programs and Quantum Time Complexity

Arjan Cornelissen
Stacey Jeffery
Maris Ozols
Alvaro Piedrafita

Span programs are an important model of quantum computation due to their correspondence with quantum query and space complexity. While the query complexity of quantum algorithms obtained from span programs is well-understood, it is not generally clear how to implement certain query-independent operations in a time-efficient manner. In this work, we prove an analogous connection for quantum time complexity. In particular, we show how to convert a sufficiently-structured quantum algorithm for f with time complexity T into a span program for f such that it compiles back into a quantum algorithm for f with time complexity 𝒪̃(T). This shows that for span programs derived from algorithms with a time-efficient implementation, we can preserve the time efficiency when implementing the span program, which means that span programs capture time, query and space complexities and are a complete model of quantum algorithms. One practical advantage of being able to convert quantum algorithms to span programs in a way that preserves time complexity is that span programs compose very nicely. We demonstrate this by improving Ambainis’s variable-time quantum search result using our construction through a span program composition for the OR function.

Details

MFCS Conference 2016 Conference Paper

Quantum Communication Complexity of Distributed Set Joins

Stacey Jeffery
François Le Gall

Computing set joins of two inputs is a common task in database theory. Recently, Van Gucht, Williams, Woodruff and Zhang [PODS 2015] considered the complexity of such problems in the natural model of (classical) two-party communication complexity and obtained tight bounds for the complexity of several important distributed set joins. In this paper we initiate the study of the quantum communication complexity of distributed set joins. We design a quantum protocol for distributed Boolean matrix multiplication, which corresponds to computing the composition join of two databases, showing that the product of two n times n Boolean matrices, each owned by one of two respective parties, can be computed with widetilde-O(sqrt{n} ell^{3/4}) qubits of communication, where ell denotes the number of non-zero entries of the product. Since Van Gucht et al. showed that the classical communication complexity of this problem is widetilde-Theta(n sqrt{ell}), our quantum algorithm outperforms classical protocols whenever the output matrix is sparse. We also show a quantum lower bound and a matching classical upper bound on the communication complexity of distributed matrix multiplication over F_2. Besides their applications to database theory, the communication complexity of set joins is interesting due to its connections to direct product theorems in communication complexity. In this work we also introduce a notion of all-pairs product theorem, and relate this notion to standard direct product theorems in communication complexity.

Details

SODA Conference 2013 Conference Paper

Nested Quantum Walks with Quantum Data Structures

Stacey Jeffery
Robin Kothari
Frédéric Magniez

We develop a new framework that extends the quantum walk framework of Magniez, Nayak, Roland, and Santha, by utilizing the idea of quantum data structures to construct an efficient method of nesting quantum walks. Surprisingly, only classical data structures were considered before for searching via quantum walks. The recently proposed learning graph framework of Belovs has yielded improved upper bounds for several problems, including triangle finding and more general subgraph detection. We exhibit the power of our framework by giving a simple explicit constructions that reproduce both the O ( n 35/27 ) and O ( n 9/7 ) learning graph upper bounds (up to logarithmic factors) for triangle finding, and discuss how other known upper bounds in the original learning graph framework can be converted to algorithms in our framework. We hope that the ease of use of this framework will lead to the discovery of new upper bounds.

Details