Four calls are optimal without a supplied catalyst
OpenQAlgorithms.Papers.Independent.Support50.P24.minimumQueryCountAmong deterministic causally ordered protocols using fixed CPTP stages and arbitrary finite memory, without a supplied -dependent state, the minimum number of forward calls required for exact universal qubit-unitary inversion is four. A four-call circuit exists. Conversely,
where is any fixed -call protocol and is a positive semidefinite trace-one qubit density matrix. The same unknown is used in all slots. The protocol, its memory and its CPTP maps are chosen before and . This optimality statement concerns inversion without advice and does not assert optimality for catalytic or clean protocols.
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P24
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
attribute [local instance] QAlgorithms.Papers.Independent.Support50.P24.groupedContinuousENorm
/-- PDF p.4: four calls are optimal among all finite-memory causally ordered CPTP
protocols without a supplied U-dependent state. The lower bound is cited to [21,27];
its separate proof dependency remains deferred, not inferred from rounded numerics. -/
theorem minimumQueryCount :
(∃ gates : List CallGate, PhysicalCalls gates ∧ calls gates = 4 ∧ ExactInverter gates) ∧
∀ n : ℕ, n ≤ 3 → ∀ A : SequentialProtocol n,
∃ (U : QubitSU) (rho : Matrix Bool Bool ℂ), IsDensityMatrix rho ∧
protocolOutput A U rho ≠ conjSuperop U.valᴴ rho := by sorry
end QAlgorithms.Papers.Independent.Support50.P24
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exists a finite list of operations on seven qubits, numbered , in which each operation is either a fixed complex matrix or a call applying an unknown Boolean-indexed to one specified qubit and leaving the other six unchanged, such that every fixed matrix in the list is unitary and exactly four operations are calls. If is the product obtained by executing this list in its given order, with the empty product equal to the identity, and is the embedding
then, for every and every complex matrix ,
Here the partial trace retains wire ; its entry sums the full matrix entries between strings that agree on the other six wires and have retained bits . In addition, for every natural number and every protocol consisting of a positive natural memory dimension , a channel from matrices to matrices on , and channels on that joint space for , there exist and a positive semidefinite matrix of trace for which
Every channel mentioned here means a map admitting a finite family of rectangular complex matrices such that its value on every matrix is and . The case is included, when there are no calls or intervening channels and the output is the memory trace of .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.