Measuring the output of a qubit circuit
DefinitionFRouting_Supplement_measureProbf-routingp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-position-verification
For a qubit circuit with no input wires and kept wires, run on with output state , measuring the kept qubits in the computational basis gives the string with probability . For a property of binary strings, .
This gives the output distribution of the bounded-error quantum algorithm of Theorem 7.10: a classical machine prints a circuit, which is run and measured.
Formalization Note Intermediate measurements and classical post-processing are deferred into the circuit by purification, the paper's convention (footnotes 1 and 3).
Definition code
import Definitions.Def_FRouting_Circuit
import Definitions.Def_QAlgorithms_ClassicalStringComputability
set_option autoImplicit false
open Matrix
namespace FRouting.Supplement
open QAlgorithms.Complexity
/-- A computational-basis outcome of `m` qubits as a binary string (`|1⟩ ↦ true`). -/
def bitsOf {m : ℕ} (o : Fin m → Fin 2) : Str :=
List.ofFn fun i => decide (o i = 1)
open scoped Classical in
/-- **The probability that measuring the output of a qubit circuit gives a string in `E`.** A qubit
circuit with no input wires is run on `|0…0⟩`, and its `m` kept qubits are measured in the computational
basis: outcome `o` has the Born probability `⟨o|σ|o⟩`, `σ` the circuit's output state. Used for the
"bounded-error quantum algorithm" of Renard, *Computational Bounds for f-Routing*, arXiv:2609.40278
(held copy, sha256 4a327f29…), Theorem 7.10, p.35.
**Formalization Note** Intermediate measurements and classical post-processing are deferred into the
circuit (purification, the paper's convention, footnotes 1 and 3). -/
noncomputable def measureProb {m : ℕ} (C : Circuit 2 0 m) (E : Str → Prop) : ℝ :=
∑ o : Fin m → Fin 2, if E (bitsOf o) then (C.outputState o o).re else 0
end FRouting.Supplement
Source
Renard, Computational Bounds for f-Routing, arXiv:2609.40278 (held copy, sha256 4a327f29…), Theorem 7.10, p.35