# Factoring Discrete Quantum Walks on Distance Regular Graphs into Continuous Quantum Walks

@article{Zhan2020FactoringDQ, title={Factoring Discrete Quantum Walks on Distance Regular Graphs into Continuous Quantum Walks}, author={H. Zhan}, journal={arXiv: Combinatorics}, year={2020} }

We consider a discrete quantum walk, called the Grover walk, on a distance regular graph $X$. Given that $X$ has diameter $d$ and invertible adjacency matrix, we show that the square of the transition matrix of the Grover walk on $X$ is a product of at most $d$ commuting transition matrices of continuous quantum walks, each on some distance digraph of the line digraph of $X$.

#### References

SHOWING 1-9 OF 9 REFERENCES

Quantum walks on general graphs

- Computer Science, Physics
- 2003

The resource requirements for implementing a quantum walk as a program on a quantum computer are compared and found to be very similar for both discrete and continuous time walks. Expand

Quantum walks on graphs

- Mathematics, Computer Science
- STOC '01
- 2001

A lower bound on the possible speed up by quantum walks for general graphs is given, showing that quantum walks can be at most polynomially faster than their classical counterparts. Expand

Quantum Walks on Regular Graphs and Eigenvalues

- Mathematics, Computer Science
- Electron. J. Comb.
- 2011

The eigenvalues of S + (U) and S +(U 2 ) for regular graphs are found and it is shown that S - (U 2) 2 + I is the transition matrix of a quantum walk on strongly regular graphs. Expand

An infinite family of circulant graphs with perfect state transfer in discrete quantum walks

- Mathematics, Computer Science
- Quantum Inf. Process.
- 2019

An infinite family of $4$-regular circulant graphs that admit perfect state transfer is constructed, the only known infinite families of examples were variants of cycles and diamond chains. Expand

Phase Measurement of Quantum Walks: Application to Structure Theorem of the Positive Support of the Grover Walk

- Mathematics, Computer Science
- Electron. J. Comb.
- 2019

A structure theorem of the positive support of the positives of the Grover walk on a regular graph whose girth is greater than $2(n-1)$ is obtained. Expand

Complex Hadamard matrices, instantaneous uniform mixing and cubes

- Mathematics
- 2013

We study the continuous-time quantum walks on graphs in the adjacency algebra of the $n$-cube and its related distance regular graphs.
For $k\geq 2$, we find graphs in the adjacency algebra of… Expand

Quantum speed-up of Markov chain based algorithms

- Mathematics, Computer Science
- 45th Annual IEEE Symposium on Foundations of Computer Science
- 2004

It is shown that under certain conditions, the quantum version of the Markov chain gives rise to a quadratic speed-up, and that the quantum escape time, just like its classical version, depends on the spectral properties of the transition matrix with the marked rows and columns deleted. Expand

Periodicities of Grover Walks on Distance-Regular Graphs

- Mathematics, Physics
- Graphs Comb.
- 2019

This paper finds some classes of such distance- regular graphs and obtains some useful necessary conditions to induce periodic Grover walks on the general distance-regular graphs and applies this necessary condition to give another proof for the strong regular graphs. Expand

The staggered quantum walk model

- Computer Science, Mathematics
- Quantum Inf. Process.
- 2016

It is proved that any instance of Szegedy’s model is equivalent to an instance of the staggered model, and it is shown that there are instances of the stagger model that cannot be cast into SzEGedy's framework. Expand