Exact compilation of locally simulated quantum query algorithms
ProvedQuantumBipartiteTesting.Bipartiteness.local_oracle_algorithm_compilationLet and be finite sets of source and logical query addresses. Fix a source address , three source addresses for each logical address , and a function mapping their binary answers to a logical binary answer. All of this data is independent of the input function .
For every -query logical quantum algorithm with finite workspace and a computational-basis Boolean output event, there is a source quantum algorithm, also with finite workspace, whose query count satisfies
and whose acceptance probability on every source function equals that of the logical algorithm with oracle
Both answer registers are full bit-string spaces, including unused encodings. The result applies the constant-query oracle reduction to arbitrary unitary interlayers and arbitrary initial unit vectors.
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction open QuantumBipartiteTesting.Bipartiteness
theorem QuantumBipartiteTesting.Bipartiteness.local_oracle_algorithm_compilation {I L : Type} [Fintype I] [Fintype L] [DecidableEq I] [DecidableEq L]
(kS kT w q : ℕ) (i0 : I) (a : L→Fin 3→I)
(g : L→(Fin 3→Bits kS)→Bits kT) (A : Algorithm L kT w q)
(out : ((L×Bits kT)×Fin w)→Bool) :
∃ wS qS : ℕ, ∃ A' : Algorithm I kS wS qS,
∃ out' : ((I×Bits kS)×Fin wS)→Bool, qS ≤ 6*q ∧ ∀ f : I→Bits kS,
A'.outputProb (QAlgorithms.xorOracle f) out' true =
A.outputProb (QAlgorithms.xorOracle (fun l => g l (fun j => f (a l j)))) out true := by sorry