§4.1, p. 25 — an ε-biased implementation of a two-outcome POVM {M, I − M} gives the (1, a + 1, ε)-block-encoding U′†(I ⊗ CNOT)U′ of M
ProvedQuantumSDP18.MeasureBE.povm_block_encodingLet be a two-outcome POVM on a finite-dimensional system, so and are positive semidefinite. Suppose the measurement is implemented on a quantum computer as follows: attach ancilla qubits in , apply a unitary , and accept when the last ancilla qubit reads . Suppose that this implementation has bias at most , that is, for every density matrix on the system,
Let , (one fresh qubit), and let be controlled by the measured qubit and target the fresh qubit. Then
that is, it is unitary and in the operator norm (Definition 2).
The result says that any reasonable implementation of a measurement yields, at essentially no extra cost, the block-encoding of its POVM element that the paper's quantum operator input model takes as input.
Formalization Note The system is an arbitrary finite type; ancillas, the last of which is measured. The block-encoding predicate is the platform's QAlgorithms.IsBlockEncoding, which takes the ancilla register first, as Definition 2 does; the circuit (written system-first, as on p. 25) is reindexed accordingly, and the all-zero element of the ancillas is . The hypothesis is added; it matters only for a zero-dimensional system, where (14) is vacuous. (14) ranges over all density matrices, as the page's "" over mixed states does.
import Mathlib import Definitions.Def_QAlgorithms_Defs_BlockEncoding import Definitions.Def_QuantumSDP18_MeasureBE_Setting
namespace QuantumSDP18.MeasureBE
open scoped ComplexOrder
/-- §4.1, p. 25: if a two-outcome POVM `{M, I − M}` is implemented by attaching `a` ancilla
qubits in `|0⟩`, applying a unitary `U` and accepting when the last qubit reads `0`, with bias at
most `ε` (equation (14)), then `U′† (I ⊗ CNOT) U′` with `U′ = U ⊗ I₂` is a
`(1, a + 1, ε)`-block-encoding of `M` (Definition 2, p. 4; ancilla register moved first). -/
theorem povm_block_encoding {ι : Type*} [Fintype ι] [DecidableEq ι] (c : ℕ)
(U : Matrix (ι × Anc c) (ι × Anc c) ℂ) (M : Matrix ι ι ℂ) (ε : ℝ)
(hU : U ∈ Matrix.unitaryGroup (ι × Anc c) ℂ) (hM : M.PosSemidef) (hIM : (1 - M).PosSemidef)
(hε : 0 ≤ ε)
(h14 : ∀ ρ : Matrix ι ι ℂ, IsDensity ρ → ‖accProb c U ρ - (M * ρ).trace‖ ≤ ε) :
QAlgorithms.IsBlockEncoding ((ancZero c, false) : Anc c × Bool)
(Matrix.reindex (reorder c) (reorder c)
((Uprime c U).conjTranspose * cnotLast (ι := ι) c * Uprime c U)) 1 ε M := by sorry
end QuantumSDP18.MeasureBE
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.