Theorem 4.8 — exact Hamming-weight counter
OpenQuantumLTF.Majority.theorem_4_8hamming-weightquantum-circuitssection-4
An exact reversible Hamming-weight counter maps to , where . It uses one- and two-qubit gates and has parallel depth .
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Basic import Definitions.Def_QAlgorithms_Defs_Circuit import Definitions.Def_QuantumLTF_Membership_gates12 import Definitions.Def_QuantumLTF_Sections45_Model
Formal statement
namespace QuantumLTF.Majority
open QAlgorithms QuantumLTF.Membership
theorem theorem_4_8 :
∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, 1 ≤ n →
let ℓ := Nat.clog 2 (n + 1)
∃ (c : Circuit gates12 (n + ℓ)) (d : ℕ),
(c.size : ℝ) ≤ C * n * Real.log (n + 1) ∧
(d : ℝ) ≤ C * Real.log (n + 1) ∧ HasDepth c d ∧
∀ T : Qubits n, ∃ v : Qubits ℓ, bitsToNat v = (Finset.univ.filter fun i => T i).card ∧
act c.unitary (ket (Fin.append T fun _ => false)) = ket (Fin.append T v) := by sorry
end QuantumLTF.MajoritySource
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, STOC 2027 submission #347, Theorem 4.8, p. 52 (PDF p. 53), citing ZYN26 Theorem 1.