BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Yixin Shen

Yixin Shen contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
quant-phComputational ComplexityData Structures and AlgorithmsCryptography and Security

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

4 published item(s)

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\)).

0 citations0 reviewsNo code linkedOpen access
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)}$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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)$.

0 citations0 reviewsNo code linkedOpen access