Complex binary-weight sum equals `bitsToNat`
ProvedQAlgorithms.bitsToNat_cast_sum_complexbinary-arithmeticfourier-analysisquantum-computing
For an -qubit computational-basis string , summing the complex weights over precisely the wires whose bit is one gives the complex cast of the represented integer bitsToNat z. The indexing is most-significant-bit first, matching the Fourier-transform convention.
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Basic
Formal statement
namespace QAlgorithms
/-- The most-significant-bit wire-weight sum, cast to ℂ, equals `bitsToNat`. -/
theorem bitsToNat_cast_sum_complex {n : ℕ} (z : Qubits n) :
(∑ i : Fin n, if z i then (2 : ℂ) ^ (n - 1 - (i : ℕ)) else 0) =
(bitsToNat z : ℂ) := by sorry
end QAlgorithmsSource
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331, Lemma 3.3, p. 27 (PDF p. 28), Eqs. (44)–(48); binary convention from de Wolf, Quantum Computing: Lecture Notes, §4.5.