Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly

Definition
QAlgorithms_Papers_Independent_Support50_P24

by Goku · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

The objects the formalized statements of Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly (arXiv:2209.02907) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • Seven: PDF pp.7,9: seven computational-basis wires, in printed order 1 through 7.
  • SevenMatrix: PDF pp.7,9: operators in the computational basis of the seven wires.
  • QubitSU: PDF p.7: the unknown forward qubit operation, with determinant one.
  • rotationY: PDF p.9, S18: the source's real y rotation.
  • bitFlip: PDF p.9, Fig.S2: Pauli X on a computational qubit.
  • controlledGate: PDF pp.9-10, Figs.S2-S3: a known controlled gate; false is an open control. All wires other than the target retain their computational-basis labels.
  • sevenControlledSwap: PDF pp.9-10: a swap, possibly with fixed computational-basis controls.
  • chronological: PDF pp.9-10: chronological products act on column vectors from the right.
  • cgTwo: PDF p.9, top of Fig.S2: complete three-wire CG circuit, including its padding. The arguments are i1,i2,0 in this order.
  • cgThree: PDF p.9, bottom of Fig.S2: complete four-wire CG circuit. The arguments are j1,m1,m2,i3, and theta=2 arccos(sqrt(2/3)).
  • firstKnown: PDF p.10, upper Fig.S3: the specified fixed V^(1), including every swap.
  • secondKnown: PDF p.10, lower Fig.S3: the specified fixed V^(2), including every swap.
  • CallGate: PDF pp.2,7: fixed known gates and forward unknown calls are distinct syntax. There is no constructor for an unknown adjoint or a controlled unknown operation.
  • PhysicalCalls: PDF pp.2,7: physicality of the fixed inserted matrices, independent of U.
  • calls: PDF pp.2,7: the query count counts exactly the forward-call constructors.
  • evaluateCalls: PDF p.9, S19: evaluateCalls a circuit with the same U substituted at every call.
  • iteration: PDF p.9, S19: one iteration f_U has two forward calls on printed wire 2.
  • fourCircuit: PDF pp.7,9, S1,S21: the actual Fig.S1 circuit consists of two iterations.
  • catalyticCircuit: PDF p.2, Eq.(1): remove only the first call, replacing its output by advice.
  • cleanCircuit: PDF p.4: erase the U dependence of the returned catalyst with one more call.
  • sourceSinglet: PDF p.7: the normalized singlet (|01>-|10>)/sqrt(2).
  • catalyst: PDF p.2: the supplied catalyst is exactly (U tensor I)|singlet>.
  • inputEmbedding: PDF p.9, S20,S24: input on wire 1, singlet on wires 2,3, zeros on 4,...,7.
  • swappedEmbedding: PDF p.9, S25: singlet on wires 1,2, input on wire 3, zeros on 4,...,7.
  • catalyticInput: PDF p.2, Eq.(1): catalyst on input wires 2,3 for that same U.
  • outputEmbedding: PDF p.7, S1: returned catalyst on wires 1,2; the output qubit is wire 3.
  • discardExcept: PDF pp.2,7: trace out all wires except q. The environment is enumerated once, by setting its unused q coordinate to false.
  • ExactInverter: PDF p.2, Theorem 1: exact equality of the induced channel on every operator.
  • SequentialProtocol: PDF pp.4,14, S58: an arbitrary fixed finite-memory causal circuit. Every stage is CPTP, hence includes measurements and classically controlled gates. The memory and all stages are chosen before the unknown U.
  • protocolOutput: PDF p.14, S58: exactly n sequential forward calls, followed by memory discard. The n=0 case is just the fixed preparation channel and discard.
  • TensorCoordinates: PDF pp.15-16: k input-side coordinates and k output-side coordinates.
  • CombCoordinates: PDF pp.16,22: grouping (I1,...,In,F) and (P,O1,...,On).
  • GroupedComb: PDF pp.15-16: operators on both groups of physical comb wires.
  • appendCoordinate: PDF pp.15-16: append the last tensor coordinate, with the displayed wire order.
  • prependCoordinate: PDF p.16: split off P, which is the first output-side coordinate.
  • causalMarginal: PDF p.15, S64: C_(i-1)=Tr_(I_i O_(i-1))(C_i)/d; it is computed, not supplied.
  • SequentialFeasible: PDF p.15, S63-S65: positivity and every causal equality, down to C_0=1. Level zero has one empty tensor word.
  • ParallelFeasible: PDF p.16, S79-S81: one-slot comb for the n parallel calls, in explicit coordinates. B is the marginal Tr_F(C)/identity_(O^n), with Tr_(I^n)(B)=identity_P. These constraints are equivalent to the source's two partial-trace equalities.
  • groupAction: PDF pp.3,22, S128: independent tensor-power actions on the two wire groups.
  • averagingKernel: PDF p.22, S130: conjugation kernel for the concrete two-group Haar average.
  • averageComb: PDF p.22, S130: Haar probability averaging, without a symmetry hypothesis on C.
  • performanceVector: PDF p.16, S77: Choi vector U on (I_j,O_j) and on (F,P), with reference first. The factors are unnormalized; cyclic wire regrouping is explicit in the indices.
  • performanceKernel: PDF p.16, S77: the unnormalized-Choi Haar kernel, with its 1/d^2 factor.
  • performanceOperator: PDF p.16, S77: the actual performance operator, not an arbitrary invariant matrix.
  • inversionObjective: PDF pp.3,16: real scalar average-fidelity objective Tr(C Omega).
  • refocusingNorm: PDF p.26: the paper-specific Hilbert-Schmidt convention sqrt(Tr A†A)/2.
  • qubitChannelFidelity: PDF pp.15,26, S66: squared normalized-Choi fidelity of two qubit unitary channels.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Channel
import Definitions.Def_QAlgorithms_Papers_Independent_Next46_P24
import Definitions.Def_QAlgorithms_Papers_Independent_Frontier18_P14

/-!
arXiv:2209.02907v5. Fixed forward-call circuits and inversion symmetry.
The reviewed, pinned Next46.P24 module supplies SU(d) Haar probability measure
and the physical one-call projectors. Its use is accepted-library reuse under
the independent-paper workflow. No unreviewed chunk is imported.
Wires in the local seven-qubit definitions are zero based: 0 means printed wire 1.
All channel equalities are equalities on matrices, hence include reference systems.
The general-f exactness assertion and four Young-coordinate results are deferred.
Compilation is pending the separately requested mechanical handoff.
-/

noncomputable section

open QAlgorithms MeasureTheory
open scoped BigOperators Matrix ComplexConjugate ComplexOrder Matrix.Norms.Elementwise

namespace QAlgorithms.Papers.Independent.Support50.P24

attribute [local instance] Classical.decEq Classical.propDecidable

/-- PDF pp.7,9: seven computational-basis wires, in printed order 1 through 7. -/
abbrev Seven := Qubits 7

/-- PDF pp.7,9: operators in the computational basis of the seven wires. -/
abbrev SevenMatrix := Matrix Seven Seven ℂ

/-- PDF p.7: the unknown forward qubit operation, with determinant one. -/
abbrev QubitSU := Matrix.specialUnitaryGroup Bool ℂ

/-- PDF p.9, S18: the source's real y rotation. -/
def rotationY (angle : ℝ) : Matrix Bool Bool ℂ :=
  fun a b => if a = b then (Real.cos (angle / 2) : ℂ)
    else if a then (Real.sin (angle / 2) : ℂ) else -(Real.sin (angle / 2) : ℂ)

/-- PDF p.9, Fig.S2: Pauli X on a computational qubit. -/
def bitFlip : Matrix Bool Bool ℂ := fun a b => if a = !b then 1 else 0

/-- PDF pp.9-10, Figs.S2-S3: a known controlled gate; false is an open control.
All wires other than the target retain their computational-basis labels. -/
def controlledGate (controls : List (Fin 7 × Bool)) (target : Fin 7)
    (A : Matrix Bool Bool ℂ) : SevenMatrix :=
  fun x y => if ∀ i, i ≠ target → x i = y i then
    if ∀ c ∈ controls, y c.1 = c.2 then A (x target) (y target)
    else if x target = y target then 1 else 0
  else 0

/-- PDF pp.9-10: a swap, possibly with fixed computational-basis controls. -/
def sevenControlledSwap (controls : List (Fin 7 × Bool)) (a b : Fin 7) : SevenMatrix :=
  fun x y => if x = (if ∀ c ∈ controls, y c.1 = c.2 then
    Function.update (Function.update y a (y b)) b (y a) else y) then 1 else 0

/-- PDF pp.9-10: chronological products act on column vectors from the right. -/
def chronological (gates : List SevenMatrix) : SevenMatrix :=
  gates.foldl (fun accumulated gate => gate * accumulated) 1

/-- PDF p.9, top of Fig.S2: complete three-wire CG circuit, including its padding.
The arguments are i1,i2,0 in this order. -/
def cgTwo (a b c : Fin 7) : SevenMatrix :=
  chronological [
    controlledGate [(a,true),(b,true)] c bitFlip,
    controlledGate [(b,true)] a bitFlip,
    controlledGate [(c,false)] b (rotationY (Real.pi / 2)),
    controlledGate [(a,false),(c,false)] b (rotationY (Real.pi / 2)),
    controlledGate [(b,false)] a bitFlip,
    sevenControlledSwap [] a b,
    sevenControlledSwap [] b c]

/-- PDF p.9, bottom of Fig.S2: complete four-wire CG circuit.
The arguments are j1,m1,m2,i3, and theta=2 arccos(sqrt(2/3)). -/
def cgThree (a b c d : Fin 7) : SevenMatrix :=
  let theta := 2 * Real.arccos (Real.sqrt (2 / 3 : ℝ))
  chronological [
    controlledGate [(a,false)] c bitFlip,
    controlledGate [(c,true),(d,true)] b bitFlip,
    controlledGate [(d,true)] c bitFlip,
    controlledGate [(b,true)] c bitFlip,
    controlledGate [(b,false)] d (rotationY Real.pi),
    controlledGate [(a,true),(b,false),(c,true)] d (rotationY (-theta)),
    controlledGate [(a,true),(b,true),(c,true)] d (rotationY theta),
    controlledGate [(d,true)] a bitFlip,
    controlledGate [] a bitFlip,
    sevenControlledSwap [] b c,
    controlledGate [] b bitFlip,
    controlledGate [(a,true)] b bitFlip,
    sevenControlledSwap [(a,true)] b c,
    controlledGate [(a,true),(b,true)] c bitFlip]

/-- PDF p.10, upper Fig.S3: the specified fixed V^(1), including every swap. -/
def firstKnown : SevenMatrix :=
  chronological [sevenControlledSwap [] 2 5, cgTwo 0 1 2,
    controlledGate [(0,true)] 6 bitFlip, (cgThree 3 4 5 6)ᴴ,
    sevenControlledSwap [] 3 6, sevenControlledSwap [] 1 3]

/-- PDF p.10, lower Fig.S3: the specified fixed V^(2), including every swap. -/
def secondKnown : SevenMatrix :=
  chronological [sevenControlledSwap [] 1 3, cgThree 0 1 2 3,
    sevenControlledSwap [] 4 6, controlledGate [(4,true)] 3 bitFlip,
    sevenControlledSwap [] 5 6, (cgTwo 4 5 6)ᴴ,
    sevenControlledSwap [] 2 4, sevenControlledSwap [] 1 5, sevenControlledSwap [] 0 4]

/-- PDF pp.2,7: fixed known gates and forward unknown calls are distinct syntax.
There is no constructor for an unknown adjoint or a controlled unknown operation. -/
inductive CallGate where
  | known : SevenMatrix → CallGate
  | call : Fin 7 → CallGate

/-- PDF pp.2,7: physicality of the fixed inserted matrices, independent of U. -/
def PhysicalCalls (gates : List CallGate) : Prop :=
  ∀ gate ∈ gates, match gate with
    | .known A => A ∈ Matrix.unitaryGroup Seven ℂ
    | .call _ => True

/-- PDF pp.2,7: the query count counts exactly the forward-call constructors. -/
def calls (gates : List CallGate) : ℕ :=
  (gates.map fun gate => match gate with | .known _ => 0 | .call _ => 1).sum

/-- PDF p.9, S19: evaluateCalls a circuit with the same U substituted at every call. -/
def evaluateCalls (gates : List CallGate) (U : QubitSU) : SevenMatrix :=
  chronological (gates.map fun gate => match gate with
    | .known A => A
    | .call q => controlledGate [] q U.val)

/-- PDF p.9, S19: one iteration f_U has two forward calls on printed wire 2. -/
def iteration : List CallGate :=
  [.call 1, .known firstKnown, .call 1, .known secondKnown]

/-- PDF pp.7,9, S1,S21: the actual Fig.S1 circuit consists of two iterations. -/
def fourCircuit : List CallGate := iteration ++ iteration

/-- PDF p.2, Eq.(1): remove only the first call, replacing its output by advice. -/
def catalyticCircuit : List CallGate :=
  [.known firstKnown, .call 1, .known secondKnown] ++ iteration

/-- PDF p.4: erase the U dependence of the returned catalyst with one more call. -/
def cleanCircuit : List CallGate := fourCircuit ++ [.call 1]

