Boolean membership oracle for a hidden Majority support
DefinitionQuantumLTF_Majority_oraclelinear-threshold-functionsmajoritymembership-queriesquantum-learning
For a hidden nonempty support , define the Majority label on by when at least half of the coordinates in equal , with ties labeled , and by otherwise. The coherent membership oracle leaves unchanged and XORs a target qubit with the bit encoding this label.
This is the oracle used throughout Section 4 for learning the hidden support of an equal-weight homogeneous linear threshold function.
Formalization Note Boolean true on an input wire encodes ; on the target wire, false encodes label and true encodes .
Definition code
import Mathlib
namespace QuantumLTF.Majority
/-- The Boolean bit encoding the `{-1,+1}` Majority label on a hidden support `A`:
`false` encodes `+1`, and `true` encodes `-1`. -/
def majorityBit {n : ℕ} (A : Finset (Fin n)) (x : Fin n → Bool) : Bool :=
decide (2 * (A.filter fun i => x i).card < A.card)
/-- The coherent Boolean membership oracle for Majority on the hidden support `A`.
The first `n` wires hold `x`; the last wire is XORed with `majorityBit A x`. -/
def majorityOracle {n : ℕ} (A : Finset (Fin n)) :
Matrix (Fin (n + 1) → Bool) (Fin (n + 1) → Bool) ℂ :=
Matrix.of fun y z =>
if (∀ i : Fin n, y i.castSucc = z i.castSucc) ∧
y (Fin.last n) = xor (z (Fin.last n)) (majorityBit A fun i => z i.castSucc)
then 1 else 0
end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331v3, Section 4, definition preceding Theorem 4.1, p. 39 (PDF p. 40)