research
∙
05/21/2023
On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation
Hamiltonian simulation is one of the most important problems in the fiel...
share
research
∙
05/10/2022
Classical verification of quantum depth
We present two protocols for classical verification of quantum depth. Ou...
research
∙
11/16/2021
Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round
From the minimal assumption of post-quantum semi-honest oblivious transf...
research
∙
08/06/2021
Quantum Meets the Minimum Circuit Size Problem
In this work, we initiate the study of the Minimum Circuit Size Problem ...
research
∙
03/20/2021
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
We investigate the existence of constant-round post-quantum black-box ze...
research
∙
11/05/2020
A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first...
research
∙
12/02/2019
Classical Verification of Quantum Computations with Efficient Verifier
In this paper, we extend the protocol of classical verification of quant...
research
∙
11/05/2019
On the Quantum Complexity of Closest Pair and Related Problems
The closest pair problem is a fundamental problem of computational geome...
research
∙
10/14/2019
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
We present an algorithmic framework generalizing quantum-inspired polylo...
research
∙
09/23/2019
On the Need for Large Quantum Depth
Near-term quantum computers are likely to have small depths due to short...
research
∙
01/10/2019
Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches
Semidefinite programming (SDP) is a central topic in mathematical optimi...
research
∙
11/12/2018
Quantum-inspired sublinear classical algorithms for solving low-rank linear systems
We present classical sublinear-time algorithms for solving low-rank line...
research
∙
04/27/2018