Linear combination of unitaries (LCU)

The LCU primitive block-encodes a linear combination of unitaries into a larger operator acting on an ancilla control register tensored with the system [Lin22, hermfunc.tex:531].

The SELECT sum and the walk operator are HilbertOperators: they are linear operators used inside a block encoding, not themselves declared as unitary Gates in this file.

def QuantumAlg.lcuProj {a : ℕ} (i : Fin (2 ^ a)) : HilbertOperator a

The control-basis projector |i><i| on the a-qubit control register.

Equations

• QuantumAlg.lcuProj i = Matrix.of fun (r c : Fin (2 ^ a)) => (if r = i then 1 else 0) * if c = i then 1 else 0

noncomputable def QuantumAlg.lcuSelect {a n : ℕ} (U : Fin (2 ^ a) → Gate n) : HilbertOperator (a + n)

The select operator SELECT = sum_i |i><i| ⊗ U_i [Lin22, hermfunc.tex:492].

Equations

• QuantumAlg.lcuSelect U = ∑ i : Fin (2 ^ a), (QuantumAlg.lcuProj i).tensor (U i).op

def QuantumAlg.lcuNorm {a : ℕ} (alpha : Fin (2 ^ a) → ℝ) : ℝ

The coefficient 1-norm lambda = sum_i alpha_i for nonnegative coefficients.

Equations

• QuantumAlg.lcuNorm alpha = ∑ i : Fin (2 ^ a), alpha i

noncomputable def QuantumAlg.lcuWalk {a n : ℕ} (V : Gate a) (U : Fin (2 ^ a) → Gate n) : HilbertOperator (a + n)

The LCU walk operator W = (V† ⊗ I) · SELECT · (V ⊗ I).

Equations

• QuantumAlg.lcuWalk V U = V.conjTranspose.op.tensor 1 * QuantumAlg.lcuSelect U * V.op.tensor 1

theorem QuantumAlg.lcuWalk_eq_sum {a n : ℕ} (V : Gate a) (U : Fin (2 ^ a) → Gate n) : lcuWalk V U = ∑ i : Fin (2 ^ a), (V.conjTranspose.op * lcuProj i * V.op).tensor (U i).op

The LCU walk operator expands into a control-block sum.

theorem QuantumAlg.LinearCombinationOfUnitaries.main {a n : ℕ} (V : Gate a) (U : Fin (2 ^ a) → Gate n) (alpha : Fin (2 ^ a) → ℝ) (halpha : ∀ (i : Fin (2 ^ a)), 0 ≤ alpha i) (hlam : 0 < lcuNorm alpha) (hV : ∀ (i : Fin (2 ^ a)), V.op i 0 = ↑√(alpha i / lcuNorm alpha)) (s t : Fin (2 ^ n)) : lcuWalk V U (prodEquiv (0, s)) (prodEquiv (0, t)) = (↑(lcuNorm alpha))⁻¹ * ∑ i : Fin (2 ^ a), ↑(alpha i) * (U i).op s t

LCU block encoding [Lin22, hermfunc.tex:531].