Graph-walk search

oracq.algorithms.input_model.graph_walks

Graph oracle input model and the Szegedy/MNRS quantum walk search framework.

The graph is supplied as a neighbor-table oracle: |v>|j>|c> -> |v>|j>|c XOR N(v,j)>, with the out-edge table uniformly padded to D=2**degree_bits columns (usually padded with self-loops). The Szegedy walk step is defined on the (current, peer, index) bipartite walk space and consists of two reflections built from neighbor superposition preparations, W = R_B R_A; the MNRS search skeleton is setup initial state preparation followed by Repeat{ walk; marked phase flip }.

References: Szegedy 2004 (the spectrum of the walk operator); Magniez–Nayak–Roland–Santha 2011 (Search via quantum walk, hitting time and step scaling).

class oracq.algorithms.input_model.graph_walks.AdjacencyOracle(operation)

Bases: OracleView

Neighbor-table query: |v>|j>|c> -> |v>|j>|c XOR N(v,j)>.

The out-edge table is arranged by vertex number, with exactly D=2**degree_bits entries per row; the caller pads the shortfall with self-loops or the like, to keep the neighbor superposition normalized as 1/sqrt(D). The paradigm reuses database_xor, with address interpreted as the low-bit concatenation of vertex and index.

oracle_kind = 'database_xor'

operation

adjacency_oracle()

Return the AdjacencyOracle view of itself, as the adapter entry point of the adjacency oracle protocol.

Returns:

This view itself.

Return type:

AdjacencyOracle

property vertex_bits

Bit width of the vertex register vertex.

property degree_bits

Bit width of the out-edge index register index.

property vertices

Total number of addressable vertices, i.e. 2**vertex_bits.

property degree

Number D of out-edge table columns per vertex after padding, i.e. 2**degree_bits.

xor_database()

Treat the neighbor table as an XOR database with address=``vertex||index`` and data=neighbor.

Returns:

XOR database view wrapping the same neighbor-table operation.

Return type:

XorDatabase

oracq.algorithms.input_model.graph_walks.as_adjacency(value)

Adapt a graph adjacency input into an AdjacencyOracle view.

Parameters:

• value – Returned as-is when already an AdjacencyOracle; otherwise it

• `` (must be a complete Operation with the)

• signature.

Returns:

Adjacency oracle view wrapping the given operation.

Return type:

AdjacencyOracle

Raises:

ValidationError – value is neither an AdjacencyOracle nor an Operation.

oracq.algorithms.input_model.graph_walks.abstract_adjacency(vertex_bits, degree_bits, *, name=None)

Open declaration of graph adjacency; the body is empty and can be bound to a gate/QRAM implementation via bind.

Parameters:

• vertex_bits – Bit width of the vertex register, range 1..32.

• degree_bits – Bit width of the out-edge index register, range 0..32.

• name – Name of the declaration slot; GraphAdjacency_{vertex_bits}_{degree_bits} by default.

Returns:

Adjacency declaration with an empty body awaiting a bound implementation.

Return type:

AdjacencyOracle

oracq.algorithms.input_model.graph_walks.gate_adjacency(neighbors, *, name=None)

Gate-level implementation for a small neighbor table: a controlled X network per (v, j) branch.

Parameters:

• neighbors – Nonempty rectangular neighbor table with rows for vertices

• numbers. (0..V-1 and D entries per row; entries are legal vertex)

• name – Name of the generated operation; derived from the table content by default.

Returns:

Adjacency oracle implemented as a controlled X network.

Return type:

AdjacencyOracle

oracq.algorithms.input_model.graph_walks.qram_adjacency(vertex_bits, degree_bits, *, name=None)

QRAM implementation of the neighbor table; the address is vertex | (index << vertex_bits) and the word is the neighbor number.

Parameters:

• vertex_bits – Bit width of the vertex register, range 1..32.

• degree_bits – Bit width of the out-edge index register, range 0..32.

• name – Name of the generated operation; qram_adjacency_{vertex_bits}_{degree_bits} by default.

Returns:

Adjacency oracle backed by the table bank.

Return type:

AdjacencyOracle

oracq.algorithms.input_model.graph_walks.szegedy_walk(adjacency, *, name=None)

Szegedy walk step W = R_B R_A, acting on the (current, peer, index) walk space.

R_A is the reflection about the subspace of neighbor superpositions on the current end, and R_B swaps the roles of the two ends (equivalent to SWAP conjugation). The graph need not be regular; when irregular, the padding scheme determines the effective transition.

Parameters:

• adjacency – Adjacency oracle, or an operation with the (vertex, index, neighbor) signature.

• name – Name of the generated operation; derived from the adjacency operation by default.

Returns:

The unitary operation of one walk step.

Return type:

Operation

oracq.algorithms.input_model.graph_walks.szegedy_setup(adjacency, *, name=None)

Prepare the MNRS initial state 1/sqrt(N) sum_v A|v>: a uniform superposition on current followed by neighbor state preparation.

The target layout matches the register declaration order of szegedy_walk: the low vertex_bits bits are current, the next vertex_bits bits are peer, and the high degree_bits bits are index.

Parameters:

• adjacency – Adjacency oracle, or an operation with the (vertex, index, neighbor) signature.

• name – Name of the generated operation; derived from the adjacency operation by default.

Returns:

Preparation view preparing the MNRS initial state.

Return type:

StatePreparation

oracq.algorithms.input_model.graph_walks.quantum_walk_search(setup, walk, marked, steps, *, name=None)

MNRS marked-vertex search skeleton: setup followed by Repeat{ walk; marked phase flip }.

Parameters:

• setup – Initial state preparation (StatePreparation protocol), with target being the whole walk space.

• walk – Walk step handle; its registers map in declaration order to consecutive slices of setup.target.

• marked – Phase oracle (target with optional work) acting on the first target.width bits of the walk space, which is the current register for szegedy_walk.

• steps – Nonnegative iteration count; choose with reference to suggest_steps.

All three handles may be open declarations; the generated program becomes executable after bind closes the implementations in batches.

Returns:

The search program of repeated walking and phase flipping.

Return type:

Operation

oracq.algorithms.input_model.graph_walks.transition_matrix(neighbors)

Build the classical random-walk transition matrix from the neighbor table, P[v][u] = |{j: N(v,j)=u}| / D.

Parameters:

neighbors – Nonempty rectangular neighbor table whose entries are legal vertex numbers.

Returns:

Row-major transition probability matrix, with each row summing to 1.

Return type:

tuple[tuple[float, …], …]

oracq.algorithms.input_model.graph_walks.hitting_times(transition, marked)

Expected number of steps for each vertex to first reach the marked set (zero for marked vertices).

Solves the linear system (I - P_free) h = 1, where P_free is the sub-transition matrix with the marked rows and columns removed.

Parameters:

• transition – Nonnegative square transition matrix with each row summing to 1.

• marked – Set of marked vertex numbers, which must be nonempty and in range.

Returns:

Expected hitting times ordered by vertex number.

Return type:

tuple[float, …]

oracq.algorithms.input_model.graph_walks.suggest_steps(transition, marked)

MNRS suggested walk step count: ceil(pi/4 * sqrt(H_avg)), where H_avg is the average hitting time.

Matches the Grover limit: on the complete graph H_avg = N/|M| and the step count recovers pi/4 * sqrt(N/|M|).

Parameters:

• transition – Nonnegative square transition matrix with each row summing to 1.

• marked – Set of marked vertex numbers, which must be nonempty and in range.

Returns:

Suggested iteration count, at least 1; zero when there are no free vertices.

Return type:

int