/-- PDF p.7: the normalized singlet (|01>-|10>)/sqrt(2). -/
def sourceSinglet (a b : Bool) : ℂ :=
  QAlgorithms.Papers.Independent.Frontier18.P14.singlet
    ((if a then 1 else 0), (if b then 1 else 0))

/-- PDF p.2: the supplied catalyst is exactly (U tensor I)|singlet>. -/
def catalyst (U : QubitSU) (a b : Bool) : ℂ := ∑ c, U.val a c * sourceSinglet c b

/-- PDF p.9, S20,S24: input on wire 1, singlet on wires 2,3, zeros on 4,...,7. -/
def inputEmbedding : Matrix Seven Bool ℂ := fun x b =>
  if x 0 = b ∧ ∀ i : Fin 7, 3 ≤ i.val → x i = false then sourceSinglet (x 1) (x 2) else 0

/-- PDF p.9, S25: singlet on wires 1,2, input on wire 3, zeros on 4,...,7. -/
def swappedEmbedding : Matrix Seven Bool ℂ := fun x b =>
  if x 2 = b ∧ ∀ i : Fin 7, 3 ≤ i.val → x i = false then sourceSinglet (x 0) (x 1) else 0

/-- PDF p.2, Eq.(1): catalyst on input wires 2,3 for that same U. -/
def catalyticInput (U : QubitSU) : Matrix Seven Bool ℂ := fun x b =>
  if x 0 = b ∧ ∀ i : Fin 7, 3 ≤ i.val → x i = false then catalyst U (x 1) (x 2) else 0

/-- PDF p.7, S1: returned catalyst on wires 1,2; the output qubit is wire 3. -/
def outputEmbedding (U : QubitSU) : Matrix Seven Bool ℂ := fun x b =>
  if x 2 = b ∧ ∀ i : Fin 7, 3 ≤ i.val → x i = false then catalyst U (x 0) (x 1) else 0

/-- PDF pp.2,7: trace out all wires except q. The environment is enumerated once,
by setting its unused q coordinate to false. -/
def discardExcept (q : Fin 7) : Superop Seven Bool := fun X a b =>
  ∑ environment : Seven, if environment q = false then
    X (Function.update environment q a) (Function.update environment q b) else 0

/-- PDF p.2, Theorem 1: exact equality of the induced channel on every operator. -/
def ExactInverter (gates : List CallGate) : Prop :=
  ∀ U : QubitSU, ∀ A : Matrix Bool Bool ℂ,
    discardExcept 2 (conjSuperop (evaluateCalls gates U * inputEmbedding) A) =
      conjSuperop U.valᴴ A

/-- PDF pp.4,14, S58: an arbitrary fixed finite-memory causal circuit.
Every stage is CPTP, hence includes measurements and classically controlled gates.
The memory and all stages are chosen before the unknown U. -/
structure SequentialProtocol (n : ℕ) where
  memory : ℕ
  memoryPositive : 0 < memory
  prepare : Superop Bool (Bool × Fin memory)
  prepareChannel : IsChannel prepare
  afterCall : Fin n → Superop (Bool × Fin memory) (Bool × Fin memory)
  afterCallChannel : ∀ i, IsChannel (afterCall i)

/-- PDF p.14, S58: exactly n sequential forward calls, followed by memory discard.
The n=0 case is just the fixed preparation channel and discard. -/
def protocolOutput {n : ℕ} (A : SequentialProtocol n) (U : QubitSU) : Superop Bool Bool :=
  fun rho =>
    let query := Matrix.kronecker U.val (1 : Matrix (Fin A.memory) (Fin A.memory) ℂ)
    let joint := (List.finRange n).foldl
      (fun state i => A.afterCall i (conjSuperop query state)) (A.prepare rho)
    fun a b => ∑ m : Fin A.memory, joint (a,m) (b,m)

/-- PDF pp.15-16: k input-side coordinates and k output-side coordinates. -/
abbrev TensorCoordinates (d k : ℕ) := Fin k → Fin d

/-- PDF pp.16,22: grouping (I1,...,In,F) and (P,O1,...,On). -/
abbrev CombCoordinates (d k : ℕ) := TensorCoordinates d k × TensorCoordinates d k

/-- PDF pp.15-16: operators on both groups of physical comb wires. -/
abbrev GroupedComb (d k : ℕ) := Matrix (CombCoordinates d k) (CombCoordinates d k) ℂ

/-- PDF p.22: matrix Haar integrals use the finite entrywise topology. -/
local instance groupedContinuousENorm (d k : ℕ) : ContinuousENorm (GroupedComb d k) :=
  inferInstanceAs (ContinuousENorm (CombCoordinates d k → CombCoordinates d k → ℂ))

/-- PDF pp.15-16: append the last tensor coordinate, with the displayed wire order. -/
def appendCoordinate {d k : ℕ} (x : TensorCoordinates d k) (a : Fin d) :
    TensorCoordinates d (k+1) := Fin.lastCases a x

/-- PDF p.16: split off P, which is the first output-side coordinate. -/
def prependCoordinate {d k : ℕ} (a : Fin d) (x : TensorCoordinates d k) :
    TensorCoordinates d (k+1) := Fin.cases a x

/-- PDF p.15, S64: C_(i-1)=Tr_(I_i O_(i-1))(C_i)/d; it is computed, not supplied. -/
def causalMarginal {d k : ℕ} (C : GroupedComb d (k+1)) : GroupedComb d k :=
  fun x y => (∑ a : Fin d, ∑ b : Fin d,
    C (appendCoordinate x.1 a, appendCoordinate x.2 b)
      (appendCoordinate y.1 a, appendCoordinate y.2 b)) / (d : ℂ)

/-- PDF p.15, S63-S65: positivity and every causal equality, down to C_0=1.
Level zero has one empty tensor word. -/
def SequentialFeasible (d : ℕ) : (k : ℕ) → GroupedComb d k → Prop
  | 0, C => C = 1
  | k+1, C => C.PosSemidef ∧ SequentialFeasible d k (causalMarginal C) ∧
    ∀ (x y : TensorCoordinates d k) (s t : TensorCoordinates d (k+1)),
      (∑ a : Fin d, C (appendCoordinate x a,s) (appendCoordinate y a,t)) =
        causalMarginal C (x, fun i => s i.castSucc) (y, fun i => t i.castSucc) *
          (if s (Fin.last k) = t (Fin.last k) then 1 else 0)

/-- PDF p.16, S79-S81: one-slot comb for the n parallel calls, in explicit coordinates.
B is the marginal Tr_F(C)/identity_(O^n), with Tr_(I^n)(B)=identity_P.
These constraints are equivalent to the source's two partial-trace equalities. -/
def ParallelFeasible {d n : ℕ} (C : GroupedComb d (n+1)) : Prop :=
  C.PosSemidef ∧ ∃ B : Matrix (TensorCoordinates d n × Fin d)
      (TensorCoordinates d n × Fin d) ℂ, B.PosSemidef ∧
    (∀ (x y s t : TensorCoordinates d n) (p q : Fin d),
      (∑ a : Fin d, C (appendCoordinate x a,prependCoordinate p s)
        (appendCoordinate y a,prependCoordinate q t)) =
          B (x,p) (y,q) * (if s = t then 1 else 0)) ∧
    (∀ p q : Fin d, (∑ x : TensorCoordinates d n, B (x,p) (x,q)) =
      if p = q then 1 else 0)

/-- PDF pp.3,22, S128: independent tensor-power actions on the two wire groups. -/
def groupAction {d k : ℕ}
    (V W : Matrix.specialUnitaryGroup (Fin d) ℂ) : GroupedComb d k :=
  fun x y => (∏ i, V.val (x.1 i) (y.1 i)) * (∏ i, W.val (x.2 i) (y.2 i))

/-- PDF p.22, S130: conjugation kernel for the concrete two-group Haar average. -/
def averagingKernel {d k : ℕ} (C : GroupedComb d k)
    (z : Matrix.specialUnitaryGroup (Fin d) ℂ × Matrix.specialUnitaryGroup (Fin d) ℂ) :
    GroupedComb d k := groupAction z.1 z.2 * C * (groupAction z.1 z.2)ᴴ

/-- PDF p.22, S130: Haar probability averaging, without a symmetry hypothesis on C. -/
def averageComb {d k : ℕ} (C : GroupedComb d k) : GroupedComb d k :=
  ∫ z, averagingKernel C z ∂
    (QAlgorithms.Papers.Independent.Next46.P24.haar d).prod
      (QAlgorithms.Papers.Independent.Next46.P24.haar d)

/-- PDF p.16, S77: Choi vector U on (I_j,O_j) and on (F,P), with reference first.
The factors are unnormalized; cyclic wire regrouping is explicit in the indices. -/
def performanceVector {d n : ℕ} (U : Matrix.specialUnitaryGroup (Fin d) ℂ) :
    CombCoordinates d (n+1) → ℂ := fun x =>
  U.val (x.2 0) (x.1 (Fin.last n)) *
    ∏ i : Fin n, U.val (x.2 i.succ) (x.1 i.castSucc)

/-- PDF p.16, S77: the unnormalized-Choi Haar kernel, with its 1/d^2 factor. -/
def performanceKernel {d n : ℕ} (U : Matrix.specialUnitaryGroup (Fin d) ℂ) :
    GroupedComb d (n+1) :=
  fun x y => performanceVector U x * conj (performanceVector U y) / (d : ℂ)^2

/-- PDF p.16, S77: the actual performance operator, not an arbitrary invariant matrix. -/
def performanceOperator (d n : ℕ) : GroupedComb d (n+1) :=
  ∫ U, performanceKernel U ∂QAlgorithms.Papers.Independent.Next46.P24.haar d

/-- PDF pp.3,16: real scalar average-fidelity objective Tr(C Omega). -/
def inversionObjective {d n : ℕ} (C : GroupedComb d (n+1)) : ℝ :=
  (C * performanceOperator d n).trace.re

/-- PDF p.26: the paper-specific Hilbert-Schmidt convention sqrt(Tr A†A)/2. -/
def refocusingNorm (A : Matrix (Fin 2) (Fin 2) ℂ) : ℝ :=
  Real.sqrt ((Aᴴ * A).trace.re) / 2

/-- PDF pp.15,26, S66: squared normalized-Choi fidelity of two qubit unitary channels. -/
def qubitChannelFidelity (A B : Matrix (Fin 2) (Fin 2) ℂ) : ℝ :=
  Complex.normSq ((Aᴴ * B).trace) / 4

example : rotationY 0 = 1 := by
  ext a b
  by_cases h : a = b <;> simp [rotationY, Matrix.one_apply, h]

example : sourceSinglet false false = 0 := by simp [sourceSinglet, QAlgorithms.Papers.Independent.Frontier18.P14.singlet]

example : calls fourCircuit = 4 ∧ calls catalyticCircuit = 3 ∧ calls cleanCircuit = 5 := by
  norm_num [calls, fourCircuit, catalyticCircuit, cleanCircuit, iteration]

example (A : SequentialProtocol 0) (U V : QubitSU) : protocolOutput A U = protocolOutput A V := by
  rfl

example (d : ℕ) (x : TensorCoordinates d 0) (a : Fin d) :
    appendCoordinate x a (Fin.last 0) = a := by
  change Fin.lastCases a x (Fin.last 0) = a
  exact Fin.lastCases_last

end QAlgorithms.Papers.Independent.Support50.P24
Source
Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly, arXiv:2209.02907v5, https://arxiv.org/abs/2209.02907v5
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

QAlgorithms.Papers.Independent.Support50.P24.CallGate

A call instruction has exactly two possible forms: a “known” instruction carrying an arbitrary complex matrix indexed in both rows and columns by the seven-bit strings {0,1}7\{0,1\}^7{0,1}7, or a “call” instruction carrying a wire index q∈{0,…,6}q\in\{0,\ldots,6\}q∈{0,…,6}. The constructor for a known instruction imposes no unitarity condition on its matrix.

QAlgorithms.Papers.Independent.Support50.P24.CombCoordinates

For every pair of natural numbers d,kd,kd,k, this abbreviates the type of ordered pairs (x,y)(x,y)(x,y) of functions {0,…,k−1}→{0,…,d−1}\{0,\ldots,k-1\}\to\{0,\ldots,d-1\}{0,…,k−1}→{0,…,d−1}, so both components are kkk-tuples of indices from a set of size ddd. When k=0k=0k=0, this type has exactly one element, the pair of empty tuples, including when d=0d=0d=0; when d=0d=0d=0 and k>0k>0k>0, it is empty.

QAlgorithms.Papers.Independent.Support50.P24.ExactInverter

