Source author record

Yixin Shen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

quant-ph Computational Complexity Data Structures and Algorithms Cryptography and Security

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Quantum Augmented Dual Attack

We present a quantum augmented variant of the dual lattice attack on the Learning with Errors (LWE) problem, using classical memory with quantum random access (QRACM). Applying our results to lattice parameters from the literature, we find that our algorithm outperforms previous algorithms, assuming unit cost access to a QRACM. On a technical level, we show how to obtain a quantum speedup on the search for Fast Fourier Transform (FFT) coefficients above a given threshold by leveraging the relative sparseness of the FFT and using quantum amplitude estimation. We also discuss the applicability of the Quantum Fourier Transform in this context. Furthermore, we give a more rigorous analysis of the classical and quantum expected complexity of guessing part of the secret vector where coefficients follow a discrete Gaussian (mod $q$ ).

preprint2022arXiv

Finding many Collisions via Reusable Quantum Walks

Given a random function $f$ with domain $[2^n]$ and codomain $[2^m]$ , with $m \geq n$ , a collision of $f$ is a pair of distinct inputs with the same image. Collision finding is an ubiquitous problem in cryptanalysis, and it has been well studied using both classical and quantum algorithms. Indeed, the quantum query complexity of the problem is well known to be $Θ(2^{m/3})$ , and matching algorithms are known for any value of $m$ . The situation becomes different when one is looking for multiple collision pairs. Here, for $2^k$ collisions, a query lower bound of $Θ(2^{(2k+m)/3})$ was shown by Liu and Zhandry (EUROCRYPT~2019). A matching algorithm is known, but only for relatively small values of $m$ , when many collisions exist. In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters where the lower bound is met. Our new method relies on a chained quantum walk algorithm, which might be of independent interest. It allows to extract multiple solutions of an MNRS-style quantum walk, without having to recompute it entirely: after finding and outputting a solution, the current state is reused as the initial state of another walk. As an application, we improve the quantum sieving algorithms for the shortest vector problem (SVP), with a complexity of $2^{0.2563d + o(d)}$ instead of the previous $2^{0.2570d + o(d)}$ .

preprint2020arXiv

Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most $k$ . We call this the $Dyck_{k,n}$ problem. We prove a lower bound of $Ω(c^k \sqrt{n})$ , showing that the complexity of this problem increases exponentially in $k$ . Here $n$ is the length of the word. When $k$ is a constant, this is interesting as a representative example of star-free languages for which a surprising $\tilde{O}(\sqrt{n})$ query quantum algorithm was recently constructed by Aaronson et al. Their proof does not give rise to a general algorithm. When $k$ is not a constant, $Dyck_{k,n}$ is not context-free. We give an algorithm with $O\left(\sqrt{n}(\log{n})^{0.5k}\right)$ quantum queries for $Dyck_{k,n}$ for all $k$ . This is better than the trival upper bound $n$ for $k=o\left(\frac{\log(n)}{\log\log n}\right)$ . Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of $Ω(n^{1.5-ε})$ for the directed 2D grid and $Ω(n^{2-ε})$ for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.

preprint2020arXiv

Quantum Query Complexity of Dyck Languages with Bounded Height

We consider the problem of determining if a sequence of parentheses is well parenthesized, with a depth of at most h. We denote this language as $Dyck_h$ . We study the quantum query complexity of this problem for different h as function of the length n of the word. It has been known from a recent paper by Aaronson et al. that, for any constant h, since $Dyck_h$ is star-free, it has quantum query complexity $\tildeΘ(\sqrt{n})$ , where the hidden logarithm factors in $\tildeΘ$ depend on h. Their proof does not give rise to an algorithm. When h is not a constant, $Dyck_h$ is not even context-free. We give an algorithm with $O\left(\sqrt{n}\log(n)^{0.5h}\right)$ quantum queries for $Dyck_h$ for all h. This is better than the trival upper bound $n$ when $h=o(\frac{\log(n)}{\log\log n})$ . We also obtain lower bounds: we show that for every $0<ε\leq 0.37$ , there exists $c>0$ such that $Q(\text{Dyck}_{c\log(n)}(n))=Ω(n^{1-ε})$ . When $h=ω(\log(n))$ , the quantum query complexity is close to $n$ , i.e. $Q(\text{Dyck}_h(n))=ω(n^{1-ε})$ for all $ε>0$ . Furthermore when $h=Ω(n^ε)$ for some $ε>0$ , $Q(\text{Dyck}_{h}(n))=Θ(n)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.