235 citations · 405 across the 36 of their papers we have counts for
7 papers · 2 filters
An efficient quantum parallel repetition theorem and applications
John Bostanci, Luowen Qian, Nicholas Spooner +1
We prove a tight parallel repetition theorem for -message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We als…
On the Pauli Spectrum of QAC0
Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos +1
The circuit class was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower…
Efficiently stable presentations from error-correcting codes
Michael Chapman, Thomas Vidick, Henry Yuen
We introduce a notion of \emph{efficient stability} for finite presentations of groups. Informally, a finite presentation using generators and relations is \emph{stable} if…
Unitary Complexity and the Uhlmann Transformation Problem
John Bostanci, Yuval Efron, Tony Metger +3
State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot…
Pseudorandom Strings from Pseudorandom Quantum States
Prabhanjan Ananth, Yao-Ting Lin, Henry Yuen
We study the relationship between notions of pseudorandomness in the quantum and classical worlds. Pseudorandom quantum state generator (PRSG), a pseudorandomness notion in the qua…
On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions
Prabhanjan Ananth, Zihan Hu, Henry Yuen
Public-key quantum money is a cryptographic proposal for using highly entangled quantum states as currency that is publicly verifiable yet resistant to counterfeiting due to the la…