For any finite list of gates, each of which is either an arbitrary complex matrix indexed by seven-bit strings or a call on a specified wire q∈{0,…,6}q\in\{0,\ldots,6\}q∈{0,…,6}, this predicate requires the following equality for every Boolean-indexed special unitary matrix UUU and every Boolean-indexed complex matrix AAA, without any positivity or normalization requirement on AAA. Replace a known gate by its matrix, and replace a call on wire qqq by the matrix whose (x,y)(x,y)(x,y) entry is Uxq,yqU_{x_q,y_q}Uxq​,yq​​ if xi=yix_i=y_ixi​=yi​ for every i≠qi\ne qi=q, and zero otherwise. If these matrices occur in list order as G1,…,GℓG_1,\ldots,G_\ellG1​,…,Gℓ​, put VU=Gℓ⋯G1V_U=G_\ell\cdots G_1VU​=Gℓ​⋯G1​, taking VU=IV_U=IVU​=I for an empty list. Define Ex,b=s(x1,x2)E_{x,b}=s(x_1,x_2)Ex,b​=s(x1​,x2​) when x0=bx_0=bx0​=b and x3=x4=x5=x6=falsex_3=x_4=x_5=x_6=\mathrm{false}x3​=x4​=x5​=x6​=false, and Ex,b=0E_{x,b}=0Ex,b​=0 otherwise, where s(false,true)=1/2s(\mathrm{false},\mathrm{true})=1/\sqrt2s(false,true)=1/2​, s(true,false)=−1/2s(\mathrm{true},\mathrm{false})=-1/\sqrt2s(true,false)=−1/2​, and the other values of sss are zero. The required equality, for all Boolean a,ba,ba,b, is

∑e:{0,…,6}→{false,true}e2=false((VUE)A(VUE)†)e[2←a], e[2←b]=(U†AU)a,b.\sum_{\substack{e:\{0,\ldots,6\}\to\{\mathrm{false},\mathrm{true}\}\\ e_2=\mathrm{false}}} \bigl((V_UE)A(V_UE)^\dagger\bigr)_{e[2\leftarrow a],\,e[2\leftarrow b]} = (U^\dagger A U)_{a,b}.e:{0,…,6}→{false,true}e2​=false​∑​((VU​E)A(VU​E)†)e[2←a],e[2←b]​=(U†AU)a,b​.

The predicate itself imposes no separate unitarity requirement on the known gates.

QAlgorithms.Papers.Independent.Support50.P24.GroupedComb

For every pair of natural numbers d,kd,kd,k, this abbreviates the type of all complex matrices whose rows and columns are indexed by ordered pairs of functions {0,…,k−1}→{0,…,d−1}\{0,\ldots,k-1\}\to\{0,\ldots,d-1\}{0,…,k−1}→{0,…,d−1}. These are square matrices of dimension d2kd^{2k}d2k, with no positivity, normalization, or other constraints imposed by the abbreviation. When k=0k=0k=0, they are 1×11\times11×1 matrices, including when d=0d=0d=0; when d=0d=0d=0 and k>0k>0k>0, their row and column index sets are empty.

QAlgorithms.Papers.Independent.Support50.P24.ParallelFeasible

For arbitrary natural numbers d,nd,nd,n, let TjT_jTj​ be the set of length-jjj tuples with entries in {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1}, and let CCC be a complex matrix indexed by Tn+1×Tn+1T_{n+1}\times T_{n+1}Tn+1​×Tn+1​. This predicate means that CCC is positive semidefinite and there exists a positive semidefinite complex matrix BBB indexed by Tn×{0,…,d−1}T_n\times\{0,\ldots,d-1\}Tn​×{0,…,d−1} such that, for every x,y,s,t∈Tnx,y,s,t\in T_nx,y,s,t∈Tn​ and p,q∈{0,…,d−1}p,q\in\{0,\ldots,d-1\}p,q∈{0,…,d−1},

∑a=0d−1C(xa,ps),(ya,qt)=B(x,p),(y,q)1{s=t},∑x∈TnB(x,p),(x,q)=1{p=q},\sum_{a=0}^{d-1}C_{(xa,ps),(ya,qt)} =B_{(x,p),(y,q)}\mathbf1_{\{s=t\}}, \qquad \sum_{x\in T_n}B_{(x,p),(x,q)}=\mathbf1_{\{p=q\}},a=0∑d−1​C(xa,ps),(ya,qt)​=B(x,p),(y,q)​1{s=t}​,x∈Tn​∑​B(x,p),(x,q)​=1{p=q}​,

where xaxaxa appends aaa to xxx, whereas pspsps prepends ppp to sss. When n=0n=0n=0, TnT_nTn​ is a singleton and equality of s,ts,ts,t is automatic. When d=0d=0d=0, both matrix index sets are empty, and the predicate holds for the unique empty matrix.

QAlgorithms.Papers.Independent.Support50.P24.PhysicalCalls

For any finite list of call instructions, this predicate holds precisely when every known instruction appearing in the list carries a unitary complex matrix on the seven-bit strings {0,1}7\{0,1\}^7{0,1}7. An instruction that specifies a call on a wire imposes no additional condition. The predicate holds for the empty list.

QAlgorithms.Papers.Independent.Support50.P24.QubitSU

QubitSU\mathrm{QubitSU}QubitSU is the special unitary group of complex matrices indexed by the two Boolean values: its elements are 2×22\times22×2 unitary matrices with determinant 111.

QAlgorithms.Papers.Independent.Support50.P24.SequentialFeasible

For natural numbers d,kd,kd,k, let Tk={0,…,d−1}{0,…,k−1}T_k=\{0,\ldots,d-1\}^{\{0,\ldots,k-1\}}Tk​={0,…,d−1}{0,…,k−1}, including the unique empty tuple when k=0k=0k=0. This defines a predicate on complex matrices CCC indexed by Tk×TkT_k\times T_kTk​×Tk​. At k=0k=0k=0, the predicate means C=1C=1C=1, the identity matrix on the singleton index set. At k+1k+1k+1, write xaxaxa for the tuple obtained by appending aaa to xxx, and define the matrix

M(C)(x,u),(y,v)=1d∑a=0d−1∑b=0d−1C(xa,ub),(ya,vb).M(C)_{(x,u),(y,v)} =\frac1d\sum_{a=0}^{d-1}\sum_{b=0}^{d-1} C_{(xa,ub),(ya,vb)}.M(C)(x,u),(y,v)​=d1​a=0∑d−1​b=0∑d−1​C(xa,ub),(ya,vb)​.

The predicate means that CCC is positive semidefinite, M(C)M(C)M(C) satisfies this same predicate at level kkk, and, for every x,y∈Tkx,y\in T_kx,y∈Tk​ and s,t∈Tk+1s,t\in T_{k+1}s,t∈Tk+1​,

∑a=0d−1C(xa,s),(ya,t)=M(C)(x,s<k),(y,t<k) 1{sk=tk},\sum_{a=0}^{d-1}C_{(xa,s),(ya,t)} =M(C)_{(x,s_{<k}),(y,t_{<k})}\, \mathbf1_{\{s_k=t_k\}},a=0∑d−1​C(xa,s),(ya,t)​=M(C)(x,s<k​),(y,t<k​)​1{sk​=tk​}​,

where s<ks_{<k}s<k​ and t<kt_{<k}t<k​ are the first kkk coordinates. Division is complex division, with division by zero defined as zero. Thus d=0d=0d=0 is included: the level-zero condition remains C=1C=1C=1, while no matrix satisfies the predicate at a positive level.

QAlgorithms.Papers.Independent.Support50.P24.SequentialProtocol

For each natural number nnn, including n=0n=0n=0, this structure consists of a natural number rrr called the memory size, a proof that 0<r0<r0<r, a preparation function from Boolean-indexed complex matrices to complex matrices indexed by {false,true}×{0,…,r−1}\{\mathrm{false},\mathrm{true}\}\times\{0,\ldots,r-1\}{false,true}×{0,…,r−1}, and, for each i∈{0,…,n−1}i\in\{0,\ldots,n-1\}i∈{0,…,n−1}, a function from matrices on that joint index set to matrices on the same set. The preparation function and every indexed function must each admit a finite Kraus representation: there must exist a natural number mmm and rectangular complex matrices E0,…,Em−1E_0,\ldots,E_{m-1}E0​,…,Em−1​ of the appropriate input and output dimensions such that ∑j=0m−1Ej†Ej=I\sum_{j=0}^{m-1}E_j^\dagger E_j=I∑j=0m−1​Ej†​Ej​=I and the function sends every input matrix XXX to ∑j=0m−1EjXEj†\sum_{j=0}^{m-1}E_jXE_j^\dagger∑j=0m−1​Ej​XEj†​. The Kraus families may differ between functions. When n=0n=0n=0, there are no indexed functions or corresponding channel conditions.

QAlgorithms.Papers.Independent.Support50.P24.Seven

Seven\mathrm{Seven}Seven is the set of all functions {0,1,…,6}→{false,true}\{0,1,\ldots,6\}\to\{\mathrm{false},\mathrm{true}\}{0,1,…,6}→{false,true}, that is, all seven-bit strings.

QAlgorithms.Papers.Independent.Support50.P24.SevenMatrix

SevenMatrix\mathrm{SevenMatrix}SevenMatrix is the space of complex matrices whose rows and columns are indexed by seven-bit strings x:{0,…,6}→{false,true}x:\{0,\ldots,6\}\to\{\mathrm{false},\mathrm{true}\}x:{0,…,6}→{false,true}; these are 128×128128\times128128×128 matrices.

QAlgorithms.Papers.Independent.Support50.P24.TensorCoordinates

For every pair of natural numbers d,kd,kd,k, this abbreviates the type of functions {0,…,k−1}→{0,…,d−1}\{0,\ldots,k-1\}\to\{0,\ldots,d-1\}{0,…,k−1}→{0,…,d−1}, equivalently ordered kkk-tuples of indices from a set of size ddd. When k=0k=0k=0, there is exactly one such tuple, the empty tuple, including when d=0d=0d=0; when d=0d=0d=0 and k>0k>0k>0, there are no such tuples.

QAlgorithms.Papers.Independent.Support50.P24.appendCoordinate

For all natural numbers d,kd,kd,k, every tuple x:{0,…,k−1}→{0,…,d−1}x:\{0,\ldots,k-1\}\to\{0,\ldots,d-1\}x:{0,…,k−1}→{0,…,d−1}, and every index a∈{0,…,d−1}a\in\{0,\ldots,d-1\}a∈{0,…,d−1}, this defines the tuple y:{0,…,k}→{0,…,d−1}y:\{0,\ldots,k\}\to\{0,\ldots,d-1\}y:{0,…,k}→{0,…,d−1} satisfying yi=xiy_i=x_iyi​=xi​ for 0≤i<k0\le i<k0≤i<k and yk=ay_k=ayk​=a. When k=0k=0k=0, the result is the one-coordinate tuple with value aaa; when d=0d=0d=0, no argument aaa exists.

QAlgorithms.Papers.Independent.Support50.P24.averageComb

For arbitrary natural numbers d,kd,kd,k and an arbitrary complex matrix CCC indexed by pairs of length-kkk tuples over {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1}, this defines the matrix-valued integral

C‾=∫SU(d)×SU(d)R(V,W) C R(V,W)† d(μd×μd)(V,W),R(V,W)(r,s),(r′,s′)=∏i=0k−1Vri,ri′∏i=0k−1Wsi,si′.\overline C =\int_{\mathrm{SU}(d)\times\mathrm{SU}(d)} R(V,W)\,C\,R(V,W)^\dagger\, d(\mu_d\times\mu_d)(V,W), \qquad R(V,W)_{(r,s),(r',s')} =\prod_{i=0}^{k-1}V_{r_i,r'_i} \prod_{i=0}^{k-1}W_{s_i,s'_i}.C=∫SU(d)×SU(d)​R(V,W)CR(V,W)†d(μd​×μd​)(V,W),R(V,W)(r,s),(r′,s′)​=i=0∏k−1​Vri​,ri′​​i=0∏k−1​Wsi​,si′​​.

Here SU(d)\mathrm{SU}(d)SU(d) consists of determinant-one unitary complex d×dd\times dd×d matrices, and μd\mu_dμd​ is its Haar measure normalized so that the whole group has measure 111. No positivity or normalization of CCC is required. Empty products equal 111, so k=0k=0k=0 gives C‾=C\overline C=CC=C; d=0, k>0d=0,\ k>0d=0, k>0 gives the empty matrix.

QAlgorithms.Papers.Independent.Support50.P24.averagingKernel

For arbitrary natural numbers d,kd,kd,k, an arbitrary complex matrix CCC indexed by pairs of length-kkk tuples over {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1}, and a pair z=(V,W)z=(V,W)z=(V,W) of determinant-one unitary complex d×dd\times dd×d matrices, this defines

KC(V,W)=R(V,W) C R(V,W)†,R(V,W)(r,s),(r′,s′)=∏i=0k−1Vri,ri′∏i=0k−1Wsi,si′,K_C(V,W)=R(V,W)\,C\,R(V,W)^\dagger, \qquad R(V,W)_{(r,s),(r',s')} =\prod_{i=0}^{k-1}V_{r_i,r'_i} \prod_{i=0}^{k-1}W_{s_i,s'_i},KC​(V,W)=R(V,W)CR(V,W)†,R(V,W)(r,s),(r′,s′)​=i=0∏k−1​Vri​,ri′​​i=0∏k−1​Wsi​,si′​​,

where †\dagger† denotes conjugate transpose. There is no positivity or normalization hypothesis on CCC. At k=0k=0k=0, the products equal 111 and KC(V,W)=CK_C(V,W)=CKC​(V,W)=C; at d=0, k>0d=0,\ k>0d=0, k>0, the matrices are empty.

