Adjacency Oracle¶

Category C1 · Module oracq.algorithms.input_model.graph_walks · Stage V3

Overview¶

The input model of the graph-walk framework: the graph is accessed through a neighbor-table oracle with query semantics

that is, given a vertex \(v\) and an outgoing-edge index \(j\), the index of the \(j\)-th neighbor is XORed into the neighbor register. Let \(g\) be the outgoing-edge index bit width and \(D = 2^g\); the outgoing-edge table of every vertex is uniformly padded to exactly \(D\) columns (usually with self-loops), so that the neighbor superposition \(\frac{1}{\sqrt D}\sum_j |N(v,j)\rangle|j\rangle\) normalizes without knowing the concrete degree. This input model (FO, the XOR query paradigm database_xor) serves both the Szegedy quantum walk and the MNRS quantum walk search.

Interface and input model¶

The core type AdjacencyOracle (a frozen dataclass, subclass of OracleView) wraps an operation with the (vertex, index, neighbor) signature and reuses the database_xor paradigm; the signature and the equal widths of vertex/neighbor are validated at construction. Three construction entry points:

abstract_adjacency(vertex_bits, degree_bits, *, name=None)   # open declaration
gate_adjacency(neighbors, *, name=None)                      # gate-level controlled-X network
qram_adjacency(vertex_bits, degree_bits, *, name=None)       # QRAM table

API entry points: abstract_adjacency, gate_adjacency, qram_adjacency

abstract_adjacency: an open declaration with an empty body; vertex_bits is at most 32 and degree_bits ranges over 0..32; gate/QRAM implementations can be bound via bind.
gate_adjacency: a gate-level implementation for small neighbor tables; the table must be a nonempty rectangle whose entries are valid vertex indices, and the bit widths are derived automatically from the table size.
qram_adjacency: the QRAM implementation, with table entries addressed by vertex | (index << vertex_bits).
as_adjacency(value) adapts a bare Operation into an AdjacencyOracle.

Attributes of AdjacencyOracle:

Attribute	Meaning
`vertex_bits` / `degree_bits`	vertex and outgoing-edge index bit widths \(v\) / \(g\)
`vertices` / `degree`	\(2^v\) and \(2^g\)
`xor_database()`	adapts to `XorDatabase`: `address = vertex‖index` (width \(v+g\)), `data = neighbor`

Implementation notes¶

gate_adjacency enumerates all \((v, j)\) branches to build a controlled-X network, emitting gates only for nonzero target bits, so on any table the query semantics agree pointwise with the truth values. qram_adjacency is a single QRAM Load table lookup. Padding is the caller’s responsibility: the framework only requires each row to have exactly \(D\) columns; in-row repetition (self-loops) does not change the XOR semantics but determines the effective transitions of the Szegedy walk. xor_database() plugs graph input into the XorDatabase ecosystem, reusing QRAM bindings and data-loading utilities.

Applicability boundary: the gate count of gate_adjacency grows with the table size, so it targets small graphs and tests; larger graphs use qram_adjacency or stay as abstract declarations with deferred binding.

Validation approach¶

Category C1 (exact discrete semantics; acceptance criteria in ../../development/validation-plan.md §2): the query semantics must equal the neighbor table pointwise. Evidence:

Structural: tests/core/test_graph_walks.py:AdjacencyOracleTests; test_bad_tables_fail_at_generation covers generation-time violations such as non-rectangular tables, out-of-range vertices, and divergent hitting times caused by unreachable marked sets.
Numerical: AdjacencyOracleTests.test_gate_adjacency_implements_neighbor_table — for the Q3 hypercube neighbor table (8 vertices × 4 columns, self-loop-padded to \(D=4\)), all 32 \((v, j)\) queries are exhausted and the readout amplitude is exactly 1 (places = 10); test_xor_database_adapter validates the adapted address/data widths and the queried values.
Binding: AdjacencyOracleTests.test_qram_adjacency_matches_gate_implementation (the gate and QRAM implementations cross-checked pointwise) and QuantumWalkSearchTests.test_abstract_handles_bind_to_gate_implementations (after the abstract declaration is bound to a gate implementation, the end-to-end semantics are unchanged; see MNRS quantum walk search) together form the gate/qram dual-binding evidence for the adjacency oracle.

Known gaps and planned stages¶

Consistent with the validation matrix: there is no witness on Johnson graphs (a dependency of element distinctness) yet; new witnesses must be added before it can be wired in. Stage V3.

Numerical validation¶

Experiment design (end-to-end walk numerics; the adjacency query itself is already covered by unit tests): taking gate_adjacency on the hypercube Q3 neighbor table (8 vertices, degree 4) as an example, H gates are applied to the vertex/index registers for a single superposition call that exhausts all 32 \((v,j)\) query branches, and four backend paths (reference, rir-pysparq, adapter-pysparq, originir-ext) verify the \(\lvert v\rangle\lvert j\rangle\lvert N(v,j)\rangle\) structure amplitude by amplitude. Additionally, a QRAM binding (qram_adjacency + memory table) runs the MNRS search end to end (K4, steps=2; OriginIR-ext has no QRAM resource, so this instance uses only the reference and rir-pysparq paths).

Case	Scale	Paths	Metric	Value
adjacency-superposition-hypercube	8 vertices × 4 columns = 32 queries	4 paths	max amplitude error / off-table branch weight	5.6e-17 / 0.0
mnrs-search-qram-k4	N=4, D=4, steps=2	reference, rir-pysparq	marked probability / final-state max error	0.578125 / 6.3e-16

Reproduction command:

PYTHONPATH=src /home/agony/projects/qcfd-dev/quantum-cfd-software/.venv/bin/python tests/verification/verify_search_walks.py

Artifact: out/verification/search_walks.json (cases adjacency-superposition-hypercube, mnrs-search-qram-k4).