Szegedy

Szegedy Quantum Walk

The Szegedy quantum walk is one of the most popular discrete quantum walk models. It takes stochastic matrix, turns it into unitary operator and use it for evolution. The evolution is purely unitary on the dimension equal to square of the graph order. The definition can be found in Quantum speed-up of Markov chain based algorithms by Szegedy. The definition of quantum search can be found in Direct Equivalence of Coined and Szegedy's Quantum Walks by Wong.

The abstract supertype is AbstractSzegedy with its default realization Szegedy. The model includes following types and methods:

Full docs

QuantumWalk.AbstractSzegedy — Type.
AbstractSzegedy

Type representing the abstract Szegedy model. Description of the default parameter can be found in https://arxiv.org/abs/1611.02238, where two oracle operator case is chosen. Default representation of AbstractSzegedy is Szegedy.

source
QuantumWalk.QWEvolution — Method.
QWEvolution(szegedy)

Create QWEvolution according to AbstractSzegedy model. By default, the constructed operator is of type SparseMatrixCSC.

source
QuantumWalk.QWSearch — Method.
QWSearch(szegedy, marked[, penalty])

Creates QWSearch according to AbstractSzegedy model. By default parameter penalty is set to 0. Evolution operators are constructed according to the definition from https://arxiv.org/abs/1611.02238.

QWSearch(qws[; marked, penalty]; check)

Update quantum walk search to new subset of marked elements and new penalty. By default marked and penalty are the same as in qws.

source
QuantumWalk.Szegedy — Type.

Szegedy(graph, sqrtstochastic)

Default representation of AbstractSzegedy. Parameter sqrtstochastic needs to be an element-wise square root of stochastic matrix.

source
QuantumWalk.check_qwdynamics — Method.
check_qwdynamics(QWSearch, szegedy, marked, parameters)

Check whetver combination of szegedy, marked and parameters produces valid QWSearch object. It checks where parameters consists of key :operators with corresponding value being list of SparseMatrixCSC. Furthermore operators needs to be square of size equals to square of graph(szegedy). order.

source
QuantumWalk.check_qwdynamics — Method.
check_qwdynamics(QWEvolution, szegedy, parameters)

Check whetver combination of szegedy, and parameters produces a valid QWEvolution object. It checks where parameters consists of key :operators with corresponding value being a list of SparseMatrixCSC objects. Furthermore operators need to be square of size equals to square of the order of graph(szegedy).

source
QuantumWalk.evolve — Method.
evolve(qwd_szegedy, state)

Multiplies state be each operator from operators from quantum walk evolution qwd_szegedy. Elements of operators and state should be of the same type.

source
QuantumWalk.initial_state — Method.
initial_state(qws_szegedy)

Generates typical initial state for Szegedy search, see https://arxiv.org/abs/1611.02238. Vectorizes and normalizes obtained sqrtstochastic matrix from model(qws).

source
QuantumWalk.measure — Method.
measure(qwd_szegedy, state[, vertices])

Performes a measurement on state on vertices. vertices defaults to list of all vertices. It is defined as the measurement of partially traced on second system state https://arxiv.org/abs/1611.02238.

source
QuantumWalk.sqrtstochastic — Method.
sqrtstochastic(szegedy)

Returns the sqrtstochastic element of szegedy.

source