QAlgorithms.Papers.Independent.Support50.P24.bitFlip

bitFlip\mathrm{bitFlip}bitFlip is the complex matrix with Boolean row and column indices whose entry at (a,b)(a,b)(a,b) is 111 when aaa is the Boolean negation of bbb, and 000 otherwise; in the order (false,true)(\mathrm{false},\mathrm{true})(false,true), it is

(0110).\begin{pmatrix}0&1\\1&0\end{pmatrix}.(01​10​).

QAlgorithms.Papers.Independent.Support50.P24.calls

For any finite list of call instructions, this natural number is the sum obtained by assigning 000 to each known-matrix instruction and 111 to each wire-call instruction. Thus it counts occurrences of wire-call instructions, including repeated calls to the same wire; the empty list has count 000.

QAlgorithms.Papers.Independent.Support50.P24.catalyst

For any complex 2×22\times22×2 unitary matrix UUU, indexed by Boolean values and having determinant 111, and any Boolean values a,ba,ba,b, this complex number is ∑c∈{false,true}Ua,cs(c,b)\sum_{c\in\{\mathrm{false},\mathrm{true}\}}U_{a,c}s(c,b)∑c∈{false,true}​Ua,c​s(c,b), where s(false,true)=1/2s(\mathrm{false},\mathrm{true})=1/\sqrt2s(false,true)=1/2​, s(true,false)=−1/2s(\mathrm{true},\mathrm{false})=-1/\sqrt2s(true,false)=−1/2​, and the other two values of sss are zero. Equivalently, its value is

{−Ua,true/2,b=false,Ua,false/2,b=true.\begin{cases} -U_{a,\mathrm{true}}/\sqrt2,&b=\mathrm{false},\\ U_{a,\mathrm{false}}/\sqrt2,&b=\mathrm{true}. \end{cases}{−Ua,true​/2​,Ua,false​/2​,​b=false,b=true.​

QAlgorithms.Papers.Independent.Support50.P24.catalyticCircuit

This is the seven-instruction list [known⁡(F),call⁡(1),known⁡(G),call⁡(1),known⁡(F),call⁡(1),known⁡(G)][\operatorname{known}(F),\operatorname{call}(1),\operatorname{known}(G),\operatorname{call}(1),\operatorname{known}(F),\operatorname{call}(1),\operatorname{known}(G)][known(F),call(1),known(G),call(1),known(F),call(1),known(G)], with wire indices 000 through 666 and the following explicit definitions of its carried matrices. Write P[M1,…,Mr]=Mr⋯M1\mathcal P[M_1,\ldots,M_r]=M_r\cdots M_1P[M1​,…,Mr​]=Mr​⋯M1​, and let X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​) and Y(α)=(cos⁡(α/2)−sin⁡(α/2)sin⁡(α/2)cos⁡(α/2))Y(\alpha)=\begin{pmatrix}\cos(\alpha/2)&-\sin(\alpha/2)\\ \sin(\alpha/2)&\cos(\alpha/2)\end{pmatrix}Y(α)=(cos(α/2)sin(α/2)​−sin(α/2)cos(α/2)​) in Boolean order (0,1)(0,1)(0,1). For a list of bit conditions LLL, the matrix CL;t(R)C_{L;t}(R)CL;t​(R) sends ∣y⟩|y\rangle∣y⟩ to ∑v∈{0,1}Rv,yt∣y[t:=v]⟩\sum_{v\in\{0,1\}}R_{v,y_t}|y[t:=v]\rangle∑v∈{0,1}​Rv,yt​​∣y[t:=v]⟩ if all conditions hold on yyy, and sends it to ∣y⟩|y\rangle∣y⟩ otherwise. A condition aaa requires ya=1y_a=1ya​=1, a condition aˉ\bar aaˉ requires ya=0y_a=0ya​=0, and empty conditions always hold. Let SL;a,bS_{L;a,b}SL;a,b​ swap the two indicated wires if the input satisfies LLL and otherwise leave it unchanged, and write Sa,b=S∅;a,bS_{a,b}=S_{\varnothing;a,b}Sa,b​=S∅;a,b​. Define

L(a,b,c)=P[C{a,b};c(X),C{b};a(X),C{cˉ};b(Y(π/2)),C{aˉ,cˉ};b(Y(π/2)),C{bˉ};a(X),Sa,b,Sb,c],\begin{aligned} L(a,b,c)=\mathcal P[& C_{\{a,b\};c}(X),C_{\{b\};a}(X),C_{\{\bar c\};b}(Y(\pi/2)), C_{\{\bar a,\bar c\};b}(Y(\pi/2)),\\ & C_{\{\bar b\};a}(X),S_{a,b},S_{b,c}], \end{aligned}L(a,b,c)=P[​C{a,b};c​(X),C{b};a​(X),C{cˉ};b​(Y(π/2)),C{aˉ,cˉ};b​(Y(π/2)),C{bˉ};a​(X),Sa,b​,Sb,c​],​

and, for ϑ=2arccos⁡2/3\vartheta=2\arccos\sqrt{2/3}ϑ=2arccos2/3​,

H(a,b,c,d)=P[C{aˉ};c(X),C{c,d};b(X),C{d};c(X),C{b};c(X),C{bˉ};d(Y(π)),C{a,bˉ,c};d(Y(−ϑ)),C{a,b,c};d(Y(ϑ)),C{d};a(X),C∅;a(X),Sb,c,C∅;b(X),C{a};b(X),S{a};b,c,C{a,b};c(X)].\begin{aligned} H(a,b,c,d)=\mathcal P[& C_{\{\bar a\};c}(X),C_{\{c,d\};b}(X),C_{\{d\};c}(X),C_{\{b\};c}(X), C_{\{\bar b\};d}(Y(\pi)),\\ & C_{\{a,\bar b,c\};d}(Y(-\vartheta)),C_{\{a,b,c\};d}(Y(\vartheta)), C_{\{d\};a}(X),C_{\varnothing;a}(X),S_{b,c},\\ & C_{\varnothing;b}(X),C_{\{a\};b}(X),S_{\{a\};b,c},C_{\{a,b\};c}(X)]. \end{aligned}H(a,b,c,d)=P[​C{aˉ};c​(X),C{c,d};b​(X),C{d};c​(X),C{b};c​(X),C{bˉ};d​(Y(π)),C{a,bˉ,c};d​(Y(−ϑ)),C{a,b,c};d​(Y(ϑ)),C{d};a​(X),C∅;a​(X),Sb,c​,C∅;b​(X),C{a};b​(X),S{a};b,c​,C{a,b};c​(X)].​

The carried matrices are

F=P[S2,5,L(0,1,2),C{0};6(X),H(3,4,5,6)†,S3,6,S1,3],G=P[S1,3,H(0,1,2,3),S4,6,C{4};3(X),S5,6,L(4,5,6)†,S2,4,S1,5,S0,4],\begin{aligned} F&=\mathcal P[S_{2,5},L(0,1,2),C_{\{0\};6}(X),H(3,4,5,6)^\dagger,S_{3,6},S_{1,3}],\\ G&=\mathcal P[S_{1,3},H(0,1,2,3),S_{4,6},C_{\{4\};3}(X),S_{5,6}, L(4,5,6)^\dagger,S_{2,4},S_{1,5},S_{0,4}], \end{aligned}FG​=P[S2,5​,L(0,1,2),C{0};6​(X),H(3,4,5,6)†,S3,6​,S1,3​],=P[S1,3​,H(0,1,2,3),S4,6​,C{4};3​(X),S5,6​,L(4,5,6)†,S2,4​,S1,5​,S0,4​],​

where †\dagger† denotes conjugate transpose.

QAlgorithms.Papers.Independent.Support50.P24.catalyticInput

For every special unitary matrix UUU indexed by the Booleans, meaning U†U=UU†=IU^\dagger U=UU^\dagger=IU†U=UU†=I and det⁡U=1\det U=1detU=1, this defines a complex matrix with rows indexed by seven-bit strings x:{0,…,6}→{false,true}x:\{0,\ldots,6\}\to\{\mathrm{false},\mathrm{true}\}x:{0,…,6}→{false,true} and columns indexed by a Boolean bbb. Define KU(a,true)=Ua,false/2K_U(a,\mathrm{true})=U_{a,\mathrm{false}}/\sqrt2KU​(a,true)=Ua,false​/2​ and KU(a,false)=−Ua,true/2K_U(a,\mathrm{false})=-U_{a,\mathrm{true}}/\sqrt2KU​(a,false)=−Ua,true​/2​ for each Boolean aaa; these are the coefficients obtained by applying UUU to the first index of the vector whose (false,true)(\mathrm{false},\mathrm{true})(false,true) coefficient is 1/21/\sqrt21/2​, whose (true,false)(\mathrm{true},\mathrm{false})(true,false) coefficient is −1/2-1/\sqrt2−1/2​, and whose other coefficients are zero. The matrix entry is

(catalyticInput⁡(U))x,b={KU(x1,x2),x0=b and x3=x4=x5=x6=false,0,otherwise.(\operatorname{catalyticInput}(U))_{x,b} = \begin{cases} K_U(x_1,x_2),& x_0=b\ \text{and}\ x_3=x_4=x_5=x_6=\mathrm{false},\\ 0,&\text{otherwise}. \end{cases}(catalyticInput(U))x,b​={KU​(x1​,x2​),0,​x0​=b and x3​=x4​=x5​=x6​=false,otherwise.​

QAlgorithms.Papers.Independent.Support50.P24.causalMarginal

For all natural numbers d,kd,kd,k and every complex matrix CCC whose rows and columns are indexed by pairs of (k+1)(k+1)(k+1)-tuples from {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1}, this defines a complex matrix indexed by pairs of kkk-tuples. Writing x=(x(1),x(2))x=(x^{(1)},x^{(2)})x=(x(1),x(2)) and y=(y(1),y(2))y=(y^{(1)},y^{(2)})y=(y(1),y(2)) for arbitrary row and column indices, and writing u⌢au\frown au⌢a for the tuple formed by appending aaa to uuu, its entries are

(causalMarginal⁡(C))x,y=1d∑a=0d−1∑b=0d−1C(x(1)⌢a,  x(2)⌢b), (y(1)⌢a,  y(2)⌢b),(\operatorname{causalMarginal}(C))_{x,y} = \frac1d \sum_{a=0}^{d-1}\sum_{b=0}^{d-1} C_{(x^{(1)}\frown a,\;x^{(2)}\frown b),\, (y^{(1)}\frown a,\;y^{(2)}\frown b)},(causalMarginal(C))x,y​=d1​a=0∑d−1​b=0∑d−1​C(x(1)⌢a,x(2)⌢b),(y(1)⌢a,y(2)⌢b)​,

where division is in C\mathbb CC. No positivity assumption is imposed on CCC. The definition permits d=0d=0d=0: both sums are empty, and complex division by zero is defined to give zero, so for k=0k=0k=0 the result is the zero 1×11\times11×1 matrix, while for k>0k>0k>0 its index set is empty.

QAlgorithms.Papers.Independent.Support50.P24.cgThree

For arbitrary positions a,b,c,d∈{0,…,6}a,b,c,d\in\{0,\ldots,6\}a,b,c,d∈{0,…,6}, with no distinctness assumptions, set ϑ=2arccos⁡2/3\vartheta=2\arccos\sqrt{2/3}ϑ=2arccos2/3​. Use Boolean order (0,1)=(false,true)(0,1)=(\mathrm{false},\mathrm{true})(0,1)=(false,true), X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), and R(α)=(cos⁡(α/2)−sin⁡(α/2)sin⁡(α/2)cos⁡(α/2))R(\alpha)=\begin{pmatrix}\cos(\alpha/2)&-\sin(\alpha/2)\\\sin(\alpha/2)&\cos(\alpha/2)\end{pmatrix}R(α)=(cos(α/2)sin(α/2)​−sin(α/2)cos(α/2)​). For seven-bit strings, let CL(t;M)C_L(t;M)CL​(t;M) have entry Mxt,ytM_{x_t,y_t}Mxt​,yt​​ when x,yx,yx,y agree outside ttt and yyy satisfies all listed requirements, entry 1x=y\mathbf1_{x=y}1x=y​ when a requirement fails, and entry 000 when x,yx,yx,y disagree outside ttt. Let SL(u,v)S_L(u,v)SL​(u,v) have entry 111 exactly when its row string is obtained from its column string by exchanging positions u,vu,vu,v if that column string satisfies LLL, and otherwise leaving it unchanged; all other entries are 000. Write P[G1,…,Gm]=Gm⋯G1\mathcal P[G_1,\ldots,G_m]=G_m\cdots G_1P[G1​,…,Gm​]=Gm​⋯G1​. Then

cgThree(a,b,c,d)=P[C[(a,0)](c;X), C[(c,1),(d,1)](b;X), C[(d,1)](c;X), C[(b,1)](c;X),C[(b,0)](d;R(π)), C[(a,1),(b,0),(c,1)](d;R(−ϑ)), C[(a,1),(b,1),(c,1)](d;R(ϑ)),C[(d,1)](a;X), C∅(a;X), S∅(b,c), C∅(b;X), C[(a,1)](b;X),S[(a,1)](b,c), C[(a,1),(b,1)](c;X)].\begin{aligned} \mathrm{cgThree}(a,b,c,d)=\mathcal P\bigl[ & C_{[(a,0)]}(c;X),\ C_{[(c,1),(d,1)]}(b;X),\ C_{[(d,1)]}(c;X),\ C_{[(b,1)]}(c;X),\\ & C_{[(b,0)]}(d;R(\pi)),\ C_{[(a,1),(b,0),(c,1)]}(d;R(-\vartheta)),\ C_{[(a,1),(b,1),(c,1)]}(d;R(\vartheta)),\\ & C_{[(d,1)]}(a;X),\ C_{\varnothing}(a;X),\ S_{\varnothing}(b,c),\ C_{\varnothing}(b;X),\ C_{[(a,1)]}(b;X),\\ & S_{[(a,1)]}(b,c),\ C_{[(a,1),(b,1)]}(c;X) \bigr]. \end{aligned}cgThree(a,b,c,d)=P[​C[(a,0)]​(c;X), C[(c,1),(d,1)]​(b;X), C[(d,1)]​(c;X), C[(b,1)]​(c;X),C[(b,0)]​(d;R(π)), C[(a,1),(b,0),(c,1)]​(d;R(−ϑ)), C[(a,1),(b,1),(c,1)]​(d;R(ϑ)),C[(d,1)]​(a;X), C∅​(a;X), S∅​(b,c), C∅​(b;X), C[(a,1)]​(b;X),S[(a,1)]​(b,c), C[(a,1),(b,1)]​(c;X)].​

Empty requirement lists always hold, and repeated positions, conflicting requirements, and controls equal to targets are interpreted by these entry formulas.

QAlgorithms.Papers.Independent.Support50.P24.cgTwo

For arbitrary positions a,b,c∈{0,…,6}a,b,c\in\{0,\ldots,6\}a,b,c∈{0,…,6}, with no distinctness assumptions, cgTwo(a,b,c)\mathrm{cgTwo}(a,b,c)cgTwo(a,b,c) is the following complex matrix on seven-bit strings. Write 0,10,10,1 for false and true, let X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​) and R(α)=(cos⁡(α/2)−sin⁡(α/2)sin⁡(α/2)cos⁡(α/2))R(\alpha)=\begin{pmatrix}\cos(\alpha/2)&-\sin(\alpha/2)\\\sin(\alpha/2)&\cos(\alpha/2)\end{pmatrix}R(α)=(cos(α/2)sin(α/2)​−sin(α/2)cos(α/2)​), and define CL(t;M)C_L(t;M)CL​(t;M) by the entry Mxt,ytM_{x_t,y_t}Mxt​,yt​​ when x,yx,yx,y agree outside ttt and the input yyy satisfies every requirement in LLL, by 1x=y\mathbf1_{x=y}1x=y​ when a requirement fails, and by 000 when x,yx,yx,y disagree outside ttt. Let S(a,b)S(a,b)S(a,b) have entry 111 exactly when its row string is its column string with positions a,ba,ba,b exchanged, and 000 otherwise. For a list of matrices, write P[G1,…,Gm]=Gm⋯G1\mathcal P[G_1,\ldots,G_m]=G_m\cdots G_1P[G1​,…,Gm​]=Gm​⋯G1​. Then

cgTwo(a,b,c)=P ⁣[C[(a,1),(b,1)](c;X), C[(b,1)](a;X), C[(c,0)](b;R(π/2)), C[(a,0),(c,0)](b;R(π/2)), C[(b,0)](a;X), S(a,b), S(b,c)].\mathrm{cgTwo}(a,b,c)= \mathcal P\!\left[ C_{[(a,1),(b,1)]}(c;X),\ C_{[(b,1)]}(a;X),\ C_{[(c,0)]}(b;R(\pi/2)),\ C_{[(a,0),(c,0)]}(b;R(\pi/2)),\ C_{[(b,0)]}(a;X),\ S(a,b),\ S(b,c) \right].cgTwo(a,b,c)=P[C[(a,1),(b,1)]​(c;X), C[(b,1)]​(a;X), C[(c,0)]​(b;R(π/2)), C[(a,0),(c,0)]​(b;R(π/2)), C[(b,0)]​(a;X), S(a,b), S(b,c)].

All requirements are checked on the input of their respective matrix, including when positions coincide or a control is the target.

QAlgorithms.Papers.Independent.Support50.P24.chronological

For every finite list [G1,…,Gm][G_1,\ldots,G_m][G1​,…,Gm​] of complex matrices indexed by seven-bit strings, chronological\mathrm{chronological}chronological starts from the identity matrix and successively multiplies each listed matrix on the left, so that

chronological([G1,…,Gm])=Gm⋯G1.\mathrm{chronological}([G_1,\ldots,G_m])=G_m\cdots G_1.chronological([G1​,…,Gm​])=Gm​⋯G1​.

For the empty list, its value is the identity matrix.

QAlgorithms.Papers.Independent.Support50.P24.cleanCircuit

This is the nine-instruction list [call⁡(1),known⁡(F),call⁡(1),known⁡(G),call⁡(1),known⁡(F),call⁡(1),known⁡(G),call⁡(1)][\operatorname{call}(1),\operatorname{known}(F),\operatorname{call}(1),\operatorname{known}(G),\operatorname{call}(1),\operatorname{known}(F),\operatorname{call}(1),\operatorname{known}(G),\operatorname{call}(1)][call(1),known(F),call(1),known(G),call(1),known(F),call(1),known(G),call(1)], with wire indices 000 through 666 and the following explicit definitions of its carried matrices. Write P[M1,…,Mr]=Mr⋯M1\mathcal P[M_1,\ldots,M_r]=M_r\cdots M_1P[M1​,…,Mr​]=Mr​⋯M1​. In Boolean order (0,1)(0,1)(0,1), let X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​) and Y(α)=(cos⁡(α/2)−sin⁡(α/2)sin⁡(α/2)cos⁡(α/2))Y(\alpha)=\begin{pmatrix}\cos(\alpha/2)&-\sin(\alpha/2)\\ \sin(\alpha/2)&\cos(\alpha/2)\end{pmatrix}Y(α)=(cos(α/2)sin(α/2)​−sin(α/2)cos(α/2)​). Write CL;t(R)C_{L;t}(R)CL;t​(R) for the matrix sending a basis string ∣y⟩|y\rangle∣y⟩ to ∑v∈{0,1}Rv,yt∣y[t:=v]⟩\sum_{v\in\{0,1\}}R_{v,y_t}|y[t:=v]\rangle∑v∈{0,1}​Rv,yt​​∣y[t:=v]⟩ if all conditions in LLL hold on yyy, and to ∣y⟩|y\rangle∣y⟩ otherwise. A condition aaa means ya=1y_a=1ya​=1, aˉ\bar aaˉ means ya=0y_a=0ya​=0, and empty conditions always hold. Let SL;a,bS_{L;a,b}SL;a,b​ swap wires a,ba,ba,b when the input conditions hold and otherwise leave the string unchanged, with Sa,b=S∅;a,bS_{a,b}=S_{\varnothing;a,b}Sa,b​=S∅;a,b​. Define

