Quantum search

Quantum Search

Quantum spatial search is an algorithm, which starts at some initial state (which depends on the graph structure), and runs for some time in order to cumulate amplitude at marked vertex. The algorithm is known to outperform classical search.

The dynamics requires evolve, measure, initial_state and check_qwdynamics functions. It provides execute, execute_single, execute_single_measured, execute_all and execute_all_measured functions - the description can be found in Quantum walk evolution section. The only difference is that QWSearch uses the state generated by initial_state function if not provided. Furthermore the function provides marked, penalty and maximize_quantum_search. The first two returns the parameters from QWSearch. The last one searches for optimal measure time. The maximization methods depends on the model (if it is continuous or discrete).

The penalty is an additional time added in optimization. Note, that if we optimize time/success_probability(time) function, the optimum is always at time 0. This would imply that algorithm achieves full efficiency if it is instantly measured. This is misleading, as the time for constructing initial state and for measurement is ignored. Hence we need to include (usually small) additional time in penalty in order to get useful result. Note the time/success_probability(time) is at called expected runtime and can be obtained by expected_runtime function.

Some function as a result outputs QSearchState instead of the original state. It consists of the original state, the runtime, the probability of measuring each marked vertex, and penalty used for computing QSearchState. Those elements can be extracted by state, runtime, probability and penalty functions.

Example

julia> n = 100;

julia> penalty_szegedy = log(n);

julia> qsearch = QWSearch(Szegedy(CompleteGraph(n)), [1], penalty_szegedy);

julia> runtime(maximize_quantum_search(qsearch))-penalty_szegedy
5.0

julia> probability(maximize_quantum_search(qsearch))
1-element Array{Float64,1}:
 0.569689

julia> execute_single_measured(qsearch, ceil(Int, pi*sqrt(100)/2))
100-element Array{Float64,1}:
 0.428475  
 0.00577298
 0.00577298
 0.00577298
 0.00577298
 0.00577298
 0.00577298
 0.00577298
 0.00577298
 ⋮         
 0.00577298
 0.00577298
 0.00577298
 0.00577298
 0.00577298
 0.00577298
 0.00577298
 0.00577298
 0.00577298

Adjusting model to QWSearch

Here we consider the example from the Quantum walk evolution section. We consider random walk search as follows: at given step we check if we are at the marked vertex. If not, we continue evolution. Hence we need to cumulate the success probability at marked vertices. We propose following implementation (including the functions from mentioned section). Again some additional assertion could be included for full functionality.

function check_qwdynamics(::Type{QWSearch},
                          abs_stoch::UniformStochastic,
                          ::Vector{Int},
                          parameters::Dict{Symbol,Any})
  @assert :stochastic ∈ keys(parameters) "parameters needs to have key stochastic"
  n = nv(graph(abs_stoch))
  @assert isa(parameters[:stochastic], SparseMatrixCSC{<:Real}) "value for :stochastic needs to be sparse matrix with real numbers"
  @assert size(parameters[:stochastic], 1) == size(parameters[:stochastic], 2) "Stochastic matrix needs to be square stochastic matrix"
  @assert mapslices(sum, parameters[:stochastic], 1)[1,:] ≈ ones(n) "Stochastic matrix needs to be square stochastic matrix of order graph"
end

function QWSearch(stoch::AbstractStochastic,
                  marked::Vector{Int},
                  penalty::Real = 0.)
   parameters = Dict{Symbol,Any}(:stochastic => stochastic_matrix(graph(stoch)))

   QWSearch(stoch, marked, parameters, penalty)
end

function initial_state(qws::QWSearch{<:AbstractStochastic})
  n = nv(graph(qws))
  fill(1./n, n)
end

function evolve(qws::QWSearch{<:AbstractStochastic}, state::Vector{<:Real})
  old_probability = measure(qws, state, marked(qws))
  state[marked(qws)] = zero(marked(qws))
  state = stochastic_evolution(parameters(qws)[:stochastic], state)
  state[marked(qws)] += old_probability
  state
end

Note that for example measure function does not change. Below we provide an evolution simulation example.

