Abstract | ||
---|---|---|
Quantum walks have received a great deal of attention recently because they can be used to develop new quantum algorithms and to simulate interesting quantum systems. In this work, we focus on a model called staggered quantum walk, which employs advanced ideas of graph theory and has the advantage of including the most important instances of other discrete-time models. The evolution operator of the staggered model is obtained from a tessellation cover, which is defined in terms of a set of partitions of the graph into cliques. It is important to establish the minimum number of tessellations required in a tessellation cover, and what classes of graphs admit a small number of tessellations. We describe two main results: (1) infinite classes of graphs where we relate the chromatic number of the clique graph to the minimum number of tessellations required in a tessellation cover, and (2) the problem of deciding whether a graph is $k$-tessellable for $kge 3$ is NP-complete. |
Year | Venue | Field |
---|---|---|
2017 | arXiv: Discrete Mathematics | Small number,Graph theory,Quantum,Discrete mathematics,Combinatorics,Clique graph,Quantum walk,Quantum algorithm,Operator (computer programming),Tessellation,Mathematics |
DocType | Volume | Citations |
Journal | abs/1705.09014 | 0 |
PageRank | References | Authors |
0.34 | 1 | 8 |
Name | Order | Citations | PageRank |
---|---|---|---|
A. Abreu | 1 | 0 | 0.34 |
Luís Felipe I. Cunha | 2 | 3 | 5.85 |
T. Fernandes | 3 | 0 | 0.34 |
Celina M. H. de Figueiredo | 4 | 296 | 38.49 |
Luis Antonio Brasil Kowada | 5 | 23 | 9.01 |
F. L. Marquezino | 6 | 19 | 6.66 |
Daniel F. D. Posner | 7 | 8 | 2.18 |
Renato Portugal | 8 | 52 | 10.01 |