3 papers
quant-ph2026
Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM
Fuyuki Kitagawa, Ryo Nishimaki, Agi Villanyi +1
We make progress towards the impossibility of imperfectly complete quantum-computation, classical-communication (QCCC) key agreement by constructing the first unconditional attacks…
quant-ph2026
A Relativizing MIP for BQP
Scott Aaronson, Anand Natarajan, Avishay Tal +1
Complexity class containments involving interactive proof classes are famously nonrelativizing: although , Fortnow and Sipser showed that that there…
quant-ph2025
Exponential Quantum Advantage for Simulating Open Classical Systems
Agi Villanyi, Yariv Yanay, Ari Mizel
A recent promising arena for quantum advantage is simulating exponentially large classical systems. Here, we show how this advantage can be used to calculate the dynamics of open c…