§3.1 — resource counts of the encryption and decryption procedures
ProvedPauliUnclonable531.Pauli.resource_countscryptographyquantum-information
Fix and a nonidentity Pauli key on qubits. The generated §3.1 procedures satisfy the following resource bounds.
- The pivot found by the left-to-right key scan exists and is the least nonidentity position: it is a position with and for all .
- The random tapes (bit strings vanishing at the pivot) number exactly .
- The encryption instruction list contains exactly fair coin draws, exactly computational-basis preparations, and at most gates.
- Its classical address-bit cost , with the instruction-list length, is at most .
- The decryption instruction list has at most local Pauli measurements, and its cost is at most .
These are the efficiency claims of Theorem 1.1: encryption and decryption run in time in the declared bit-cost model, using random bits, basis preparations and single-qubit Clifford gates or measurements.
Formalization Note. The counts are of the concrete instruction lists encProgram k and decProgram k; the cost functions encBitCost and decBitCost are the mission's declared address-bit cost model, in which each wire address occupies bits.
Differences from the source:
- encoding: finite-dimensional complex Hilbert-space operators and binary strings → complex matrices indexed by finite computational bases, Fin 2 bits and real Born probabilities; reason: these are the same finite-dimensional objects after choosing the source basis
Preamble
import Mathlib import Definitions.Def_PauliUnclonable531_Pauli_Ensemble open scoped Matrix Matrix.Norms.L2Operator ComplexOrder set_option autoImplicit false
Formal statement
namespace PauliUnclonable531.Pauli
theorem resource_counts (n : ℕ) (hn : 1 ≤ n) (k : Key n) :
(∃ j, pivot k = some j ∧ active k.val j = true ∧
∀ i : Fin n, i < j → active k.val i = false) ∧
Fintype.card (Tape k) = 2^(n-1) ∧
fairCount (encProgram k) = n-1 ∧ preparationCount (encProgram k) = n ∧
gateCount (encProgram k) ≤ 2*n ∧ encBitCost k ≤ 100*(n+1)^2 ∧
(decProgram k).length ≤ n ∧ decBitCost k ≤ 100*(n+1)^2 := by sorry
end PauliUnclonable531.Pauli
Source
Prabhanjan Ananth, Seyoon Ragavan, Amit Sahai, STOC 2027 submission #531 (October 2026) / arXiv:2607.21551v4, Theorem 1.1 (efficiency clause), p.3, and §3.1, pp.16–17