research
∙
06/22/2023
Unitary Complexity and the Uhlmann Transformation Problem
State transformation problems such as compressing quantum information or...
share
research
∙
06/09/2023
Pseudorandom Strings from Pseudorandom Quantum States
A fundamental result in classical cryptography is that pseudorandom gene...
research
∙
01/23/2023
On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions
Public-key quantum money is a cryptographic proposal for using highly en...
research
∙
01/18/2023
stateQIP = statePSPACE
Complexity theory traditionally studies the hardness of solving classica...
research
∙
11/02/2022
Pseudorandom (Function-Like) Quantum State Generators: New Definitions and Applications
Pseudorandom quantum states (PRS) are efficiently constructible states t...
research
∙
10/12/2022
Unitary property testing lower bounds by polynomials
We study unitary property testing, where a quantum algorithm is given qu...
research
∙
12/18/2021
Cryptography from Pseudorandom Quantum States
Pseudorandom states, introduced by Ji, Liu and Song (Crypto'18), are eff...
research
∙
11/15/2021
Quantum soundness of testing tensor codes
A locally testable code is an error-correcting code that admits very eff...
research
∙
11/04/2021
Quantum search-to-decision reductions and the state synthesis problem
It is a useful fact in classical computer science that many search probl...
research
∙
10/09/2021
Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
We investigate the connection between the complexity of nonlocal games a...
research
∙
08/16/2021
Interactive Proofs for Synthesizing Quantum States and Unitaries
Whereas quantum complexity theory has traditionally been concerned with ...
research
∙
09/27/2020
Quantum soundness of the classical low individual degree test
Low degree tests play an important role in classical complexity theory, ...
research
∙
08/07/2020
Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
Quantum variational algorithms are one of the most promising application...
research
∙
06/01/2020
Quantum Garbled Circuits
We present a garbling scheme for quantum circuits, thus achieving a deco...
research
∙
02/24/2020
On the complexity of zero gap MIP*
The class MIP^* is the set of languages decidable by multiprover interac...
research
∙
02/19/2020
Quantum statistical query learning
We propose a learning model called the quantum statistical learning QSQ ...
research
∙
01/13/2020
MIP*=RE
We show that the class MIP* of languages that can be decided by a classi...
research
∙
05/27/2019
Perfect zero knowledge for quantum multiprover interactive proofs
In this work we consider the interplay between multiprover interactive p...
research
∙
05/30/2018