julia> dynamic = QWSearch(UniformStochastic(CompleteGraph(100)), [1])
QuantumWalk.QWSearch{UniformStochastic{LightGraphs.SimpleGraphs.SimpleGraph{Int64}},Float64}(UniformStochastic{LightGraphs.SimpleGraphs.SimpleGraph{Int64}}({100, 4950} undirected simple Int64 graph), [1], Dict{Symbol,Any}(Pair{Symbol,Any}(:stochastic,
  [2  ,   1]  =  0.010101
  [3  ,   1]  =  0.010101
  [4  ,   1]  =  0.010101
  [5  ,   1]  =  0.010101
  [6  ,   1]  =  0.010101
  ⋮
  [94 , 100]  =  0.010101
  [95 , 100]  =  0.010101
  [96 , 100]  =  0.010101
  [97 , 100]  =  0.010101
  [98 , 100]  =  0.010101
  [99 , 100]  =  0.010101)), 0.0)

julia> measure(dynamic, execute_single(dynamic, 0), [1])
1-element Array{Float64,1}:
 0.01

julia> measure(dynamic, execute_single(dynamic, 40), [1])
1-element Array{Float64,1}:
 0.340416

julia> measure(dynamic, execute_single(dynamic, 1000), [1])
1-element Array{Float64,1}:
 0.999961

Documentation

Following functions are connected to the quantum search:

Full docs

QuantumWalk.QSearchState — Type.
QSearchState(state, probability, runtime, penalty)
QSearchState(qws, state, runtime)

Creates container which consists of state, success probability probability, running time runtime and penalty penalty.

In second case state is measured according to qws.

Example

julia> qws = QWSearch(Szegedy(complete_graph(4)), [1]);

julia> result = QSearchState(qws, initial_state(qws), 0)
QSearchState{Array{Float64,1},Int64,Int64}([0.0, 0.28867513459481287, 0.28867513459481287, 0.28867513459481287, 0.28867513459481287, 0.0, 0.28867513459481287, 0.28867513459481287, 0.28867513459481287, 0.28867513459481287, 0.0, 0.28867513459481287, 0.28867513459481287, 0.28867513459481287, 0.28867513459481287, 0.0], [0.25], 0, 0)
source
QuantumWalk.QWSearch — Type.
QWSearch(model, parameters, marked, penalty[; check])

Simulates quantum search on model with marked vertices and additional parameters. penalty represents the cost of initial state creation and measurement, which should be included for better optimization, see documentation of maximizing_function. Note that marked vertices needs to be between 1 and nv(graph(model)). Furthermore penalty needs to be nonnegative.

check_qwdynamics is executed if and only iff check is true.

Needs implementation of

  • initial_state(qws::QWSearch)
  • evolve(qws::QWSearch{<:QWModelDiscr}, state) or evolve(qws::QWSearch{<:QWModelCont}, state, time::Real)
  • measure(qws::QWSearch, state[, vertices])
  • check_qwdynamics(QWSearch, model::QWModel, parameters::Dict{Symbol}, penalty::Real)
  • proper constructors.

Offers functions

  • execute
  • execute_single
  • execute_single_measured
  • execute_all
  • execute_all_measured
  • maximize_quantum_search.

It is encoureged to implement constructor, which changes the penalty and/or marked vertices only, as their are usually simple to adapt.

source
QuantumWalk.execute — Method.
execute(qws,[ initstate,] runtime[, all, measure])

Run proper execution of quantum spatial search depending on given keywords. The initial state is generated by initial_state(qws) if not provided. all and measure keywords defaults to false. For detailed description please see documentation of corresponding function, like execute_single_measured or execute_all. Note that for all equal to true model in qws needs to be disrete.

source
QuantumWalk.execute_all — Method.
execute_all(qws,[ initstate,] runtime)

Evolve initstate acording to qws for time runtime. runtime needs to be nonnegative. The initial state is generated by initial_state(qws) if not provided. Returns Vector of all QSearchState{typeof(initstate)} including initstate.

source
QuantumWalk.execute_all_measured — Method.
execute_all_measured(qws,[ initstate,] runtime)

Evolve initstate acording to qws for time runtime. runtime needs to be nonnegative. The initial state is generated by initial_state(qws) if not provided. As a result return matrix of type Matrix{Float64} for which i-th column is measurement probability distribution in (i-1)-th step.

source
QuantumWalk.execute_single — Method.
execute_single(qws, [ initstate,] runtime)

Evolve initstate acording to qws for time runtime. The initial state is generated by initial_state(qws) if not provided. runtime needs to be nonnegative. QSearchState{typeof(initstate)} is returned.

