Fixed-direction -query algorithm with forward and inverse oracle access (no controlled access)
DefinitionPRUPermLayer_Supplement_MixAlgp2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandom-unitariesquantum-cryptographyquery-complexity
A fixed-direction -query algorithm with forward and inverse access to an -qubit oracle () consists of
- a direction for each query : a forward query applies to the query register, an inverse query applies ;
- a number of extra qubits (workspace and reference register);
- unitaries on the query register and the extra qubits, which do not depend on ;
- an effect , , the measurement operator of the output .
The oracle is used only through and ; there is no controlled version of or . This is the algorithm class of Theorem 1.6.
Formalization Note This is the mission's forward-query model FwdAlg with a fixed direction per query; the order of the directions is part of the algorithm. Section 2.2 allows the direction to be chosen classically from earlier measurement outcomes, while this is the fixed-direction subclass used by Theorem 1.6's exhibited attack. Intermediate measurements are purified into the workspace, whose size is arbitrary, and the final measurement is an arbitrary effect.
Definition code
import Mathlib import Definitions.Def_QAlgorithms_Defs_Basic import Definitions.Def_QAlgorithms_Defs_Information namespace PRUPermLayer.Supplement /-- A fixed-direction `q`-query algorithm with **forward and inverse access** to an `n`-qubit oracle `U` (Shen–Zhong, *Pseudorandom Unitaries from a Random Permutation and One Layer of Single-Qubit Gates*, manuscript (STOC 2027 submission; held version sha256 395fcfa3…5bcb), §1.1, p.2 (PDF p.4): "Forward queries apply the unitary itself, while inverse queries apply its inverse"; Theorem 1.6, p.4 (PDF p.6); §2.2, p.9 (PDF p.11) for the forward model it extends). The data are: the direction `d i` of query `i` (`true` = forward, the oracle applies `U`; `false` = inverse, it applies `U†`); the number `m` of extra qubits (workspace and reference register); unitaries `A₀, …, A_q` on the query register (`N = 2ⁿ` labels) together with the `m` extra qubits; and the effect `M` (`0 ⪯ M ⪯ I`) of the output "1". **Formalization Note** This is the published `PRUPermLayer.FwdAlg` with a direction for each query and nothing else: every oracle call applies `U ⊗ I` or `U† ⊗ I` to the query register, so there is no controlled access to `U` or `U†`. Section 2.2 permits the direction to be chosen classically from earlier measurement outcomes; this structure is the fixed-direction subclass used by the proof of Theorem 1.6, whose four calls occur in the fixed order `U†, U, U†, U`. Intermediate measurements are purified into the workspace, whose size `m` is arbitrary, and the final measurement is an arbitrary effect. -/ structure MixAlg (n q : ℕ) where /-- direction of query `i`: `true` = forward (`U`), `false` = inverse (`U†`) -/ d : Fin q → Bool /-- number of workspace (and reference) qubits -/ m : ℕ /-- the unitaries `A₀, …, A_q` -/ A : Fin (q + 1) → Matrix.unitaryGroup (Fin (2 ^ n) × QAlgorithms.Qubits m) ℂ /-- the effect of the output `1` -/ M : Matrix (Fin (2 ^ n) × QAlgorithms.Qubits m) (Fin (2 ^ n) × QAlgorithms.Qubits m) ℂ isEffect : QAlgorithms.IsEffect M end PRUPermLayer.Supplement
Source
Shen–Zhong, Pseudorandom Unitaries from a Random Permutation and One Layer of Single-Qubit Gates, manuscript (STOC 2027 submission; held version sha256 395fcfa33ec861a7e9c10d88cfcefc2794b77ad1674c02661c9298c5ba565bcb), §1.1, p.2 (PDF p.4); Theorem 1.6, p.4 (PDF p.6); §2.2, p.9 (PDF p.11)