Stacey Jeffery

Stacey Jeffery

Auto-generated profile, based on publicly available information

Stacey Jeffery

QuSoft and CWI Amsterdam the Netherlands

Research Focus & Metrics

Academic Career Length

10Years (2017-Present)

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

Representative Publications

View All Publications
14 November 2018 in Algorithmica
Verified
Journal Article
Closed access
PDF file
TITsuyoshi Ito
Tsuyoshi Ito
SJStacey Jeffery
Stacey Jeffery

17 August 2017 in Quantum
Verified
Journal Article
Open access
PDF file
SJStacey Jeffery
Stacey Jeffery
SKShelby Kimmel
Shelby Kimmel
We give a new upper bound on the quantum query complexity of decidingst-connectivity on certain classes of planar graphs, and show the bound is sometimes exponentially better than previous results. We then show Boolean formula evaluation reduces to deciding connectivity on just such a class of graphs. Applying the algorithm forst-connectivity to Boolean formula evaluation problems, we match theO(N)bound on the quantum query complexity of evaluating formulas onNvariables, give a quadratic speed-up over the classical query complexity of a certain class of promise Boolean formulas, and show this approach can yield superpolynomial quantum/classical separations. These results indicate that thisst-connectivity-based approach may be the "right" way of looking at quantum algorithms for formula evaluation.

3 September 2018 in arXiv
Verified
Preprint
Open access
PDF file
SCShantanav Chakraborty
Shantanav Chakraborty
AGAndrás Gilyén
András Gilyén
SJStacey Jeffery
Stacey Jeffery
We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms and derive general results that are applicable to a variety of input models, including sparse matrix oracles and matrices stored in a data structure. We develop several tools within the block-encoding framework, such as singular value estimation of a block-encoded matrix, and quantum linear system solvers using block-encodings. The presented results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices. In addition, we develop a technique of variable-time amplitude estimation, based on Ambainis' variable-time amplitude amplification technique, which we are also able to apply within the framework. As applications, we design the following algorithms: (1) a quantum algorithm for the quantum weighted least squares problem, exhibiting a 6-th power improvement in the dependence on the condition number and an exponential improvement in the dependence on the precision over the previous best algorithm of Kerenidis and Prakash; (2) the first quantum algorithm for the quantum generalized least squares problem; and (3) quantum algorithms for estimating electrical-network quantities, including effective resistance and dissipated power, improving upon previous work.

13 February 2025 in arXiv
Verified
Preprint
Open access
PDF file
SJStacey Jeffery
Stacey Jeffery
Composition is something we take for granted in classical algorithms design, and in particular, we take it as a basic axiom that composing ``efficient'' algorithms should result in an ``efficient'' algorithm -- even using this intuition to justify our definition of ``efficient.'' Composing quantum algorithms is a much more subtle affair than composing classical algorithms. It has long been known that zero-error quantum algorithms \emph{do not} compose, but it turns out that, using the right algorithmic lens, bounded-error quantum algorithms do. In fact, in the bounded-error setting, quantum algorithms can even avoid the log factor needed in composing bounded-error randomized algorithms that comes from amplifying the success probability via majority voting. In this article, aimed at a general computer science audience, we try to give some intuition for these results: why composing quantum algorithms is tricky, particularly in the zero-error setting, but why it nonetheless works \emph{better} than classical composition in the bounded-error setting.

9 December 2019 in arXiv
Verified
Preprint
Open access
PDF file
SASimon Apers
Simon Apers
AGAndrás Gilyén
András Gilyén
SJStacey Jeffery
Stacey Jeffery
The main results on quantum walk search are scattered over different, incomparable frameworks, most notably the hitting time framework, originally by Szegedy, the electric network framework by Belovs, and the MNRS framework by Magniez, Nayak, Roland and Santha. As a result, a number of pieces are currently missing. For instance, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. In recent work by Ambainis et al., this problem was resolved for the more restricted hitting time framework, in which quantum walks must start from the stationary distribution. We present a new quantum walk search framework that unifies and strengthens these frameworks. This leads to a number of new results. For instance, the new framework not only detects, but finds marked elements in the electric network setting. The new framework also allows one to interpolate between the hitting time framework, which minimizes the number of walk steps, and the MNRS framework, which minimizes the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. Whereas the original frameworks only rely on quantum walks and phase estimation, our new algorithm makes use of a technique called quantum fast-forwarding, similar to the recent results by Ambainis et al. As a final result we show how in certain cases we can simplify this more involved algorithm to merely applying the quantum walk operator some number of times. This answers an open question of Ambainis et al.

9 August 2026
Verified
Book Chapter
Open access
PDF file
LELynn Engelberts
Lynn Engelberts
YCYanlin Chen
Yanlin Chen
AGAmin Shiraz Gilani
Amin Shiraz Gilani
MHMaya-Iggy van Hoof
Maya-Iggy van Hoof
SJStacey Jeffery
Stacey Jeffery
RWRonald de Wolf
Ronald de Wolf
The assumed hardness of the Shortest Vector Problem (SVP) in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension d, they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. k-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of k of the input vectors. Iterating these “sieving steps” sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for \(k=2\), but taking larger k reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from \(2^{0.3098 d}\) to \(2^{0.2846 d}\), using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby “center points” to focus the search on the neighborhoods of these center points. Our algorithm uses \(2^{0.1887d}\) classical bits and QCRAM bits, and \(2^{o(d)}\) qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to \(2^{0.1887d}\).