235 citations · 405 across the 36 of their papers we have counts for
5 papers · 1 filter
Cryptography from Pseudorandom Quantum States
Prabhanjan Ananth, Luowen Qian, Henry Yuen
Pseudorandom states, introduced by Ji, Liu and Song (Crypto'18), are efficiently-computable quantum states that are computationally indistinguishable from Haar-random states. One-w…
Quantum soundness of testing tensor codes
Zhengfeng Ji, Anand Natarajan, Thomas Vidick +2
A locally testable code is an error-correcting code that admits very efficient probabilistic tests of membership. Tensor codes provide a simple family of combinatorial construction…
Quantum search-to-decision reductions and the state synthesis problem
Sandy Irani, Anand Natarajan, Chinmay Nirkhe +2
It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the $\textit{de…
Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen
We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy, a classification of languages according to the complexity of arithmetical for…
Interactive Proofs for Synthesizing Quantum States and Unitaries
Gregory Rosenthal, Henry Yuen
Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense…