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:

Documentation

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{G, T}(graph, sqrtstochastic)

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

Szegedy(graph[, stochastic, checkstochastic])

Constructors of AbstractSzegedy. Parameter stochastic needs to be a stochastic matrix. Flag checkstochastic decides about checking the stochastic properties.

Matrix stochastic defaults to the uniform walk operator, and checkstochastic deafults to false in case of default stochastic. If matrix stochastic is provided by the user, the default value of stochastic is true.

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 AbstractMatrix. 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 AbstractMatrix objects. Furthermore operators need to be square of size equals to square of the order of graph(szegedy).

source
QuantumWalk.sqrtstochastic — Method.
sqrtstochastic(szegedy)

Returns the sqrtstochastic element of szegedy.

source