图行走搜索

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)

基类：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.

返回:

This view itself.

返回类型:

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.

返回:

XOR database view wrapping the same neighbor-table operation.

返回类型:

XorDatabase

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

Adapt a graph adjacency input into an AdjacencyOracle view.

参数:

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

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

• signature.

返回:

Adjacency oracle view wrapping the given operation.

返回类型:

AdjacencyOracle

抛出:

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.

参数:

• 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.

返回:

Adjacency declaration with an empty body awaiting a bound implementation.

返回类型:

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.

参数:

• 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.

返回:

Adjacency oracle implemented as a controlled X network.

返回类型:

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.

参数:

• 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.

返回:

Adjacency oracle backed by the table bank.

返回类型:

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.

参数:

• 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.

返回:

The unitary operation of one walk step.

返回类型:

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.

参数:

• 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.

返回:

Preparation view preparing the MNRS initial state.

返回类型:

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 }.

参数:

• 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.

返回:

The search program of repeated walking and phase flipping.

返回类型:

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.

参数:

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

返回:

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

返回类型:

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.

参数:

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

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

返回:

Expected hitting times ordered by vertex number.

返回类型:

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|).

参数:

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

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

返回:

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

返回类型:

int