Ancilla bound for iterated QMA amplification
ProvedShiQMAVariableRounds.iter_anc_leamplificationcircuitsqmaquantum-complexityuniformity
The ancilla count is bounded by 3^r times the original count plus input-dependent overhead.
Preamble
import Definitions.Def_ShiQMAVariableRounds import Theorems.Thm_ShiClassQMAAmpX_ampFamilyX_resource_identities_and_regularity import Theorems.Thm_ShiQMAVariableRounds_iter_anc_identity set_option autoImplicit false set_option maxHeartbeats 2000000 open ShiShallow ShiClassQMA ShiClassQMAAmpX ShiQMAVariableRounds
Formal statement
theorem ShiQMAVariableRounds.iter_anc_le (F : QMAFamily) (r n : Nat) :
(iter F r).anc n ≤ 3 ^ r * (F.anc n + 2 * n + 3) := by sorrySource