L(a,b,c)=P[C{a,b};c(X),C{b};a(X),C{cˉ};b(Y(π/2)),C{aˉ,cˉ};b(Y(π/2)),C{bˉ};a(X),Sa,b,Sb,c],\begin{aligned} L(a,b,c)=\mathcal P[& C_{\{a,b\};c}(X),C_{\{b\};a}(X),C_{\{\bar c\};b}(Y(\pi/2)), C_{\{\bar a,\bar c\};b}(Y(\pi/2)),\\ & C_{\{\bar b\};a}(X),S_{a,b},S_{b,c}], \end{aligned}L(a,b,c)=P[​C{a,b};c​(X),C{b};a​(X),C{cˉ};b​(Y(π/2)),C{aˉ,cˉ};b​(Y(π/2)),C{bˉ};a​(X),Sa,b​,Sb,c​],​

and, for ϑ=2arccos⁡2/3\vartheta=2\arccos\sqrt{2/3}ϑ=2arccos2/3​,

H(a,b,c,d)=P[C{aˉ};c(X),C{c,d};b(X),C{d};c(X),C{b};c(X),C{bˉ};d(Y(π)),C{a,bˉ,c};d(Y(−ϑ)),C{a,b,c};d(Y(ϑ)),C{d};a(X),C∅;a(X),Sb,c,C∅;b(X),C{a};b(X),S{a};b,c,C{a,b};c(X)].\begin{aligned} H(a,b,c,d)=\mathcal P[& C_{\{\bar a\};c}(X),C_{\{c,d\};b}(X),C_{\{d\};c}(X),C_{\{b\};c}(X), C_{\{\bar b\};d}(Y(\pi)),\\ & C_{\{a,\bar b,c\};d}(Y(-\vartheta)),C_{\{a,b,c\};d}(Y(\vartheta)), C_{\{d\};a}(X),C_{\varnothing;a}(X),S_{b,c},\\ & C_{\varnothing;b}(X),C_{\{a\};b}(X),S_{\{a\};b,c},C_{\{a,b\};c}(X)]. \end{aligned}H(a,b,c,d)=P[​C{aˉ};c​(X),C{c,d};b​(X),C{d};c​(X),C{b};c​(X),C{bˉ};d​(Y(π)),C{a,bˉ,c};d​(Y(−ϑ)),C{a,b,c};d​(Y(ϑ)),C{d};a​(X),C∅;a​(X),Sb,c​,C∅;b​(X),C{a};b​(X),S{a};b,c​,C{a,b};c​(X)].​

The carried matrices are

F=P[S2,5,L(0,1,2),C{0};6(X),H(3,4,5,6)†,S3,6,S1,3],G=P[S1,3,H(0,1,2,3),S4,6,C{4};3(X),S5,6,L(4,5,6)†,S2,4,S1,5,S0,4],\begin{aligned} F&=\mathcal P[S_{2,5},L(0,1,2),C_{\{0\};6}(X),H(3,4,5,6)^\dagger,S_{3,6},S_{1,3}],\\ G&=\mathcal P[S_{1,3},H(0,1,2,3),S_{4,6},C_{\{4\};3}(X),S_{5,6}, L(4,5,6)^\dagger,S_{2,4},S_{1,5},S_{0,4}], \end{aligned}FG​=P[S2,5​,L(0,1,2),C{0};6​(X),H(3,4,5,6)†,S3,6​,S1,3​],=P[S1,3​,H(0,1,2,3),S4,6​,C{4};3​(X),S5,6​,L(4,5,6)†,S2,4​,S1,5​,S0,4​],​

where †\dagger† denotes conjugate transpose.

QAlgorithms.Papers.Independent.Support50.P24.controlledGate

For any finite list LLL of pairs consisting of a position in {0,…,6}\{0,\ldots,6\}{0,…,6} and a Boolean value, any target position t∈{0,…,6}t\in\{0,\ldots,6\}t∈{0,…,6}, and any complex Boolean-indexed matrix AAA, controlledGate(L,t,A)\mathrm{controlledGate}(L,t,A)controlledGate(L,t,A) is the matrix indexed by seven-bit strings with entries

