BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:UW-Madison-Physics-Events
BEGIN:VEVENT
SEQUENCE:1
UID:UW-Physics-Event-9404
DTSTART:20250917T193000Z
DTEND:20250917T203000Z
DTSTAMP:20260413T084153Z
LAST-MODIFIED:20250916T180421Z
LOCATION:Rm. 3610\, Morgridge Hall
SUMMARY:Succinct Arguments for BatchQMA and Friends under 8 rounds\, W
 isconsin Quantum Institute\, Rishab Goyal\, UW-Madison
DESCRIPTION:</p>We study the problem of minimizing round complexity in
  the context of succinct classical argument systems for quantum comput
 ation. All prior works either require at least 8 rounds of interaction
  between the quantum prover and classical verifier\, or rely on the id
 ealized quantum random oracle model (QROM). We design: <br>
\n <br>
\n
 1. A 4-round public-coin (except for the first message) argument syste
 m for batchQMA languages. Under the post-quantum hardness of functiona
 l encryption and learn- ing with errors (LWE)\, we achieve optimal com
 munication complex- ity (i.e.\, all messages sizes are independent of 
 batch size). If we only rely on the post-quantum hardness of LWE\, the
 n we can make all messages except the verifier’s first message to be
  independent of the batch size.<br>
\n <br>
\n2. A 6-round private-coi
 n argument system for monotone policy batchQMA languages\, under the p
 ost-quantum hardness of LWE. The communication complexity is independe
 nt of the batch size as well as the monotone circuit size. <br>
\n <br
 >
\nUnlike all prior works\, we do not rely on “state-preserving” 
 succinct arguments of knowledge (AoKs) for NP for proving soundness. O
 ur main technical contribution is a new approach to prove soundness wi
 thout rewinding cheating provers. We bring the notion of straight-line
  partial extractability to argument systems for quantum computation.<b
 r>
\n
URL:https://www.physics.wisc.edu/events/?id=9404
END:VEVENT
END:VCALENDAR