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
∙
01/18/2023
An Automata-based Framework for Verification and Bug Hunting in Quantum Circuits (Technical Report)
We introduce a new paradigm for analysing and finding bugs in quantum ci...
research
∙
06/30/2022
Online TSP with Predictions
We initiate the study of online routing problems with predictions, inspi...
research
∙
12/11/2021
A Note on the Post-Quantum Security of (Ring) Signatures
This work revisits the security of classical signatures and ring signatu...
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
∙
10/10/2021
Group Signatures and Accountable Ring Signatures from Isogeny-based Assumptions
Group signatures are an important cryptographic primitive providing both...
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
∙
12/09/2020
Constant-round Blind Classical Verification of Quantum Sampling
In a recent breakthrough, Mahadev constructed a classical verification o...
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
∙
10/22/2020
On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work
We revisit the so-called compressed oracle technique, introduced by Zhan...
research
∙
08/14/2020
On the Hardness of Massively Parallel Computation
We investigate whether there are inherent limits of parallelization in t...
research
∙
06/10/2020
Tight Quantum Time-Space Tradeoffs for Function Inversion
In function inversion, we are given a function f: [N] ↦ [N], and want to...
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/20/2019
Lower Bounds for Function Inversion with Quantum Advice
Function inversion is that given a random function f: [M] → [N], we want...
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
∙
10/25/2018
On the Sample Complexity of PAC Learning Quantum Process
We generalize the PAC (probably approximately correct) learning model to...
research
∙
03/28/2018
On the Algorithmic Power of Spiking Neural Networks
Spiking Neural Networks (SNN) are mathematical models in neuroscience to...
research
∙
01/11/2018