[controlledGate(L,t,A)]x,y={0,if xi≠yi for some i≠t,Axt,yt,if xi=yi for every i≠t and yj=v for every (j,v)∈L,1,if xi=yi for every i≠t, some requirement in L fails, and xt=yt,0,otherwise.\bigl[\mathrm{controlledGate}(L,t,A)\bigr]_{x,y} = \begin{cases} 0,&\text{if }x_i\ne y_i\text{ for some }i\ne t,\\ A_{x_t,y_t},&\text{if }x_i=y_i\text{ for every }i\ne t \text{ and }y_j=v\text{ for every }(j,v)\in L,\\ 1,&\text{if }x_i=y_i\text{ for every }i\ne t,\text{ some requirement in }L \text{ fails, and }x_t=y_t,\\ 0,&\text{otherwise}. \end{cases}[controlledGate(L,t,A)]x,y​=⎩⎨⎧​0,Axt​,yt​​,1,0,​if xi​=yi​ for some i=t,if xi​=yi​ for every i=t and yj​=v for every (j,v)∈L,if xi​=yi​ for every i=t, some requirement in L fails, and xt​=yt​,otherwise.​

The list may be empty, in which case all its requirements hold; it may contain repeated positions, conflicting requirements, or the target itself. No unitarity assumption is imposed on AAA.

QAlgorithms.Papers.Independent.Support50.P24.discardExcept

For every wire index q∈{0,…,6}q\in\{0,\ldots,6\}q∈{0,…,6}, this defines a function from arbitrary complex matrices indexed by seven-bit strings to complex matrices indexed by Booleans. For any such input matrix XXX and any Boolean row and column indices a,ba,ba,b, its entry is

(discardExcept⁡(q)(X))a,b=∑e:{0,…,6}→{false,true}eq=falseXe[q←a], e[q←b],(\operatorname{discardExcept}(q)(X))_{a,b} = \sum_{\substack{e:\{0,\ldots,6\}\to\{\mathrm{false},\mathrm{true}\}\\ e_q=\mathrm{false}}} X_{e[q\leftarrow a],\,e[q\leftarrow b]},(discardExcept(q)(X))a,b​=e:{0,…,6}→{false,true}eq​=false​∑​Xe[q←a],e[q←b]​,

where e[q←a]e[q\leftarrow a]e[q←a] replaces coordinate qqq of eee by aaa and preserves every other coordinate. Thus the sum contains one term for each assignment to the six other wires; no positivity or normalization assumption is imposed on XXX.

QAlgorithms.Papers.Independent.Support50.P24.evaluateCalls

Given a finite list of call instructions and a complex 2×22\times22×2 unitary matrix UUU, indexed by Boolean values, with determinant 111, replace each known instruction by its carried matrix and each call on wire q∈{0,…,6}q\in\{0,\ldots,6\}q∈{0,…,6} by the seven-bit matrix Eq(U)E_q(U)Eq​(U) whose entries, for seven-bit strings x,yx,yx,y, are

Eq(U)x,y={Uxq,yq,xi=yi for every i≠q,0,otherwise.E_q(U)_{x,y}= \begin{cases} U_{x_q,y_q},&x_i=y_i\text{ for every }i\ne q,\\ 0,&\text{otherwise}. \end{cases}Eq​(U)x,y​={Uxq​,yq​​,0,​xi​=yi​ for every i=q,otherwise.​

If the resulting matrices, in list order, are M1,…,MrM_1,\ldots,M_rM1​,…,Mr​, the value of the definition is Mr⋯M1M_r\cdots M_1Mr​⋯M1​. For an empty list it is the identity matrix on {0,1}7\{0,1\}^7{0,1}7.

QAlgorithms.Papers.Independent.Support50.P24.firstKnown

firstKnown\mathrm{firstKnown}firstKnown is the following complex matrix indexed by seven-bit strings with positions 0,…,60,\ldots,60,…,6. Use Boolean order (0,1)=(false,true)(0,1)=(\mathrm{false},\mathrm{true})(0,1)=(false,true), let X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), R(α)=(cos⁡(α/2)−sin⁡(α/2)sin⁡(α/2)cos⁡(α/2))R(\alpha)=\begin{pmatrix}\cos(\alpha/2)&-\sin(\alpha/2)\\\sin(\alpha/2)&\cos(\alpha/2)\end{pmatrix}R(α)=(cos(α/2)sin(α/2)​−sin(α/2)cos(α/2)​), and ϑ=2arccos⁡2/3\vartheta=2\arccos\sqrt{2/3}ϑ=2arccos2/3​. Here CL(t;M)C_L(t;M)CL​(t;M) has entry Mxt,ytM_{x_t,y_t}Mxt​,yt​​ if x,yx,yx,y agree outside ttt and the input yyy satisfies every requirement (j,v)∈L(j,v)\in L(j,v)∈L, entry 1x=y\mathbf1_{x=y}1x=y​ if a requirement fails, and entry 000 if x,yx,yx,y disagree outside ttt; SL(u,v)S_L(u,v)SL​(u,v) exchanges input positions u,vu,vu,v when all requirements in LLL hold and otherwise leaves the input unchanged, with matrix entries 111 for that resulting output and 000 elsewhere. Empty lists impose no requirements, P[G1,…,Gm]=Gm⋯G1\mathcal P[G_1,\ldots,G_m]=G_m\cdots G_1P[G1​,…,Gm​]=Gm​⋯G1​, and †{}^\dagger† denotes conjugate transpose. With the two explicitly defined matrices E,FE,FE,F below,

firstKnown=P[S∅(2,5), E, C[(0,1)](6;X), F†, S∅(3,6), S∅(1,3)],E=P[C[(0,1),(1,1)](2;X), C[(1,1)](0;X), C[(2,0)](1;R(π/2)),C[(0,0),(2,0)](1;R(π/2)), C[(1,0)](0;X), S∅(0,1), S∅(1,2)],F=P[C[(3,0)](5;X), C[(5,1),(6,1)](4;X), C[(6,1)](5;X), C[(4,1)](5;X),C[(4,0)](6;R(π)), C[(3,1),(4,0),(5,1)](6;R(−ϑ)), C[(3,1),(4,1),(5,1)](6;R(ϑ)),C[(6,1)](3;X), C∅(3;X), S∅(4,5), C∅(4;X), C[(3,1)](4;X),S[(3,1)](4,5), C[(3,1),(4,1)](5;X)].\begin{aligned} \mathrm{firstKnown} ={}&\mathcal P\bigl[ S_{\varnothing}(2,5),\ E,\ C_{[(0,1)]}(6;X),\ F^\dagger,\ S_{\varnothing}(3,6),\ S_{\varnothing}(1,3) \bigr],\\ E={}&\mathcal P\bigl[ C_{[(0,1),(1,1)]}(2;X),\ C_{[(1,1)]}(0;X),\ C_{[(2,0)]}(1;R(\pi/2)),\\ &\qquad C_{[(0,0),(2,0)]}(1;R(\pi/2)),\ C_{[(1,0)]}(0;X),\ S_{\varnothing}(0,1),\ S_{\varnothing}(1,2) \bigr],\\ F={}&\mathcal P\bigl[ C_{[(3,0)]}(5;X),\ C_{[(5,1),(6,1)]}(4;X),\ C_{[(6,1)]}(5;X),\ C_{[(4,1)]}(5;X),\\ &\qquad C_{[(4,0)]}(6;R(\pi)),\ C_{[(3,1),(4,0),(5,1)]}(6;R(-\vartheta)),\ C_{[(3,1),(4,1),(5,1)]}(6;R(\vartheta)),\\ &\qquad C_{[(6,1)]}(3;X),\ C_{\varnothing}(3;X),\ S_{\varnothing}(4,5),\ C_{\varnothing}(4;X),\ C_{[(3,1)]}(4;X),\\ &\qquad S_{[(3,1)]}(4,5),\ C_{[(3,1),(4,1)]}(5;X) \bigr]. \end{aligned}firstKnown=E=F=​P[S∅​(2,5), E, C[(0,1)]​(6;X), F†, S∅​(3,6), S∅​(1,3)],P[C[(0,1),(1,1)]​(2;X), C[(1,1)]​(0;X), C[(2,0)]​(1;R(π/2)),C[(0,0),(2,0)]​(1;R(π/2)), C[(1,0)]​(0;X), S∅​(0,1), S∅​(1,2)],P[C[(3,0)]​(5;X), C[(5,1),(6,1)]​(4;X), C[(6,1)]​(5;X), C[(4,1)]​(5;X),C[(4,0)]​(6;R(π)), C[(3,1),(4,0),(5,1)]​(6;R(−ϑ)), C[(3,1),(4,1),(5,1)]​(6;R(ϑ)),C[(6,1)]​(3;X), C∅​(3;X), S∅​(4,5), C∅​(4;X), C[(3,1)]​(4;X),S[(3,1)]​(4,5), C[(3,1),(4,1)]​(5;X)].​

QAlgorithms.Papers.Independent.Support50.P24.fourCircuit

This is the eight-instruction list [call⁡(1),known⁡(F),call⁡(1),known⁡(G),call⁡(1),known⁡(F),call⁡(1),known⁡(G)][\operatorname{call}(1),\operatorname{known}(F),\operatorname{call}(1),\operatorname{known}(G),\operatorname{call}(1),\operatorname{known}(F),\operatorname{call}(1),\operatorname{known}(G)][call(1),known(F),call(1),known(G),call(1),known(F),call(1),known(G)], with wire indices 000 through 666 and the following explicit meanings for its carried matrices. Write P[M1,…,Mr]=Mr⋯M1\mathcal P[M_1,\ldots,M_r]=M_r\cdots M_1P[M1​,…,Mr​]=Mr​⋯M1​, and let X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​) and Y(α)=(cos⁡(α/2)−sin⁡(α/2)sin⁡(α/2)cos⁡(α/2))Y(\alpha)=\begin{pmatrix}\cos(\alpha/2)&-\sin(\alpha/2)\\ \sin(\alpha/2)&\cos(\alpha/2)\end{pmatrix}Y(α)=(cos(α/2)sin(α/2)​−sin(α/2)cos(α/2)​) in Boolean order (0,1)(0,1)(0,1). The operator CL;t(R)C_{L;t}(R)CL;t​(R) applies RRR to wire ttt if the input string satisfies all conditions in LLL, and otherwise acts as the identity: in the satisfied case its action on ∣y⟩|y\rangle∣y⟩ is ∑v∈{0,1}Rv,yt∣y[t:=v]⟩\sum_{v\in\{0,1\}}R_{v,y_t}|y[t:=v]\rangle∑v∈{0,1}​Rv,yt​​∣y[t:=v]⟩. A condition aaa requires input bit aaa to be 111, and aˉ\bar aaˉ requires it to be 000; empty conditions always hold. Let SL;a,bS_{L;a,b}SL;a,b​ swap wires a,ba,ba,b when those input conditions hold and otherwise act as the identity, with Sa,b=S∅;a,bS_{a,b}=S_{\varnothing;a,b}Sa,b​=S∅;a,b​. Define

L(a,b,c)=P[C{a,b};c(X), C{b};a(X), C{cˉ};b(Y(π/2)), C{aˉ,cˉ};b(Y(π/2)),C{bˉ};a(X),Sa,b,Sb,c],\begin{aligned} L(a,b,c)=\mathcal P[& C_{\{a,b\};c}(X),\ C_{\{b\};a}(X),\ C_{\{\bar c\};b}(Y(\pi/2)),\ C_{\{\bar a,\bar c\};b}(Y(\pi/2)),\\ & C_{\{\bar b\};a}(X),S_{a,b},S_{b,c}], \end{aligned}L(a,b,c)=P[​C{a,b};c​(X), C{b};a​(X), C{cˉ};b​(Y(π/2)), C{aˉ,cˉ};b​(Y(π/2)),C{bˉ};a​(X),Sa,b​,Sb,c​],​

and, for ϑ=2arccos⁡2/3\vartheta=2\arccos\sqrt{2/3}ϑ=2arccos2/3​,

H(a,b,c,d)=P[C{aˉ};c(X),C{c,d};b(X),C{d};c(X),C{b};c(X),C{bˉ};d(Y(π)),C{a,bˉ,c};d(Y(−ϑ)),C{a,b,c};d(Y(ϑ)),C{d};a(X),C∅;a(X),Sb,c,C∅;b(X),C{a};b(X),S{a};b,c,C{a,b};c(X)].\begin{aligned} H(a,b,c,d)=\mathcal P[& C_{\{\bar a\};c}(X),C_{\{c,d\};b}(X),C_{\{d\};c}(X),C_{\{b\};c}(X), C_{\{\bar b\};d}(Y(\pi)),\\ & C_{\{a,\bar b,c\};d}(Y(-\vartheta)),C_{\{a,b,c\};d}(Y(\vartheta)), C_{\{d\};a}(X),C_{\varnothing;a}(X),S_{b,c},\\ & C_{\varnothing;b}(X),C_{\{a\};b}(X),S_{\{a\};b,c},C_{\{a,b\};c}(X)]. \end{aligned}H(a,b,c,d)=P[​C{aˉ};c​(X),C{c,d};b​(X),C{d};c​(X),C{b};c​(X),C{bˉ};d​(Y(π)),C{a,bˉ,c};d​(Y(−ϑ)),C{a,b,c};d​(Y(ϑ)),C{d};a​(X),C∅;a​(X),Sb,c​,C∅;b​(X),C{a};b​(X),S{a};b,c​,C{a,b};c​(X)].​

Then

F=P[S2,5,L(0,1,2),C{0};6(X),H(3,4,5,6)†,S3,6,S1,3],G=P[S1,3,H(0,1,2,3),S4,6,C{4};3(X),S5,6,L(4,5,6)†,S2,4,S1,5,S0,4],\begin{aligned} F&=\mathcal P[S_{2,5},L(0,1,2),C_{\{0\};6}(X),H(3,4,5,6)^\dagger,S_{3,6},S_{1,3}],\\ G&=\mathcal P[S_{1,3},H(0,1,2,3),S_{4,6},C_{\{4\};3}(X),S_{5,6}, L(4,5,6)^\dagger,S_{2,4},S_{1,5},S_{0,4}], \end{aligned}FG​=P[S2,5​,L(0,1,2),C{0};6​(X),H(3,4,5,6)†,S3,6​,S1,3​],=P[S1,3​,H(0,1,2,3),S4,6​,C{4};3​(X),S5,6​,L(4,5,6)†,S2,4​,S1,5​,S0,4​],​

where †\dagger† denotes conjugate transpose.

QAlgorithms.Papers.Independent.Support50.P24.groupAction

For all natural numbers d,kd,kd,k and all determinant-one unitary complex d×dd\times dd×d matrices V,WV,WV,W, this defines a complex matrix R(V,W)R(V,W)R(V,W) indexed by pairs of length-kkk tuples over {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1}, with entries

R(V,W)(r,s),(r′,s′)=(∏i=0k−1Vri,ri′)(∏i=0k−1Wsi,si′).R(V,W)_{(r,s),(r',s')} =\left(\prod_{i=0}^{k-1}V_{r_i,r'_i}\right) \left(\prod_{i=0}^{k-1}W_{s_i,s'_i}\right).R(V,W)(r,s),(r′,s′)​=(i=0∏k−1​Vri​,ri′​​)(i=0∏k−1​Wsi​,si′​​).

For k=0k=0k=0, both products are empty products equal to 111, so this is the singleton matrix [1][1][1]. For d=0d=0d=0 and k>0k>0k>0, the matrix has an empty index set.

QAlgorithms.Papers.Independent.Support50.P24.inputEmbedding

This complex matrix has rows indexed by seven-bit strings xxx and columns indexed by Boolean values bbb, with bit positions numbered 000 through 666. Its entries are

Ex,b={1/2,x0=b, x1=false, x2=true, and x3=x4=x5=x6=false,−1/2,x0=b, x1=true, x2=false, and x3=x4=x5=x6=false,0,otherwise.E_{x,b}= \begin{cases} 1/\sqrt2,&x_0=b,\ x_1=\mathrm{false},\ x_2=\mathrm{true}, \text{ and }x_3=x_4=x_5=x_6=\mathrm{false},\\ -1/\sqrt2,&x_0=b,\ x_1=\mathrm{true},\ x_2=\mathrm{false}, \text{ and }x_3=x_4=x_5=x_6=\mathrm{false},\\ 0,&\text{otherwise}. \end{cases}Ex,b​=⎩⎨⎧​1/2​,−1/2​,0,​x0​=b, x1​=false, x2​=true, and x3​=x4​=x5​=x6​=false,x0​=b, x1​=true, x2​=false, and x3​=x4​=x5​=x6​=false,otherwise.​

QAlgorithms.Papers.Independent.Support50.P24.inversionObjective

For arbitrary natural numbers d,nd,nd,n and an arbitrary complex matrix CCC indexed by pairs of length-(n+1)(n+1)(n+1) tuples over {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1}, this defines the real number

Re⁡tr⁡(CHd,n),Hd,n=∫SU(d)[pU(x)pU(y)‾d2]x,y dμd(U),pU(r,s)=Us0,rn∏i=0n−1Usi+1,ri,\operatorname{Re}\operatorname{tr}(C H_{d,n}), \qquad H_{d,n}=\int_{\mathrm{SU}(d)} \left[\frac{p_U(x)\overline{p_U(y)}}{d^2}\right]_{x,y}\,d\mu_d(U), \qquad p_U(r,s)=U_{s_0,r_n}\prod_{i=0}^{n-1}U_{s_{i+1},r_i},Retr(CHd,n​),Hd,n​=∫SU(d)​[d2pU​(x)pU​(y)​​]x,y​dμd​(U),pU​(r,s)=Us0​,rn​​i=0∏n−1​Usi+1​,ri​​,

where μd\mu_dμd​ is Haar probability measure on the determinant-one unitary complex d×dd\times dd×d matrices. No positivity or normalization hypothesis is imposed on CCC. The product is 111 when n=0n=0n=0; when d=0d=0d=0, the matrices are empty and the objective is 000.

QAlgorithms.Papers.Independent.Support50.P24.iteration

This is the four-instruction list [call⁡(1),known⁡(F),call⁡(1),known⁡(G)][\operatorname{call}(1),\operatorname{known}(F),\operatorname{call}(1),\operatorname{known}(G)][call(1),known(F),call(1),known(G)], with wire indices numbered 000 through 666 and with the carried seven-bit matrices defined as follows. Write P[M1,…,Mr]=Mr⋯M1\mathcal P[M_1,\ldots,M_r]=M_r\cdots M_1P[M1​,…,Mr​]=Mr​⋯M1​, so that the matrices act in their displayed order. Let X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​) and Y(α)=(cos⁡(α/2)−sin⁡(α/2)sin⁡(α/2)cos⁡(α/2))Y(\alpha)=\begin{pmatrix}\cos(\alpha/2)&-\sin(\alpha/2)\\ \sin(\alpha/2)&\cos(\alpha/2)\end{pmatrix}Y(α)=(cos(α/2)sin(α/2)​−sin(α/2)cos(α/2)​), in Boolean order (0,1)(0,1)(0,1). Write CL;t(R)C_{L;t}(R)CL;t​(R) for the matrix that, on a basis string yyy, applies RRR to wire ttt when all the specified conditions in LLL hold on yyy, and otherwise leaves yyy unchanged; applying RRR means replacing ∣y⟩|y\rangle∣y⟩ by ∑v∈{0,1}Rv,yt∣y[t:=v]⟩\sum_{v\in\{0,1\}}R_{v,y_t}|y[t:=v]\rangle∑v∈{0,1}​Rv,yt​​∣y[t:=v]⟩. A condition aaa means ya=1y_a=1ya​=1, a condition aˉ\bar aaˉ means ya=0y_a=0ya​=0, and an empty condition list is always satisfied. Write SL;a,bS_{L;a,b}SL;a,b​ for the basis permutation that swaps wires a,ba,ba,b when the conditions in LLL hold on the input string and otherwise leaves it unchanged, and abbreviate S∅;a,bS_{\varnothing;a,b}S∅;a,b​ by Sa,bS_{a,b}Sa,b​. Define

L(a,b,c)=P[C{a,b};c(X), C{b};a(X), C{cˉ};b(Y(π/2)), C{aˉ,cˉ};b(Y(π/2)),C{bˉ};a(X), Sa,b, Sb,c],\begin{aligned} L(a,b,c)=\mathcal P[& C_{\{a,b\};c}(X),\ C_{\{b\};a}(X),\ C_{\{\bar c\};b}(Y(\pi/2)),\ C_{\{\bar a,\bar c\};b}(Y(\pi/2)),\\ & C_{\{\bar b\};a}(X),\ S_{a,b},\ S_{b,c}], \end{aligned}L(a,b,c)=P[​C{a,b};c​(X), C{b};a​(X), C{cˉ};b​(Y(π/2)), C{aˉ,cˉ};b​(Y(π/2)),C{bˉ};a​(X), Sa,b​, Sb,c​],​

and, with ϑ=2arccos⁡2/3\vartheta=2\arccos\sqrt{2/3}ϑ=2arccos2/3​,

H(a,b,c,d)=P[C{aˉ};c(X), C{c,d};b(X), C{d};c(X), C{b};c(X), C{bˉ};d(Y(π)),C{a,bˉ,c};d(Y(−ϑ)), C{a,b,c};d(Y(ϑ)), C{d};a(X), C∅;a(X), Sb,c,C∅;b(X), C{a};b(X), S{a};b,c, C{a,b};c(X)].\begin{aligned} H(a,b,c,d)=\mathcal P[& C_{\{\bar a\};c}(X),\ C_{\{c,d\};b}(X),\ C_{\{d\};c}(X),\ C_{\{b\};c}(X),\ C_{\{\bar b\};d}(Y(\pi)),\\ & C_{\{a,\bar b,c\};d}(Y(-\vartheta)),\ C_{\{a,b,c\};d}(Y(\vartheta)),\ C_{\{d\};a}(X),\ C_{\varnothing;a}(X),\ S_{b,c},\\ & C_{\varnothing;b}(X),\ C_{\{a\};b}(X),\ S_{\{a\};b,c},\ C_{\{a,b\};c}(X)]. \end{aligned}H(a,b,c,d)=P[​C{aˉ};c​(X), C{c,d};b​(X), C{d};c​(X), C{b};c​(X), C{bˉ};d​(Y(π)),C{a,bˉ,c};d​(Y(−ϑ)), C{a,b,c};d​(Y(ϑ)), C{d};a​(X), C∅;a​(X), Sb,c​,C∅;b​(X), C{a};b​(X), S{a};b,c​, C{a,b};c​(X)].​

The two carried matrices are

F=P[S2,5,L(0,1,2),C{0};6(X),H(3,4,5,6)†,S3,6,S1,3],G=P[S1,3,H(0,1,2,3),S4,6,C{4};3(X),S5,6,L(4,5,6)†,S2,4,S1,5,S0,4],\begin{aligned} F&=\mathcal P[S_{2,5},L(0,1,2),C_{\{0\};6}(X),H(3,4,5,6)^\dagger,S_{3,6},S_{1,3}],\\ G&=\mathcal P[S_{1,3},H(0,1,2,3),S_{4,6},C_{\{4\};3}(X),S_{5,6}, L(4,5,6)^\dagger,S_{2,4},S_{1,5},S_{0,4}], \end{aligned}FG​=P[S2,5​,L(0,1,2),C{0};6​(X),H(3,4,5,6)†,S3,6​,S1,3​],=P[S1,3​,H(0,1,2,3),S4,6​,C{4};3​(X),S5,6​,L(4,5,6)†,S2,4​,S1,5​,S0,4​],​

where †\dagger† denotes conjugate transpose.

QAlgorithms.Papers.Independent.Support50.P24.outputEmbedding

For every Boolean-indexed complex special unitary matrix UUU, this defines a complex matrix with rows indexed by seven-bit strings xxx and columns indexed by a Boolean bbb. For Boolean indices a,ca,ca,c, set KU(a,c)=Ua,false/2K_U(a,c)=U_{a,\mathrm{false}}/\sqrt2KU​(a,c)=Ua,false​/2​ when c=truec=\mathrm{true}c=true and KU(a,c)=−Ua,true/2K_U(a,c)=-U_{a,\mathrm{true}}/\sqrt2KU​(a,c)=−Ua,true​/2​ when c=falsec=\mathrm{false}c=false; this is the coefficient obtained by applying UUU to the first index of the vector with coefficients 1/21/\sqrt21/2​ at (false,true)(\mathrm{false},\mathrm{true})(false,true), −1/2-1/\sqrt2−1/2​ at (true,false)(\mathrm{true},\mathrm{false})(true,false), and zero elsewhere. Then

(outputEmbedding⁡(U))x,b={KU(x0,x1),x2=b and x3=x4=x5=x6=false,0,otherwise.(\operatorname{outputEmbedding}(U))_{x,b} = \begin{cases} K_U(x_0,x_1),& x_2=b\ \text{and}\ x_3=x_4=x_5=x_6=\mathrm{false},\\ 0,&\text{otherwise}. \end{cases}(outputEmbedding(U))x,b​={KU​(x0​,x1​),0,​x2​=b and x3​=x4​=x5​=x6​=false,otherwise.​

QAlgorithms.Papers.Independent.Support50.P24.performanceKernel

For arbitrary natural numbers d,nd,nd,n and any determinant-one unitary complex d×dd\times dd×d matrix UUU, this defines the complex matrix indexed by pairs of length-(n+1)(n+1)(n+1) tuples over {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1} whose entries are

KU(x,y)=pU(x) pU(y)‾d2,pU(r,s)=Us0,rn∏i=0n−1Usi+1,ri.K_U(x,y)=\frac{p_U(x)\,\overline{p_U(y)}}{d^2}, \qquad p_U(r,s)=U_{s_0,r_n}\prod_{i=0}^{n-1}U_{s_{i+1},r_i}.KU​(x,y)=d2pU​(x)pU​(y)​​,pU​(r,s)=Us0​,rn​​i=0∏n−1​Usi+1​,ri​​.

The bar denotes complex conjugation. For n=0n=0n=0, the product in pUp_UpU​ equals 111. The definition includes d=0d=0d=0: its matrix index set is then empty, and complex division by zero is defined as zero.

QAlgorithms.Papers.Independent.Support50.P24.performanceOperator

For every pair of natural numbers d,nd,nd,n, this defines a complex matrix Hd,nH_{d,n}Hd,n​, indexed by pairs of length-(n+1)(n+1)(n+1) tuples over {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1}, by the matrix-valued integral

Hd,n=∫SU(d)KU dμd(U),(KU)x,y=pU(x)pU(y)‾d2,pU(r,s)=Us0,rn∏i=0n−1Usi+1,ri.H_{d,n}=\int_{\mathrm{SU}(d)}K_U\,d\mu_d(U), \qquad (K_U)_{x,y}=\frac{p_U(x)\overline{p_U(y)}}{d^2}, \qquad p_U(r,s)=U_{s_0,r_n}\prod_{i=0}^{n-1}U_{s_{i+1},r_i}.Hd,n​=∫SU(d)​KU​dμd​(U),(KU​)x,y​=d2pU​(x)pU​(y)​​,pU​(r,s)=Us0​,rn​​i=0∏n−1​Usi+1​,ri​​.

Here μd\mu_dμd​ is Haar measure on the determinant-one unitary complex d×dd\times dd×d matrices, normalized to have total mass 111. Empty products equal 111, covering n=0n=0n=0; for d=0d=0d=0, the resulting matrix is empty, with division interpreted using complex division, including 1/0=01/0=01/0=0.

QAlgorithms.Papers.Independent.Support50.P24.performanceVector

For arbitrary natural numbers d,nd,nd,n and any determinant-one unitary complex d×dd\times dd×d matrix UUU, this defines a complex-valued function on pairs (r,s)(r,s)(r,s) of length-(n+1)(n+1)(n+1) tuples over {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1} by

pU(r,s)=Us0,rn∏i=0n−1Usi+1,ri.p_U(r,s)=U_{s_0,r_n}\prod_{i=0}^{n-1}U_{s_{i+1},r_i}.pU​(r,s)=Us0​,rn​​i=0∏n−1​Usi+1​,ri​​.

When n=0n=0n=0, the product is 111, so pU(r,s)=Us0,r0p_U(r,s)=U_{s_0,r_0}pU​(r,s)=Us0​,r0​​. When d=0d=0d=0, there are no such tuple pairs.

QAlgorithms.Papers.Independent.Support50.P24.prependCoordinate

For all natural numbers d,kd,kd,k, every index a∈{0,…,d−1}a\in\{0,\ldots,d-1\}a∈{0,…,d−1}, and every tuple x:{0,…,k−1}→{0,…,d−1}x:\{0,\ldots,k-1\}\to\{0,\ldots,d-1\}x:{0,…,k−1}→{0,…,d−1}, this defines the tuple y:{0,…,k}→{0,…,d−1}y:\{0,\ldots,k\}\to\{0,\ldots,d-1\}y:{0,…,k}→{0,…,d−1} satisfying y0=ay_0=ay0​=a and yi+1=xiy_{i+1}=x_iyi+1​=xi​ for 0≤i<k0\le i<k0≤i<k. When k=0k=0k=0, the result is the one-coordinate tuple with value aaa; when d=0d=0d=0, no argument aaa exists.

QAlgorithms.Papers.Independent.Support50.P24.protocolOutput

For every natural number nnn, every protocol AAA consisting of a positive memory size rrr, a preparation channel PPP from a Boolean register to a Boolean register together with an rrr-dimensional memory, and channels FiF_iFi​ on that joint register for 0≤i<n0\le i<n0≤i<n, and every Boolean-indexed special unitary matrix UUU, this defines a function on arbitrary Boolean-indexed complex matrices ρ\rhoρ. Here each channel is a function with a finite representation X↦∑jEjXEj†X\mapsto\sum_jE_jXE_j^\daggerX↦∑j​Ej​XEj†​ satisfying ∑jEj†Ej=I\sum_jE_j^\dagger E_j=I∑j​Ej†​Ej​=I. Set Q=U⊗IrQ=U\otimes I_rQ=U⊗Ir​, and define the joint matrices in increasing index order by

J0=P(ρ),Ji+1=Fi(QJiQ†)(0≤i<n).J_0=P(\rho),\qquad J_{i+1}=F_i(QJ_iQ^\dagger)\quad(0\le i<n).J0​=P(ρ),Ji+1​=Fi​(QJi​Q†)(0≤i<n).

The output matrix has entries

(protocolOutput⁡(A,U)(ρ))a,b=∑m=0r−1(Jn)(a,m),(b,m)(\operatorname{protocolOutput}(A,U)(\rho))_{a,b} = \sum_{m=0}^{r-1}(J_n)_{(a,m),(b,m)}(protocolOutput(A,U)(ρ))a,b​=m=0∑r−1​(Jn​)(a,m),(b,m)​

for all Boolean a,ba,ba,b. No density assumption is imposed on ρ\rhoρ; when n=0n=0n=0, the formula uses J0=P(ρ)J_0=P(\rho)J0​=P(ρ) and makes no application of UUU.

QAlgorithms.Papers.Independent.Support50.P24.qubitChannelFidelity

For every pair of complex 2×22\times22×2 matrices A,BA,BA,B, this defines the real number

∣tr⁡(A†B)∣24,\frac{\left|\operatorname{tr}(A^\dagger B)\right|^2}{4},4​tr(A†B)​2​,

where †\dagger† denotes conjugate transpose. Both matrices are arbitrary, with no unitarity or normalization hypotheses; if either matrix is zero, the value is 000.

QAlgorithms.Papers.Independent.Support50.P24.refocusingNorm

For every complex 2×22\times22×2 matrix AAA, this defines the real number

Re⁡tr⁡(A†A)2=12∑i=01∑j=01∣Aij∣2,\frac{\sqrt{\operatorname{Re}\operatorname{tr}(A^\dagger A)}}{2} =\frac12\sqrt{\sum_{i=0}^{1}\sum_{j=0}^{1}|A_{ij}|^2},2Retr(A†A)​​=21​i=0∑1​j=0∑1​∣Aij​∣2​,

where †\dagger† denotes conjugate transpose and the square root is the nonnegative real square root. No unitarity or normalization assumption is imposed on AAA, and A=0A=0A=0 gives value 000.

QAlgorithms.Papers.Independent.Support50.P24.rotationY

For every real angle α\alphaα, rotationY(α)\mathrm{rotationY}(\alpha)rotationY(α) is the complex matrix with Boolean row and column indices which, in the order (false,true)(\mathrm{false},\mathrm{true})(false,true), is

(cos⁡(α/2)−sin⁡(α/2)sin⁡(α/2)cos⁡(α/2)).\begin{pmatrix} \cos(\alpha/2)&-\sin(\alpha/2)\\ \sin(\alpha/2)&\cos(\alpha/2) \end{pmatrix}.(cos(α/2)sin(α/2)​−sin(α/2)cos(α/2)​).

QAlgorithms.Papers.Independent.Support50.P24.secondKnown

secondKnown\mathrm{secondKnown}secondKnown is the following complex matrix indexed by seven-bit strings with positions 0,…,60,\ldots,60,…,6. Use Boolean order (0,1)=(false,true)(0,1)=(\mathrm{false},\mathrm{true})(0,1)=(false,true), let X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), R(α)=(cos⁡(α/2)−sin⁡(α/2)sin⁡(α/2)cos⁡(α/2))R(\alpha)=\begin{pmatrix}\cos(\alpha/2)&-\sin(\alpha/2)\\\sin(\alpha/2)&\cos(\alpha/2)\end{pmatrix}R(α)=(cos(α/2)sin(α/2)​−sin(α/2)cos(α/2)​), and ϑ=2arccos⁡2/3\vartheta=2\arccos\sqrt{2/3}ϑ=2arccos2/3​. Here CL(t;M)C_L(t;M)CL​(t;M) has entry Mxt,ytM_{x_t,y_t}Mxt​,yt​​ if x,yx,yx,y agree outside ttt and the input yyy satisfies every requirement (j,v)∈L(j,v)\in L(j,v)∈L, entry 1x=y\mathbf1_{x=y}1x=y​ if a requirement fails, and entry 000 if x,yx,yx,y disagree outside ttt; SL(u,v)S_L(u,v)SL​(u,v) exchanges input positions u,vu,vu,v when all requirements in LLL hold and otherwise leaves the input unchanged, with matrix entries 111 for that resulting output and 000 elsewhere. Empty lists impose no requirements, P[G1,…,Gm]=Gm⋯G1\mathcal P[G_1,\ldots,G_m]=G_m\cdots G_1P[G1​,…,Gm​]=Gm​⋯G1​, and †{}^\dagger† denotes conjugate transpose. With the two explicitly defined matrices E,FE,FE,F below,

secondKnown=P[S∅(1,3), F, S∅(4,6), C[(4,1)](3;X), S∅(5,6), E†,S∅(2,4), S∅(1,5), S∅(0,4)],E=P[C[(4,1),(5,1)](6;X), C[(5,1)](4;X), C[(6,0)](5;R(π/2)),C[(4,0),(6,0)](5;R(π/2)), C[(5,0)](4;X), S∅(4,5), S∅(5,6)],F=P[C[(0,0)](2;X), C[(2,1),(3,1)](1;X), C[(3,1)](2;X), C[(1,1)](2;X),C[(1,0)](3;R(π)), C[(0,1),(1,0),(2,1)](3;R(−ϑ)), C[(0,1),(1,1),(2,1)](3;R(ϑ)),C[(3,1)](0;X), C∅(0;X), S∅(1,2), C∅(1;X), C[(0,1)](1;X),S[(0,1)](1,2), C[(0,1),(1,1)](2;X)].\begin{aligned} \mathrm{secondKnown} ={}&\mathcal P\bigl[ S_{\varnothing}(1,3),\ F,\ S_{\varnothing}(4,6),\ C_{[(4,1)]}(3;X),\ S_{\varnothing}(5,6),\ E^\dagger,\\ &\qquad S_{\varnothing}(2,4),\ S_{\varnothing}(1,5),\ S_{\varnothing}(0,4) \bigr],\\ E={}&\mathcal P\bigl[ C_{[(4,1),(5,1)]}(6;X),\ C_{[(5,1)]}(4;X),\ C_{[(6,0)]}(5;R(\pi/2)),\\ &\qquad C_{[(4,0),(6,0)]}(5;R(\pi/2)),\ C_{[(5,0)]}(4;X),\ S_{\varnothing}(4,5),\ S_{\varnothing}(5,6) \bigr],\\ F={}&\mathcal P\bigl[ C_{[(0,0)]}(2;X),\ C_{[(2,1),(3,1)]}(1;X),\ C_{[(3,1)]}(2;X),\ C_{[(1,1)]}(2;X),\\ &\qquad C_{[(1,0)]}(3;R(\pi)),\ C_{[(0,1),(1,0),(2,1)]}(3;R(-\vartheta)),\ C_{[(0,1),(1,1),(2,1)]}(3;R(\vartheta)),\\ &\qquad C_{[(3,1)]}(0;X),\ C_{\varnothing}(0;X),\ S_{\varnothing}(1,2),\ C_{\varnothing}(1;X),\ C_{[(0,1)]}(1;X),\\ &\qquad S_{[(0,1)]}(1,2),\ C_{[(0,1),(1,1)]}(2;X) \bigr]. \end{aligned}secondKnown=E=F=​P[S∅​(1,3), F, S∅​(4,6), C[(4,1)]​(3;X), S∅​(5,6), E†,S∅​(2,4), S∅​(1,5), S∅​(0,4)],P[C[(4,1),(5,1)]​(6;X), C[(5,1)]​(4;X), C[(6,0)]​(5;R(π/2)),C[(4,0),(6,0)]​(5;R(π/2)), C[(5,0)]​(4;X), S∅​(4,5), S∅​(5,6)],P[C[(0,0)]​(2;X), C[(2,1),(3,1)]​(1;X), C[(3,1)]​(2;X), C[(1,1)]​(2;X),C[(1,0)]​(3;R(π)), C[(0,1),(1,0),(2,1)]​(3;R(−ϑ)), C[(0,1),(1,1),(2,1)]​(3;R(ϑ)),C[(3,1)]​(0;X), C∅​(0;X), S∅​(1,2), C∅​(1;X), C[(0,1)]​(1;X),S[(0,1)]​(1,2), C[(0,1),(1,1)]​(2;X)].​

QAlgorithms.Papers.Independent.Support50.P24.sevenControlledSwap

For any finite list LLL of position–Boolean requirements and any positions a,b∈{0,…,6}a,b\in\{0,\ldots,6\}a,b∈{0,…,6}, sevenControlledSwap(L,a,b)\mathrm{sevenControlledSwap}(L,a,b)sevenControlledSwap(L,a,b) is the matrix indexed by seven-bit strings whose (x,y)(x,y)(x,y) entry is 111 exactly when xxx is obtained as follows, and is 000 otherwise: if yj=vy_j=vyj​=v for every (j,v)∈L(j,v)\in L(j,v)∈L, first replace coordinate aaa of yyy by the original value yby_byb​, then replace coordinate bbb by the original value yay_aya​; if some requirement fails, leave yyy unchanged. An empty list always satisfies the requirements. The positions a,ba,ba,b need not be distinct; when a=ba=ba=b, the string remains unchanged. Controls may repeat, conflict, or involve either swapped position, and are checked on the original string yyy.

QAlgorithms.Papers.Independent.Support50.P24.sourceSinglet

For Boolean values a,ba,ba,b, this complex-valued function is

s(a,b)={1/2,a=false, b=true,−1/2,a=true, b=false,0,a=b.s(a,b)= \begin{cases} 1/\sqrt2,&a=\mathrm{false},\ b=\mathrm{true},\\ -1/\sqrt2,&a=\mathrm{true},\ b=\mathrm{false},\\ 0,&a=b. \end{cases}s(a,b)=⎩⎨⎧​1/2​,−1/2​,0,​a=false, b=true,a=true, b=false,a=b.​

QAlgorithms.Papers.Independent.Support50.P24.swappedEmbedding

This complex matrix has rows indexed by seven-bit strings xxx and columns indexed by Boolean values bbb, with bit positions numbered 000 through 666. Its entries are

Ex,b={1/2,x0=false, x1=true, x2=b, and x3=x4=x5=x6=false,−1/2,x0=true, x1=false, x2=b, and x3=x4=x5=x6=false,0,otherwise.E_{x,b}= \begin{cases} 1/\sqrt2,&x_0=\mathrm{false},\ x_1=\mathrm{true},\ x_2=b, \text{ and }x_3=x_4=x_5=x_6=\mathrm{false},\\ -1/\sqrt2,&x_0=\mathrm{true},\ x_1=\mathrm{false},\ x_2=b, \text{ and }x_3=x_4=x_5=x_6=\mathrm{false},\\ 0,&\text{otherwise}. \end{cases}Ex,b​=⎩⎨⎧​1/2​,−1/2​,0,​x0​=false, x1​=true, x2​=b, and x3​=x4​=x5​=x6​=false,x0​=true, x1​=false, x2​=b, and x3​=x4​=x5​=x6​=false,otherwise.​
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me