source
QuantumWalk.execute_single_measured — Method.
execute_single_measured(qws,[ initstate,] runtime)

Evolve initstate acording to qws for time runtime. The initial state is generated by initial_state(qws) if not provided. runtime needs to be nonnegative. Measurement probability distribution is returned.

source
QuantumWalk.expected_runtime — Method.
expected_runtime(runtime, probability)
expected_runtime(state)

Returns the expected runtime needed for quantum walk, considering it as Bernoulli process. It equals to runtime/probability. In the case of state provided the measurement is made, penalty is included.

source
QuantumWalk.initial_state — Function.
initial_state(qws)

Generates initial state for qws.

source
QuantumWalk.marked — Method.
marked(qws)

Returns marked vertices element of qws.

source
QuantumWalk.maximize_quantum_search — Method.
maximize_quantum_search(qws_cont [, maxtime, tstep])

Determines optimal runtime for continuous quantum walk search. The time is searched in [0, maxtime] interval, with penalty penalty(qws_cont). It is recommended for penalty to be nonzero, otherwise time close to 0 is usually returned. Typically penalty equal to log(nv(graph(qws_cont))) is enough, but optimal value may depend on the model or graph chosen.

The optimal time is chosen according to expected runtime, which equals to runtime over probability. This comes from interpreting the evolution as the Bernoulli process.

tstep is used for primary grid search to search for determine intervale which is supsected to have small expected runtime. To large value may miss the optimal value, while to small may greatly increase runtime of the algorithm.

maxtime defaults to graph order n, tstep defaults to sqrt(n)/5. Note that in general the probability is not maximal.

julia> qws = QWSearch(CTQW(complete_graph(100)), [1], 1., 0.01);

julia> result = maximize_quantum_search(qws)
QSearchState{Array{Complex{Float64},1},Float64,Float64}(Complex{Float64}[0.6211421326794925 + 0.6956647632995185im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im  …  0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103912 - 0.023085974674888862im, 0.027973603660103895 - 0.023085974674888883im, 0.027973603660103895 - 0.023085974674888883im, 0.027973603660103895 - 0.023085974674888883im, 0.027973603660103895 - 0.023085974674888883im], [0.8697670118862033], 11.996369403338626, 1.0)


julia> probability(result)
1-element Array{Float64,1}:
 0.8697670118862033
source
QuantumWalk.maximize_quantum_search — Method.
maximize_quantum_search(qws_discr [, runtime, mode])

Determines optimal runtime for discrete quantum walk search. The time is searched in [0, runtime] interval, with penalty penalty(qws_discr). It is recommended for penalty to be nonzero, otherwise time close 0 is returned. Typically small penalty approximately equal to log(n) is enough, but optimal value may depend on the model or graph chosen.

The optimal time depends on chosen mode:

  • :firstmaxprob stops when probability start to decrease,
  • :firstmaxeff stops when expected runtime start to increase,
  • :maxtimeeff chooses exhaustively the time from [0, runtime] with smallest expected time,
  • :maxtimeprob chooses exhaustively the time from [0, runtime] with maximal success probability,
  • :maxeff (default) finds optimal time with smallest expected time, usually faster than :maxtimefff.

Note last three modes always returns optimal time within the interval.

maxtime defaults to graph order n, mode defaults to :maxeff.

julia> qws = QWSearch(Szegedy(complete_graph(200)), [1], 1);

julia> result = maximize_quantum_search(qws);

julia> runtime(result)
6

julia> probability(result)
1-element Array{Float64,1}:
 0.5000160413993847

julia> result = maximize_quantum_search(qws, 100, :maxtimeprob);

julia> runtime(result)
39

julia> probability(result)
1-element Array{Float64,1}:
 0.5509378780415133
source
QuantumWalk.penalty — Method.
penalty(qws)

Returns penalty element of qws.

source
QuantumWalk.penalty — Method.
penalty(qsearchstate)

Returns the penalty time for which the state was calulated.

source
QuantumWalk.probability — Method.
probability(qsearchstate)

Returns the list of probabilities of finding marked vertices.

source
QuantumWalk.runtime — Method.
runtime(qsearchstate)

Returns the time for which the state was calulated.

source
QuantumWalk.state — Method.
state(qsearchstate)

Returns the state of qsearchstate.

source