The oracle as a string oracle and as an XOR quantum oracle
DefinitionCertRandQROM_Supplement_qOracleOfcertified-randomnesscryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexityrandom-oracle-model
Let and fix binary codes of oracle inputs.
- The string oracle answers on the code of and on every string that is not the code of an input.
- The quantum oracle acts on qubits by
where the first qubits hold the query string , the last qubit is the answer bit, and is the string oracle's answer.
The first is the classical query access of the verifier, the second the quantum query access of the prover ("coherently evaluate ").
Formalization Note strOracleOf and qOracleOf; the latter is a QStateSearch.Supplement.QOracle (a matrix on for every , the label being ignored): a permutation matrix which is its own inverse. The input with a given code is picked by choice and is unique when enc is injective.
Definition code
import Mathlib
import Definitions.Def_PvsNP
import Definitions.Def_QStateSearch_Supplement_QOracle
import Definitions.Def_CertRandQROM_Supplement_proofBits
set_option autoImplicit false
namespace CertRandQROM.Supplement
variable {K : Type} {e n m : ℕ}
open Classical in
/-- **The oracle `H : [n] × Σ → {0,1}` as a Boolean function on bit strings** (classical query
access, Definition 6.1, Syntax of Verify, p.27 of Coladangelo et al., arXiv:2608.31112, sha256
b75095a2…): on the string `domBits (i, x)` of an input the answer is `h (i, x)`; on every other
string it is `0`.
**Formalization Note** The input is chosen with `Classical.choose`; it is unique when `enc` is
injective. Strings that are not the code of an input (e.g. an index `≥ n`) lie outside the
oracle's domain and are answered `0`. -/
noncomputable def strOracleOf (enc : K → Fin e → Bool) (h : Fin n × (Fin m → K) → Bool)
(s : PvsNP.Str) : Bool :=
if hs : ∃ u : Fin n × (Fin m → K), domBits enc u = s then h hs.choose else false
open Classical in
/-- **The oracle `H` as a quantum oracle** (quantum query access, Definition 6.1, Syntax of
Prove, p.27; "coherently evaluate `H_i(e_i)`", Construction 6.2, step 1, p.29), in the published
circuit model `QStateSearch.Supplement.QOracle`: on `k` qubits it is the standard XOR oracle
`|a⟩|b⟩ ↦ |a⟩|b ⊕ H(a)⟩`, the first `k − 1` qubits holding the query string `a` and the last
qubit the answer bit, with `H(a) = strOracleOf enc h a`. The oracle label is ignored.
**Formalization Note** The matrix entry at row `z`, column `u` is `1` exactly when `u` is `z`
with its last bit XORed with `H(z|_{first k−1})`; this is a permutation matrix and an
involution. A query of the wrong length is answered `0` (the identity). -/
noncomputable def qOracleOf (enc : K → Fin e → Bool) (h : Fin n × (Fin m → K) → Bool) :
QStateSearch.Supplement.QOracle :=
fun _ k => Matrix.of fun z u =>
if u = (fun j : Fin k =>
if j.val + 1 = k then xor (z j) (strOracleOf enc h (List.ofFn z).dropLast) else z j)
then 1 else 0
end CertRandQROM.Supplement
Source
Coladangelo, Khurana, Mutreja, Roberts, Slote, Tal, Unconditional Certified Randomness without Structure, arXiv:2608.31112 (sha256 b75095a2…), Definition 6.1, Syntax, p.27 (PDF p.29); §6.2, Biased Random Oracle, p.28 (PDF p.30); Construction 6.2, step 1, p.29 (PDF p.31)