QMA Lower Bounds for Batch Verification via Approximate Degree

Mark Bun, Mandar Juvekar, Samuel King

We study batch verification in QMA query and communication complexity, where the goal is to understand how the resources needed to verify $m$ copies of a Boolean function $f$ depen…