Theorem 6.12: an efficient quantum Fourier transform for , and
OpenSemisimpleQFT.theorem_6_12Let (with for the walled Brauer algebra). The Fourier transform can be implemented on a quantum computer up to operator norm error
by quantum circuits with gate complexity
The Fourier transform is performed with respect to the subalgebra adapted bases from Section 5.3 and the orthogonal form in Section 5.4.
Precise form. There are absolute constants and such that for every (resp. ), every in the semisimple range ( for , for , for ) and every , there exist a subalgebra adapted system of Fourier bases for the chain of Section 5.3 that is in the orthogonal form and labelled as in Theorem 4.17, and a circuit of one- and two-qubit unitary gates with at most gates, being the expression inside , such that
Here is the normalized Fourier transform of Definition 3.1 from the scaled diagram basis (Eq. (4.10)) to the states ; stores a basis element by the bit string of its diagram and stores by the bit strings of the Bratteli paths and , all remaining qubits being before and after.
import Definitions.Def_SemisimpleQFT_Circuit open scoped BigOperators ComplexConjugate
namespace SemisimpleQFT
theorem theorem_6_12 :
∃ (C : ℝ) (k : ℕ),
(∀ (n d : ℕ) (ε : ℝ), n < d → 0 < ε → ε ≤ 1 →
HasEfficientQFT n (brauerLevel n) d (brauerBratteli n) Shape.size shapeBits
(softO C k ((n : ℝ) ^ ((15 : ℝ) / 2) *
(Real.sqrt (n : ℝ) + Real.log (d : ℝ) + Real.log (1 / ε))))
(C * ((Nat.card (brauerLevel n n) : ℝ) ^ k / Real.sqrt (d : ℝ) + ε))) ∧
(∀ (r s d : ℕ) (ε : ℝ), r ≤ s → r + s < d + 2 → 0 < ε → ε ≤ 1 →
HasEfficientQFT (r + s) (walledLevel r (r + s)) d (walledBratteli r (r + s))
pairSize pairBits
(softO C k (((r + s : ℕ) : ℝ) ^ ((15 : ℝ) / 2) *
(Real.sqrt ((r + s : ℕ) : ℝ) + Real.log (d : ℝ) + Real.log (1 / ε))))
(C * ((Nat.card (walledLevel r (r + s) (r + s)) : ℝ) ^ k / Real.sqrt (d : ℝ) + ε))) ∧
(∀ (n d : ℕ) (ε : ℝ), 2 * n < d + 2 → 0 < ε → ε ≤ 1 →
HasEfficientQFT (2 * n) (partitionLevel n) d (partitionBratteli n) Shape.size shapeBits
(softO C k ((n : ℝ) ^ ((15 : ℝ) / 2) *
((n : ℝ) + Real.log (d : ℝ) + Real.log (1 / ε))))
(C * ((Nat.card (partitionLevel n (2 * n)) : ℝ) ^ k / Real.sqrt (d : ℝ) + ε))) := by sorry
end SemisimpleQFT
Confirmed by the mission captain (proposal self-audit).