Zobrazeno 1 - 10
of 76
pro vyhledávání: '"Jeffery, Stacey"'
Autor:
Jeffery, Stacey, Pass, Galina
We introduce an object called a \emph{subspace graph} that formalizes the technique of multidimensional quantum walks. Composing subspace graphs allows one to seamlessly combine quantum and classical reasoning, keeping a classical structure in mind,
Externí odkaz:
http://arxiv.org/abs/2401.08355
Publikováno v:
Quantum 8, 1444 (2024)
Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction (exactness). Second, through careful accounting (thr
Externí odkaz:
http://arxiv.org/abs/2311.15873
Publikováno v:
TQC 2023
We present a quantum algorithm for sampling an edge on a path between two nodes s and t in an undirected graph given as an adjacency matrix, and show that this can be done in query complexity that is asymptotically the same, up to log factors, as the
Externí odkaz:
http://arxiv.org/abs/2303.03319
Publikováno v:
31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 10:1-10:17 (2023)
Undirected $st$-connectivity is important both for its applications in network problems, and for its theoretical connections with logspace complexity. Classically, a long line of work led to a time-space tradeoff of $T=\tilde{O}(n^2/S)$ for any $S$ s
Externí odkaz:
http://arxiv.org/abs/2212.00094
Autor:
Jeffery, Stacey
An important tool in algorithm design is the ability to build algorithms from other algorithms that run as subroutines. In the case of quantum algorithms, a subroutine may be called on a superposition of different inputs, which complicates things. Fo
Externí odkaz:
http://arxiv.org/abs/2209.14146
Autor:
Jeffery, Stacey, Zur, Sebastian
While the quantum query complexity of $k$-distinctness is known to be $O\left(n^{3/4-1/4(2^k-1)}\right)$ for any constant $k \geq 4$, the best previous upper bound on the time complexity was $\widetilde{O}\left(n^{1-1/k}\right)$. We give a new upper
Externí odkaz:
http://arxiv.org/abs/2208.13492
Autor:
Dulek, Yfke, Jeffery, Stacey, Majenz, Christian, Schaffner, Christian, Speelman, Florian, de Wolf, Ronald
In theoretical computer science, conferences play an important role in the scientific process. The decisions whether to accept or reject articles is taken by the program committee (PC) members. Serving on a PC for the first time can be a daunting exp
Externí odkaz:
http://arxiv.org/abs/2105.02773
Publikováno v:
Proceedings of the 19th Theory of Cryptography Conference (TCC 2021), pp. 90-120
Quantum cryptography is known for enabling functionalities that are unattainable using classical information alone. Recently, Secure Software Leasing (SSL) has emerged as one of these areas of interest. Given a target circuit $C$ from a circuit class
Externí odkaz:
http://arxiv.org/abs/2101.12739
Publikováno v:
Proceedings of MFCS 2020, LIPIcs, vol. 170, pp. 26:1--26:14, 978-3-95977-159-7 (2020)
Span programs are an important model of quantum computation due to their tight correspondence with quantum query complexity. For any decision problem $f$, the minimum complexity of a span program for $f$ is equal, up to a constant factor, to the quan
Externí odkaz:
http://arxiv.org/abs/2005.01323
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
Externí odkaz:
http://arxiv.org/abs/1912.04233