iitis / quantumwalk.jl

QuantumWalk.jl: Package for building algorithms based on quantum walks

QuantumWalk

Description

QuantumWalk.jl is a package for Julia programming language implementing models of quantum continuous and discrete walks used for performing quantum spatial search. It's main purpose is to provide general functionalities by crossing usage of quantum models and applications implementations.

Currently the package provides implementation of

• Szegedy quantum walks Szegedy with abstract supertype AbstractSzegedy,
• continuous-time quantum walks CTQW and CTQWDense with abstract supertype AbstractCTQW,

and dynamics

• simple quantum walk QWEvolution,
• quantum spatial search QWSearch.

In particular for the last dynamic algorithm maximize_quantum_search finding optimal measure time are implemeneted. Note the function works in general for arbitrary discrete-time quantum walk. The results are not guaranteed for continuous-time quantum walk, as times is not discretized.

Installation

The package can be installed using Pkg.clone command as

(v1.0) pkg> add QuantumWalk

All of the required modules will be installed automatically.

Exemplary usage and citing

Our package was already used in papers concerning quantum attacks

• Adam Glos, Jarosław Adam Miszczak. Impact of the malicious input data modification on the efficiency of quantum algorithms, DOI:10.1007/s11128-019-2459-3, arXiv:1802.10041 (2018).

In case of citing, please use the following BibTeX form:

@misc{glos2018quantumwalkjl,
  author       = {Adam Glos and Jaros{\l}aw Adam Miszczak},
  title        = {{iitis/QuantumWalk.jl}},
  year         = {2018},
  url          = {https://github.com/iitis/QuantumWalk.jl}
}

quantumwalk.jl's Issues

Determine useful examples for test in Coined

For tests

doctest not working

Currently julia docs does not work (code based on Documenter module). Whent doctest is turned on julia do test does not pass.

Max probability function for Szegedy Walk

Determine function determining max probability function for Coined evolution. First option: Make evolution as long as the probability increases. Second option: need to determine interval in which the maximum exists, then make bisection.

Update Readme.md

Szegedy{<:Any,<:Number} vs AbstractSzegedy

Why this is relevant? See: evolve in szegedy_evolution.jl

Performance of Coined walk

Check performance for Coined walk. 5000 vertices should not be a big problem for sparse graphs
Possibilities

• perform multiplication by coined walk separately or joined
• generating coin operators issue

Improve test for maximizing_function

Currently test checks whether there is no error compilation. It would be good to check whether the result is correct for various quantum walk search problem

New interface

Define two Abstract types: Problem and Solver. Both should be supertype of various type of problems. For example

• Walk <: Problem
• Search <: Problem
  and
• CTQW <: Solver
• Szegedy <: Solver
• Coined <: Solver

Determine good names for abstract types. QuantumModel, and SearchProblem may be good. May be an occasion to implemented pure walk functions.

Possible methods for determining maximal probability

Determining how to search for maximal proability

• increase step as long as time is increasing (for how long?),
• make bisection (CTQW only)
  Related: #9 #10 #11

[Question] Implementing the 1D walk using the Szegedy Model

Hi, as a test, I wanted to implement the 1D Quantum walk using the Szegedy model with periodic boundary conditions.

This is my code -

using QuantumWalk
using Plots
using LinearAlgebra
using QuantumInformation
using LightGraphs

init = 1/√2 * real(
	(ket(32, 64) ⊗ ket(33, 64))
	+
	(ket(32, 64) ⊗ ket(33, 64))
)
qwe = QWEvolution(Szegedy(cycle_graph(64)));
j = execute_all_measured(qwe, init, 100)
i = 10 # change this
plot(j[i])

This however does not give the correct graphs.

Could you please check where I have made a mistake? It seems as if I have misunderstood the way the initial state is meant to be provided, but I couldn't figure out how to fix it.

Do DOI

MethodError in maximize_quantum_search

MethodError at line 80 in qwsearch/maximizing_function.jl

result = quantum_search(qss, Optim.minimizer(optresult))

merge quantum_search and walk

includes all_, measure_

Check performance for Szegedy Walk

make NEWS.md

Max probability function for CTQW

Determine function determining max probability function for CTQW. Probably needs to determine interval in which the maximum exists, then make bisection.

make additional function merging quantum_search, all_, measure_ etc.

create a function, where all and measure will be an optional keywords

state parameter (default value and type)

Reconsider whether search should be of type Bool or Symbol. Reconsider the default value of state

Tests for coined walk evolution

Documentation fo quantumsearch

Make documentation for quantumsearch

Max probability function for coined

Determine function determining max probability function for Coined evolution. First option: Make evolution as long as the probability increases. Second option: need to determine interval in which the maximum exists, then make bisection.

Add many time-ponits for CTQW based QSS

Currently CTQW is implemented for single time-point only. Generalize it to multiple point of time case.

Add more tests to CTQW search (without error, proper evolution)

Currently there is a lack of good tests on quantum spatial search evolution on graphs different than CompleteGraph

Implement Coined Walk based search

Make Github pages

Similar to LightGraphs: http://juliagraphs.github.io/LightGraphs.jl/latest/

Documentation for module

Different model QSS

Check the existence for different models of quantum spatial search

Determine useful examples for testing for Szegedy

Tests fo Szegedy Walk Evolution

quantum_search possibilities

Currently quantum_search can only initiate searches with default parameters. Decide, whether this is enough.

Implement Szeged Walk search

Unclear behaviour of maximize_quantum_search

I get expected_runtime as follows

dim=107 res=4.688486215021979e-14
dim=108 res=42.659085358552566
dim=109 res=42.93092522057161

The above results were generated using the attached exmaple
ex1.txt